Domino tiling of a 2xN rectangle in O(ln n) I solved this problem using Dynamic Programming in $\mathcal{O}(n)$ time. I found that is equivalent to the Fibonacci Numbers.

$F(0) = F(1) = 1$

$F(n) = F(n-1)+F(n-2)$

Where the $F(n-1)$ term is from fixing the left most domino vertically, and the $F(n-2)$ from fixing it horizontally (which implies that the domino under it must also placed horizontally).

Because the Fibonacci Numbers can be generated in $\mathcal{O}(\lg n)$ using

$F(2n) = F(n)F(n+1)+F(n-1)F(n)$

$F(2n+1) = F(n)F(n)+F(n-1)F(n-1)$

Then I try to find the same expression from the domino tiling. Again, I classify all possible tilings in two set. First, all tiling like the one below

Therefore, $F_H(n) = F(i)F(n-i-2)$. Because I want to split in the middle (or close) I consider $n=2k, i=k$ and $n=2k+1, i=k$.
Then

$F_H(2k) = F(k)F(2k-k-2) = F(k)F(k-2)$ and $F_H(2k+1) = F(k)F(2k+1-k-2) = F(k)F(k-1)$.

Then, all tiling of the form

Again, $F_V(n) = F(i)F(n-i-1)$ and when $n=2k, i=k$ and $n=2k+1, i=k$ we have

$F_V(2k) = F(k)F(2k-k-1) = F(k)F(k-1)$ and $F_V(2k+1) = F(k)F(2k+1-k-1) = F(k)F(k)$

Combining all the former expressions,

$F(2k) = F_H(2k) + F_V(2k) = F(k)F(k-2) + F(k)F(k-1)$

$F(2k+1) = F_H(2k+1) + F_H(2k+1) = F(k)F(k-1) + F(k)F(k)$

However, those final expression does not produce the same numbers. Because they look really similar I belive my approach is not completly wrong but I can not find where I make my mistake.

Final notes:

In the first classification, I fix the top most domino horizontally and if I consider a 1-tile shifted horizontal domino (left or right) under it, then the rectangle can not be tiled.
For the (correct) expression $F(2n+1)=F(n)F(n)+F(n-1)F(n-1)$, notice that $F(n)F(n)$ can be mapped to the second case, because $n+1+n = 2n+1$, but the other term $F(n-1)F(n-1)$ can not (at least in the same way), $(n-1)+2+(n-1)\neq 2n+1$. The same can be notice in $F(2n)$ and again one term can be mapped to the second case while the other can not (to the first case). I belive my mistake should be around the first case.

In your second attempt you tried to fixate the $(k+1)$th term. But instead of the two cases

1 2 ... k k+1 k+2 ... n
           |
           |

and

1 2 ... k k+1 k+2 ... n
           -----
           -----

there exist a third case:

1 2 ... k k+1 k+2 ... n
        ----
        ----

So if $n = 2 k$, then you have $f(k)f(k-1)$ for the first case, $f(k)f(k-2)$ for the second one, and $f(k-1)f(k-1)$ for the third one. This gives in total:

$f(2k) = f(k)f(k-1) + f(k)f(k-2) + f(k-1)f(k-1) = f(k)[f(k-1) + f(k-2)] + f(k-1)f(k-1) = f(k)^2 + f(k-1)^2$.

Now this formula looks like the formula for $F(2n+1)$ that you posted.

  Because the Fibonacci Numbers can be generated in O(lgn) using

  F(2n)=F(n)F(n+1)+F(n−1)F(n)

  F(2n+1)=F(n)F(n)+F(n−1)F(n−1)

Simple reason: the formula assumes that $F(1) = F(2) = 1$ while you have $f(0) = f(1) = 1$. So after an index shift it should match.

Identical procedure for the odd case $n = 2k + 1$.

edit: Tried to do the index shift but failed. Reason was, that you wrote down the wrong formula for $F(2n+1)$. It should be $F(2n+1)=F(n)^2+F(n+1)^2$. Then the index shift works:

$f(2k) = F(2k+1) = F(k)^2+F(k+1)^2 = f(k-1)^2 + f(k)^2$.


Finding the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to given string s I got stumped by this question during a coding challenge and I haven't come up with promising ideas for how to solve it. I am looking for hints or approaches to solve the problem, not necessarily the code.

Given a string s find the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to s.
Strings may contain only lowercase English letters.
Examples:
For s = "cbaba", the output should be smallestPalindrome(s) = "cbabc"
For s = "abcbc", the output should be smallestPalindrome(s) = "abdba"
Trickier test cases:
input: "xgdfcs", output: "xgeegx"
input: "aazzzzba", output: "abaaaaba"
input: "aiyudauzzzzuaduyie", output: "aiyudavaaaavaduyia"

Guaranteed constraints:
4 ≤ s.length ≤ 5x10^5.

My previous approach was to:

Check if word is a palindrome by moving two pointers (i, j) at both ends of the word towards the middle.
If the two characters don't match, either set i-th character equal to the j-th, viceversa, OR set both equal to some character that appears later in the alphabet.

...but I couldn't figure out how to decide which option in step 2) should be taken. Maybe there's a better approach to it.
I'm trying to avoid posting the name of the company that posed me this question to prevent future interviewees from knowing the answer in advance, so you can assume I found the question here:

Source: https://codelearn.io/training/detail/33520

Let's assume the length is even for now. Split the word up into two equal parts, $w = lr$. Let $l^R$ be the reverse of $l$.
If $l^R = r$, we are done immediately. Otherwise, if $r < l^{R}$ we can set $r$ equal to $l^R$. The more involved case is when $l^R < r$. In that case we will need to increment $l$ by one (view the lowercase English words as a base-26 number - this exactly matches lexicographic order), after which we can set $r$ equal to the reversed left hand side and we'll still be lexicographically bigger.
Now if our original word was odd in length we apply the exact same process, except when we shouldn't increment $l$ by one but start the increment one more to the right: at the middle element instead.
Some example code in C:
void increment_base26(char* s, int len) {
    int i = len - 1;
    while (i >= 0) {
        if (s[i] == 'z') s[i] = 'a'; // Wrap around and carry.
        else { s[i] += 1; break; }
        i -= 1;
    }
}

void reverse(char *s, int len) {
    for (int i = 0; i < len - 1 - i; ++i) {
        char t = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = t;
    }
}

void next_lexicographic_palindrome(char* s) {
    int len = strlen(s);
    int half = len / 2; // Rounds down.
    int half_plus_mid = half + (len % 2);
    reverse(s, half);                                // Compute l^R.
    int cmp = strncmp(s, s + half_plus_mid, half);   // Compare l^R and r.
    if (cmp > 0) memcpy(s + half_plus_mid, s, half); // l^R > r, can just copy over l^R.
    reverse(s, half);                                // Undo l^R -> l.
    if (cmp >= 0) { return; }                        // Simple cases l^R >= handled.
    increment_base26(s, half_plus_mid);              // Increment left + mid.
    reverse(s, half);                                // Copy over the new l^R to r.
    memcpy(s + half_plus_mid, s, half);
    reverse(s, half);
}


Typical set in Shannon's source coding theorem I was following the textbook by David Mackay: Information theory inference and learning algorithms.

I have question on asymptotic equiparition' principle:

  For an ensemble of $N$ $i.i.d$ random variables $X^N=(X_1,X_2....X_N),$ with $N$ sufficiently large, the outcome $x=(x_1,x_2...x_N)$ is almost certain to belong to a subset of $|A_x^N|$ having only $2^{NH(x)}$ members, with each member having probability  "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that typical set doesn't nesscarry to contain the most probable element set.

On the other hand, "smallest-sufficient set" $S_{\delta}$ which defines to be:

  the smallest subset of of $A_x$ satisfying  $P(x\epsilon S_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $  In other words, $S_{\delta}$ is constructed by taking the most probable elements in $A_x$, then the second probable......until the total probabily is  $\ge1-{\delta}$.

My question is, as $N$ increases, does $S_{\delta}$ approaches typical set such that these two sets will end up be equivalent of each other? If the size of the typical set is identical to the size of $|S_{\delta}|$,  then why are we even bother with $S_{\delta}$? Why can't we just take the typical set as our compression scheme instead?

The elements in the typical set have typical probability, close to $2^{-NH(x)}$. An element with untypically large probability, say the one with maximal probability, may not satisfy this constraint. Same goes for the rest of $S_\delta$.

The source coding theorem does take the typical set as an encoding scheme.


Deletion from 2,3,4 tree Consider a 2,3,4 tree like so,

           53
         /    \
        /      \
       /        \
     46          60 | 70
    / \         /    \   \
   /   \       /      \   \
  /     \     /        \   \
 41     48  55|59    65|68  73|75|79

How to delete 41 from the tree from here ? I would like to know the intermediate steps involved.

The problem you're encountering is that a deletion is cascading and triggering another deletion. In particular, you're deleting from a node with only one key. Rather than working from the bottom up, it may be easier to work from the top downwards to preserve all of the properties of the 2-3-4 tree while giving an extra key to the node you're deleting from. Here are the rules for deletion:

If node containing key has more than one key, just remove the key.
Otherwise, we're trying to remove a 2-node (node containing 1 key). Traverse the path from the root to this node and perform one of the following operations on every 2-node except the root node to transform it into a 3-node or 4-node (node containing 2 or 3 keys):

If node has a sibling that's a 3-node or a 4-node, have the parent steal a key from one such sibling and have the 2-node in question steal from the parent. The child of the sibling key we stole becomes a child of the node we just expanded.
If the node's parent is a 2-node and its sibling is also a 2-node, fuse all three together into a new 4-node. Note that this can only happen when the parent is the root since all other 2-nodes should've already been fixed.
If all of the node's siblings are 2-nodes, steal a key from the parent (we know we can do this because we're converting every node we hit into a 3-node or a 4-node) and fuse together the node, the stolen key, and an adjacent sibling.

So starting from the tree below, we see that 41 is the only key in its node so let's start from the root and perform operations as necessary on the way to 41. We start at the root 53 and do nothing:

    -->   53
        /    \
       /      \
      /        \
    46          60 | 70
   / \         /    \   \
  /   \       /      \   \
 /     \     /        \   \
41     48  55|59    65|68  73|75|79

Then we get to 46 which is a 2-node. One of its siblings has more than 1 key so we perform operation 1. In particular, have the parent steal a sibling key 60 and have the node containing 46 steal 53 from the parent. The original left child of 60 becomes the right child of 53.

              60
            /     \
           /       \
          /         \
   --> 46 | 53       70
      /   |  \       \   \
     /    |   \       \    \
    /     |    \       \     \
   41     48  55|59   65|68  73|75|79

