title: Stack Permutation Algorithm

text:
# Question
Title: Stack Permutation Algorithm
I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.

For example if the top of the stack is on the left, then say the N=3 rotate instruction would do the following:

```
A B C D -> C A B D

```

A few more examples:

```
A B C D -> B A C D (N=2)
A B C D -> D A B C (N=4)

```

In other words the Nth element is removed and put at the top of the stack.

The question arises where I need to be able to permute the top N stack elements, but using the minimum number of rotate instructions.

**How do I find the optimal sequence of rotations to perform for any given permutation?**

A naive algorithm would be the following:

1. Starting with the largest rotation (N=4 above), keep applying until the required element is in the 4th position.
2. Reduce the size of the rotation by one and apply 1) again.

An example of the naive algorithm would be:

```
Permute: A B C D -> D A C B

```

If we list the rotate instructions in order as a list of numbers, would give:

```
4 4 3 3

```

But in fact, the optimal rotates would be:

```
3 2 4

```

---

**EDIT** \- Further Investigations

I thought I would initially just try to enumerate all the optimal sequences for a given size of permutation - i.e. brute force it. And then look for patterns.

Here is the list I generated for size 4. I've renumbered the stack elements starting from zero, as that is actually more natural (since the top stack element is never moved to the top). So a 1 operation would bring the secondmost element to the top etc.:

```
-   ABCD
1   BACD
12  CBAD
123 DCBA
13  DBAC
133 CDBA
2   CABD
21  ACBD
213 DACB
22  BCAD
223 DBCA
23  DCAB
232 ADCB
233 BDCA
3   DABC
31  ADBC
312 BADC
313 CADB
32  BDAC
322 ABDC
323 CBDA
33  CDAB
332 ACDB
333 BCDA

```

A few observations are immediately apparent:

* The maximum number of operations needed is N-1 for a permuation of size N.
* There are more optimal sequences starting with 3 than with 2, and more with 2 than with 1.
* There is a regular pattern to the sequences starting in 1 or 3
* The longer sequences contain the shorter ones to the left hand side. In other words if 322 appears then so will 32 and 3.
* There is a unique optimal sequence for each permuation

The pattern seems to be the following for those starting with 3 for example:

```
3(123)(23) - where the brackets indicate a choice

```

or for 1

```
1(23)3

```

But the pattern is not so obvious for those starting with 2.

Still, all that doesn't help in finding the *actual* sequence for a permutation.

---

**EDIT**

Thanks all for your answers, it was fun!

I've now implemented the algorithm in my Forth compiler.

# Answer
> 6 votes
Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are equivalent problems because if we choose a prefix $\sigma(1)\sigma(2)\ldots \sigma(i)$ and right-cycle it, then we can reverse that by choosing the $\sigma(i)$ (now the leftmost point) and inserting it at position $i$. Likewise rather than start from the identity, we end at the identity.

Let $\sigma(i^\*)$ be the right most element that is the beginning of an inversion, i.e., there exists $j\>i^\*$ with $\sigma(i^\*)\>\sigma(j)$ (if none exists then no moves are necessary because $\sigma$ is the identity permutation). For instance in 1 3 2 4 that would be 3 since it starts the inversion (3,2). And in 4 3 2 1 that would be 2.

**Observation 1**: $\sigma(i^\*+1)\sigma(i^\*+2)\cdots \sigma(n)$ is sorted.

We must move all elements on the left side of $\sigma(i^\*)$ to the right side of $\sigma(i^\*)$. This is because we must correct the inversion and that can't happen until we perform a move with $\sigma(i^\*)$ itself, which can't happen until $\sigma(i^\*)$ is "uncovered" on the left side. While performing these hops over $\sigma(i^\*)$ we can maintain the invariant that everything to the right of $\sigma(i^\*)$ is sorted; this is just insertion into a sorted array.

So the number of moves necessary $= i^\*$, since we hop everything to the left of $\sigma(i^\*)$, and lastly move $\sigma(i^\*)$ to its correct index.

Concluding note: to actually find the indices, we could use an order-statistic tree initialized with all values to the right of $\sigma(i^\*)$. When we jump $\sigma(1)$ over $\sigma(i^\*)$ we insert $\sigma(1)$ into the tree and call rank($\sigma(1)$); the rank can be used to compute the insertion index. Repeat with $\sigma(2), \ldots$.

# Answer
> 1 votes
Thanks to user111398. Here is some (Excel) VBA code to prove it works:

```
Option Explicit

Public Sub Test()
    Dim sPermutation As String

    Dim lIndex As Long

    For lIndex = 0 To 2 * 3 * 4 * 5 - 1
        sPermutation = GetPermutation(lIndex, "ABCDE")
        Debug.Print sPermutation & ": " & GetRotates(sPermutation)
    Next

End Sub

Public Function GetPermutation(ByVal lPermutationIndex As Long, ByVal sPermute As String) As String
    Dim lIndeces() As Long
    Dim lIndex As Long
    Dim sPermutation As String

    ReDim lIndeces(Len(sPermute) - 1)
    For lIndex = 0 To UBound(lIndeces)
        lIndeces(lIndex) = lPermutationIndex Mod (lIndex + 1)
        lPermutationIndex = lPermutationIndex \ (lIndex + 1)
    Next

    For lIndex = 0 To UBound(lIndeces)
        sPermutation = Left$(sPermutation, lIndeces(lIndex)) & Mid$(sPermute, lIndex + 1, 1) & Mid$(sPermutation, lIndeces(lIndex) + 1)
    Next
    GetPermutation = sPermutation
End Function

Public Function GetRotates(ByVal sPermutation As String) As String
    Dim lIndex As Long
    Dim sMove As String
    Dim lFulcrum As Long

    ' Find rightmost inversion (fulcrum)
    For lIndex = Len(sPermutation) To 2 Step -1
        If Mid$(sPermutation, lIndex, 1) < Mid$(sPermutation, lIndex - 1, 1) Then
            lFulcrum = lIndex - 1
            Exit For
        End If
    Next

    ' No inversion then no rotates
    If lFulcrum = 0 Then
        GetRotates = "-"
        Exit Function
    End If

    ' Keep moving leftmost to the right of the inversion and keep sorted
    Do
        sMove = Left$(sPermutation, 1)
        For lIndex = lFulcrum + 1 To Len(sPermutation)
            If sMove < Mid$(sPermutation, lIndex, 1) Then
                sPermutation = Mid$(sPermutation, 2, lIndex - 2) & sMove & Mid$(sPermutation, lIndex)
                GetRotates = (lIndex - 2) & GetRotates
                lFulcrum = lFulcrum - 1
                Exit For
            End If
        Next
        If lIndex > Len(sPermutation) Then
            sPermutation = Mid$(sPermutation, 2) & sMove
            GetRotates = (Len(sPermutation) - 1) & GetRotates
            lFulcrum = lFulcrum - 1
        End If
    Loop Until lFulcrum = 0

End Function

```

Obviously you can convert the **GetRotates** function to use arrays and your own flavour of language.

Note that the output of **GetRotates** is zero based and is based on moving elements to the top of the stack.

As suggested in the accepted answer, an Order Statistic Tree can be used to improve the performance of the sorting to the right of the inversion.

# Answer
> 1 votes
As previously suggested we will discuss the inverse problem, sorting. If we want to sort `5 3 6 2 7 4 1` to `1 2 3 4 5 6 7` by moving elements to the left (top) the only way to get `7` to the bottom is to move `4` and `1` out of the way. Then to get `6` as second last element we also need to move `2`. Then to get `5` at the right position we also need to move `3`. Now that we know which numbers to move (`1` to `4`) we can easily find an optimal way to do that, just move these numbers to front from large to small.

Hence, in general, for a permutation of $1,\dots,n$ the numbers that do not have to be moved are the maximal sequence that is a subsequence $k,k+1, \dots n-2,n-1,n$ of the original permutation. All other numbers are moved, from large to small. The sequence is easily found, starting at the end.

In the first example, the subsequence is $5,6,7$ in $\underline 5,3,\underline 6,2,\underline 7,4,1$

# Answer
> 1 votes
This is only an attempt to provide another implementation that solves the *nth stack sorting* problem (I had to give it a name, ...) with permutations of an arbitrary size $n$ in $O(n)$ ---though the implementation given below works only for digits in the range $\[0, n)$.

Actually, the analysis provided by user111398 is very nice and (s)he is absolutely right: to compute the optimal number of moves required to sort the permutation it just suffices counting the number of inversions, or locations $j\>i$ with $\sigma(i)\>\sigma(j)$. Indeed, the problem can be optimally solved in $O(n)$ just by undoing all inversions from the last symbol all the way down to the first one ---and, as a corollary the length of the optimal solution is actually bounded by $(n-1)$.

For this, there is no need to use an order-statistic tree, but just to compute the inverse of the permutation. The inverse $\pi^{-1}$ of a permutation $\pi$ records the location of each symbol, i.e., $\pi^{-1}\[\pi\[i\]\] = i$.

Thus, in the first iteration, if and only if $\pi^{-1}\[n-1\] \< \pi^{-1}\[n-2\]$, then rotating all symbols up to the location of symbol $(n-2)$ undoes the inversion. Next, another rotation is practiced if and only if $\pi^{-1}\[n-2\] \< \pi^{-1}\[n-3\]$ and so ... As each rotation only undoes one inversion, this number of rotations is the optimal number of moves required to sort the permutation.

```
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

using namespace std;

// return the number of moves required to optimally solve the given
// permutation
int solve (vector<int>& perm)
{

  // compute the inverse permutation
  vector<int> inv (perm.size (), 0);
  for (auto i = 0 ; i < perm.size () ; inv[perm[i]] = i, i++);

  // process all symbols backwards but 0 which is necessarily well
  // placed in the last iteration
  int nbmoves = 0; // initialize the optimal number of moves required
  int ith = perm.size () - 1;
  do {

    // if and only if the i-th symbol appears before the (i-1)-th
    // symbol
    if (inv[ith] < inv [ith-1]) {

      cout << "* [" << ith << "] ";
      copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
      cout << endl;

      // then rotate all symbols up to the location of the (ith-1)
      // symbol
      for (auto i = inv[ith-1] ; i > 0 ; perm[i]=perm[i-1], i--);
      perm[0]=ith-1;

      // increment the required number of moves
      nbmoves++;

      // and update the inverse
      for (auto i = 0 ; i < perm.size () ; inv[perm[i]] = i, i++);
    }
    else {
      cout << "  [" << ith << "] ";
      copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
      cout << endl;
    }

    // move to the next symbol
    ith--;
  } while (ith > 0);

  cout << "  ";
  copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
  cout << endl;

  return nbmoves;
}

int main (int argc, char* argv[])
{

  // for all cases given in the command line
  for (auto i = 1 ; i < argc ; i++) {

    vector<int> perm;
    for (auto j = 0 ; argv[i][j] ; j++)
      perm.push_back (argv[i][j] - '0');
    int solution = solve (perm);
    cout << endl << " # moves required: " << solution << endl << endl;
  }
}

```

This implementation only accepts permutations with symbols in the range $\[0, n)$:

```
$ ./stack_perm 2764935801
* [9] 2, 7, 6, 4, 9, 3, 5, 8, 0, 1,
* [8] 8, 2, 7, 6, 4, 9, 3, 5, 0, 1,
* [7] 7, 8, 2, 6, 4, 9, 3, 5, 0, 1,
* [6] 6, 7, 8, 2, 4, 9, 3, 5, 0, 1,
* [5] 5, 6, 7, 8, 2, 4, 9, 3, 0, 1,
* [4] 4, 5, 6, 7, 8, 2, 9, 3, 0, 1,
* [3] 3, 4, 5, 6, 7, 8, 2, 9, 0, 1,
* [2] 2, 3, 4, 5, 6, 7, 8, 9, 0, 1,
* [1] 1, 2, 3, 4, 5, 6, 7, 8, 9, 0,
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

 # moves required: 9

```

Hope this helps,

---
Tags: algorithms, permutations, stacks
---


# Question
Title: Algorithm for creating n-multiset out of x?
I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that the sum of all values is 15. Those are the nodes of my (sparse) graph, the edges are defined by the rule: diminish the (non-null) value of an index by 1 and add 1 to (index +1). The values are the balls, the indices are the boxes.

Following the twelvefold way, i find that i have to create 15-multisets out of 21 and that there are $\binom{n + x - 1}{k}$ possibilities. In my case, those are 3.2E10 which is small compared to 21 to the 15th power (6.8E20) and can be kept in the memory of my machine.

What i now need is an algorithm for the creation of all nodes. The primitive way would be 15 nested loops counting from 1 to 21, inside of all doing some tests if the node is a permutation of (and so identical with) an already created node, but that would be too time-consuming (6E20 possibilities). Is there a faster way, looking only at the 3E10 "real" states?

# Answer
> 2 votes
Every such arrangement of 15 balls to 21 boxes corresponds, in a one-to-one fashion, to a string of the form \*|\**|*|||*...|\*, where there are a total of 35 symbols in the string, exactly 15 stars and 20 bars. (Think of each * as a ball, and each | as a divider between two boxes.) These, in turn, correspond to the set of binary strings of length 35 that contain exactly 20 one's, which in turn corresponds to the set of ways to choose a subset of 20 positions out of a set of 35 possibilities.

It follows that you can enumerate the set of valid nodes by enumerating all ways to choose a subset of size 20 that's contained in $\\{1,2,\dots,35\\}$. There are standard ways to perform this enumeration. One way is to use the combinatorial number system, which creates a correspondence between these subsets and integers in the range $\\{1,2,\dots,{35 \choose 20}\\}$. See also https://en.wikipedia.org/wiki/Combination#Enumerating\_k-combinations, Get a fixed-size family of k-element subsets, https://cs.stackexchange.com/a/72543/755 for more.

---
Tags: algorithms, combinatorics
---


# Question
Title: If A and B are NP-complete, then A ∪ B need not be NP-complete
I am studying the proof of this exercise (link)

> There exist N P-complete languages A and B such that A ∪ B is not N P-complete. Example:
>
> $A = \\{1x : x ∈ SAT\\} ∪ \\{0x : x ∈ \\{0, 1\\}^∗\\};$ $B = \\{0x : x ∈ SAT\\} ∪ \\{1x : x ∈ \\{0, 1\\}^∗\\};$.
>
> The languages A and B are N P-complete (prove it). On the other hand, A ∪ B contains allbinary strings (i.e. A ∪ B = {0, 1}∗); and thus it is not N P-complete.

I know the Union (L1 ∪ L2) of two NP language L1,L2 ∈ NP is NP. I can describe a TM not-deterministic for $\\{1x : x ∈ SAT\\}$ (and for $\\{0x : x ∈ SAT\\}$) and therefore $\\{1x : x ∈ SAT\\}$ is NP (note, I know SAT is NP). I have a problem to understand why $\\{0x : x ∈ \\{0, 1\\}\\}^∗$ is NP? I remember $\\{0, 1\\}^∗$ is in P, and I cannot describe a TM not-deterministic for $\\{0x : x ∈ \\{0, 1\\}\\}^∗$

# Answer
P is a subset of NP, so any P language is NP as well. Also note that any deterministic machine is a non-deterministic machine where the image of the transitions function has always a size exactly equal to one. This implies that from each configuration you get a unique following configuration.
> 3 votes

---
Tags: turing-machines, np-complete, np, nondeterminism
---