Finally we're at 41 which is also a 2-node and all of its siblings are 2-nodes so we perform operation 3. In particular, we steal 46 from the parent and fuse 41, 46, and 48 into a new node.

                   60
                 /     \
                /       \
               /         \
              53         70
             / \         / \
            /   \       /   \
           /     \     /     \
--> 41|46|48  55|59  65|68  73|75|79

Now the node containing 41 has more than one key so we can go ahead and delete 41.


Show that the diameter of a MST is sometimes larger by a factor $\Omega(n)$ than the diameter of the graph $G$ As my title points out, I don't understand how do you show that, in general, the diameter of a MST (minimal spanning tree) can be bigger than the diameter of G, by the factor $\Omega(n)$. $(n:= |V|, G =(V,E)) $.

And I don't understand, how big is $\Omega(n)$ and why $\Omega$?

I made a example where the distance of two nodes in $G$ is smaller than the distance of the two nodes in the MST.

Is it correct to write,

$D_{MST} = D_{G} \cdot \Omega(n)$  ?
$\Omega(n) = D_{MST}/D_{G}$ ?

$D_{G} =$ diameter of graph $G$ and $D_{MST} =$ diameter of MST.

You say that you don't understand how to show that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

However, it seems that what you don't understand is what it means that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

It is impossible to prove a theorem if you don't understand its statement.

Here is what you are asked to do. Given a weighted graph $G$, we will use the following notation:

$n(G)$ is the number of vertices in $G$.
$D(G)$ is the diameter of $G$.
$D_{MST}(G)$ is the minimum diameter of a minimum spanning tree of $G$.

  Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and $D_{MST}(G) = \Omega(n(G)) \cdot D(G)$.

It seems that you are not familiar with the notation $\Omega(\cdot)$. It is the counterpart of big O, and described in the answers to this question.

Unpacking the big $\Omega$ notation, we can rephrase the question:

  Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and there exists a constant $C>0$ such that $D_{MST}(G_i) \geq C n(G_i) D(G_i)$.

The question is somewhat ambiguous – it's not clear if you need to provide an example for every $n$ or just for infinitely many $n$. I assumed the latter, but in fact in your case there is a sequence $G_i$ with $n(G_i) = i$, so you can try proving this stronger statement instead.


Virutalization of peripheral device I have this question to answer: "Please shortly explain how an interface virtualizes a peripheral device to the CPU."

I don't really understand what the question is asking for. I know the theory behind virtual memory. I understand that a harddisk can be seen as a peripheral device.

Could the theory behind virtual memory be what the question is asking for or did I totally misunderstand it?

"Virtualization" is a broad term that means abstracting away details of the device, and providing a more generic/abstract/higher-level interface or view of the device.  Sometimes it involves pretending that you have a simpler virtual device (with simple commands) instead of the complex physical peripheral you actually have (with its messy interface).

See, e.g., https://en.wikipedia.org/wiki/Storage_virtualization, https://en.wikipedia.org/wiki/I/O_virtualization, https://en.wikipedia.org/wiki/Virtualization, https://en.wikipedia.org/wiki/Virtual_file_system, https://en.wikipedia.org/wiki/Virtual_disk, https://en.wikipedia.org/wiki/Data_virtualization.


What does `Dv` mean in $F\star$ language? In the $F\star$ tutorial it says

  Dv, the effect of a computation that may diverge;

what does diverge mean here? It's not explained and it confuses me.

I guess it means the type consists but the value varies, but if so why there isn't a non-diverge non-terminate effect?

In the theory of computation "diverge" means "does not terminate" or "runs forever". This is a computational effect (of a peculiar kind).


How to use convex hull for this problem Problem:

You are to collect a total of $N$ litres of red and $M$ litres of blue liquid. For doing job $i$ for time $t$, you get $a_i  t$ litres of red and $b_i  t$ litres of blue liquid. $t$ need not be an integer. At a time you can only do one job. You can choose some (or all) of the jobs and do it for your desired time. Given such $n$ jobs in the input and their respective $a_i$ and $b_i$ find the lowest total time in which you can get $N$ litres of red and $M$ litres of blue liquid.

How do I solve this problem using convex hull?

Perhaps you want a hint first?
Of course you start by considering all vectors $(a_i,b_i)$ first. The vector $(a_i,b_i)$ indicates the amounts you earn by working one hour on job $i$.

What is the meaning of any point on the line segment between points $(a_i,b_i)$ and $(a_j,b_j)$?

If any point $(a_k,b_k)$ is within the triangle $(0,0)$, $(a_i,b_i)$, $(a_j,b_j)$ why can you discard it?


Lamport logical clock: why event occurs in a process with smaller pid is treated earlier? In lamport's paper1, he define global local timestamp, which is composed of process id and local lamport timestamp.

This timestamp is used to order all the events in a distributed system.

The rule to compare two events is following.

My Question

Imagine we have two events, one happens in process 1 (P1), with local timestamp 9, another event happens in process 2 (P1), with identical timestamp 9.

Based on lamport's rule, the first one is earlier than second one.

C1(9) => c2(9)

But why?

From my understanding, it does't make sense. An event is treated earlier just because it is born in a process which has smaller pid?

Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”

No, "it doesn't make sense". You are correct in the sense that that choice is not a logical consequence of any requirements and known truths. It could be considered as arbitrarily selected.

Well, we do not need to make any sense when we are forced to decide which one of two global timestamps, $(T_i,i)$ and $(T_j,j)$ where $T_i=T_j$, is earlier than the other one, as long as our choices are consistent, so that we will be able to arrive at a total ordering that respects the local ticks. There are indeed many different ways to decide that can lead to many different total orderings.

What does it mean by "choice being consistent"? Here is a simple example. Suppose we have three global timestamps, (1,5), (1,2), (1,4). It is consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,5) $\prec$ (1,4). However, it is not consistent if we decide (1,5) $\prec$ (1,2), (1,2) $\prec$ (1,4), (1,4) $\prec$ (1,5). Intuitively, if (1,5) precedes (1,2) and (1,2) precedes (1,4), then (1,5) must precedes (1,4). That is, the transitivity of $\prec$ must be respected; otherwise, $\prec$ is not a partial ordering any more. The transitivity of temporal
ordering of events is the essence of time.

Among many schemes to decide which global timestamp is earlier in a pair of two global timestamps with the same local timestamp, the easiest and most natural one is the one specified in the paper. That is, $(T_i,i) \prec (T_j,j)$ where $T_i=T_j$ and $i<j$. Since we have assumed that the second coordinate, the process number is globally unique, this scheme is complete in the sense that all those kind of pairs are ordered and this scheme is apparently consistent. Moreover, whenever the process numbers do have any inkling to the actual order of physical time as what happens in many situations, smaller process number usually indicates earlier in physical time. So, after all, that decision in the paper makes a lot of sense.


Densely connected non overlapping subgraph I'm trying to detect quasi cliques in an undirected graph. My problem is that I don't want any overlap between cluster.

I'm currently trying to detect community using Louvain algorithm, but it detects subgraphs with a low clustering coefficient (0.60) and when I detect maximal or quasi cliques they tend to overlap.

How can I compute a clique decomposition of an undirected graph with no overlap between clusters ?
Is there an algorithm with an implementation of it which can deal with my problem ?

Thanks

If you want to find cliques, or quasi-cliques, don't expect non-overlapping communities, as their definitions imply that there might be overlap between clusters.
When it comes to community detection or clustering, you need to make a formal definition of a community or cluster (in this case it is a clique). There are two types of definitions:

Non-overlapping definitions - There are some definitions that do not allow any overlap between communities such as $k$-cores. Basically, the following properties prevent $k$-cores of being overlapping:

$k$-cores are maximal
Union of two $k$-cores is a $k$-core.

There are lots of different techniques such as modularity optimization, seed expansion, etc. If you are looking for stricter non-overlapping community definitions, you can dig further in this paper (and the sequence of other papers) and find the one ghat works well on coefficient clustering score:

Fortunato, Santo. "Community detection in graphs." Physics reports 486.3 (2010): 75-174.

Overlapping definitions - However, some definitions such as cliques or quasi-cliques, allow overlap between clusters, even though you consider maximality. Below, I show a simple example where few maximal cliques overlap with each other (link for image).


Verifier for A_tm in polynomial time - how to formally prove it does not exist? How would you formally prove the non-existance of a polynomial time verifier for $A_\mathrm{TM}$?

I mean we can't just say that in order to read a certain certificate we need more than poly-time because we need to prove it for any possible certificate. What would be the correct proof ?

Suppose by contradiction $A_\mathrm{TM}$ has polytime verifier $\Longrightarrow$ $A_\mathrm{TM}$ is in NP $\Longrightarrow$ $A_\mathrm{TM}$ is decideable by some non-deterministic TM in polytime $\Longrightarrow$ $A_\mathrm{TM}$ is dcidiable by some deterministic $2^{\mathrm{polytime}}$ TM $\Longrightarrow$ $A_\mathrm{TM}$ is decidable $\Longrightarrow$ contradiction.


Understanding how quicksort operates I am having a hard time understanding the quick sort partition operation.
I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand how the two subarrays (q-1, q+1) are constructed.
I have looked at various other SE articles, such as:

How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
Randomized Selection

I understand the notion of:

 1. Select a pivot (typically the last item in the array, at least in simplified methods)
 2. Create one subarray to the left of items smaller than the pivot
 3. Create one subarray to the right of items larger than the pivot
 4. Recursively call partition on each of the subarrays

However, in the following example, is where I get lost

8 1 9 3 5 7 6

Here, 6 is my pivot

7 is larger than 6, so my array now looks like:

8 1 9 3 5 6 7

Here is where I get lost. Does the rest of my sequencing look like:

8 1 3 5 6 9 7
1 3 5 6 8 9 7

Where:
1 3 5 is my smaller array and
8 9 7 is my larger array (where each then get partition recursively called?)

I am most confused by the proper construction of the larger and smaller arrays and in which order to put the numbers in. Any help is appreciated. I am happy to edit my post for clarity if I am unclear.

EDIT:
I tried using some base code from this address, and edited it slightly to create more print statements, but still don't understand why it would sort to:
1 3 5 6 9 7 8 and not 1 3 5 6 8 9 7 initially

Here is the code:

class QuickSort
{
    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    void sort(int arr[], int low, int high)
    {

        printArray(arr);

        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    // Driver program
    public static void main(String args[])
    {
        int arr[] = {8, 1, 9, 3, 5, 7, 6};
        int n = arr.length;

        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n-1);

        System.out.println("sorted array");
        printArray(arr);
    }
}
/*This code is contributed by Rajat Mishra */