# Question
Title: Design a Turing machine that accepts L={ww^r | w:(0,1)*}?
Can anyone help :(

L = {ww^r | w element of (0,1)\*}

Would it be like in :pseudo code, check if the string is equal to itself in reverse?

# Answer
> 1 votes
This can be done with a PDA or a TM. I'll assume you need a deterministic TM, for what I'm assuming is homework.

The strategy is to find the length of the string to determine where the middle is, then treat the tape as a stack to see if all of the characters match before and after that midpoint.

Here's an algorithm that can do it:

1. For every two input characters you read until you hit `#`, write a `0` after the last `#`. This will keep track of where the "middle" is. Mark the inputs as you read them.
2. If you hit `#` where you expected to find a number, the string length is odd, and so the machine can halt and reject.
3. Otherwise, write another `#` after your string of zeros.
4. Unmark all inputs and move the read head to the second `#`.
5. Using the number of zeros you have, mark the right half of the input.
6. Starting in the middle, working your way out, mark the left character and unmark the right if they match.
7. If you encounter a pair that doesn't match, halt and reject.
8. If you get all of the way to the `#`s, halt and accept.

For example, let's look at input `#101100#` (`#` here means the edges of the input). The read head is at the first `#`.

1. Input starts as `# 1 0 1 1 0 0 #` (leaving room for markers)
2. Mark the first two inputs, write a 0 at the end: `# 1'0'1 1 0 0 # 0`
3. Mark the next two inputs, write a 0 at the end: `# 1'0'1'1'0 0 # 0 0`
4. Mark the next two inputs, write a 0 at the end: `# 1'0'1'1'0'0'# 0 0 0`
5. You've found the second `#`, so the string is of even length. Write a # at the end: `# 1'0'1'1'0'0'# 0 0 0 #`
6. Unmark everything: `# 1 0 1 1 0 0 # 0 0 0 #`
7. Now, starting from the second `#`, mark the inputs from the right, and the `0`s from the left until all of the `0`s are marked:
8. First iteration: `# 1 0 1 1 0 0'# 0'0 0 #`
9. Second: `# 1 0 1 1 0'0'# 0'0'0 #`
10. Third: `# 1 0 1 1'0'0'# 0'0'0'#`
11. You now know the midpoint of the string (it's where an unmarked input is to the left of a marked input).
12. Starting from that midpoint, mark the left and unmark the right if they match: `# 1 0 1'1 0'0'# 0'0'0'#`
13. Continue working outward, comparing in this way: `# 1 0'1'1 0 0'# 0'0'0'#`
14. On the third step, we find that `1` and `0` don't match. Halt and reject.

I'll leave it as an exercise to you to determine how to convert this algorithm into a TM.

---
Tags: turing-machines
---


# Question
Title: Pairwise hash functions that are independent from each other
Is there there a way to build a collection of universal hash functions $H=\\{h| h:U\to D \\}$ where the values of two hash functions are independent one from another? i.e., $\Pr\_{h\_1,h\_2\in H}(h\_1(x)=y \land h\_2(z)=w )=|D|^{-2}$ for each $x,y,z,w\in U$.

Also, is there a term for such collection?

# Answer
If you select $h\_1,h\_2$ independently at random, then by definition

$$\Pr\_{h\_1,h\_2}\[h\_1(x)=y \land h\_2(z)=w\] = \Pr\_{h\_1}\[h\_1(x)=y\] \times \Pr\_{h\_2}\[h\_2(z)=w\].$$

If your hash family is universal, then both probabilities on the right-hand side will be $1/|D|$.

In other words, if $H$ is universal, then it automatically follows that

$$\Pr\_{h\_1,h\_2}\[h\_1(x)=y \land h\_2(z)=w\] = 1/|D|^2.$$

Every universal collection works -- no extra conditions or requirements are needed.
> 1 votes

---
Tags: hash, hash-tables
---


# Question
Title: How to prove that Exact Cover is NP-complete using SAT?
I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover.

Here's the solution from the link (where C is the clause(s), A is the universe, and F is the subsets of the universe):

```
C1=(x1 ∨ x2) C2=(x1 ∨ x2 ∨ x3) C3=(x2) C4=(x2 ∨ x3)

A={x1, x2, x3, C1, C2, C3, C4, p11, p12, p21, p22, p23, p31, p41, p42}

F={{p11},{p12},{p21},{p22},{p23},{p31},{p41},{p42},
X1, f={x1, p11}
X1, t={x1, p21}
X2, f={x2, p22, p31}
X2, t={x2, p12, p41}
X3, f={x3, p23}
X3, t={x3, p42}
{C1, p11},{C1, p12},{C2, p21},{C2, p22},{C2, p23},{C3, p31},{C4, p41},{C4, p422}}

```

I understand how this proves that it is NP-complete, but I do not understand how A and F was populated. In other words, I am unable to figure out the "algorithm" behind creating the p11...p42 variables.

# Answer
> I understand how this proves that it is NP-complete

It isn't a "proof" by any means. It's an example of how a reduction might work, but it hasn't been stated as a formal proof.

From your example, it looks like the algorithm/proof is as follows:

* The universe consists of $3$ types of elements: one element $x\_i$ for every variable $i$, one element $C\_j$ for every clause $j$, and one element $p\_{i,j}$ for every occurrence of a variable $i$ as a literal in clause $j$.
* For every variable $i$, we create two sets; the *true* set and the *false* set. The true (resp. false) set contains $x\_i$, together with, for every clause in which variable $i$ appears negated (resp. non-negated), $p\_{i,j}$. As an example, if $x\_1$ appears as a literal in clause $2$ and $\neg x\_1$ appears in clauses $3,4$, we create the sets $\\{x\_1,p\_{1,2}\\},\\{x\_1,p\_{1,2},p\_{3,4}\\}$.
* For every element $p\_{i,j}$, we create a set $\\{C\_j,p\_{i,j}\\}$ and a singleton set $\\{p\_{i,j}\\}$.

As the variable true/false sets are the only sets containing $x\_i$, for each variable $i$, a solution to Exact Cover must contain exactly one of the corresponding true/false sets. This gives a correspondence between the variable true/false sets selected in Exact Cover solutions and variable assignments to the SAT instance.

Moreover, any Exact Cover solution must, for every clause $j$, contain for some $i$ the set $\\{C\_j,p\_{i,j}\\}$ (since these are the only sets containing $C\_j$). If $i$ is a positive literal in clause $j$, this means the false set for variable $i$ cannot be in the solution, since it also contains $p\_{i,j}$. Similarly, if $i$ is a negated literal in clause $j$, we cannot have selected the true set for variable $i$. Thus, variable $i$ satisfies clause $j$ in the variable assignment corresponding to the selected variable true/false sets.

Conversely, given a satisfying assignment to the SAT instance, we can simply select the variable true/false sets corresponding to the assignment. For every clause we can select any set $\\{C\_j,p\_{i,j}\\}$ for which $i$ is a satisfying literal of clause $j$. This covers the $x\_i$'s and $C\_j$'s. The remaining $p\_{i,j}$'s can be covered by singletons.
> 2 votes

---
Tags: np-complete
---


title: Problem with the modulus calculation

text:
# Question
Title: Problem with the modulus calculation
I am trying to solve the following calculation, but I can't find the suitable value for B.

```
    6/3 (mod 6)
    A= 3
    B= ?
    M = 6
    (A * B) % M = 1
    (3 * B) % 6 =1

```

Somebody please guide me what is the problem with this.

Zulfi.

# Answer
> 0 votes
You are looking for an integer value for $B$ such that $3B=1 \mod 6$.

But if $B$ is even then $3B=0 \mod 6$ and if $B$ is odd then $3B=3 \mod 6$.

$B$ must be either even or odd. So there is no value for $B$ that satisfies $3B=1 \mod 6$.

---
Tags: modular-arithmetic
---


# Question
Title: Is there any base representation that produces a non-regular language for set S?
To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc.

Given the set $S$ of natural numbers such that $S = \\{2^i| i \in \mathbb{N}\\}$ prove that for some base representation of set $S$, the resulting language is not regular.

I have tried but I can't seem to figure out how to prove this. I figure that base 3 would probably result in a nonregular language, but then how would I prove it?

# Answer
> 1 votes
You are right in saying that the binary representation of the language is regular because it is defined by the expression $10^\*$(regular expression). You are also right in saying that this does not hold for the ternary representation. You can prove the latter in various ways including the "calssic" *pumping lemma* (quite cumbersome in this case) or using ***Cobham's Theorem***.

This theorem says that if you have a subset of $\mathbb{N}$ and you take $m,n \in \mathbb{N} $ such that they are *multiplicatively independent*, then your set is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is *ultimately periodic*.

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


# Question
Title: Which Graph Algorithm should I use to find all possible groups in a graph?
I have the following situation:

(Alex, Bob)

(Alex, Charlie)

(Debra, Erika)

Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And Debra is friends with Erika.

I would like to figure out how many independent friends groups there are. So if someone is a friend of a friend (or a friend of a friend to the nth degree), they would belog to the same group. In other words how many groups are there, that do not overlap eachother.

From the list above I would expect 2 groups:

(Alex, Bob, Charlie)

(Debra, Erika)

Which algorithm should I use to calculate these groups, from the list provided above?

Note: In the actual case the number of friendships is in the tens of millions, so I am looking for the most efficient solution.

# Answer
These are called the connected components of the graph.

For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a *really* big graph, see this question on Stack Overflow for practical considerations.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Is there any other computation theory besides the one in automata theory?
I'm a bit confused at a fundamental level.

In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, security, or automata theory for example). Of course, there are also calculus and nonlinear mathematics in Computer Science, but it seems to me that that doesn't matter in the subject Theory of Computation.

Theory of Computation is supposedly for machines. In Theory of Computation, the object of interest is languages and one-dimensional strings/sequences of symbols.

But why is it that it's only for linear, one-dimensional sequences of symbols? The natural phenomenon is also more to analog than digital (take a look at physics, waves for example). Does it mean that Theory of Computation or Theory of Automata is restricted only to machines/computation that is using one-dimensional strings/sequences of symbols?

In general, not only in Computer Science, is there any other object of interest for computation, other than languages and strings? Since languages and strings of symbols are discrete. What about nonlinear mathematics, dynamical system, and wave for example? They are not strings of symbols, right? So, what about their Computation Theory? Is it still restricted to automata, grammars, Turing machine, or are they totally something different?

Are all things can be represented with languages/ strings of symbols? Are languages/string of symbols enough to represent any thing/phenomenon?

What is computation theory exactly for things other than languages/ strings of symbols (if any)?

Sorry that I don't know how to phrase all these better. Can somebody please enlighten me, or provide any keywords that I can search for? Thank you very much!

# Answer
There is indeed computability-theory for non-discrete settings. This area is called *computable analysis*. A decent tutorial to computable analysis is here (if you have an institutional subscription, or can get it from a library):

https://link.springer.com/chapter/10.1007%2F978-0-387-68546-5\_18

The tutorial focuses quite a bit on the case where we are computing with real numbers, or at least elements of metric spaces. Computable analysis can handle much more situations though. Roughly speaking, we probably have reasonable computability-notions for any kind of space appearing in ordinary mathematics.

It turns out that many concepts from the classical, discrete computability theory still apply, but topological aspects also become very relevant.
> 3 votes

# Answer
Your question is very philosophical in nature because you are asking about what is considered by computation and it’s physical implementations. In short, there is a ongoing discussion on different accounts of concrete computation e.g. the simple mapping account, the semantic account, the syntactic account, the mechanistic account, the causal, the counterfactual and the dispositional account.

This stanford plato article will help you understand each and their implications. https://plato.stanford.edu/entries/computation-physicalsystems/
> 2 votes

# Answer
Computer science is not entirely contained in symbolic logic, but it is impossible for a computational model to be 100% continuous: to be a model is to be representational, is to be *symbolic*, in some sense.

That concern is at the heart of where computer science comes from, historically. It is not a field devoted to the "computational understanding of reality", even thought this may an interesting peripheral issue to many of us. It is not primarily the study of concrete computational systems, even thought they are our visible face to society. It is, originally, the study of how mathematics can formally reason about itself. Concrete computational systems are of interest to us, as much as they can "reason" about themselves, representationally. That's what software is.

Our current, common sense understanding of symbol is rooted in the connection between *digital* and *textual*. Strings of characters is what we got. That may change someday.
> 1 votes

---
Tags: complexity-theory, formal-languages, computability, formal-grammars, computation-models
---


# Question
Title: Show that language of distinct binary strings is irregular
Let $Σ =\\{\textbf{\[},\textbf{\]},\textbf{,},\textbf{0},\textbf{1}\\}$, and let $L⊂Σ^\*$ be the language containing list representations of finite sets of binary strings: i.e., every string $x∈L$ is of the form $x= \textbf{\[}x\_0\textbf{,} x\_1\textbf{,} \ldots\textbf{,} x\_n\textbf{\]}$, where:

* for all $0\le i\le n$, $x\_i$ is a string in $\\{\textbf{0},\textbf{1}\\}^\*$, and
* none of the $x\_i$ repeat: if $i$ is not equal to $j$, then $x\_i$ is not equal to $x\_j$.

Show that $L$ is not regular.

$\ \\\$

$\textbf{EDIT: Below is my attempt: }$

Suppose $L$ is regular.

Suppose the pumping length is n.

Consider the string $x$ = $\[0^n, 0^{n-1}, ... , 0\]$.

By the Pumping Lemma, $x=uvw$, where

* $u$ = $\[$
* $v$ = $0^n$, $0^{n-1}$, $0$
* $w$ = $\]$

Then, $|v|\>0$ and $|uv| \leq n$

So, $x \in L$ and $|x| \geq n$.

$\ $

Choose $k=2$.

Then, $uv^2w$ = $\[0^n, 0^{n-1}, ... , 0 0^n, 0^{n-1}, ... , 0\]$

Since each of the strings in x are repeated, this is a contradiction to the Pumping Lemma. Therefore, $L$ is not regular.

# Answer
Suppose that the pumping length is $n$. Consider the string $$ w = \[0^n,0^{n-1},\ldots,0\]. $$ You take it from here.
> 3 votes

---
Tags: regular-languages
---


title: Largest number of unique values in sets

text:
# Question
Title: Largest number of unique values in sets
Let's say I have 100 sets of values, and each set contains roughly 100,000 values. From these sets, I want to find the 10 sets that collectively have the largest number of unique values.

The brute force method of just checking all combinations is a combinatorial nightmare. I also thought about doing a rough approach (solution doesn't have to be perfectly optimal) of just finding 'the next best set' to add in sequence. So finding the largest set, then checking each of the rest of the 99 sets for smallest overlap, then checking the next 98 sets for smallest overlap, etc, but that's still `100+99+98+97+96+95+94+93+92+91 = 955` things to do.

Is there something more efficient?

# Answer
Your problem is known as Maximum coverage. The greedy algorithm (repeatedly take a set which covers the maximum number of uncovered elements) is a $1-1/e$ approximation, and runs quite efficiently.
> 1 votes

---
Tags: sets
---


# Question
Title: Build a histogram from a very large data sample
I want to calculate a histogram from an array of size `N`. `N` is very large.

I know 2 ways to do so:

1. The naive approach is to find the maximum and the minimum in the first traverse and to split the range into equal bin ranges then to fill bins during the second traverse. However this approach produces degenerate histograms where most of data is piled in one bin if the sample has outliers.
2. The way to counter degenerate histograms is to calculate IRQ or MAD, then calculate range based on this robust measure of scale, and then fill bins in one traverse. However calculation of IRQ or MAD may be slow and requires random access to the array.

I'm intrested if there is a way to build a histogram in between this extreme approaches fulfilling conditions:

* some loss of quality is acceptable
* the array doesn't fit in RAM so random access is the thing I want to avoid
* low time complexity, i'm ready to trade space `~log(N)` for time

# Answer
> 1 votes
One reasonable method is to choose a random sample of, say, 1000 items from the array. This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data).

Compute a histogram of those 1000 items, and use that to select bin ranges.

Then, perform a second linear pass on the entire dataset where you accumulate counts in those bins, using those bin ranges.

This will be efficient (nearly as efficient as the naive approach), and help you avoid degenerate histograms.

---

There are more sophisticated methods that are possible as well, from the literatures on streaming algorithms. For instance, you can use a streaming algorithm to estimate the quantiles of the data, which lets you estimate the IQR in a single pass through the data, then you use these estimated information to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins. There are also streaming algorithms to estimate the histogram counts, then you can use that to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins. There's a beautiful literature on this subject. See, e.g., Tracking Quantiles of Network Data Streams with Dynamic Operations by Cao et al, Approximate Frequency Counts over Data Streams by Manku et al, and many others. That said, while this is principled and elegant, it might also be more complex than necessary -- simple random sampling might be good enough for your needs.

---
Tags: algorithms, counting
---


# Question
Title: How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
Given the set of natural numbers, $S = \\{2^i|i\in\mathbb{N}\\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular language using the pumping lemma?

I cannot seem to find any sort of pattern for ternary representations of $S$, and so I'm finding it really difficult to prove this using the pumping lemma.

I tried to make a few strings in $L$ and got $\\{1, 11, 22, 121, 1012, 2101, \dots\\}$ but cannot find any sort of pattern that leads to using the pumping lemma. So, how would you prove that this is not a regular language using the pumping lmma? Thanks in advance.

# Answer
This answer is a simpler version of Colin McQuillan's answer to the same question.

---

Suppose the language is regular. The pumping lemma gives strings $u,v,w$ such that every string $x\_n=u v^n w$ is a power of $2$.

Interpreting these strings as numbers and writing $d$ and $e$ for the lengths of $v$ and $w$ respectively, we have $$ x\_n = u 3^{dn+e} + v 3^{d(n-1)+e} + v 3^{d(n-2)+e} + \dots + v 3^e + w.$$ So, $$x\_{n+1}-3^dx\_n = v3^e + w - 3^dw.$$

Note that the right-hand side is a constant as $n$ goes to infinity. Letting $c$ be the right-hand side, we have $$\frac{x\_{n+1}}{x\_n} - 3^d= \frac{c}{x\_n}.$$

Since $x\_{n+1}$ is a bigger power of 2 than $x\_n$, $\dfrac{x\_{n+1}}{x\_n}$ is always an integer. That means the right-hand side is always an integer as well. Since $\dfrac c{x\_n}$ goes to $0$ as $n$ goes to infinity, it must become 0 eventually.

Well, when it does become 0, we have $\dfrac{x\_{n+1}}{x\_n}=3^d$, which cannot happen since the left-hand side, a power of 2 that is greater than 1, can never be a power of 3.

---

Here is an easy exercise.

**Exercise**. Check that the above proof works the same if you replace 3 by any positive integer that is not a power of 2.
> 4 votes

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


# Question
Title: Prove the equivalence of regular expressions
I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated.

Suppose there exists regular expressions R, S and T.

Then is **R\*****R\* R\***?

I know the way to prove this is by showing that L(R\*) is a subset of L(R\*R\*) and vice versa, but I have no idea how to do that.. Just started learning about regular languages so I'm a bit confused. Can I please get any direction on how to do this?

# Answer
> 3 votes
Start with $$ R^\*R^\* = \left(\bigcup\_{i=0}^\infty R^i\right) \left(\bigcup\_{j=0}^\infty R^j\right) = \bigcup\_{i=0}^\infty \bigcup\_{j=0}^\infty R^i R^j = \bigcup\_{i=0}^\infty \bigcup\_{j=0}^\infty R^{i+j}. $$ As $i,j$ go over all pairs of non-negative integers, $i+j$ goes over all non-negative integers, hence $$ R^\*R^\* = \bigcup\_{i=0}^\infty \bigcup\_{j=0}^\infty R^{i+j} = \bigcup\_{k=0}^\infty R^k = R^\*. $$

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


# Question
Title: Using decision oracle to solve optimization problem of maximum polyomino tiling
So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of polyominos $p\_1, p\_2, ..., p\_n$ (not necessarily distinct), and we want to find a tiling of a rectangle of dimension $a \times b$ with $a, b \leq n$ that maximizes the number of squares covered, where we can use each $p\_i$ at most once, and polyominos must be fully contained within the rectangle. Now, we have the decision problem which tells us, for a given $t$, if there is some tiling covering at least $t$ squares, and the optimization problem which is finding a tiling that covers the maximum number of squares.

There are two parts: first, if you can solve the optimization problem in polynomial time, can you solve the decision problem in polynomial time? And secondly, if you can solve the decision problem in polynomial problem, can you solve the optimization problem in polynomial time?

The first part is easy, for if we have an oracle that solves the optimization in polynomial time, solving the decision problem in polynomial time is obvious.

However, given an oracle for the decision problem, I was unable to find a way to solve the optimization problem in polynomial time. The main issue I'm facing is that the decision oracle only works for rectangular boards, which means we can't just place pieces and then use the oracle to see if the placement works, since we won't have a rectangular board if we want to exclude the piece we just placed. It isn't hard to determine the actual maximum number of tiles you can cover, and you can even find the actual pieces you need to use, but I haven't been able to figure out a way to find an arrangement of the pieces in polynomial time using the oracle. I assume there is some trick here, but I don't see it.

Here are some more details. A similar problem can be found here, so to address the commenter's question a priori we sort of hope that this problem can be solved using the decision oracle. However, there is only one difficulty with adapting this approach which makes it seem fruitless:

1. The oracle in the linked question is in a sense stronger because it works on any graph. In particular we can encode the notion of coloring using a modified graph. In this sense the oracle of this problem is much, much weaker since it only works on rectangular boards.

# Answer
Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.

## A gangly polyomino in a double-width problem instance

Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \times (b+1)$ in which each polyomino's width has been doubled, and a new polyomino has been added that consists of a row of $2a+1$ blocks with a column of $b$ blocks hanging below its leftmost block (thus giving it a total height of $b+1$) and a double-width copy of polyomino $p\_1$ (the *template polyomino*) below the top row and to the right of the left column but pushed up and left as far as it will go, so that at least one block of column 2 below row 1 is occupied, and at least one block of row 2 to the right of column 1 is occupied. Intuitively, because all other polyominos have even width, the only way to fill up the odd-width rectangle we have is to use this gangly new polyomino, in which case its horizontal and vertical "arms" must form the topmost row and leftmost column, respectively.

Let the size of an optimal solution to the original problem be $k$ (this can be found in $O(\log {ab})$ time with binary search using only decision problem oracle calls). **Iff there is a solution to the newly constructed decision problem instance with size $2k+(2a+1)+(b+1) = 2(k+a)+b+2$, then there is a solution to the original instance that has $p\_1$ in its top-left corner.**

If the answer is "no", try the same instance again but with a different template polyomino: form the gangly polyomino by pressing $p\_2$ into the top-left corner instead of $p\_1$. Repeat this until you find you hit a "yes" instance. If none of the polyominos results in a "yes" instance when pressed into the top-left corner, start again with $p\_1$ but one block down from where it was in the first constructed problem, *and with the blocks at positions $(2, 2)$ and $(2, 3)$ also filled in*. Why? These represents a (double-width) block that we know must remain empty in every optimal solution (since if there was some optimal solution where it was covered by a polyomino, we would have found it by now). Add 2 to the target value for the decision problem to compensate for the added filler blocks.

If performing this down-one-row move would cause the polyomino to extend past the bottom of the range, add the 2 filler blocks as usual but instead move the template polyomino back up to the top (so that its topmost block occupies row 2) and as far left as possible so as to not overlap any existing block.

In general, a constructed instance with $f$ filler blocks gets $f$ added to its decision problem target.

Once you hit a "yes" instance, you know that this placement of the template polyomino is part of some optimal solution, so you *keep that placement of the template in the gangly polyomino from that point on*. Form the next problem with the next available polyomino as template immediately below the last one, or flush with the top and to the right as usual.

## Time complexity

Each time we try all $n$ polyominos at some position, we add at least 2 blocks (either 2 filler blocks, or the double-width blocks corresponding to some input polyomino) to the gangly polyomino. We can only add at most $ab$ such pairs of blocks before it is no longer possible to obtain a "yes" answer, so at most $abn$ calls to the decision oracle suffice.
> 3 votes

---
Tags: algorithms, np-complete, np
---


# Question
Title: Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems
The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link failures.

Looking into the details of this algorithm (in Figure 2, page 133), I found that it implicitly assumes the "conditional write" primitives at the side of servers:

```
case received from w
    <W, label_w>: label_j = max{label_w, label_j};
                  send <ACK-W> to w;

```

Here, the statement `label_j = max{label_w, label_j}` is equivalent to `if (label_j < label_w) then label_j = label_w`, requiring the variable `label_j` maintained by each process $j$ to be monotonic. This in turn needs the `if-then` "conditional write" primitive.

My first question is:

> (1) Is this "conditional write" primitive necessary? Do you know any literature on emulations of atomic, SWMR registers without such primitives?

---

In the last section of the same paper, titled "Discussion and Further Research", the authors mentioned the emulations of stronger shared memory primitives in message-passing systems in presence of failures. One typical example is read-modify-write (RMW).

My second question is:

> (2) Do you know any literature on the emulations of RMW-like primitives?

Google search and a quick glance over the "cited by" papers do not bring me anything specific.

# Answer
Partial answer:

> ... if (label\_j \< label\_w) then label\_j = label\_w
>
> Is this "conditional write" primitive necessary?

Are you asking "Does this processor have to act 'as if' that test-and-assign was a single atomic instruction, so every message this processor sends to any other processor seems to show that the internal label\_j variable always increases monotonically?"

Yes, from the outside, the processor must act "as if" the internal label\_j value increases atomically and monotonically.

Are you asking "Does this processor need to actually modify label\_j atomically?"

No. There are several ways to arrange things such that the updates appear, from the outside, to increment label\_j atomically, even though the actual code that processor runs internally uses normal non-atomic sequences of instructions that (a) test the condition, (b) choose to branch, and then (c) update the value of label\_j, while allowing lots of other stuff to interrupt the processor and modify that processor's memory between 'a' and 'b' and 'c'.

The simplest way is for that processor to be a uniprocessor that always processes incoming messages one at a time -- it buffers up messages from all other processors in a FIFO queue, chooses the oldest *complete* message (if any) from the queue to process, and otherwise doesn't even look at any incoming message until after it has finished dealing with the chosen message.

My understanding is that, in the systems described by that paper, no other processor can directly read the internal state of the label\_j variable inside that processor.

> Do you know any literature on the emulations of RMW-like primitives?

I was fascinated by Marice Herlihy's 1991 proof that: The atomic compare-and-swap instruction can emulate atomic-read, atomic-write, and fetch-and-add, but even if a CPU has atomic-read, atomic-write, and fetch-and-add, it can't emulate atomic compare-and-swap.

I am looking forward to reading a more complete answer.
> 1 votes

# Answer
A partial answer to the second question:

In the book "Distributed Algorithms" by Nancy A. Lynch (1996) (Section 13.2 "Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables"), we have the following *impossibility* result:

> *Theorem 13.11* There does *not* exist a shared memory system using read/write shared variables that implements a read-modify-write atomic object and guarantees 1-failure termination.
> 2 votes

# Answer
The SWMR ABD algorithm cannot emulate conditional write *per se*, but if the single writer is a stable leader, with a fault-tolerant leader election algorithm and appropriate modifications to the ABD algorithm (i.e. epoch counters in each message), it is possible to emulate conditional write, as shown in this industry paper: https://arxiv.org/abs/1702.04242.

I found this result surprising given the impossibility proof you mentioned, but I haven't taken the time to determine exactly what loophole in the proof it exploits (I hope it's not just partial synchrony!).
> 0 votes

---
Tags: algorithms, reference-request, distributed-systems, concurrency, synchronization
---


# Question
Title: Why do we need to take the derivative of the activation function in backwards propagation?
I was reading this article here: https://towardsdatascience.com/how-does-back-propagation-in-artificial-neural-networks-work-c7cad873ea7.

When he gets to the part where he calculates the loss at every node, he says to use the following formula:

"`delta_0 = w . delta_1 . f'(z)` where values delta\_0, w and f’(z) are those of the same unit’s, while delta\_1 is the loss of the unit on the other side of the weighted link."

And $f$ is the activation function.

He then says:

"You can think of it this way, in order to get the loss of a node (e.g. Z0), we multiply the value of its corresponding f’(z) by the loss of the node it is connected to in the next layer (delta\_1), by the weight of the link connecting both nodes."

However, he doesn't actually explain why we need the derivative term. Where does that term come from and why do we need it?

My idea so far is this:

The fact that the identity activation function causes the term to disappear is a hint. The node doesn't feed into the next exactly as is, it depends on the activation function. When the activation function is the identity, the loss at that node just passes to the next one based on the weight. Basically, you just need to factor in the activation function somehow, specifically in a way that doesn't matter when it's the identity, and of course the derivative is a way to do this.

The issue is that this isn't very rigorous, so I'm looking for a slightly more detailed explanation.

# Answer
> 2 votes
As a disclaimer, I didn't read that page, but I can certainly explain where the derivatives come from. The backpropagation algorithm is actually a variant of the gradient descent algorithm.

Think about a single function for the moment. Suppose you have a function which responds to a single input and a single weight: $f(w, x)$. We want to adjust $w$ so that it gives expected answers for various known values of $x$.

Then by Taylor's theorem:

$$f(w + \delta w, x) \approx f(w, x) + \delta w \frac{\partial f}{\partial w}(w, x)$$

Or to put it another way:

$$f(w + \delta w, x) - f(w, x) \approx \delta w \frac{\partial f}{\partial w}(w, x)$$

So if you find a value for $x$ which gives the wrong output, this gives you an estimate of how "wrong" $w$ is, and it's related to the derivative of $f$.

This idea extends to multi-variate calculus. If you have a vector of weights and inputs $\mathbf{w}$ and $\mathbf{x}$, then Taylor's theorem says:

$$f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) \approx f(\mathbf{w}, \mathbf{x}) + \nabla\_{\mathbf{w}}f \cdot \delta \mathbf{w}$$