Please run your code with four more lines of printing statements, as shown below. Once you have seen the output, it will be immediate for you see what is happening. Basically, given the sequence 8 1 9 3 5 7 6, the partition routine rearranges it to 1 3 5 8 9 7 6 at first. Then it exchanges 6 with 8, the first element beyond the end of elements not larger than 6. So the sequence becomes 1 3 5 6 9 7 8.

System.out.print("Pivot with " + pivot + ": ");  // add this line
printArray(arr);  // add this line

    // swap arr[i+1] and arr[high] (or pivot)
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

System.out.print("Exchange   " + pivot + ": ");  // add this line
printArray(arr);  // add this line

Aside from the question proper, what you needed most is an Integrated Development Environment (IDE) where you can trace code execution and check the values of all relevant variables step by step easily. Using the command line can only serve as a temporary measure. I recommend Intellij Community Edition; others might have different recommendations. Once you are able to use that machinery, you will be able to answer others' questions such as this one just like I have answered your question. Well, as long as you will program in java, an IDE is a must unless you do not mind lagging behind other by a factor of 2 to 10. Just a bit of unsolicited advice that I offer to everyone of my local students. It is entirely up to you what to do, of course.


Connecting an unconnected forest of subtrees in a graph? If I have a weighted graph $G=(V,E)$ and three subgraphs $T_1$, $T_2$ and $T_3$ in $G$ which are trees and all unconnected from each other.

What is the best way to connect these three trees such that the resultant connected tree is of minimal cost?

If it helps, I have already used the floyd-warshall algorithm to calculate the total distance matrix of $G$.

I was thinking of just iterating over all pairs of vertices $(T_1,T_2)$, $(T_1,T_3)$ and $(T_2,T_3)$ in the distance matrix and find two values from two of those groups that sum to the least. But that feels like it would be very inefficient.

essentially iterating over every vertex almost twice to get the distance values, and then iterating over those values twice again to find the smallest sum. Ending up with a complexity of like $\mathcal{O}(V^3)$ or $\mathcal{O}(V^4)$ or something (forgive me, its been a few years since i did any complexity theory)

Is there a simpler, more efficient solution that I am missing?

EDIT:
I have previously worked out a solution (not necessarily very efficient), to the problem if there are only two trees. Using the distance matrix, I iterate over every pair of vertices in $T_1$ and $T_2$, and then use dijkstra's algorithm to find the shortest path that joins the pair of vertices with the lowest value in the distance matrix.

Am I on the right track at least for the instance where there are only 2 trees? This method seems to get a lot trickier and much less efficient when there are more than 2 trees.

CLARIFICATION:
There seems to have been a bit of confusion (in a subsequently deleted comment) about what I am asking, so I will be more explicit.

The subgraphs $T_1$, $T_2$ and $T_3$ are trees in $G$, but are not connected to eachother.

here is an example:

I am trying to work out a good method of connecting all three trees such that it results in the smallest total cost

From the example I have given, it is pretty trivial to connect $T_2$ and $T_3$, just find an MST over the union of their two vertex sets because they share a single edge. However my problem stems from trying to connect $T_1$ to the rest; there are a lot of ways in which I can draw a path from $T_1$ to the other two, but I want to find the shortest one.

The only way I have thought of so far is to iterate over all the vertices in $T_1$ and see which one is closest to the vertices in $T_2$ and $T_3$ and then use dijkstra to find the shortest path. But this becomes pretty inefficient with very large scale graphs.

So I am looking for a more efficient method of doing this.

I hope that is more clear.

UPDATE:
In response to @D.W.'s answer to my related question here on solving a simplified version of this problem with only two vertex sets.

In order to extend that solution to this, more complicated, instance of the problem with three distinct vertex sets. Do I just need to create 3 dummy vertices $\{t_1,t_2,t_3\}$in $G$ with edge lengths 0 that link to $T_1$, $T_2$ and $T_3$ respectively, and then run dijkstra 3 times: $t_1 \rightarrow t_2$, $t_1 \rightarrow t_3$ and $t_2 \rightarrow t_3$, to find the minimum path $p_1$ that joins two of the three vertex sets; then if, say, the shortest path lay between $t_2$ and $t_3$ then run dijkstra again to find the shortest path $t_1 \rightarrow t_4$ where $t_4$ is a dummy vertex with 0 edge cost linking to the set $\{T_2 \cup T_3 \cup p_1\}$?

Or is that making things too complicated?

Your problem is known as the group Steiner tree problem, and it is NP-hard. More specifically, in this problem we are given a weighted graph $G=(V,E)$, and $k$ (vertex-disjoint) sets $S_1,S_2,\ldots,S_k \subseteq V$, and asked to find the minimum cost tree that uses at least one vertex from each $S_i$, where $i \in [k]$.

But don't fall into despair yet. Luckily for you, you have a very small number of "terminal trees", specifically three. The good news is that the problem is solvable in polynomial-time for fixed $k$. Moreover, it can be solved in something called FPT time, in fact there is an algorithm solving it running in $2^k n^{O(1)}$ time. When $k = 3$ is fixed, this is polynomial time. Let me shortly describe the idea, or at least give the pointers for a possible algorithm.

Misra et al. [1] observe that group Steiner tree reduces to the so-called directed Steiner out-tree problem. This, in turn, is solvable in a certain time bound using the idea of branching walks (of Nederlof) and inclusion-exclusion. The added nice thing is that the algorithm (as usual with such an inclusion-exclusion approach) needs only polynomial space. Moreover, there is evidence such algorithms are practical too. The Misra et al. [1] paper gives the necessary references.

[1] Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2012). FPT algorithms for connected feedback vertex set. Journal of combinatorial optimization, 24(2), 131-146.