Where $\nabla\_{\mathbf{w}}f$ is the gradient of $f$ with respect to the weights only.

Now let's think about your case, where the function $f$ has a specific form: it's a function applied to the dot product of $\mathbf{w}$ and $\mathbf{x}$:

$$f(\mathbf{w},\mathbf{x}) = h(\mathbf{w} \cdot \mathbf{x})$$

Then:

$$\begin{align\*} f(\mathbf{w} + \delta \mathbf{w},\mathbf{x}) - f(\mathbf{w}, \mathbf{x}) & = h((\mathbf{w} + \delta \mathbf{w}) \cdot \mathbf{x}) - h(\mathbf{w} \cdot \mathbf{x}) \\ & \approx (\mathbf{x} \cdot \delta \mathbf{w})\\, h'(\mathbf{w} \cdot \mathbf{x}) \end{align\*}$$

Again, this gives you an approximation to how "wrong" the weights are given a "wrong" observation.

The backpropagation algorithm works by combining all of the training data into a single loss function which measures how "bad" the current set of weights is in training the data, and then does more or less exactly the above procedure, estimating the gradient of the loss function with respect to the weights, and then moving all of the weights in that direction.

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


title: Minimum frame size in ethernet

text:
# Question
Title: Minimum frame size in ethernet
Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 μs. The minimum frame size is:

a) 94

b) 416

c) 464

d) 512

My approach:- I have read in the book that minimum frame transmission time is atleast twice the round trip time.So by that logic i can say that the answer will be 464.As soon as the first bit of jamming signal reaches the sender,it know about the collision. But I need to know whether time to transmit jamming signal over the link should also be included in this case?I mean whether the first bit of the jamming signal is sufficient to for the sender to detect the collision or the complete jamming signal needs to be received at sender side,which will make the answer as 512.

I dont have the answer as this question was in some exam in 2005 and there was no answers available to this.

# Answer
> 2 votes
This might not be the correct answer to your question(as I am not sure about jamming signal), but it might resolve the query.

As Ethernet uses CSMA/CD for error detection, the time taken to transmit the data must be greater than or equal to twice the time taken to propagate the data. Only then the station will come to know if there had been a collision.

```
Tt >= 2*Tp

```

# Answer
> 0 votes
The original size of ethernet IEEE 802.3 standard define the minimum ethernet frame size as 64 bytes .The minimum size of ethernet frame that carries on ICMP packet in 74 bytes.you can test this by installing a packet analyzer on your desktop and by running a ping packet with no options to distination inside your network.it will generate a 74 byte packet with a 60 byte IP header ,8 byte ICMP header,and ethernet frame size.

# Answer
> -1 votes
2^n \> 46.4\*10^-6 * 10^6; n \> log(464)/log(2) ~ 8.86...so set n = 9....2^9 = 512

---
Tags: computer-networks
---


title: Complement of $a^n b^n c^n$

text:
# Question
Title: Complement of $a^n b^n c^n$
I am trying to find the complement of the language $L = \\{ a^n b^n c^n \mid n \ge 0\\}$.

I know that one of the things I gotta do is take out $n \ge 0$ so $\\{a^n b^n c^n \mid n \> 0\\}$ but I feel there is not enough.Is making it so $a^i b^j c^k$ so that $i \neq j \neq k$ enough and make it so that $i,j,k \> 0$?

Or am I completely off track?

# Answer
The complement is the set of all strings over alphabet $\\{a,b,c\\}$ that are not of the form $a^i b^i c^i$ for some $i\geq 0$. That includes all strings $a^ib^jc^k$ where $i\neq j$, $i\neq k$ and/or $j\neq k$, as you say, but also some other strings. Mouse-over the box below for a hint.

> For example, $bacbabc$ is in the complement.
> 2 votes

# Answer
First note that strings in $L= \\{a^ib^jc^k: i=j=k\ge 0\\}$ have a specific order and specific count of the symbols. The complement of $L$ (denoted as $L'$) then includes every string over the alphabet $\\{a,b,c\\}$ that does not satisfy the order and/or the count constraints. This implies that $L'$ consists of the following languages over the alphabet $A=\\{a,b,c\\}$:

1. To relax the order constraint: a string in $L'$ could have either $ba, ca$, and/or $bc$ as a substring. This can be represented as the regular expression: $(a+b+c)^\*(ba+cb+ca)(a+b+c)^\*$.
2. To relax the count constraint: a string $w$ in $L'$ could have either $i\ne j$, $i\ne k$, or $j\ne k$. Clearly, part 1 is a regular language and part 2 is CF, and hence their union $L'$ is CF.
> 1 votes

# Answer
Note that every string in $\\{a,b,c\\}^\*$ starts with a string from $L$ (even if in some cases that string is the empty string, with $n$=0).

If a string is not in $L$ then the prefix $a^nb^nc^n$ (for largest possible $n$) is followed by a *non-empty* suffix.
> 0 votes

---
Tags: formal-languages
---


title: Removing vertices from a labelled graph

text:
# Question
Title: Removing vertices from a labelled graph
Let $G$ be an undirected graph with each vertex labeled with an integer. Is there an algorithm to remove a subset of vertices such that in the resulting graph with deleted vertices no vertices with different integer labels are connected with an edge, but also among all groups of vertices labeled with the same integer, the size of the smallest group (i.e., the number of vertices) is maximum possible?

For example, in the following picture there is a graph with v1, v7, v8, v9 labeled with 0 and the rest of the vertices labeled with 1. We can either remove v1 and will have 3 vertices labeled with 0 and 5 vertices labeled with 1, thus the size of the smallest group being 3. Or we can remove v4, v3 and v2, then we will have 4 vertices labelled with 0 and 2 vertices labelled with 1, thus the size of the smallest group being 2. We can remove isolated vertices too, but it will either decrease or wont change the size of the smallest group, so this isn't useful. Overall number of vertices removed is of no interest, it's just the size of the smallest group.

# Answer
The problem is $NP$-complete by reduction from $3$-SAT. In the reduction, the goal will be to have at least one vertex of each labeled class left.

For every variable, we create $2$ vertices linked by an edge that have unique colors. Which of these two vertices we delete will determine the truth value of this variable. We create an additional copy of this gadget, which is not connected to anything else but allows us to conserve one vertex of the opposite color class.

For every clause with $3$ literals, we create a clique on $3$ vertices (corresponding to the $3$ literals), each with unique colors. We must delete all but one of the vertices from this gadget, and the vertex which is not deleted signifies which literal causes the clause to be satisfied. We create two further copies of this gadget, which are not connected to anything else but (similarly to the variable gadgets) allow us to conserve vertices of the unused color classes.

We now connect every vertex whose preservation denotes making a true (resp. false) assignment to a variable to the literals which are incompatible with that assignment.

For a clause with $2$ literals we do the same, except with $2$ (instead of $3$) cliques on $2$ (instead of $3$) vertices.
> 6 votes

# Answer
First, let us solve the decision problem:

> can we remove vertices such that the smallest group will have at least $T$ vertices?

This can be answered in a greedy fashion. At each step, pick an inconsistent edge $u,v$ (i.e., $u$ and $v$ have different labels) such that one of the vertices belong to a minimum size group, delete the vertex that belongs to a group which has more than $T$ vertices. If both have more than $T$ vertices delete one of them arbitrarily. If both have $T$ vertices return `fail`. Update the datastructre to reflect the deletion of the vertex, and repeat this step until all the inconsistent edges are removed.

Now you can solve the original problem by doing a binary search on $T$, and find the maximum value $T$ for which we have a `success`.
> 0 votes

---
Tags: graphs
---


# Question
Title: Network Flow - Minimum flow in a network
I have a directed graph **G=(V,E)** with a source **s**$\in V$ and a sink **t**$\in V$. There is a minimum capacity (lower bound) **l $\_{e}$** for each edge in **G**. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow -

1) We need to assign a large capacity to all edges and find flow **f**
2) Construct **G $\_{1}$** where all edges are reversed and each edge has capacity **f$\_{e}$ \- l$\_{e}$**
3) We need to then find the max flow from t to s in G$\_{1}$ that is f$\_{1}$
4) Then, the minimum flow in G is **f-f$\_{1}$**