DCFL substitution closure Deterministic context-free languages are not in general closed under substitution. I have been looking at the DK-test (it is described in the 3rd edition of Sipser's Intro. to Theory of Computation, 2012) which can be used to check if a given CFG is deterministic, and it seems to me this can be used to show that DCFLs are closed under substitution when the substituted languages are disjoint DCFLs. Is this a known result? Or is anything known about the substitution closure of DCFLs with other restrictions on the substituted languages?

Since $ab$ is a DCFL, your result would imply that DCFLs are closed under concatenation, which they aren't. So your result can't hold.


How exactly do we define parametric polymorphism? My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:

In parametric polymorphism, the type is given as a variable: (pseudocode)
Function f: <.Type T> T $\to$ T {...}

Whereas in ad-hoc polymorphism, we write different functions for each type:

Function f: Int $\to$ Int {...}
Function f: Bool $\to$ Bool {...}

But by that definition, we can always “pretend” to do parametric polymorphism:

Function f: <.Type T> T $\to$ T { if T == Int then {...}; If T == Bool then {...} }

How exactly do we define, from a type theory standpoint, parametric polymorphism, so that this is not allowed? Do we simply say that the term T is not allowed to be used in the body of $f$?
The reason I’m asking is: I am reading about the fact that parametric polymorphism allows certain nice guarantees that ad-hoc polymorphism doesn’t.

An informal, but better way of explaining parametric polymorphism is that the term has a uniform definiton/semantics for all types. A simple example is the identity function:

$$λ x. x$$

This is one term that can be reasonably given the type $ℕ → ℕ$, $\mathsf{Bool} → \mathsf{Bool}$, etc. Therefore, we also consider it reasonable for it to give it the type $∀a. a → a$, because it is a single term that works for every type.

If you want to talk about terms where types are explicitly talked about, then this becomes somewhat less clear. However, an informal idea of what must be going on in those definitions is that the type variables are completely unknown to the definition. So in:

$$Λa. λ(x : a). x$$

even though we get syntactically different terms for each choice of $a$, the definition didn't specify what happens for particular choices of $a$, or something of that sort.

The more formal/precise way of explaining all of this is usually relational parametricity. That's kind of complicated to get into, but it says that there are ways of interpreting our definitions into relations in addition to the normal semantics. In this explanation, parametric polymorphism is about preserving relatedness. So, if you instantiate a polymorphic value to related types, the values you get are related in a coherent way. And the reason why relations are used is that they give a precise (but general) way of talking about what it means for things to be 'uniform' like above.


Examples of languages not decidable by a TM using certain upper bounds on space/time I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain classes of time / space hierarchies. For example, what are some examples of a decidable language that can't be decided by a TM using space O(log n) and time less than n, on inputs of length n?

Might the Travelling Salesman Problem be an example to the above question, since I think the brute-force algorithm for TSP would take space O(n) (store the current shortest path, and compare it with each new path that's being explored)?

Look up the time hierarchy and space hierarchy theorems. They give examples of languages which can be computed using $f(n)$ time (or space), and require more or less $f(n)$ time (or space). These languages are basically the following:

  Descriptions of Turing machines that halt after time $f(n)$ (after using space $f(n)$).

Perhaps you won't consider these languages natural. Unfortunately, the best lower bounds known for natural languages are currently only $\Omega(n)$ (for time) and probably even worse for space. However, it is conjectured that NP-hard problems require exponential time (this is known as the Exponential Time Hypothesis).


Reduction as a flowchart I'm trying to understand the reduction as a flowchart graph.

Let's say the boxes $A$ and $B$ are TMs/Functions and $x$ is the input.
Is this plot represent reduction from $A$ to $B$ ($A\le B$) or from $B$ to $A$ ($B\le A$)?
Or maybe it can be both of the way depending on the context?

The arrow is going from $A$ to $B$. It means you are solving problem $A$ using problem $B$. So, it is a reduction from $A$ to $B$


Domain Theory and Polymorphism Domain theory gives an amazing theory of computability in the presence of simple types. But when parametric polymorphism is added there doesn't seem to be a nice theory that explains whats going on quite as nicely as domain theory explains computation over simple types. Certainly I wouldn't expect such a thing to exist for System-F because no set theoretic models of System-F exist. What about a restriction of System-F that has predictive and has a universe hierarchy? Has this been studied? Is there a nice domain theory that applies to it? Going further what about dependent types? Can domain theory somehow be mixed with weak $\omega$-groupoids to accomplish something?

There are many ways to model polymorphism via domain theory, let me just describe one that is easy to understand, so you can think about it yourself. It's a "PER model".

Take any model of the untyped $\lambda$-calculus, for instance a domain $D$ such that $D \to D$ is a retract of $D$ (for instance, take $D$ such that $D \cong \mathbb{N}_\bot \times (D \to D))$. Let $\Lambda : D \to (D \to D)$ and $\Gamma : (D \to D) \to D$ be the retraction and the section, respectively.

We are going to interpret the types as partial equivalence relations (PER) on $D$. Recall that a PER is a relation which is symmetric and transitive, but it need not be reflexive. To each type $\tau$ we thus assign a PER $\sim_\tau$. Think of $x \sim_\tau x$ as "$x$ is an element of $\tau$" and $x \sim_\tau y$ as "$x$ and $y$ are equal as far as $\tau$ is concerned".

We can have some basic types (but need not), for instance if we make sure that $\mathbb{N}_\bot$ is a subdomain of $D$ via an embedding $\iota : \mathbb{N} \to D$ then we may define $\sim_\mathtt{nat}$ by
$$x \sim_\mathtt{nat} y \iff \exists n \in \mathbb{N} . x = \iota(n) = y.$$

Given PERs $\sim_\tau$ and $\sim_\sigma$, define the function space PER $\sim_{\tau \to \sigma}$ by
$$x \sim_{\tau \to \sigma} y \iff
  \forall z, w \in D . z \sim_\tau w \Rightarrow \Lambda(x)(z) \sim_\sigma \Lambda(y)(w)$$

The terms are interpreted as untyped $\lambda$-calculus terms as one would normally interpret them in $D$.

Here's the punchline. You may interpret polymorphism as intersection of PERs, that is:
$$x \sim_{\forall X. \tau(X)} y \iff
  \text{for all PERs $\approx$, $x \sim_{\tau(\approx)} y$}.
$$
We can caclulate the PER corresponding to $\forall X. X$: it is the intersection of all PERs, but that is going to be the empty PER. Calculating $\forall X . X \to X$ is an interesting exercise. Calculating $\forall X . X \to X \to X$ is a difficult exercise (which kept me busy for a week when I was a student of domain theory).

If we want recursion in our language then we need to account for fixed points. One possibility is to restrict PERs to those which contain $\bot_D$ and are closed under suprema of increasing chains. More precisely, take only those PERs $\approx$ for which

$\bot_D \approx \bot_D$, and
if $x_0 \leq x_1 \leq x_2 \leq \cdots$ and $y_0 \leq y_1 \leq y_2 \leq \cdots$ are increasing chains in $D$ such that $x_i \approx y_i$ for all $i$, then $\sup_i x_i \approx \sup_i y_i$.

We can now interpret $\mathtt{fix}_{\tau} : (\tau \to \tau) \to \tau$ by applying the Kanster-Tarski theorem about existence of fixed points, just like we do in ordinary domain theory. This time, $\forall X . X$ is not empty, as it contains precisely $\bot_D$.


Sampling a uniform distribution of fixed size strings containing no forbidden substrings Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word?

For short output strings with few forbidden words, I would use simple rejection sampling. Pick a string (uniformly) with the specified alphabet and length, return that string if it contains no element of the forbidden list, try again otherwise.

If I use that algorithm for output lengths several times larger than the typical forbidden word, then the probability of rejection will be higher. (Most words are 2 or 3 characters long.)

Assume the requested output length is too long to enumerate and store every possible value. My alphabet size would be 16 to 36 characters, but solutions to large alphabets would be interesting to  think about. (In which case I would call these things random sentences, forbidden n-grams, and dictionary words.)

My forbidden word list will have one hundred to one thousand strings. I would like to avoid solutions requiring expensive precomputation or lots of memory.

My first idea was to try to build a random string incrementally, in contrast to the all-or-nothing approach of straightforward rejection sampling. I doubt that my algorithm produces each possible output with equal probability.

The algorithm idea follows:

Initialize a char buffer long enough to fit outlen characters.
Pick a random letter of the alphabet and append it to the buffer.
If the buffer ends with a forbidden word of length k, then remove the  last k letters from the char buffer and go to 2.
Otherwise, go to 2 if the buffer has less than outlen characters.
Return the contents of the buffer if it is full.

Step 3 serves to rewind the algorithm, returning the char buffer to a previous legal state.

I understand that clearing the whole buffer in step 3 definitely would produce uniform output just like the straightforward rejection sampling method. However, the average number of rejections before the first valid output is generated will be the same.

I've gotten stuck trying to determine if my proposed algorithm is uniform. I have had no luck finding alternative algorithms either. I haven't yet looked at how this algorithm's performance would compare to basic rejection sampling.

Suppose the alphabet is $\{a,b\}$, and you have one forbidden word, $aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over $ab,ba,bb$. Hence the first letter has the following distribution: $a$ with probability $1/3$, $b$ with probability $2/3$. In contrast, the allowable words are
$$
aba,abb,bab,bba,bbb.
$$
So the first letter should have the distribution $a$ with probability $2/5$, $b$ with probability $3/5$.

Here is an algorithm that does work. Construct a DFA (or UFA) for your language. For each state $q$, using dynamic programming you can count how many words of length $m$ are accepted when the automaton is started at $q$. Let us denote this by $c(q,m)$.

The correct distribution of the first letter $\sigma_1$ of a word of length $n$ in the language is
$$
\Pr[\sigma_1 = \sigma] = \frac{c(\delta(q_0,\sigma),n-1)}{c(q_0,n)}.
$$
More generally, given the first $\ell$ letters $\sigma_1 \ldots \sigma_\ell$, the following letter has the distribution
$$
\Pr[\sigma_{\ell+1} = \sigma \mid \sigma_1 \ldots \sigma_\ell] = \frac{c(\delta(q_0,\sigma_1\ldots\sigma_\ell\sigma),n-\ell-1)}{c(\delta(q_0,\sigma_1\ldots\sigma_\ell),n-\ell)}.
$$
Ignoring the cost of arithmetic, you can implement this scheme in roughly $O(|Q|n)$, where $Q$ is the set of states, or in $O(|\Sigma|n^2)$. (The former, assuming that $|Q| = \Omega(|\Sigma|)$.)

As an example, let us consider the counterexample above. We construct a DFA containing two states (we can omit the sink state, obtaining a UFA) $q_0,q_1$. The transition function is $\delta(q_0,a) = q_1$, $\delta(q_0,b) = q_0$, $\delta(q_1,b) = q_0$. The relevant values of $c$ are
$$
\begin{array}{c|cc}
n & c(q_0,n) & c(q_1,n) \\\hline
0 & 1 & 1 \\
1 & 2 & 1 \\
2 & 3 & 2 \\
3 & 5 & 3
\end{array}
$$
These are computed by the recurrences $c(q_0,n) = c(q_0,n-1) + c(q_1,n-1)$ and $c(q_1,n) = c(q_0,n-1)$, with base case $c(q,0) = 1$.

Since $\delta(q_0,a) = q_1$ and $\delta(q_0,b) = q_0$, we see that (for $n = 3$) $\Pr[\sigma_1 = a] = c(q_1,2)/c(q_0,3) = 2/5$ and $\Pr[\sigma_1 = b] = c(q_0,2)/c(q_0,3) = 3/5$.


DFA with limited states Lets $L_z \ := \{ a^i b^i c^i : 0 \leq i < z \}$

$\{a,b,c\} \in \sum^*$

there is a DFA with $\frac{z(z+1)}{2}+1$ states - How can I prove this?

And I need largest possible number $n_z$, for which i can prove that every NFA, which accepts $L_z$, have $n_z$ states, at least!

But first I need to show that $n_z = \frac{z(z+1)}{2}$
 right?

Constructing a DFA

There is an algorithm to construct a minimal DFA for a regular language. In this case, it isn't too hard to come up with a DFA with $z(z+1)/2$ states.

Observe that $L_z = \{\epsilon, abc, aabbcc, \ldots, a^{z-1}b^{z-1}c^{z-1}\}$. Once you know the number of $a$'s at the beginning of the word, you know how many $b$'s and $c$'s to expect. Here's a simple DFA built from this observation (with $z' = z-1$):

[source]

Following the usual convention, if there is no transition for a particular letter from a particular node, the automaton goes to a sink state.

This automaton has $n$ states reached after reading $0$ to $z-1$ letters a ($k,0,0$ for $0\le k\le z-1$), and branches of length $2k$ for $0 \le k \le z-1$ to read the right number of b's and c's ($k,i,0$ and $k,k,i$ for $1 \le i \le k \le z-1$). That's a total of $z + \sum_{k=0}^{z-1} (2k) = z^2$ states, plus one to account for the implicit sink state.

It's possible to compress this automaton a bit.

   Notice that every side branch finishes by counting the c's. Instead of tracking how many c's have already been seen, think in terms of how many c's are left to read. You can merge all the states of the form $k,k,k-n$, for all $k \ge 1$, into a state $-,n$ from which $n$ occurrences of c must be read. In particular, there will be only two final states: one for the empty word, and one after reading the right number of c's. In this automaton, the $k$th side branch has $k$ edges to read the b's (so $k-1$ states, as the start state belongs to the a trunk, and the end state belongs to the c collector), and there are $z-1$ transitions to count the c's (so $z$ states, corresponding to $0$ through $z-1$ c's left).

The total number of states in this automaton (including the sink state) is $z + \sum_{k=1}^{z-1} (k-1) + (z-1) + 1 = z(z+1)/2 + 1$.

Constructing an NFA

In other words, $n_z$ is the number of states in a minimal NFA that recognizes $L_z$. If you have a DFA with $N$ states, that's an NFA with $N$ states. So $n_z \le z(z+1)/2+1$. For most languages, a minimal NFA is smaller than a minimal DFA: nondeterminism adds expressive power in terms of how much you can accomplish with a number of states.

In this particular case, it happens that the minimal DFA above is also a minimal NFA (if I didn't make a mistake). Here's an informal proof.

   Consider the states in the middle of reading the b's. When reading $a^k b^i | b^{k-i} c^k$, where $|$ represents the current position, the state must account for both $k$ and $i$, to remember both the number of seen a's (which is necessary, because we'll need to count the c's later) and the number of seen b's (or, equivalently, the number of b's still required). This requires distinct states for every $(i,k)$ such that $1 \le i \lt k \le z-1$. In addition, there must be $z-1$ states to count the a's at the beginning, and $z-1$ states to count the c's at the beginning, plus a sink state. That's a total of $z(z+1)/2+1$ states.


"Greater than AND smaller than" condition in integer linear program with a binary variable I found this related question, but that's not quite it

Is it possible to model this with integer programming:

$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$, $B, D \in \mathbb R$ and $C \in \mathbb N$. We have upper and lower bounds on $B$, $C$ and $D$.

Thanks MrHug, I should have thought of this myself after your first hint.

after using the solution from here twice with the resulting binaries $A_1$ and $A_2$ we can form another problem:
$$A = \begin{cases} 1 & \text{if } A_1+A_2 \geq 2 \\ 0 & \text{otherwise}\end{cases}$$

This one can be solved with a little hint from there:

$$A_1 + A_2 \geq 2 - M * (1-A) \\
2 - \epsilon \geq A_1 + A_2 - M * A$$

where $M$ is a big value and $\epsilon$ is a very small value (above 0, below 1).

It's a bit unfortunate that so many variables are needed as $A$, $A_1$ and $A_2$ are cubic in my case. But I'm glad about this solution.


Language where every prefix has almost equal a's and b's Is the following language regular?

$$L = \{x \in \{a, b\}^* \mid \text{in every prefix \(w\) of \(x\), } 0 \le |w|_a − |w|_b \le 2\}$$
If so, give a DFA for it with as few states as possible. If you claim that it is
not regular give a pumping lemma proof that it is not regular.

I'm doing exam prep and have tried pumping this to no avail. I think I created a DFA that works but I'm not entirely sure because pumping similar examples (i.e. if the number of a's is strictly greater than b's) yielded results that are not regular. Is my DFA correct? Or is there something I can pump that will fail the lemma?

Hint: as you read each letter of the input, imagine trying to keep track of the difference between the number of $a$'s and the number of $b$'s.  What is the set of possible values that this could possibly take on, if the input is in $L$?  What's the largest this difference could be?  What's the smallest it could be?


Inductive sequence of words in a biprefix code Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) < m(X_2)$, i.e. the maximal length of the first is strictly lower than the second. Now, if $v \in X_2$ we define a sequence such that $v_0 = v$ and $v_{i+1} = 1$ if $v_i \notin X_1A^*$ and $v_{i+1} = y_ix_i$ if instead $v_i \in X_1A^*$, with $v_i = x_iy_i$ with $x_i \in X_1, y_i \in A^*$.
Now, let $u,v \in X_2$ and suppose there exist two integers $i \leq j$ such that $u_{i} = v_j$. Since $X_1$ is biprefix, this implies that $u_{i-1} = v_{j-1}$. Why does this imply that $u_0 = v_{j-1}$? The paper I am reading motivates this last deduction by induction, but I can’t see how $j-1$ could stay fixed in the process. Any hints?

Your paper has a typo. It should be $u_0 = v_{j-i}$ rather than $u_0 = v_{j-1}$.
Indeed, consider the following example: the alphabet is $A = \{0,1\}$, and the two codes are $X_1 = A^1$ and $X_2 = A^2$. Take $u = 01$ and $v = 10$. Then $u_0 = 01$, $v_0 = 10$, and $v_1 = 01$. If $i = 0$ and $j = 1$ then $u_i = v_j$, yet $u_0 \neq v_{j-1}$; but $u_0 = v_{j-i}$.
You already know that $u_i = v_j$ implies $u_{i-1} = v_{j-1}$. Applying this step $i$ times, you immediately conclude that $u_0 = v_{j-i}$.


Edit Distance Algorithm (variant of longest common sub-sequence) I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming.

The problem is defined as follows:

suppose that you are making a spell-checker with suggestions for misspelled words.  You would like to be able to find the words that are closest to the string of non-word letters that a user has input.

These words can differ from the typed string by

missing a letter
having an extra letter
having a letter replaced with another letter

the costs are:

$c_i$, the cost of an insert

$c_d$, the cost of a deletion

$c_r$, the cost of a replacement

with the intention of beginning with a recursive approach that can be converted into a dynamic program, the idea is to build up from substrings.

let T(j,k) denote minimum cost to transform
substring A[1...j] to substring B[1...k].

then there are four ways to convert A[1...j]
into B[1...k]

1. delete the jth character of A[1...j] and
convert the first j-1 characters of A into the
first k characters of B.  This equals cost cd +
T(j-1, k)

2. convert the first j characters of A into the
first k-1 characters of B, and insert a kth
character into B[1...k-1].  This equals cost ci
+ T(j, k-1)

3. replace the jth character of A with the kth
character of B and convert the first j-1
characters of A into the first k-1 characters
of B.  This equals cost cr + T(j-1,k-1)

4. If characters A[j] = B[k], just convert
A[1..(j-1)] into B[1..(k-1)]
This has cost T(j-1,k-1)

This can be written as a recursion equation,
taking the minimum over all four alternatives
at each step:

T(j,k) = minimum of:
    {    T(j-1, k) + cd
         T(j,k-1) + ci
        T(j-1,k-1) if A[j] = B[k]
      T(j-1, k-1) + cr if A[j] != B[k]
    }

The question is this: suppose we're to add a "swap" function which corrects two letter which are typed in the wrong order.  How would we modify the euation for the cost of changing string A into string B if the the cost of a swap is $C_s$?

My thought is:

T(j-1, k+1) if A[j,k] = B[k,j] ?

the additional cost of adding a swap function should be:

T(j-2,k-2) + Cs  , if A[j-1]=B[k],and A[j]=B[k-1]

I found the answer by studying the Damerau–Levenshtein distance modification of the classic edit distance problem.

Source: https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance


What do you call a "non-probabilistic Bloom Filter"? One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.

It is a technique for caching easy answers for a subset of an input domain before falling back to an expensive computation. In that respect it reminds me of the semantics of a Bloom Filter or the pre-optimization idea of a Karnaugh Map.

Simple description w/ pseudocode:

// Determine whether "foo" is true with respect to the given ComplexThingy,
//   for the inputs bar and baz

boolean isFoo(ComplexThingy t, A a, B b):
    // Let's say A and B are enums, or ints in a limited range, etc.
    return expensive_computation(t, a, b)

// Alternative implementation w/ enhanced ComplexThingy for which
//   "trivial" cases (i.e. those that can ignore all but one dimension of the
//   input space) have been precomputed and stored in a simple bit array

boolean isFoo(ComplexThingyV2 t, A a, B b):
    if t.quickPosLookup[a]
        return true
    if t.quickNegLookup[b]
        return false
    return expensive_computation(t, a, b)

Hopefully I've been able to convey that clearly. Thanks for your time!

This is related to the notion of "fast path, slow path" from computer systems.  In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first test whether the input falls into that case and if so solve it and return immediately; otherwise, fall back to the complex computation.  For instance, the slow path might have to handle corner cases and difficult situations that arise only rarely.


Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular? Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$
is also regular?

I have a 'feeling' that it is, but I can't sketch a proof for it.

Yes, the language is regular:
Consider a DFA A such that $L(A)=L$
Now, assume that you know, somehow, that when given a word $w$, the run of $A$ will end up in state $q$.

All you need to check now is that there is a run of $A$ on some word of length $|w|$ that gets from $q$ to an accepting state. This can be done by using the product automaton $A\times A$, where the first component acts exactly like $A$, and the second acts like $A$, but starts from state $q$ and ignores the input - that is, for each letter it nondeterministically goes anywhere that $A$ can go. Then, a run is accepting if the first component ends up in $q$, and the second component ends in an accepting state.

Finally, you can drop the assumption by taking $|Q|$ copies of this construction, where each copy "guesses" in which state $A$ will end up in. You end up with a nondeterministic construction of size $|Q|^3$


Why does the converse of the clock condition imply that any two concurrent events occur at the same time? In Lamport's paper, Time, Clocks, and the ordering of Events in a Distributed System he says that the converse of the clock condition does not hold and if it did, we could expect concurrent events to occur at the same time. I am not sure how he arrives at this conclusion.
The Clock Condition is:
For any events a, b in a distributed system:
if a -> b then C(a) < C(b).
The converse does not hold:
if C(a) < C(b) then a -> b.
Where C(n) assigns a logical clock number to any event in the system. Logical clock numbers monotonically increasing values for each process in the system and two conditions hold in order for partial orderings given that the clock condition is true:

if a and b are both events in a process P_i and a comes before b, then C_i(a) < C_i(b)

if a is a sending event in P_i and b is a receiving event in P_j then C_i(a) < C_j(b).

Intuitively I can see why the converse does not hold. It is possible in the system of logical clocks that C(a) < C(b) when we do not have a partial ordering that guarantees the relation a -> b. But I have no clue why the converse being true would imply that any two concurrent events occur at the same time.

Assume the clock condition AND its converse: $$C(a)\lt C(b) \Rightarrow a \rightarrow b \tag{*}\label{*}$$
Next, take note that $\neg(a \rightarrow b)$ implies either $b \rightarrow a$ or $a \nrightarrow b$ (i.e. if '$a$ does NOT happen before $b$' then either '$b$ happens before $a$' or they are concurrent events).
Now, since the implication $\eqref{*}$ is (assumed) true, its contrapositive must also be true:
$$\neg(a \rightarrow b) \Rightarrow C(a)\geq C(b)$$
Applying our negation rule, we find either $b \rightarrow a \Rightarrow C(a)\geq C(b)$ (which reduces to the clock condition) or $$a \nrightarrow b \Rightarrow C(a)\geq C(b)$$
Lamport is only interested in the latter case: "...we cannot expect the converse condition to
hold as well, since that would imply that any two $\mathbf{concurrent}$ events must occur at the same time."
To show this, remember Lamport said when $a,b$ are concurrent then both $a \nrightarrow b$ and $b \nrightarrow a$ so $$b \nrightarrow a \Rightarrow C(b)\geq C(a)$$
The last two equations imply if $a$ and $b$ are concurrent, $C(a)=C(b)$.
To derive the contradiction, take any two events $a, b$ concurrent but on separate processes. Then their clock numbers must be the same. Now if there is another concurrent event before or after $a$ (on the same process), then it too must have the same clock number as $b$ and therefore $a$. But that contradicts the clock condition (e.g. see condition C1 in the paper).


What's the difference between Clock and Second Chance Page-Replacement Algorithm? I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm.

could anyone help me understand?

Clock is second chance.  Given the same input they will both produce the same replacements at the same points in time.  The only difference is the details of implementation.  Second chance is usually described in terms of a "fifo" which is assumed to be a linked list where there is a pointer to the head and tail and every node contains a pointer to next.  Then when you remove a page from the head of the fifo you do it by setting head = head->next.  When you insert a page on the tail of the fifo you do it by setting tail->next = new_node, tail = new_node, new_node->next = NULL.

Clock is just a simpler (and slightly faster) implementation of a fifo where you keep a circular linked list.  tail->next points to what was the head in our old structure.  We only need one pointer, the pointer to tail.  Now removing a node from head is simply tail->next=tail->next->next and inserting a node on the tail is new_node->next = tail->next, tail->next = new_node, tail = new_node.  This is all about the same as the non-circular version.  The efficiency comes when you need to move a node from the head to the tail.  That's just tail = tail->next with the circular list.

Two-handed clock

By adding a second clock hand to the clock algorithm you get an extremely low-cost approximation of not-recently-used (which is an approximation of least-recently-used.)

In the two-handed clock algorithm you have two clock hands.  One of the hands is just like before, it points at the next page being considered for replacement.  When a replacement is required we just keep moving this clock hand (clearing reference bits) until we find a page with the reference bit cleared, and that's the page that gets replaced.  (So this clock hand is just doing the clock implementation of second chance.)

The second clock hand is another pointer into the circularly linked list.  The purpose of the second hand is to clear reference bits.  Every once in a while you clear the reference bit on the linked-list node that the second hand is pointing to, and set second_hand = second_hand->next.  This eliminates one of the problems with second chance, which is that when a page is only used a small amount right after it is first fetched then second-chance will require two cycles through the fifo before that page gets replaced.  In the two-handed clock algorithm those "short-term usage" pages get replaced after just one cycle through the fifo.

Another replacement algorithm you might look at is WSClock of Carr and Hennessy.  It is a combination of the two-handed clock with a bunch of heuristics that are helpful in practice.


Example of decidable set whose preimage is not decidable I know that if a set is a decidable, there exists an algorithm that enumerates it and prints value 1 if a given element belongs to the set and 0 otherwise. Therefore, its image is decidable, too. I think, though, that this is not true for the preimage of of the set under a partially computable function. Can someone provide an example that might help me to understand it, please?

Consider the set $S$ consisting of everything, and the partially computable function $f$ which on input $n$ simulates the $n$th Turing machine, returning whatever the machine outputs (if it ever halts!). The preimage of $S$ under $f$ is the set of all halting Turing machines, which isn't decidable.


Specific case of a ranking model So the problem I'm solving is this: I have a list of conversations of 3 messages each (for eg. "hi", " how are you", "remind me to fix this bug" is one conversation, and my problem will have many of these) and need to pick out the message that is most likely to be a task ("remind me to fix this bug" would be the message in the conversation above; "don't forget to commit your code" would be another in some other conversation). What kind of machine learning/NLP model could I use to relatively rank the messages in a conversation and "learn" across conversations? And what would my training data look like?

My thoughts: each data point in the training data is one conversation (a set of 3 messages) along with the message with the highest likelihood of being a "task." I was thinking of using a linear weighted function of features such as TF-IDF score. But how would I learn the weights?

Build a boolean classifier that classifies a message as either "task" or "not a task".  Choose a classifier that can output a confidence score (many classifiers can, including ensembles like random forests; neural networks and deep learning; logistic regression; and more).

Train the classifier on many messages.

For a collection of 3 messages, apply the classifier to each message and get the confidence score.  Then, use the confidence scores to rank the 3 messages: e.g., choose the message that has the highest confidence/probability of being "task" as the one that is most likely to be the task.

This is different from what you had in mind: here each instance is a message, not a conversation.

Which features to use is a separate question, but you'll probably want to use standard NLP features (bag of words, word2vec, and so on).  That belongs in a separate question.  As a warning, if each message is very short as indicated in your example, the performance of your classifier might not be great.

Also, you will need a large collection of messages where you know the label (classification) of each.


Converting reality to Petri net I'm autistic and I think a bit differently. I have superior memory and visual thinking, but I have a problem with converting real thing to abstract. I'd like to model reality processes with Petri nets. But... when I think of cooking meal or using a coffee vendor machine, I see in my head vegetables, kitchen utensils, cooking books and coffee machines I have seen in my entire life, but no graphs.

I am able to draw for example binary counters, because their graphs look like real things. But I can't see Greek salad as a graph. I need some help. When I see the examples, I should learn it all very quickly, but now I have nothing to start and nobody to ask.

I'm not sure how to approach your particular problem, but here is an attempt.

Consider the recipe you are using as a collection of steps, some of which depend on others; for a salad you might have "make dressing", "shred lettuce", "slice cucumber" etc. The dependencies are given through resources, which here are ingredients, possibly in some processed state, like oil, vinegar, cucumber, sliced cucumber, etc.

To model this process as a Petri net, you use

places to represent the various resources, i.e. you have a "vinegar" place, a "shredded lettuce" place, etc,
tokens on those places to represent the amount of each resource you have; initially this would be something like one token on each unprocessed ingredient,
transitions to model actual steps in the recipe; for example you could have a "make vinaigrette" transition consuming a token from the "oil" and "vinegar" places and producing a token in the "dressing" place.

The amount of detail here depends on what you want to do with the model; you might for example want to keep track of equipment in addition to ingredients (with the "make vinaigrette" transition additionally consuming a clean whisk and producing a used whisk), etc.

Is this the kind of example you had in mind?


Solving inhomogeneous recursion using quadratic particular solution I am interested in solving recursions and while I was trying to solve this one:
$a_n=a_{n-1}+4n-3$

I ran onto a problem, I don't see how to find an explicit solution using standard inhomogeneous method(finding homogeneous and particular solution). Specifically I have a problem with finding particular solution. Problem for me is how to find expression to represent $f(n)=4n-3$. I do know how to solve for $f(n)=n$ with representing $f(n)$ as polynomial $an+b$ and substituting in the recursion. Is there a way to solve this type of recursions when $f(n)$ isn't depending just on $n$. Can we solve for even more complicated expressions such as $f(n)=5n^2+2n+4$ or any polynomial of degree $n$

Given:

$a(n) = a(n-1) + 5n^2 + 2n + 4$

We hypothesise that because the difference is quadratic, $a(n)$ is cubic. In particular:

$a(n) = a_3 n^3 + a_2 n^2 + a_1 n + a_0$

So:

$a_3 n^3 + a_2 n^2 + a_1 n + a_0 = a_3 (n-1)^3 + a_2 (n-1)^2 + a_1 (n-1) + a_0 + 5n^2 + 2n + 4$

$\Rightarrow 3 a_3 n^2 + (-3 a_3 + 2 a_2) n + (a_3 - a_2 + a_1) = 5n^2 + 2n + 4$

This must be true for all $n$. Therefore:

$3 a_3 = 5$

$-3 a_3 + 2 a_2 = 2$

$a_3 - a_2 + a_1 = 4$

Note that $a_0$ doesn't appear in these equations, so this is effectively a linear system, three equations in three unknowns. The unique solution is:

$a_3 = \frac{5}{3}$

$a_2 = \frac{7}{2}$

$a_1 = \frac{35}{6}$

And so:

$a(n) = \frac{5}{3} n^3 + \frac{7}{2} n^2 + \frac{35}{6} n + a_0$

is a solution to the recurrence equation for any $a_0$.


Concatenation of language to itself zero times I was solving this question:

  Which of the following statement(s) is/are false?

  $L^0=\{\epsilon\}$
  $|L^0|=0$

The answer given was None. That is, none of these statements are false and both are true. However, I feel both are wrong. I feel

$L^1=L$  and
$L^0=\phi$

Also

$|L^0|=|\phi|=0$

Am I wrong with this?

$L^0$ is defined to be $\{\varepsilon\}$. (Since a string formed by concatenating zero strings together is the empty string).

This gives the answer to the first question - which is correct.

Now, $\{\varepsilon\}$ contains exactly one string - which is the empty string. Therefore: $|\{\varepsilon\}|=1$. (The given answer is wrong).

Note that $|\{\varepsilon\}|=1\ne0=|\varepsilon|$. Also, note that $\{\varepsilon\} \ne \emptyset$.


Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$ I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky.
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following one, so I have been trying to modify it so that I "force" to have one more $b$, but I don't see how to do this. The obvious choice would be to replace $\epsilon$ with $b$, but that would potentially get two more $b$'s. Is there a trick for this one?
$$\begin{align}
  S &\to \epsilon \\
  S &\to aSbS \\
  S &\to bSaS \enspace.
\end{align}$$

You can simply consider the following grammar: $$ S\to S_1 b S_1$$ where $S_1$ is the start variable of a grammar for the language of words $w$ with $|w|_a = |w|_b$. Correctness is self-explanatory.
So using the grammar you wrote, you get the following grammar:
$$ S\to T b T$$
$$ T \to aTbT| bTaT | \epsilon$$


DFA accepts common strings, reduction to NPcomplete $B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and
all of the $M_i$ accept some common string.} \}$

I'm trying to show that B is NP-complete. I know I have to reduce it to another NP-complete problem, but I'm having a lot of trouble coming up with the algorithm that decides B.

I was thinking I could keep track of all the DFAs accepted by M1 and then check those in M2, any that accept there I'd feed to M3 and so on until I either ran through all the DFAs (accept) or ran out of accepted strings (reject).
I'm not really convinced this runs in NP time though. How exactly do I prove that it does? Or is this a terrible algorithm?

Thank you!

Your problem is actually not NP-complete (unless NP=PSPACE), though it is NP-hard. The problem is that the witness - the string in the intersection - could be very long.

Kozen showed that DFA-intersection is PSPACE-complete, which implies the preceding paragraph. For a very similar proof (of a different statement), see my writeup.


Unknown notation "$e^T$" in a machine learning paper I'm trying to understand the material in "A Dual Coordinate Descent Method for Large-scale Linear SVM" by Hsieh et. al. (link to paper) There is an equation for the Dual form of an unconstrained optimisation problem,

$$
f(\mathbf{\alpha})=\dfrac{1}{2}\mathbf{\alpha}^T\bar{Q}\alpha-e^T\alpha
$$

I don't understand what the $\mathbf{e}^T$ means, it's not explained in the surronding text, so I assume it's just some common notation. Later in the paper $\mathbf{e}_i$ is defined as $\mathbf{e}_i=[0,\ldots,1,0,\ldots,0]^T$, so maybe it's some sort of selector term? Not sure if this second mention is even related.

Please may someone explain to be what the $\mathbf{e}^T$ bit is doing in this formula? Thank you for your time.

The superscript $T$ is the transpose operation. The vector $e$ is probably the constant one vector, though this is not standard notation and so it would be mentioned in the definitions part of the paper. Overall, $e^T\alpha = \langle e,\alpha \rangle = \sum_i \alpha_i$.


Some questions regarding compilers and assemblers Lots of basic questions are there in my mind. I need to clear them.

Statement 1: A compiler converts a human-readable codes to object codes, and those are converted to a machine code (executable) by linker.

Am I right here?

At wikipedia, it is written that

Object files are produced by an assembler, compiler, or other language
translator, and used as input to the linker.

Question 1: An assembler converts assembly language code (MOV A, B ADD C) to machine code. In case of high-level language like C++, that is generated by linker above. So assembler is not used anywhere. So how can it create an object file as written above?

Intermediate code is generated to make the code run on different architectures.

Question 2: Are *.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

Question 3: When we compile a C++ program in Turbo C++, we get *.obj files which are the object files. Can we use them to generate the executable in some other architecture?

I agree with Raphael, don't look too far for a precise meaning of those terms. AFAIK, there is none. (And that rule is also true for terms which have a precise meaning, often the same word in used with a different precise meaning in different contexts).

  A compiler converts a human-readable codes to object codes,

I'd say that compiler is used for translators which lower the abstraction level or do deep restructuring.  The source doesn't have to be human-readable (but often is), it was common for compiler to generate assembler and not object code (gcc still does it even if it call the assembler itself) and compilers generating C are quite common.

  and those are converted to a machine code (executable) by linker.

I don't think making a difference between machine code and object code is common (and I'm not even sure which difference you are making). That makes your question 1 irrelevant. Traditionally, the linker doesn't convert, it takes several object files and resolves symbolic references between them. But pushing things traditionally part of the compilation to link time is more and more common in order to take advantage of the knowledge of the whole program.

  Question 2: Are *.class (bytecode) files created by java compiler object files? If yes, then can we say that the JVM that runs them is a type of linker (however its not creating the executable)?

The JVM contains a type of linker as it is able to combine several .class files.

  Question 3: When we compile a C++ program in Turbo C++, we get *.obj files which are the object files. Can we use them to generate the executable in some other architecture?

You could write a translator doing that (Apple did for the 68000 at the time of its transition to PowerPC for instance). Machine language is a programming language. Depending on the amount of transformation you are allowing yourself, you could even call that a compiler.


Bit times and propagation delay Nodes A and B are accessing a shared medium using CSMA/CD, with propagation delay
of 245 bit times between them (i.e., propagation delay equals to the amount of time to transmit 245 bits). Minimum frame size is 64 bytes. Suppose node  begins transmitting a frame at  = 0 bit time. Before A finishes, node B begins transmitting a frame. Assume no other nodes are active.

What is the latest time by which B can begin its transmission?

Attempt:
Considering that t=512 bit times is the time at which A finishes transmission, shouldn't the latest time by which B begins its transmission be at t=245 bit time? (At t=1, 1st bit is pushed on the link, and at t=245 bit time, this is the last "timing" that B can start transmitting before it senses that A is transmitting). However, the answer given is 244 bit time and I do not understand why.

I would say that at t=0 the first bit would begin getting pushed on the link, which would imply that the 245th bit would begin getting pushed at t=244. Thus you'd want to start pushing at t=244.