> My question is- Why can't we find a `s to t` path in `G` with the least value of l$\_{e}$. The least value of l$\_{e}$ would be the minimum flow that could be pushed through the network?

# Answer
> 0 votes
Imagine you have the following graph (in red are the minimum capacities):

The $(s,t)$-path with the lowest flow demand needs $1$ unit of flow, but the minimum flow is $4$. And the $(s,t)$-path with minimum sums of capacities has a sum of $2$, so this also doesn't work.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Some questions about the Computability of Turing Machines
I'm learning for a test and I have some important questions about Computability of deterministic and non deterministic Turing Machines.

Consider we have the partial functions $f,g,h,t: \mathbb{N} \rightarrow \mathbb{N}$ with $f$ is Turing Machine computable, $g$ not Turing Machine computable, $h$ is not While solvable and $t$ is While computable. Are the following answers correct? And is there anything changing if we had an non deterministic TM?

There is no proof to do words are ok :)

1. Is $f \circ g$ Turing Machine computable?
2. Is $g \circ f$ Turing Machine computable?
3. Is $t \circ h$ While computable?
4. Is $h \circ t$ While computable?

My answers:

First of all, we know that Turing Machine = While Computability. (#)

1. I would say, that we do not know if it is or is not TM computable, because there may a TM who can handle the output of an not TM computable function.
2. I would say no, because if whatever $g$ takes, it won't be TM computable.
3. and 4. Because of (#) it is the same like 1. and 2.

Could that be right? It is for an multiple choice test and those questions are tricky.

# Answer
The answer is "we don't know without more information" for all 4.

Suppose $f$ is the identity function $f(x) = x$. Then $f \circ g = g \circ f = g$, which is non-computable.

On the other hand, suppose $g$ is a *total* non-computable function (which is a special case of $g$ being a *partial* non-computable function), and suppose $f$ is the constant zero function $f(x) = 0$. In this case:

Deterministic vs. non-deterministic Turing machine doesn't affect the answer, because a deterministic Turing machine can simulate the execution of a non-deterministic Turing machine (potentially with an exponential slowdown) by dovetailing.
> 2 votes

---
Tags: turing-machines, church-turing-thesis
---


# Question
Title: Shortest path from $s$ to $v$ in unweighted simple directed graphs
Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an **efficient algorithm for finding the length of a shortest path from $s$ to every other vertex in the graph**, fulfilling the following condition: the path includes at most two red edges. In other words, every $v∈V$ should be labeled with the length of a shortest path from $s$ to $v$ in which there are at most two edges from $E'$ and any number of edges from $E\backslash E'$.

# Answer
> 4 votes
Create a new graph $G' = (W,F)$ as follows:

* For every every $v\in V$, create three vertices $v\_0,v\_1,v\_2$ in $W$. The index $i$ in $v\_i$ represents the fact that any path to this vertex uses exactly $i$ red edges.
* For every edge $(u,v)\in E\setminus E'$, create the edges $(u\_0,v\_0)$, $(u\_1,v\_1)$ and $(u\_2,v\_2)$ in $F$.
* For every edge $(u,v)\in E'$, create the edges $(u\_0,v\_1)$, $(u\_1,v\_2)$ in $F$.

Now you just have to compute the length of the shortest path from $s\_0$ to any other vertex in your new graph $G'$ (if the vertex is unreachable then let this distance be $+\infty$). The length of the corresponding shortest path from $s$ to $v$ in $G$ is then the minimum of the lengths to $v\_0,v\_1$ and $v\_2$.

# Answer
> 0 votes
The problem you posted is a *single source shortest-path* which given a graph *G(V, E)* and a designated vertex $s\in V$, requires computing the shortest path from $s$ to all vertices $v\in V$ where the cost of a path $\omega(\pi)$ is defined as the sum of all edge costs in $\pi$.

For this specific problem in particular, I would highly recommend a straight application of Dijkstra's algorithm. Indeed, there is no need to replicate vertices and the problem can be optimally solved over the original graph without modifications. There is, however, a subtle question to take into account ...

There are two necessary modifications over the original implementation of Dijkstra's algorithm (here I'm referring to the implementation in the link given above under section "Practical optimizations and infinite graphs"):

1. For each vertex generated, keep track of the number of red edges that were taken in the path from $s$ to it. If a descendant is generated with a number of red edges that exceeds your threshold (2 in your case) then dismiss it, i.e., instead of **if n not in explored** (before last line in the pseudocode referred to above) you should say **if n not in explored and number(red\_edges)\<=2**
2. However, *duplicate detection* (which is implemented in **if n not in explored**) is tricky here: assume you find a shortest path from $s$ to a node $v$ after expanding 2 red edges. As Dijkstra's guarantees that this is the optimal path from $s$ to $v$ you certainly accept it, but it might happen that this path can not be extended to reach another vertex $u\in V$ because it is necessary to traverse another red edge. Hence, if $v$ is found again, it should be added to OPEN (called *frontier* in the pseudocode) even if the new path has a greater cost if and only if the number of red edges of the new path is less than the number of red edges traversed in the optimal path. This way, if the optimal path can not be extended to reach the vertex $u$ there is a chance for this sub-optimal path to reach it.

If memory is an issue for you, then the same problem can be solved using depth-first search strategies. Let me know if you are interested in these ...

Hope this helps,

PS - As you are a new contributor let me please emphasize the following: Tassle's response is definitely right and mine ain't better than his/hers. In addition (s)he was first to provide a correct answer to your problem, so please follow his advice and do not forget to accept her/his answer as it certainly closes the question. That is typical in stack exchange and it is a way to acknowledge the contributions of unknown people.

---
Tags: algorithms, graphs
---


# Question
Title: When does a semaphore issue a wait and when does it issue a signal?
In my textbook, *Operating Systems: Internals and Design Principles (9th Edition)* by William Stallings in chapter 5, it explains how semaphores work:

> The fundamental principle is this: Two or more processes can cooperate by means of simple signals, such that a process can be forced to stop at a specified place until it has received a specific signal. Any complex coordination requirement can be satisfied by the appropriate structure of signals. For signaling, special variables called semaphores are used. To transmit a signal via semaphore `s` , a process executes the primitive `semSignal (s)` . To receive a signal via semaphore s, a process executes the primitive `semWait (s)` ; if the corresponding signal has not yet been transmitted, the process is suspended until the transmission takes place.

I can't find a description in chapter 5 of when a semaphore would issue a semSignal vs a semWait (which are also sometimes called signal and wait). Can anyone describe the conditions under which semSignal would be issued vs a semWait?

# Answer
The semaphore doesn't issue those. A semaphore is an object that can be used by processes to coordinate between themselves. Thus, a process will call semSignal or semWait on a shared semaphore. We can't describe the conditions under which it will do that in general, because it's up to each process how it wants to use semaphores. Semaphores are a primitive that can be used in many ways. You should be able to find many examples online or in your textbook of using semaphores for coordination; that will give you some examples of specific processes and when those particular processes will invoke those operations on a semaphore.
> 1 votes

---
Tags: operating-systems, process-scheduling, mutual-exclusion, semaphore
---


title: Grammar is LL(1) or not?

text:
# Question
Title: Grammar is LL(1) or not?
S -\> AS | b

A -\> SA | a

I get FIRST of S = {a,b} for S-\>AS and FIRST of S = {b} for S-\>b

Hence FIRST(AS) ∩ FIRST (b) is not a disjoint This is not LL(1)

But I checked this site http://smlweb.cpsc.ucalgary.ca/start.html and this shows the grammar is LL(1).  Here I am confused!

Is it LL(1) or not?

# Answer
That website uses a different notation than what you assumed. This would be the correct input:

```
S -> A S | b.
A -> S A | a.

```

You entered `AS` (and `SA`) which it does not recognize as `A` followed by `S`, but as a single nonterminal named `AS`.

With that input it correctly says that the language is not $\text{LL}(1)$.
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Difference between a skiplist and an Indexable skiplist
Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little example?), I can only find so little about it online. Thanks.

# Answer
An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries. In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do this in logarithmic time.

It does this by keeping track of the width of the links in the skiplist.
> 2 votes

---
Tags: algorithms, time-complexity, search-algorithms, lists
---


# Question
Title: What does normalizing with hidden bit really mean?
I have a question related to representing numbers in base 2 with floating point. For example, if I have such a number $$0.000011 \cdot 2^3$$ then is its normalized form this? $$1.1\cdot 2^{-2}$$ Generally speaking about normalizing, normalizing with hidden bit, does it imply that the first number of mantissa should always be zero, or does hidden bit just mean that a "one" should be taken left to the point?