Disclaimer: I know nothing of networking and little of comp sci but hey, I thought I'd give the logic a whirl. I could be completely wrong.


Finding lost bottle (algorithm problem) The question is as follows:

  A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on a shelf with $n-1$ bottles of non-reactive material, and the scientist doesn't know which is compound A. There is exactly one bottle of compound A among the $n$ bottles on the shelf. The scientist has $O(log(n))$ beakers full of compound B. How can he determine which of the $n$ bottles is the compound A in exactly 10 days time?

I am a little stuck because I don't know how to narrow down the specific bottle in only 10 days. It is pretty obvious that you can just apply the first half of the bottles to the first beaker, and then if it doesn't react you know that the desired bottle is in the second half and so forth. But how do I narrow it down without witnessing the results of the first few tests?

We need to create something where a series of explosions will help us narrow down which one it is (lets say at first its amongst n/4, then n/10, then n/100, etc).
How the heck do I do this?

This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it.

You can solve it as follows:
Number your bottles from $0$ to $n-1$, and label your beakers from $1$ to $\lfloor\log_2(n-1)\rfloor+1$ (the number of bits needed to represent numbers $0$ to $n-1$ in binary).

Now for every bottle, do the following: let $x$ be the label of the bottle. For every $i$ such that there is an $1$ at the $i$'th position in the binary representation of $x$, put a bit of that bottle's compound in beaker $i$.