# Answer
Generally speaking, *normalized* means "put in scientific notation." That just means, the mantissa should never start with 0, and should be less than the base. In binary that means the mantissa must be "1". Since the mantissa of a normalized binary floating point number is always 1, we don't need to store the 1. The first mantissa bit is *hidden* in the sense that it always exists, but we don't actually store the bit, because we know its value is 1.

So your normalized result ($1.1 \times 2^{-2}$) is correct, and it is correct because you've moved the first 1 to the left of the binary point.
> 7 votes

# Answer
**Shorter Answer** (As requested by `greybird` in the comments) :

**The gist of "normalizing" in scientific notation, is not to allow the same number to have multiple corresponding codes**, i.e., we want each of the codes to be uniquely corresponding to a single number. This is not the case with floating point notation.

Both notations are in the form $X * 10 ^ Y$($X$ is called the significand or the mantissa, $Y$ is called the exponent), but with the difference that in the scientific form, the $X$ will be *normalized* (explained how in the example below), i.e., every number will be represented as a single code, but in the floating point notation every number will have multiple representations(so basically, the scientific notation is a special variant of the floating point notation).

**Example:** in base 10 scientific notation encoding which is in the form $X * 10 ^ Y$, if we do not agree on beginning all $X$s with digits in the range \[1, 9\], then every number will have many scientific notation codes corresponding to it, for instance, $7.53$ could be encodable as all these codes: $75.3\*10^{-1}, \ \ \ \ 7.53\*10^0, \ \ \ \ 0.753\*10^1, \ \ \ \ 0.0753\*10^2, \ \ \ \ ... \ \ .$

The same story is true about base 2 scientific notation, we do not want multiple codes for the same number, e.g, $ (0.011 * 10^{10})\_{2}, \ \ \ \ (0.110 * 10^{01})\_{2}, \ \ \ \ (1.10 * 10^{00})\_{2}, \ \ \ \\, ... \ \ .$ So we have to make an agreement about the $X$, the same way we did above(in base 10). Now, we *could* agree on anything, for instance, beginning all $X$s with 00.01, or with 0.001, or etc. but these are obvious wastes of bits. So a better agreement is to begin all $X$s with "0.", because this way we won't be storing any insignificant bits. But you know what? There's still a 0 there... we don't like to consider it *significant* as well, is there still a better way? Well there is. We could begin the numbers with "1."(This is IEEE754, i.e., no more the scientific notation in its usual form, rather a variant of it). But, you might ask, how about representing the number 0.0? If all $X$s begin with 1., then *normally* the number 0.0 will not be representable. That's a very good question, but let me first explain what's meant by the "hidden bit 1" and after that, we'll get back to this question.

Let's say we have agreed on beginning all $X$s with "1.", then why storing this "1." too in memory at all?! **We know it must be considered when decoding every code to a number, so we don't need to store it explicitly in memory at all**. The benefit is obvious, we can add another bit to the fractional part of the $X$(after the dot) and thus make the number range both bigger and more precise (bigger for positive exponents, more precise for negative exponents).

Now back to the question on representing the number 0.0 in IEEE754. We can simply agree on some special bit pattern to represent it. When all exponent bits and all mantissa bits are 0 we will *interpret* the number differently, i.e, we'll consider it as $^{+}\_{-}0.0$ (instead of $^{+}\_{-}1.0 * 2 ^ 0$) (And... Yes, there are two codes for zero in IEEE754). There are also other special values for representing these symbols:

* +Infinity: {sign bit 0, all exponent bits 1, all mantissa bits 0}
* -Infinity: {sign bit 1, all exponent bits 1, all mantissa bits 0}
* NaN(Not a Number, e.g., $\frac{1}{0}$ and etc.): {all bits 1}

Also there are *denormals* (because they begin with a "0." instead of "1.") that fill the ugly gap around 0 (i.e. smaller absolute value than the smallest possible normal).

* denormals: {all exponent bits 0, at least one mantissa bit non-zero}.

---

**Longer Answer** (If you want to learn the IEEE754 more slowly) :

I'll explain this with an example. If you consider these three numbers and their binary values:

* 0.06 = 0.000011110101110...
* 3.14 = 11.0010001111...
* 31.72 = 11111.101110...