Now after 10 days, the beakers which explode will exactly spell out the number of the explosive bottle in binary.


The barbers paradox first order logic formalization I tried to look on the site and while I found some similar questions, I did not find the first order logic formalization of the following sentence (the basic barber's paradox), so I wanted to ask if I got the right first order logic formalization of it, and I am sure others will benefit from this thread as well.

Sentence: there exists a barber who shaves all the people that don't shave themselves.

My attempt: this complicated sentence can be made simpler by inferring that "for all of those who does not shave themselves, are shaved by the barber"

And now it seems to be easier to substitute with variables so:

$$\exists x(\lnot S(x,x) \rightarrow S(b,x))$$

where $S(x,x)$ is shaving(verb), $x$ are the persons (who don't shave themselves), and $b$ is a shortcut for barber, so if a person does not shave himself, it can be inferred that he is shaved by the barber.

You're not being asked to do any inference; just to express something.

  there exists a barber who shaves all the people that don't shave themselves

translates directly as

$$\exists b\, \forall x\,\big(\neg S(x,x) \rightarrow S(b,x)\big)\,.$$

(There exists a barber such that everyone who doesn't shave themself is shaved by the barber.)

Your version says that there exists a person who, if they don't shave themself, is shaved by the barber. That's not equivalent. For example, it's true in any world where at least one person does shave themself: just let $x$ be that person, so $\neg S(x,x)$ is false, so $\neg S(x,x)\rightarrow\text{anything}$ is true.


Question regarding Karp-Lipton theorem In the proof in wikipedia, it goes like this:

Let $L \in \Pi_{2}$, so we can describe membership in $L$ as a formula:

$\forall_{y}\exists_{z} V(x,y,z)=1 \iff x \in L$

(where V is polynomial deterministic verifier etc...)
Now they look at the subformula : $s(y)=\exists_{z} V(x,y,z)$ and say that because it's an instance of $SAT$, and according to the hypothesis that $NP \subseteq P/poly$, its equivalent to $C(s(y))$, where $C$ is a valid circuit for solving $SAT$.

These are my questions:

What does $s(y)$ mean? Like what's the meaning of saying that something equals some predicate? It look like merely a technical part of the proof but I can't wrap my head around it.
What's the meaning of exchanging a logical predicate with circuit evaluation mean? Does it mean that we can decide if for every $y$ there exists $z$ such that $V(x,y,z)=1$ with a circuit?

The subformula $s(y) = \exists z V(x,y,z)$ is a Boolean function which depends on $x$ and $y$. In this context we can assume that $x$ is fixed, so we only show the dependence on $s(y)$. Here $\exists z V(x,y,z)$ is the definition of the function: the value of $s$ on an input $y$ equals the truth value of the formula $\exists z V(x,y,z)$ (recall we're assuming that $x$ is fixed).

Since $V$ runs in polynomial time, as in Cook's theorem we can encode $V(x,y,z)$ is a polynomial size formula in the variables $x,y,z$. Given the fixed input $x$ and an input $y$, we can substitute $x$ and $y$ in the formula for $V(x,y,z)$ to get a formula $\varphi_{x,y}$ depending only on $z$. We can also convert this formula to CNF. The new formula is satisfiable, i.e. $s(y)$ is true, iff $\varphi_{x,y} \in SAT$.

If we have a circuit $C$ solving SAT we can use it to check whether $\varphi_{x,y}$ is satisfiable. That's what Wikipedia means when it writes $C(s(y))$: write $s(y)$ as an instance $\varphi_{x,y}$ of SAT, and then run $C$ on the instance to get the truth value of $s(y)$. Since $C$ solves SAT, $C(s(y)) = s(y)$, that is, on input $\varphi_{x,y}$ the circuit $C$ will output the truth value of $s(y)$.


Are you allowed to change the specifications of a problem when doing reductions? I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. However, the input of problem A does not give me enough information to be able carry out all of these demands that problem B require.

My reduction will look something like this:

**A**(G(V, E), K) =
     a = V
     b = E
     P = **B**(a, b, K)
     if(P)
         return true

My question is if it is okay to ignore some of these demands and simply change the B problem to a simpler one which then would allow me to find a reduction which satisfies both problems?

I'm sorry for being so vague, it is a homework problem and I would like to not publish the details.

It doesn't matter what B exactly is, it could be graph problem or something else. Nobody cares as long as you construct its instance in polynomial time and it has a solution precisely when the instance of A has. Maybe you need to use some structure of A to construct B, but maybe some parts of A don't need to be used at all, who knows.

So precisely what you must do is follow the definitions, and then everything is fair game with no authority setting any special rules.


Alternative definitions of ZPP and probabilistic Turing Machines There are two ways to define a probabilistic Turing Machine:

A Turing Machine that can toss coins during its computation.
A deterministic Turing Machine that takes two inputs: $(x,r)$, where $x$ is the original input and $r$ is taken from a distribution of coin tosses.

For example, Arora and Barak give an "alternative definition" for $\mathrm{BPP}$:

  Definition 7.4 (BPP, alternative definition)
  $\mathrm{BPP}$ contains a language $L$ if there exists a polynomial-time TM $M$ and a polynomial $p\colon \mathbb{N}\to \mathbb{N}$
  such that for every $x \in \{ 0, 1 \}^{∗}$, $\Pr_{r \in \{ 0,1 \}^{p(|x|)}} [M (x, r) = L(x)]\geq 2 / 3 $.

My problem is formulating a similar alternative definition for $\mathrm{ZPP}$.

$\mathrm{ZPP}$ can be defined as the class of languages with a randomized algorithm that always outputs the correct answer, and for every input the expected running time of the algorithm is polynomial.

If we want a similar alternative definition for $\mathrm{ZPP}$, then $r$ should be an infinite stream because the algorithm may need to use any number of coin tosses before it finishes (with small probability).

Is there any problem with a Turing Machine that takes as a second input an infinite long stream?

The definition works fine if you allow $r$ to be infinite, and require that $M(x,r)$ agrees with $L$ with probability $1$ when $r$ is distributed according to the coin toss measure on $\{0,1\}^{\mathbb{N}}$ (toss a fair coin an infinite number of times). In this setting, in order to get $\mathsf{ZPP}$, you need to require that the expected running time will be polynomial in $|x|$.

However, you don't really need an infinite number of coins to get $\mathsf{ZPP}$, and could do with an exponential amount of coins. Suppose $L\in\mathsf{ZPP}$, hence there exists a probabilistic Turing machine $M(x)$, such that for all $x\in\Sigma^*$ it holds that $M(x)=L(x)$ and $\mathbb{E}[T_x]\le |x|^c$, where $T_x$ is the running time of $M$ on input $x$. You can now define an equivalent Turing machine $M'$ which is exponential in the worst case (rather than unbounded), and still satisfies the above conditions. Given input $x$, $M'$ simulates $M$ for $2^{|x|^c}$ steps, and if $M$ did not halt in this time, check "manually" if $x\in L$. This can be done by running a PSPACE machine for $L$ (which exists since $\mathsf{ZPP\subseteq PSPACE})$. You can now show that $M'$ is also polynomial in expectation (think about the appropriate choice of $c$ for this to work).


Replacing n with 2n in asymptotic bounds I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|_1$ of a subgroup inside the symmetric group $S_n$.

I want to compute the same bound for the symmetric group $S_{2 n}$. Should I just replace the $n$ in $2^{-\Omega(n)}$ and make it $2^{-\Omega(2n)} = 2^{-\Omega(n)}$?

Or, do I have to work it out from the scratch as follows?

$$
| p - q|_1 = \sum_\rho | p_\rho - q_\rho|
 \nonumber\\
  \le \sum_\rho \frac{d_\rho}{\left(2 n\right)!} 2^{O\left( n\right)}  n^{\frac{n}{2}}
  \nonumber\\
   \le \sum_\rho \frac{\sqrt{\left(2n\right)!}}{\left(2 n\right)!} 2^{O\left( n\right)}  n^{\frac{n}{2}}
    \nonumber\\
     \le  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}}{\sqrt{\left(2 n\right)!}}
        \nonumber\\
            =  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\sqrt{\left(2 n\right)!}\sqrt{\left(2 n\right)!}}
                    \nonumber\\
            =  \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\sqrt{\left(2 n\right)^{2n}}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}\left(2 n\right)^{n}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{n}{2}}n^{n}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{\left(2 n\right)!}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{\left(2 n\right)^{\left(2 n\right)}}