as you can see, the position of the radix point(the dot) is different in each of them. (it's in the 2nd place in 0.0000111101, in 3rd place in 11.0010001111, and in the 6th place in 11111.101110) So **how can we store the position of the radix point in hardware**? Remember we only have 0s and 1s there.

You might propose for example, we can put a number of 0s instead of it, so when we see those 0s we know it's our radix point! But that wouldn't work obviously. because there's no way to tell whether those 0s are really part of the binary number or our radix point. You can't use 1s either, and you can't use any mixed pattern of 1s and 0s as well, just for the same reason. So what do we do?

A better answer is: We can agree on some position to put the radix point there, and then **specify how much it has to move towards left or towards right to give us the correct number**(from now on we'll call this movement "offset"). If we use this new way, the above numbers will become(for brevity, I've only written 10 bits after radix point, for each):

* 0.06 = 0.0000111101 **&** radix point is in place, no movement to left or right is needed.
* 3.14 = 1.1001000111 **&** radix point must move 1 place towards right
* 31.72 = 1.1111101110 **&** radix point must move 4 places towards right

So now, we can keep these in our hardware(for now let's say we only want offsets as big as 7 at maximum (which means 3 bits for offset). Only so that all three below shapes fit in one line):

```
offset                        offset                          offset
   |                             |                               |
   |    0.06                     |    3.14                       |    31.72
   v                             v                               v
 +-+--------------+            +-+--------------+              +-+--------------+
 |000|0000111101  |            |001|1001000111  |              |100|1111101110  |
 +----------------+            +----------------+              +----------------+

```

(Notice #1: 4 is 100 in binary!)

(Notice #2: That vertical line after offset doesn't exist in hardware obviously, It's just put there as a vision helper so that you don't get ocular cancer when trying to distinguish the offset bits from the rest.)

So far so good, by only having these in place, we have achieved our initial goal. However, as always, there's still room for improvements! Two of such improvements are explained below.

* improvement #1: How about negative numbers? Easily enough, we can just add a sign bit at the beginning of our hardware representations. Usually 0 for positives and 1 for negatives.
* improvement #2: In our hardware representation of the first number(0.00001111...), we have so many 0s. That's an unforgivable waste of bits(i.e treasure!). To solve this, we can agree to begin every hardware representation from the first bit that is 1 and then work out the offset, so first representation becomes this(again I've only written 10 of the bits after the radix point):
* 0.06 = 1.1110101110 **&** radix point must move 5 places towards left.

please notice that we have lost no precision because those 0s were "really" 0s and they were not produced for example out of rounding. So it's completely safe to do this. But now, there's also another benefit along with this new convention: **We can even skip another bit 1 when storing any numbers**(sometimes called the hidden bit, as the OP asked), because with this new convention we can be sure that all* of our hardware representations will begin with a bit 1! So now we can also see why when converting ieee754 representations to decimal, we have the "1.M" in the formula:$(−1)^{S}∗2^{E−127}\*1.M$. **Because we hid it when writing the rest of the bits in hardware but we shouldn't forget it when interpreting the hardware stuff back to decimal**. Anyway, here are our representations so far:

```
 offset                        offset                          offset
    |                             |                               |
Sign|        M                Sign|        M                  Sign|        M
 |  |        |                 |  |        |                   |  |        |
 |  |  0.06  |                 |  |  3.14  |                   |  |  31.72 |
 v  v        v                 v  v        v                   v  v        v
++--+--------+-----+          ++--+--------+-----+            ++--+--------+-----+
|0|101|1110101110  |          |0|001|1001000111  |            |0|100|1111101110  |
+------------------+          +------------------+            +------------------+

```

So far the OPs question has been answered, you can skip reading the rest of the answer. But the above representations still have one small (or big if you will) flaw. The first offset (101) is towards left, but the other two offsets (001 and 100) are towards right! But currently, we can't say that by looking at our representations! **We have devised no ways to keep this important piece of information, namely, the direction in which the radix point must be moved.**

We *could* consider another bit for that, but instead, here we'll do something else(and so does ieee754 similarly). Basically, what we need is a way to keep both positive and negative offsets, to represent movement towards left and right respectively(a radix point in a binary number moves towards left if the number is multiplied by positive powers of 2 and towards right if the number is multiplied by negative powers of 2). Now to have both positive and negative offsets, you may choose any notation, say two's complements or etc. But here we'll use Excess-N notation(and so does ieee754). To do this in our own case, let's take these steps:

1. We'll use 4 bits instead of 3 offset bits and we'll call these 4 bits E.
2. We'll agree on an arbitrary number between 0 and 15. Say 12. This is our N in Excess-N. So we're using Excess-12 now.
3. We'll subtract 12 from any number we read in the E.

Now we can have both positive and negative offsets! For example, if you fill the E with number 15 (all 1s), it will mean +3 offset (15-12), or if you fill the E with number 8, it will mean -4 offset (8-12). (Also you can see that if we had chosen either 0 or 15 as N in the second step, we wouldn't be able to produce either negative or positive offsets respectively). But in our case 12 isn't a good choice for N too, because we can have an offset of -12, but we can't even have an offset of +4, so a better N would be 7 or 8 because they make both positive and negative offsets representable as much as possible(of course in some special cases, you might need more positive or more negative offsets based on the problem and then there's nothing stopping you from choosing 'N's other than 7 and 8. but in our case, we have no assumptions about the type of the problem, so we'll keep it as much generic as possible). Now, assuming N is 7, our final version of the representations will become like this:

```
    E                             E                               E
    |                             |                               |
Sign|        M                Sign|        M                  Sign|        M
 |  |        |                 |  |        |                   |  |        |
 |  |  0.06  |                 |  |  3.14  |                   |  |  31.72 |
 v  v        v                 v  v        v                   v  v        v
+---+--------+-----+          +---+--------+-----+            +---+--------+-----+
|0|1100|1110101110 |          |0|0110|1001000111 |            |0|0011|1111101110 |
+------------------+          +------------------+            +------------------+

```

and to convert these to their decimal equivalents, one only needs to use this formula: $ (−1)^{S}∗2^{E−7}\*1.M $

(With the float data type defined in ieee754 things are very similar(except for special values, denormals, roundings and some other technicalities). They're only different in bit lengths. E is 8 bits instead of 4, and M is 23 bits instead of 10, plus 1 sign bit which make up 32 bits in total, and the formula becomes: $ (−1)^{S}∗2^{E−127}\*1.M $ ).

Hope that helps.

---

* Of course not exactly all of them in ieee754. There are special values like denormalized numbers as mentioned in the shorter answer.
> 2 votes

# Answer
The "hidden bit" refers to concrete representations, where you represent the -2 exponent as a bit field in memory storage, and the .1\[00000...\] as another bit field. For example in IEEE 32-bit format, it is:

```
00111110110000000000000000000000
+^^^^^^^^_______________________

```

With the sign, exponent (in bias format), and the hidden-bit mantissa.
> 0 votes

---
Tags: floating-point, number-formats, normal-forms
---


# Question
Title: Is dynamic programming restricted to optimization problems?
The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean that DP can only be used to solve optimization problems? Otherwise, it would make more sense to write (1) as "if it can be decomposed in sub-problems" (i.e. it is recursive). Obviously, this definition includes optimization problems with optimal sub-problems.

# Answer
> 8 votes
Dynamic Programming can be used to solve a problem as long as the problem has a *recursive substructure* and the *sub-structural problems are overlapping*. So, as long as a problem has the two properties, DP can be used for solving it. Problems with these properties are definitely not restricted to only optimization problems. So, yes.

Here are some good examples of non-optimization problems which can be solved quickly using DP:

1. Coin Change Problem
2. Counting the number of increasing subsequences in a given sequence
3. If you forget everything, calculating upto the first $n$ Fibonacci Numbers using its recurrence relation can be done using Dynamic Programming.

---
Tags: dynamic-programming
---


# Question
Title: Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$?
I used IDA$^\*$ for optimally solving the 8-puzzle and my friends used A$^\*$ for it too (with same manhattan distance heuristic).

I calculated the average running time and number of nodes of my algorithm for 20 examples and my friend's algorithm. The time average for my algorithm was much faster than my friend's algorithm, but my average number of nodes visited is a lot more than my friend's.

**I know IDA$^\*$ visits each node more than once but why is it faster than A$^\*$?**

# Answer
> 2 votes
Since you already implemented IDA$^\*$ you certainly understand why it expands more nodes than A$^\*$, i.e., it starts from the start state with a new depth-first traversal in each iteration. Note first that, the overall number of nodes visited by IDA$^\*$, while necessarily larger than A$^\*$ is not that much larger. The reason is that the number of nodes at each depth progresses according to a geometric series with factor $b$, the branching factor. As a result, the number of nodes at depth $d$, $b^d$, is much larger than the sum of all nodes expanded at the previous iterations, i.e., $b^d\>\sum\_{i=0}^{d-1}b^i$. From this difference, it turns out that IDA$^\*$ requires $\frac{b}{b-1}$ additional expansions which is asymptotically optimal as the limit for large $b$ is 1. Concluding, for *any* algorithm visiting all nodes at depth $d$ is much more difficult than visiting all nodes at the preceding depths.

In case that you want to delve more into this issue, I strongly recommend you reading the original paper: Korf, Richard E. Depth-First iterative-deepening: An optimal admissible tree search. Artificial Intelligence (27), 97-109, 1985. See in particular Theorem 4.2:

> Depth-first iterative-deepening is asymptotically optimal among brute-force tree searches in terms of time, space, and length of solution.

Of course, it delivers optimal solutions so that it is admissible and hence, asymptotically optimal. It only practices depth-first traversals and therefore, it is asymptotically optimal in terms of space (requiring with a good implementation only $O(d)$).

As for the time, I already outlined the main theoretical reason but let me know highlight three main reasons why it is so fast in practice:

1. First of all, for almost all purposes, the overall running time of any algorithm is dominated by the time it takes to expand nodes (other operations are rather simple and atomic). It is indeed when expanding nodes that IDA$^\*$ can be extraordinarily fast because:

1.1. IDA$^\*$ is implemented recursively so that all you need is to take the state given as an argument and to generate a child at a time (for your specific case this simply means swapping the blank with an adjacent tile, that's only one statement!). However, for A$^\*$ the expansion operation requires: first, popping a state from the queue, then generating all its children (i.e., moving the blank tile in all possible directions).

1.2. While the preceding operation makes some difference, the really important one is that A$^\*$ requires sorting nodes in OPEN. Even if you do this with a 1-bucket (which would take $O(1)$), note that IDA$^\*$ does not require to sort nodes at all, so that while A$^\*$ takes time which is linear in the number of nodes expanded, IDA$^\*$ takes none at all.
2. Thirdly, one of the contributions of best-first search algorithms (such as A$^\*$) is that they avoid re-expanding nodes by using a CLOSED list (which in spite of its name is usually implemented as a set!!). IDA$^\*$ does not have *duplicate-detection* mechanisms and hence, again, A$^\*$ performs an extra operation which is not performed at all by IDA$^\*$. If you want to know more about *duplicate-detection* in IDA$^\*$ see: Reinefeld, A.; Marsland, T. Enhanced iterative-deepening search. IEEE Transactions on Pattern Analysis and Machine Intelligence (16) 7, 701-710, 1994.

The last point is truly relevant. In the case of the sliding-tile puzzle there are not many transpositions indeed and the shortest cycle consists of 12 moves, so that the number of re-expansions is not that large. Putting all these together, IDA$^\*$ is a killer machine for all sizes of the sliding-tile puzzle.

However,, in spite of all its advantages, it might not be of practical interest in those applications that have a large number of transpositions. There have been various attempts to overcome this difficulty with limited success, see for example:

Dow, P. Alex; Korf, Richard E. Duplicate avoidance in depth-first search with applications to treewidth. International Joint Conference on Artificial Intelligence, 480-485, 2009.

Hope this helps,

---
Tags: algorithms, search-algorithms, artificial-intelligence
---


# Question
Title: Which sort algorithm to choose given two specific arrays?
**Interview question:**

Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose.

I said merge sort. I thought that given two lists both of which are sorted (which I assumed) I can just merge them i.e use the merge part of merge sort. I was then asked if the numbers were not even or odd would I have chosen merge sort still? Then I was asked if both arrays were not sorted i.e. A contain even numbers (not sorted) and B contain odd numbers (not sorted) which algorithm will I use. I said in practice quicksort typically performs better. I wanted to ask if the length of the arrays is not too big because then bucket sort might do but given his insistence on odd and even integer arrays I did not go for bucket sort (I was afraid I was mentioning all the algorithms). Does anyone know which algorithm might the interviewer be looking for?

# Answer
> 5 votes
I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime.

Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then run your super fast algorithm on these arrays to sort your original array super fast as well. Thus, a faster algorithm for this case would lead to a faster algorithm in the general case. So you can safely choose to use whatever sorting algorithm is fastest in the general case (asymptotycally $O(n\log n)$).

---
Tags: algorithms, sorting, arrays
---


title: graph theory proof or disproving

text:
# Question
Title: graph theory proof or disproving
I was requested to prove or disprove the following statement if a graph is conncted does it necessarily means that E\>(V-1)(V-2)/2 v represents vertex and E the edges I think I need to disprove it with overall disproval but how?

# Answer
> 1 votes
If you think it's false, the easiest way to disprove it would be to find a counterexample. That is, find a graph where $E \leq \frac{1}{2}(V-1)(V-2)$. Try some easy connected graphs (e.g. a straight-line path graph) and see if you can find a suitable graph.

# Answer
> 0 votes
I assume that you're talking about the graph being a simple graph. In that case:

For a connected graph, $e \geq v - 1$. Therefore, in the worst case, your statement would be true if $v - 1 \> \frac{(v - 1)(v - 2)}{2}$.

The inequality reduces to $(v - 1)(v - 4) \< 0$, which means that the possible values of $v$ for the statement to be true are $2$ and $3$. For all $v$ that are not are equal to $2$ or $3$, your statement won't hold true.

So, the statement is not true for all values of $v$.

EDIT: If you want direct counter-examples, consider any connected simple graph with 4 vertices. That'd be a counter-example.

---
Tags: graphs
---


title: What type of function is main()?

text:
# Question
Title: What type of function is main()?
As the functions are of 2 type:
1.Pre-defined/library functions,
2.User defined functions.

What type of function is *main()* function?

This doubt comes in my mind while writing a program we define the *main()* function as we do the others.

Please help!!!

# Answer
Library functions are functions that somebody else coded, and are available for use.

User-defined functions are functions that the user defines. This is the case of the C/C++ `main()`.

You can think of `main()` as a placeholder or hook. The user supplies it, but the standard library knows to call it after initializing itself.
> 3 votes

---
Tags: functional-programming, c++
---


# Question
Title: How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes
So here's the problem:

-You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid square is empty)

-You must minimize the number of empty grid squares by filling this grid with Tetris shapes which are each composed of exactly 4 blocks (a block is 1x1)

What is an algorithm that can consistently do this given any mxn partially-filled grid?

# Answer
> 2 votes
This question can be reduced to the exact cover problem which is NP-Complete. A typical method for solving the exact cover problem is known as Algorithm X.

Consider the set of choices you have: For each tetris piece of $4$ units, you can select an orientation and a location to place it on the board. For each choice, the piece will cover $4$ squares on the board. Let matrix $A$ be our exact cover matrix. The columns of $A$ are the constraints that must be satisfied exactly once i.e. there is a constraint for every unfilled grid location on the given board. Each row represents a "choice" i.e. a tetris piece, orientation and location and has $1$s in only the columns which correspond to the locations that that placement of the tetris piece would cover.

To account for the grid locations that have already been filled, we make sure that any row is removed that would either

* Fall outside of the $m$x$n$ grid
* Cover one of the cells already covered in the given $mxn$ grid

Then it remains to select a subset of rows $S$ such that for each column $i$: $$\sum\_{row\in S}row\[i\] = 1$$

Algorithm X is one way of solving this problem (with the help of the dancing links technique. Other algorithms exist as well (AC3 is taught as an introductory constraint-satisfaction solver algorithm at some universities). Soduku puzzles are another example of exact cover problems.

Notice that max cover is a **decision problem**, whereas the question you posted is an optimization problem. This can be addressed by just searching for the maximum number of columns covered over the search. Of course this will result in a much slower runtime since you will have to run the algorithm for longer. You may benefit from introducing some heuristics into your search as well. For example, say you are at some point in your search where:

* The best cover you have seen so far covers $s$ locations.
* Your current cover covers $k$ locations.
* There are $x$ remaining open locations on the board that are part of a connected group of at least 4 open locations.

If $k+x\leq s$, you can cut the search tree off here, since there is no way this current layout of tiles can lead to a better solution that the one you have already found.

---
Tags: algorithms, optimization, np-hard
---