\nonumber\\
= \frac{2^{O\left( n\right)}  n^{\frac{3n}{2}}}{ n^{2 n}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{ n^{\frac{n}{2}}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{ 2^{-\frac{n}{2}} n^{\frac{n}{2}}}
\nonumber\\
= \frac{2^{O\left( n\right)}  }{  \frac{n}{2}^{\frac{n}{2}}}
\nonumber\\
\le \frac{2^{O\left( n\right)}  }{  \left(\frac{n}{2}\right)!}
\nonumber\\
\lll 2^{-\Omega \left(n\right)}
$$

In mathematics we have the substitution principle. If a certain statement is true, then it also holds if you replace all occurrences of $n$ by some other expression, as long as that other expression has the same type as $n$. In particular, you can substitute $2n$ for $n$ and deduce that $|p-q|_1 \lll 2^{-\Omega(2n)}$. You can then conclude that $|p-q|_1 \lll 2^{-\Omega(n)}$, using the definition of $\Omega$.


Convert conjunctive normal form to equivalent boolean formula with only NAND gates Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause).  I want to convert it to an equivalent boolean formula that uses only NAND gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NAND gates that has size $O(n)$? If $O(n)$ isn't achievable, what's the best that is?

Yes, it can be converted to such a formula of size $O(n)$ (i.e., only a constant-factor increase in formula size).  The conversion simply recursively applies the following rules:

$$\begin{align*}
\neg a &\equiv NAND(a,\text{True})\\
a \lor b &\equiv NAND(\neg a, \neg b)\\
a \land b &\equiv \neg NAND(a,b)
\end{align*}$$

It is easy to check that the resulting formula has linear size.

For instance, the clause $x_1 \lor \neg x_2 \lor \neg x_3$ represents $(x_1 \lor \neg x_2) \lor \neg x_3$, so applying the above rules we obtain the boolean formula

$$NAND(NAND(NAND(NAND(x_1,\text{True}),x_2),\text{True}),x_3).$$

In this way, each clause can be converted to a boolean formula of size $O(1)$.  All that remains is to convert the conjunction of these clauses, and that can be done by expressing $c_1 \land \cdots \land c_m$ as $((c_1 \land c_2) \land \cdots) \land c_m$ and then applying the rule for $a \land b$ repeatedly.


Are there grammar classes between Chomsky level 1 and 2? Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?

I know I'm pretty late, but oh well.

There's a class of grammars known as indexed grammars (describing indexed languages, which are a proper subset of CS languages and a superset of CF languages). The rules look very much like the ones in a CF grammar, but every LHS nonterminal has an associated stack of index symbols, and when rewriting that nonterminal, the stack can be manipulated by other nonterminals in the RHS. For example:

$A[\sigma] \rightarrow B[\sigma x] C[\sigma y]$

which means "rewrite nonterminal A to nonterminals B and C, copy the stack and push x to B's stack and y to C's stack" or

$A[\sigma x] \rightarrow B[\sigma]$

meaning "if there's an A with x on top of its stack, rewrite it to B and pop that x off the B's stack".

Some examples of indexed languages are $\left\{ a^n b^n c^n d^n | n \geq 1 \right\}$ or $\left\{ www | w \in \left\{ a, b \right\}^+ \right\}$.

As for the automaton, indexed languages are exactly the class of formal languages recognizable by a nondeterministic nested-stack automaton, which is basically a NPDA in which some elements of the stack may be other stacks.

Concerning practical use, wikipedia says that indexed grammars sometimes find use as affordably processable descriptors of natural languages.

Edit: As Raphael mentioned, indexed languages | grammars are closely related to mildly context-sensitive languages.

There's a class of grammars similar to indexed grammars called linear indexed grammars. While in an IG, every nonterminal in the RHS recieves a copy of the LHS's stack, LIGs require that at most one nonterminal in the RHS recieves the stack. Given that any LIG can be transformed into an equivalent IG, they're strictly less powerful and it has been shown that the set of languages they generate is equivalent to the set of mildly context-sensitive languages.


Can a processor without stack pointer registers, have a subroutine calls and interrupts? Suppose a processor does not have any stack pointer registers, which of the following statements is true?

It cannot have subroutine call instruction
It cannot have nested subroutines call
Interrupts are not possible
All subroutine calls and interrupts are possible

====================================================================

I think answer is 2.

Reason- Because in nested subroutine calls, we push old subroutines into stack and point most recent call with stack pointer.

Please, explain which is the correct option. According to book the answer is 1.

The Control Data Cyber series had no stack pointer, but it had a Pascal compiler. Seymour Cray says your book is wrong. (The Subroutine Call instruction that this computer isn’t supposed to have would store the return address into the location after the instruction it branched to, forming an instruction that could be used to jump back to the caller). If your instructor doesn’t know who Seymour Cray is then they shouldn’t be teaching.

And there were microprocessors that handled interrupts by switching to a second set of registers. So the answer would be 4.


How can SML infer types like this? Wikipedia says:

fun factorial n =
    if n = 0 then 1 else n * factorial (n-1)

  A Standard ML compiler is required to infer the static type int -> int of this function
  without user-supplied type annotations. I.e., it has to deduce that n
  is only used with integer expressions, and must therefore itself be an
  integer, and that all value-producing expressions within the function
  return integers.

I don't understand how a compiler could infer this. It sounds like SML is essentially solving the halting problem for the factorial function, and showing that it only halts on positive integer inputs.

Am I missing something?

The classic Hindley-Milner type inference algorithm requires each literal value to be unambiguously inferable to a type: 0 is an int, while 0.0 is a real. Haskell's type system has been enhanced to include a certain kind of bounded polymorphism, so that 0 can have any type that is a number (more precisely, of any type that is an instance of the Num type class: 0 is of type Num a => a).

See the wikipedia article on Hindley-Milner for further details on the algorithm (the article explanations are much better than anything I could write on that topic).


Understanding algorithm for maximum sum of non-consecutive elements There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:

https://stackoverflow.com/questions/4487438/maximum-sum-of-non-consecutive-elements

That said, I have read this post many times, and many other posts online about how to solve this problem, and I still do not understand why the solution is correct.

Following another post about the problem (that shows the solution, but again lacks in an explanation as to why the solution is correct), I created the following snippit to run in JShell:

class MaxSubset {
    public static Integer maxSum(final List<Integer> ints) {
        final class MaxSubsetR {
            private Integer maxSumR(final List<Integer> ints, final Integer i, final String str) {
                if(i == 0) {
                    System.out.println("in i == 0: " + str);
                    System.out.println("in i == 0: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 0: get 0 " + ints.get(0) + " " + str);
                    System.out.println("returning: " + ints.get(0));
                    return ints.get(0);
                }

                if(i == 1) {
                    System.out.println("in i == 1: " + str);
                    System.out.println("in i == 1: get i " + ints.get(i) + " " + str);
                    System.out.println("in i == 1: get 0 " + ints.get(0) + " " + str);
                    System.out.println("in i == 1: get 1 " + ints.get(1) + " " + str);
                    System.out.println("returning: " + Math.max(ints.get(0), ints.get(1)));
                    return Math.max(ints.get(0), ints.get(1));
                }
                System.out.println("no match " + i + " " + str);
                return Math.max(maxSumR(ints, (i - 1), "left"), ints.get(i) + maxSumR(ints, (i - 2), "right"));
            }
        }
        return new MaxSubsetR().maxSumR(ints, ints.size() - 1, "init");
    }
}

but after running the algorithm and watching the output, I'm still just as confused as I was when I began.

Can someone explain this algorithm to me? In particular:

1) How is the alternation of choosing (i - 1) or (i - 2) is even determined in the recursion in the first place?

2) How does simply subtracting 1 or 2 from the size of the array create the effect of selecting the optimal subset of non-adjacent items?

3) And just generally, how is it going about picking the right items from the list to achieve the stated goal?

New Question

4) We note that the List<Integer> never mutates during the recursion, so for the two if statements, i == 0 will always return the first item in the list, regardless of list size, and the i == 1 case will always return the greater of the first or second item in the list, regardless of list size. So, how is it that every item in the list is even being considered, if the return statements literally only care about arr[0] and arr[1]?

EDIT NOTES

I have re-written my second question to, hopefully, make it more clear what I mean.

For ease of reading, here is the algorithm in pseudo-code, without print statements:

func maxSum(Int[] arr, Int i)
  if(i == 0) return arr[0]
  if(i == 1) return Math.max(arr[0], arr[1])
  return Math.max(maxSum(arr, (i - 1)), maxSum(arr, (i - 2)) + arr[i])

and it would be called with

maxSum(arr, arr.size - 1)

Let me try to explain how to solve the problem. You are looking for a set of non-consecutive array elements with a maximum sum.

Let's say you have an array of 100 elements. Which ones of elements #99 and #100 can be in the optimal solution? They cannot both be present, because they would be consecutive. They cannot both be absent, because then adding #100 would create a larger sum without violating the rules. So one of #99 and #100 is present, and the other is not.

If #99 is present, then the solution is also the optimal solution for 99 elements. If #100 is present, then the items without #100 would be the optimal solution for 98 elements. So there are two possible ways to get an optimal solution for 100 elements: You take the optimal solution for 98 elements and add #100, or you take the optimal solution for 99 elements.

So f (A, n) = max (f (A, n-1), f (A, n-2) + A[n]) if n ≥ 2; f (A, 1) = A[1] and f (A, 0) = 0.

Note that implementing this using recursion is horribly inefficient. It's best to calculate f (A, 1), f (A, 2), f (A, 3) in sequence in linear time.