Full circularity vs strong circularity for attribute grammars Attributes of an attribute grammar can have a circular dependency. In my compiler construction course I learned, that there are two types of circularity for attribute grammars:

full circularity can be checked in exponential time
strong circularity can be checked in polynomial time

Full circularity implies strong circularity, but not vice versa, so if there is an attribute grammar that is strong circular, it might still not be full circular. Thus, if I reject all strong circular attribute grammars, I might reject some grammars even though they are not full circular. I tried to come up with a dividing example to better understand this case, that is an attribute grammar that is strong circular but not full circular, but with no luck yet.

Question

Is there a dividing example that makes the difference clear?
Are there well known real-world attribute grammars that are strong circular but not full circular?
Would it be a real limitation for a tool to accept only strong non-circular grammars?

I assume the terms strong circularity and full circularity are well known. If they are not you can find the lecture notes here (lecture 12, 13 and 14).

You are using the terms in a weird way. A grammar can be circular or non-circular. Since FULLY testing this property is EXPTIME, one wants a simpler (easier to test) property.
This is where strong NON-circularity comes in. In strong non-circularity, you basically combine the dependencies of all possible sub-trees, even for combinations that can't appear together. So if a grammar is strong non-circular, it particularly rules out the combinations that CAN happen together. I.e. the grammar is non-circular.

So this means that strong NON-circularity implies NON-circularity. Sure you can invert implications by negating both sides of it. I think this is what you did when you say that "Full circularity implies strong circularity".
But I don't think it makes sense to call a grammar that is NOT strongly NON-circular "strong circular". IMHO that would be a confusing term, because it sounds like such a grammar was "even more circular" than other grammars, but it is the opposite - it only fails the strong-non-circularity test which isn't a necessary condition. So such a grammar would rather be "less circular" than other grammars, because it "looks circular" without necessarily being circular.
But that doesn't sound right either (because in the end, it is either circular or not). If anything, I would call it "weakly circular", because that property doesn't guarantee anything - to be certain, you still need to apply the full circularity test.

To adress the question: in practice you usually only work with S-Attribute Grammars, which don't even need to be tested for circularity, because they can't be circular.

I dug out this example (attributes starting with i are inherit attributes, attributes starting with s are synthetic ones):

S -> A
    ix.1 = 1        (1)
    iy.1 = 2        (2)
    sx.0 = sz.1     (3)
A -> A a
    ix.1 = sy.1     (4)
    iy.1 = ix.0     (5)
    sy.0 = sz.1     (6)
    sz.0 = 0        (7)
A -> a
    sy.0 = 0        (8)
    sz.0 = ix.0     (9)
A -> b
    sy.0 = iy.0     (10)
    sz.0 = 0        (11)

this grammar is non-circular, but it fails the strong-non-circularity test, because in the strong-non-circularity test, you take the union of the dependency-sets for the productions of the same nonterminal. So you have the edges for both A->a and A->b together, although they can't appear together (because you can't apply both productions at the same time).

The production of A -> A a then yields the following dependency-graph:
let Q and R be the prefixes for the two A's in the production, then you have the nodes

{ Qia, Qib, Qsb, Qsc, Ria, Rib, Rsb, Rsc }

and the edges

{ (Qsb, Qia),     from (4)
  (Qia, Rib),     from (5)
  (Rib, Rsb),     from (10)
  (Rsb, Ria),     from (4)
  (Ria, Rsc),     from (9)
  (Rsc, Qsb)      from (6)
}

this is a cycle and therefore the strong-non-circularity test fails. The point why the strong-non-circularity test is wrong here, is because the edges (Rib, Rsb) and (Ria, Rsc) come from different productions.


Intuition for convolution in image processing I have read many documents about convolution in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing convolution on an image. For example, intuition of derivation on the graph is make it more linear for example.

I think a quick summary of the definition is: convolution is multiplied overlap square between image and kernel, after that sum again and put it into anchor. And this doesn't make any sense with me.

According to this article about convolution I cannot imagine why convolution can do some "unbelievable" things. For example, line and edge detection on the last page of this link. Just choose appropriate convolution kernel can make nice effects (detect line or detect edge).

Can anyone provide some intuition (doesn't need to have to be a neat proof) on how it can do that?

I think the simplest way to think of Convolution is as a method of changing a pixel's value to a new value based on the weight of nearby pixels.

It's easy to see why Box Blur:

_____________
|1/9|1/9|1/9|
|1/9|1/9|1/9|
|1/9|1/9|1/9|
-------------

works. Convolving this kernel is the same as going through every pixel of a photo and making the new value of the pixel the average of itself and the eight surrounding pixels.

If you get that, you can see why Gaussian Blur works:

_____________________
|.01|.04|.07|.04|.01|
|.04|.16|.26|.16|.04|
|.07|.26|.41|.26|.07|
|.04|.16|.26|.16|.04|
|.01|.04|.07|.04|.01|
---------------------

It's basically the same thing, except the averaging is weighted more strongly toward pixels that are closer. The function that defines how quickly the weights fall off as you move further away is the Gaussian Function, but you don't need to know the details of the function in order to use it for blurring.

The edge detection kernel in the linked article makes sense if you stare at it long enough too:

__________
|-1|-1|-1|
|-1|.8|-1|
|-1|-1|-1|
----------

It's basically saying that the value of any pixel starts at 8/9ths of it's original value. You then subtract the values of every pixel around it to arrive at your new pixel.

So if the value of a pixel is high and the value of the pixels around it are high too, they will cancel each other out. If the value of the pixel is low and all of the pixels around it are low as well, they will also cancel each other out. If the value of the pixel is high and the value of the pixels around it are low (as in a pixel on the edge of an object) the new pixel value will be high.


Generating a adjacency matrix representing a DAG Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph.

Graph can be randomly created although I would ideally generate a graph of desired size and topology similar to what one can do with JGraphT.

My general intent is to create a very large graph representation (billions of nodes and edges) in parallel by first generating an adjacency matrix to ensure connectedness and then create a representation (RDF, etc) in parallel.

Any further suggestions or alternative approaches are welcome.

Yes there is an easy way to generate a random DAG. If a graph is a DAG it can be separated into levels or ranks. The idea is to rank the nodes and randomly generate edges from lower ranked nodes to higher ranked nodes. A little bit of Googling finds the exact same question asked on stackoverflow a few months ago (with sample code!).

My only concern is that an adjacency matrix representation for a graph with billions of nodes/edges won't fit in memory. However, it's possible I misunderstood your intent in that part of the question.


Saturated sets in bipartite graph Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the neighborhod of $W$ in $Y$ (aka Hall's marriage condition).

My goal is to find a subset $W^*\subseteq X$ with $|W^*| = |N(W^*)|$, if such a subset exists (obviously it need not exist). Since I'm not aware of a formal name for this property, I'd refer to such a $W^*$ as a saturated set.

Questions:

Is this property widely known? Does it have a different name?
Assuming the marriage condition holds, it is straightforward to show that every union of saturated sets is also saturated. One interesting problem is to find the maximum saturated set. I describe below a somewhat naive solution with runtime $O(|V|\cdot |E|)$, but I suspect it can be solved even faster. Any idea?
Allegedly, a weakly easier problem is to find a saturated set, not necessarily the maximum one (again, assuming the marriage condition holds). Can we solve this problem faster than $O(|V|\cdot |E|)$?

Edit:
Here's a sketch for the algorithm I mentioned above: Assume the marriage condition holds for $G$. Then, as said, with a bit theory work we can show that

Lemma: Let $G$ be a bipartite graph satisfying the marriage condition. Then, every union of saturated sets is also saturated.

The Lemma suggests that there exists a unique maximum saturated set. The question can hence be stated differently:

  Given a node $x\in X$, determine whether it participates in a saturated set or not.

If the answer is yes, then it also participates in the maximum saturated set. The pseudo algorithm goes as follows:

Run the Hopcroft–Karp algorithm to find a maximal matching $M$ that covers $X$ in $O(\sqrt {|V|}|E|)$ time. Such a matching exists due to the marriage condition.
For every node $x\in X$,

Temporarily add a node $x'$ to $X$, which is connected to every neighbor of $x$. Call the graph we obtain $G_x$.
Notice that $M$ is a partial matching of $G_x$ that is almost maximal (up to one edge); thus, we can find a maximal matching $M_x$ for $G_x$ by finding an augmenting path in $G_x$, in $O(|V|+|E|)$ time (same details as in Hopcroft–Karp).
If $|M|<|M_x|,$ continue. Else, if $|M|=|M_x|$, add $x$ to the returned set.

The analysis follows from first principles. If there exists any saturated set $W\subseteq X$ with $x\in W$, i.e., $|W|=|N_G(W)|$ then
$$
|W\cup \{x'\}|=|W|+1 = |N_G(W)|+1=|N_{G_x}(W)|+1,
$$
so $W\cup \{x'\}$ violates the marriage condition in $G_x$. Consequently, $|M|=|M_x|$. We can analogously show that if $x$ does not participate in any saturated set, then $|M_x|=|M|+1$.

Let's fix a maximal matching $M$. Let $Z\subseteq Y$ be the set of nodes that are not matched to nodes in $X$. We can see a node $x\in X$ belongs to a saturated set if and only if there does not exist an alternating path from $x$ to a node in $Z$, i.e., a path $xy_1x_1\cdots y_kx_kz$ where $(x_i,y_i)\in M$ and $z\in Z$ (the proof is similar to the correctness proof of your algorithm).

So you can add directions to all edges in $E$ such that edges in $M$ have the direction from $X$ to $Y$ while edges not in $M$ have the direction from $Y$ to $X$, then the nodes in $X$ that are not reachable from any node in $Z$ make up the maximal saturated set. You can run a simple BFS to see which nodes in $X$ is reachable from nodes in $Z$. The time complexity is $O\left(\sqrt{|V|}|E|\right)$.


Proving that it is undecidable if a Turing machine accepts a language that is its own reverse I have a Turing machine M. How can I prove that $L(M) = (L(M))^R$ is decidable by constructing a Turing machine that can do this? I know how to figure out if two DFA's accept the same language (using the symmetric difference) however I don't believe it works for Turing machines. Now I am able to design a Turing machine where, for a string w, I can determine whether or not the reverse of w is also accepted by the language. The problem is that I'm having trouble determining if the set of all strings is the same as the set of all reverse strings. If I design another TM then I feel like it's just going to infinitely loop. So how can I prove that this is decidable?

The decision problem

  Given Turing machine $M$, is $L(M) = (L(M))^R$?

is undecidable. This is a simple consequence of Rice's theorem.

The property (i.e. class of Turing-recognizable languages)

$$\mathcal{S}_{\mathrm{rev}} = \{ L \mid L \; \text{recognizable and } L = L^R \}$$

is non-trivial, since $\emptyset \in \mathcal{S}_{\mathrm{rev}}$ and $\{ ab \} \notin \mathcal{S}_{\mathrm{rev}}$.


How to construct an ordinary matching from a fractional matching? Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge  $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.

My question is : does the fractional matching give a matching that we know (of $G$) i.e. with no conflicting edges? I am confused, since there is no criteria for choosing a fraction  $f(e) \in [0,1]$, for every $e \in E$. For example, if we have $e_{1}, e_{2} \in E$ such that $v \in e_{1}, e_{2} $ and I assign $f(e_{1})=1/4$ and $f(e_{2})= 1/2$, then $f(e_{1})+f(e_{2})=3/4 \leq 1 $, hence both $e_{1}$ and $e_{2}$ should belong to the fractional matching.

Thank you in advance.

It is not possible to get a maximum matching from any fractional matching by only looking at the values of the fractional matching. Consider the undirected triangle graph with  vertices $v_1,v_2,v_3$ and edges $e_1=(v_1,v_2), e_2=(v_1,v_3), e_3=(v_2,v_3)$. If we assign $f(e_1)=f(e_2)=f(e_3)=\frac{1}{2}$, this is a valid fractional matching. However, an actual matching can only contain one of the edges, so we cannot distinguish these edges by their value.

It is of course always possible to obtain a matching from a fractional matching by first selecting all edges with at least a certain fraction and then removing edges such that you end up with a matching. This matching, however, is usually not a maximum matching.


Need of reducing problems if we already know that a problem is undecidable In the Reducibility chapter of Sipser's Theory of Computation book, an example is:

We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is undecidable, so is HALT(TM)

My question is, if we already know that A(TM) is undecidable, what is the need for deciding HALT(TM). It's a basic question though.

Hope you got it.

There's a difference between the statements:

There is an undecidable problem.

and

The problem HALT(TM) is undecidable.

For the first one, it sounds like you proved by by showing directly

The problem A(TM) is undecidable.

The point of using a reduction, is that it lets you deduce the undecidability of HALT(TM) from the undecidability of A(TM), as opposed to starting "from scratch".  More generally, reductions let you compare the hardness of different problems to each other, which is a general theme in computability and complexity.


How do I use message passing to find the maximum of all values in a grid? I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly at a loss as to how to begin writing the message passing code to solve this. Any help on knowing how to break this problem down would be greatly appreciated.

The question is as follows:

  Suppose $N^2$ processes are arranged in an $N$ by $N$ square grid. $P_{i j}$ refers to at the grid position (row $i$, column $j$). A process can communicate, using message passing, only with its neighbors to the left and right, and above and below. (Processes on the corners have only two neighbors; others on the edges of the grid have three neighbors.) Every process has a local integer value $v_{i j}$.
  Show an efficient computation scheme at each of the nodes that will eventually result in every process knowing the maximum of all values in the grid.

Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes.

After this, the last row would contain the maximum values of each column. Then, we could have the last row propagate the maximum value in the right direction so that the (n,n)th element contains the maximum value from this row. Since this row contained the maximum values from each column, (n,n)th element will essentially possess the maximum value from the entire grid.

We could then choose to propagate this value through the grid in parallel backwards till all the nodes know about this maximum value.

Complexity will be O(n) and there will be 4n hops of message passing through this proposed scheme.

Edit: Here's A pseudo-code. Disclaimer: not tested, might contain bugs

findMaxAllThreads(){
    int maxVal;

    // At the start, each element's max value will exactly be its value itself.
    maxVal = procId.val;

    // If this is the first element in the column, simply send the current
    // max value to the next element within the column.
    if(procId.row == 1)
        sendMessage(procId.row + 1, procId.col, maxVal);

    // For any other element in a particular column, except the last one,
    // compare the received value with the current max value and send the
    // updated value to the next element.
    else if(procId.row < n)
    {
        // wait for the message from the previous element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value till this node.
        if(val > maxVal)
            maxVal = val;

        // send the updated max value to the next element in the column.
        sendMessage(procId.row + 1, procId.col, maxVal);
    }

    // If we reach the last element in the column, we need to propagate the
    // values rightwards to the next element within the last row.
    else
    {
        // Receive the message from the (n-1)th element in the column.
        recvMessage(procId.row - 1, procId.col, val);

        // update the max value. Note that this will be the maximum value of
        // this particular column.
        if(val > maxVal)
            maxVal = val;

        // If this is the (n,1)th element in the whole grid (bottom left), then
        // simply propagate the max value to the next element rightwards in the
        // row.
        if(procId.col == 1)
            sendMessage(procId.row, procId.col + 1, maxVal);
        else
        {
            // Wait for the value from the previous element in this row.
            recvMessage(procId.row, procId.col - 1, val);

            // Update the max value till now.
            if(val > maxVal)
                maxVal = val;

            // If this is not the (n,n)th element in the grid, propagate the
            // value to the right.
            if(procId.col != n)
            {
                // Propagate the max value to the right.
                sendMessage(procId.row, procId.col + 1, maxVal);
            }

            // if this is the bottom-right (n,n)th element in the grid, wait
            // for the final value arriving from  the (n, n-1)th element from
            // the left.
            else
            {
                // Receive the message from the (n-1)the element in the nth row.
                recvMessage(procId.row, procId.col - 1, val);

                // Update the value. Note that this is also the maximum value
                // in the entire grid.
                if(val > maxVal)
                    maxVal = val;

                // Now maxVal contains the maximum value from all the processes.
                // We could choose to report it or if we want, we could
                // propagate it all the way back to the first node, so that
                // it's known globally as the max value.
            }
        }
    }
}


Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata? Tomorrow is my presentation and I want to clear my concepts…

I've read that in DFA, "For each state, transition on all possible symbols (alphabet) should be defined."

Is for each state, defining transition on all possible symbols mandatory in DFA? If its not, then please give any examples?

Suppose a DFA was allowed to have missing transitions.  What happens if you encounter a symbol which has no transtion defined for it?  The result is undefined.  That would seem to violate the "deterministic" characteristic of a DFA.

However, it's trivial to transform such an incomplete DFA into a complete DFA.  Simply add a new state, illegal, and map any undefined transitions to the illegal state.  Finally, add transitions for every symbol from the illegal state back to itself. This illegal state is often called a sink state, because once data falls into the sink there's no way to get out.

So, from a practical perspective, it's kind of moot, as long as you have a well-defined way to handle missing transitions.


Finding a $g(n)$ so that $f(n) = O(g(n))$ I am having trouble on the following algorithms question:
Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$.
I know that this means I need to find constants $c,n_{0}$ so that $f(n) \leq g(n)$ for all $n > n_{0}$.
I began by considering the expansion of $f(n) = n^{5}\cdot1^{22} + n^{5}\cdot2^{22} + ... + n^{5}\cdot(n-1)^{22} + n^{5}\cdot n^{22}$.
This gave me two ideas for a solution:
First, I thought to set $g(n) = c \cdot n^{27}$ (given that this is the largest exponential term of $f(n)$), but where I am stuck is picking the right $c$.  I had the idea of picking $(n-1)n^{5}$ (there are $n-1$ other terms and the largest exponential of each term is $n^{5}$), but I'm stuck for two reasons:

Can $c$ be dependent on $n$?  By definition it seems like the answer is no since $c$ is a constant.

The choice of $c = (n-1)n^{5}$ is dubious.  Consider the term $(n-1)^{22}n^{5}$, the largest portion is $(n-1)^{23}$, not $n^{5}$.

My second idea is to let $g(n) = c \cdot n^{5} + n^{27}$, and let $c = \sum^{n-1}_{y{=}1} (y^{22})$, but again this seems incorrect because $c$ depends on $n$.
I would love some feedback on these attempts, thanks!

For any $f$ we have $f \in O(f)$ i.e. trivial answer to your question is $g=f$.  Presumably  you need  to clarify more exactly conditions on $g$. On other hand if we change all members of sum with maximum one, then we have $f \in O(n^{28})$.
Now about questions:

$c$ is independent from $n$ by definition
outgoing from 1. you cannot consider $c = (n-1)n^{5}$


Decidability algorithm, whether substring belongs to L It isn't very hard to decide if word belongs to language L. CYK algorithm should do here.

Occured thought, can CYK be modified to detect if all words of language L contain some specific subword?

On the contrary, it can be arbitrarily hard to decide if a word is in a language. Not only are there undecidable languages (such as the halting language), but there is an infinite hierarchy of undecidable languages, each one even harder than the previous one!

It also seems unlikely that an algorithm for deciding membership in a language would be easily modified to decide if every string in a language has some particular property. That's a completely different problem, requiring completely different analysis.


How to decide which bytes will form a packet ?(computer networks) In wireless communication , I understand what it means to transmit a "bit" but I wanted to understand what exactly does it mean by a packet .

*******POST EDIT/RECEIVING INITIAL ANSWERS*******
I got the following question , which is also there in my comment ,

How to decide which bytes should form one packet of data ?
What distinguishes one packet from another ?

for the following query

*****EDIT CLOSES HERE ****

There will be a signal of certain frequency, $ \omega $ which is transmitted .If the amplitude crosses a threshold then it means then we say that a "bit" about the information which is interpreted or encoded by a signal of frequency $ \omega $ is detected or received .
(Please correct me If I am wrong)

Similarly , I would like to understand what exactly a "packet of data" in networking means electronically(logically or physically maybe) . What is the definition of a packet ?

Still if the previous version of this question is required then its in the following link :

https://hastebin.com/tejapuvace.coffeescript

Looking forward to replies , thanks a lot .

A packet is a sequence of bytes. Nothing more, nothing less.

When transmitting packets, a signal is formed in such a way that boundaries between packets are easily identified, and that the bytes forming the packets can be transmitted and decoded by the receiver.

Electrical signals at high frequencies must be formed in such a way that they are not damaged during transmission. A digital signal (low signal = 0, high signal = 1) at high frequency has no chance to survive transmission because of higher frequencies added by sharp signal changes.

In addition, information for error detection and correction is added before transmitting and checked + removed after receiving the signal, so a package that is sent cannot only be received, but checked for correctness.

(The actual way the signal is formed will only be known by a handful of highly specialised engineers. It's no secret, just very difficult and not of any interest to most people. As I said in a comment, "applied magic").


How to use Neural Network classification if data not same size? I have data like this.

[0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 1 0 1 ]
[0 1 0 1 0 1 1 1 1 0]
...

I want to classify with Neural Network but my data different size . I can not delete or add more arbitaly data. It may make the result not correct. So, How to classification data different size ?

You can padd your data.

  I can not delete or add more arbitaly data. It may make the result not correct.

Don't make assumptions about neural networks. They can map any function, and if you don't add more data (padding) then you can't even train your network in the first place.

If your data consists of merely 0's and 1's. You could either do the following:

pad all blanks with 0.5 ([0 1 0 1 0, 0.5, 0.5, 0.5, .0.5]), however the neural network will think that 0.5 is as far from 1 as it is from 0.
pad all blanks with 0.5 (this is what I recommend), if your data is binary (e.g. true/false), then all false must be set to 0 consistently. 0 then has the double meaning: false or not present.

There is no other option besides adding 'blank' data, if you don't add data, the network will still see this as a 0.

But you should try before you ask. "It may make the result not correct." is not a good argument to not do something. Your data doesn't seem that big, so you can easily test through trial and error.


An $O(n)$ algorithm to FFT-evaluate an FFT evaluation This question is from a practice exam in my algorithms class. I'm posting the question and the answer listed in that practice exam:

  Let $W$ be an $n\times n$ matrix whose $(i,j)$-th entry is $\omega_n^{ij}$, where $\omega_n$ is a principal $n$th root of unity. Let $X=(X_0,\dots,X_{n-1})$ be an $n$-vector. The product $W \times X$ can be computed in $O(n\log n)$ time. Let $FFT(X)$ denote the vector that results by applying the FFT evaluation algorithm to the vector $X$.

  Describe an $O(n)$ algorithm to compute $FFT(FFT(x))$.

  Answer: $FFT(FFT(x))$ is $W^2\times X$
  $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, and $n$ otherwise.

I'm confused about everything:
1. How does this run in $O(n)$? To compute $(W^2)_{jk}$ I'm already  iterating through $n^2$ elements....
2. Why is $FFT(FFT(x)) = W^2\times X$?
3. Why is $(W^2)_{jk} = 0$ if $j+k$ is not a multiple of $n$, $n$ otherwise?

I would appreciate an answer that isn't too advanced as my math skills are limited to basic undergrad math classes of an engineering major.

Let's answer your questions one by one.

You don't compute $W^2$ by squaring $W$ algorithmically. Rather, you compute $W^2$ "on paper", and you find out a formula for $W^2$. Given this formula, you can check that
$$ (W^2 X)_j = \sum_{k=0}^{n-1} (W^2)_{jk} X_k = nX_{-j}, $$
where $-j$ is the unique $k$ such that $j+k$ is a multiple of $n$. For example, if $n = 5$ then the correspondence between $j$ and $k$ is
$$
\begin{array}{c|c}
j & k \\\hline 0 & 0 \\ 1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1
\end{array}
$$
Let $Y = W^2X$. Then $Y_j = nX_{-j}$, and so we can compute $Y$ from $X$ in linear time $O(n)$.
Since $FFT(X) = W\times X$, $FFT(FFT(X)) = W\times FFT(X) = W \times (W \times X) = (W \times W) \times X = W^2 \times X$.
This is a calculation:
$$
\begin{align*}
W^2_{jk} &= \sum_{i=0}^{n-1} W_{ji} W_{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{ji} \omega_n^{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\ &= \sum_{i=0}^{n-1} (\omega_n^{j+k})^i.
\end{align*}
$$
If $j+k$ is a multiple of $n$ then $\omega_n^{j+k} = 1$ and so
$$ W^2_{jk} = \sum_{i=0}^{n-1} 1^{j+k} = \sum_{i=0}^{n-1} 1 = n. $$
Otherwise, $\omega_n^{j+k} \neq 1$ and so we can use the formula for the sum of a geometric series to conclude
$$ W^2_{jk} = \sum_{i=0}^{n-1} (\omega_n^{j+k})^i = \frac{(\omega_n^{j+k})^n - 1}{\omega_n^{j+k} - 1} = 0 $$
since $\omega_n^{(j+k)n} = (\omega_n^n)^{j+k} = 1^{j+k} = 1$.


TCP Connection Termination - FIN, FIN ACK, ACK I've been reading that to terminate a TCP connection 3 handshakes are required: FIN, FIN ACK, and ACK. However, when closing a connection, Wireshark displays FIN ACK, FIN ACK, ACK; it never displays FIN by itself.

However, when establishing a connection Wireshark clearly displays the three handshakes: SYN, SIN ACK, ACK.

So I'm kinda confused why when closing the connection the three handshakes aren't displayed like that.

A TCP implementation might send a standalone FIN in the first closing segment. However, it can also send a FIN ACK, instead.

The latter is strictly better:  the implementation can bundle a "free" ACK with the FIN segment without making it longer. This is because, if you don't ACK, there is still room in the segment for the ACK number, which will be ignored, and waste bandwidth. Hence the last-sent ACK is simply re-sent, just in case the receiver missed it.

This is true for all TCP segments. Hence, except for the very first SYN segment, where the sender has no information about the ACK number, all the other segments will usually have the ACK flag on.


How do you solve this [1,5,9,4] pair numbers problem? So given an array of [1,5,9,4], find all pairs of numbers that can sum/subtract/divide/multiply to another number in the array(that number is not part of the pair), and return the total count of pairs satisfying this condition. (If a pair has 2 math operators that fit to the same number or if a pair can combine to 2 different numbers, dont count it twice).

How do I start this? and how do I explain my asymptotic complexity(Im a noob wit this)?

This can be done in $O(n^2 \space log \space n)$.

Insert all N array elements with the indexes into a balanced BST.
For every $i \in \{0,...N-1\}$
For every $j \in \{0,...N-1\} \space and \space j \ne i$
Search for $(A[i]+A[j]),(A[i]-A[j]),(A[i]*A[j]),(A[i]/A[j])$ in the BST and add $(A[i],A[j])$ if it is found in the BST and  its corresponding BST entry $index \ne i\space and \space j$

Steps 1 and 2 runs for $O(n)$ time.
Step 2 runs for $n-1$ times = $O(n)$.
Step 3 runs for $4*log\space n = O(log\space n)$.
Hence, time complexity is $O(n^2\space log \space n)$.


Why is it that any graph traversal method can be described as pre-order, in-order, or post-order? What do those terms mean? There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-order.

What do those terms mean? How do I properly categorize an algorithm as pre-order, in-order, or post-order?

Take a binary tree with the following structure:

A traversal algorithm that considers every node in a tree must consider each node in some order. It might touch the nodes in this order: 2, 1, 3. Or this order: 1, 2, 3. And so on.

We can categorize these nodes into groups for convenience. Let us say that Node 1 is the Parent Node while Node 2 and Node 3 are Children of the Parent.

When we use terms like "pre-order", "in-order", or "post-order", we are really describing the order in which our implementation of an algorithm touches the parent node.

For example, an algorithm performs a pre-order traversal of the graph above if it touches the parent node before the child nodes. ( vis 1, 2, 3 )

An algorithm performs an in-order traversal of the graph above if it touches the parent node in between the child nodes. ( vis 2, 1, 3 )

An algorithm performs a post-order traversal of the graph above if it touches the parent node after the child nodes. ( vis 2, 3, 1 )

So, when we describe an algorithm as having a particular order, we aren't necessarily describing the algorithm--but rather we are describing the implementation of the algorithm.

For example, what if we want to implement Depth-First Search (DFS) of a more complicated graph?

Here's a larger graph traversed with a pre-order implementation of DFS:

Let us say that B and G are children of F, but none of the other nodes are considered children of F.

Notice that--given that definition--every parent node is processed before it's children. There might be several nodes processed in the course of doing that, but--no matter which parent node you check, it is guaranteed to be processed before its children.

The same goes for in-order traversal ( every parent is guaranteed to be processed in between its children ):

And post-order traversal ( every parent is guaranteed to be processed after each of its children ):

Note that all of the above are different implementations of the same algorithm, namely Depth-first Search. So, we have taken one algorithm and implemented it three different ways, each handling parents in a different order relative to their children.

In the same way, any graph traversal algorithm can be categorized as pre-order, in-order, post-order--or possibly none of the above. These terms merely describe the order in which parent nodes are processed relative to their children.

Note that the Wikipedia entry on tree traversal describes several implementations of several traversal algorithms, but is able to categorize all of these algorithms in terms of the order in which they process parents relative to their children.


Convex polygon formulation We have a sorted list of side lengths that can be used to form a polygon. There are $n$ such values ($n \le 1000$).

Now we need to find if we can use any 10 of these values to form a non-degenerate convex polygon.

How do we approach this? Anything up to the order of $O(n^2 \log n)$ is acceptable. Better if possible. I need the general idea on how to proceed, the properties of convex polygons which can be exploited here, etc.

Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence.

Proof. Here.

Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_j < \sum_{i=1}^n a_i$ for all $j$.
Theorem 2. The sequence $a_1,\ldots,a_n$ is a sequence of edge length for a polygon iff it satisfies $n$-gon inequality.

Proof. Here. (note the proof here requires advanced math and also proves Theorem 1)
The problem reduce to:

Given a sequence of $n$ non-negative reals, find a $k$ element subsequence that satisfies $k$-gon inequality.

An simple algorithm: Check if $a_i,\ldots,a_{i+k-1}$ is a solution for every $1 \leq i\leq n-k+1$. If none of them work, then there is no solution.
Proof. If we have any solution $a_{i_1},\ldots,a_{i_k}$, find the largest $j$, such that $a_{i_{j+1}}-a_{i_j}>1$, (i.e. there is a gap). If there is no such gap then we are done. If there is one, then $a_{i_2},\ldots,a_{i_{j}},a_{i_{j+1}-1},a_{i_{j+1}},\ldots,a_{i_k}$ is also a solution. (intuitively, we used the largest element in the gap and removed the smallest element). We can repeat this step (at most $k-1$ times) and fill in all the gaps. Eventually we produced a solution of the form $a_{i_k}-k+1,a_{i_k}-k,\ldots,a_{i_k}-1,a_{i_k}$ for some $i$.
The algorithm can be done naively in $O(kn)$ time. Maybe there is a smarter way to do it.
A interesting follow up question:

Given a sequence of $n$ non-negative reals, find the longest subsequence $S$, such that every $k$ element subsequence of $S$ satisfies $k$-gon inequality.


Where is knowing the 2^k largest elements in a array useful? I came across this question today on stackoverflow. It asks:

  Find the largest, $2$nd, $4$th, $8$th, ..., $2^{\log n}$-th largest element in an arrary. Use $O(n)$ algorithm. $2^k$

I've come across this before and know how it can be done, but I've been been trying to find examples of algorithms that incorporate the above into the actual algorithm for a while now since I'm curious about how it can be used in practice. However, I haven't had any luck at looking this up online haven't had any results. Therefore, I'm asking if anyone knows a formal name for an algorithm that solves the above or some examples of algorithms that use the above in some way or another.

If you implement a solution to the problem in an obvious way using quickselect with partitioning ($\log_2 n$ selects, with the $i$th one costing $n/(2^i)$), you will end up with an array partitioned in such a way that it is essentially Williams's binary heap.


Distribution of beans in jars to k members Here is the problem. We have N jars. Each jar can have any number of beans. These beans have to be distributed among C children. The resulting distribution should serve two goals Now

the number of beans that each child gets must be the same (+/- 1 when total number of beans is not a multiple of C)
each child to get all the beans from minimum number of distinct jars. Why? It is possible that beans in a jar may be contaminated. We want as few children to get infected as possible. E.g. if we have two jars with N beans each and two children, each child gets N beans. we would want child one to get N beans from jar 1 and child two to get beans from jar 2. As opposed to a solution, wherein child 1 gets half beans from jar 1 and half beans from jar 2. In former solution, if jar 1 is contaminated, only child 1 is infected. In latter solution, both children are infected.

So if

C = 5
beans = {B0:12, B1:12, B2:12, B3:12, B4:12} // Jar:<Bean-Count>

Distribution should be

{C1:{B0:12}, C1:{B1:12}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

Because each child has beans from exactly one jar. Following distribution will be less preferred

{C0:{B0:6, B1:6}, C1:{B0:6, B1:6}, C2:{B2:12}, C3:{B3:12}, C4:{B4:12}}

What will be the algorithm for achieving the distribution strategy with above goals in mind?

If this is a practical problem, it can be solved using integer linear programming (ILP).

We'll introduce three kinds of integer variables:

$x_{i,j}$ counts the number of beans from jar $i$ that are given to child $j$.
$y_{i,j}$ is 1 if child $j$ gets any beans from jar $i$, or 0 otherwise.
$z_i$ is the number of children who get at least one bean from jar $i$.

Then we'll add some constraints to enforce the requirements in the question:

$\lfloor B/C \rfloor \le \sum_i x_{i,j} \le  \lceil B/C \rceil$ where $B$ is the total number of beans across all the jars.  This ensures that each child receives the same number of beans.
$0 \le x_{i,j} \le B_i y_{i,j}$, where $B_i$ is the number of beans in jar $i$, and $0 \le y_{i,j} \le x_{i,j}$.  This ensures that $x_{i,j}$ and $y_{i,j}$ are consistent with each other.
$\sum_j x_{i,j} \le B_i$.  This ensures that you don't give out more beans from jar $i$ than are available.
$z_i = \sum_j y_{i,j}$.

Finally, the objective function is the average of the $z_i$'s, i.e., $\frac{1}{N} \sum_i z_i$.  We feed this to an integer linear programming solver and ask it to minimize the objective function, subject to the constraints above.

The worst-case running time of ILP solvers is exponential time, but in practice they are sometimes much more efficient than you might think.  If you have $N,C < 50$, I suspect this might be efficient enough to work in practice.  The only way to find out for sure is to try it.


Why are there more non-computable functions than computable ones? I'm currently reading a book in algorithms and complexity. At the moment I'm, reading about computable and non-computable functions, and my book states that there are many more functions that are non-computable than computable, in fact the majority is non-computable it says. In some sense I can intuitively accept that but the book does not give a formal proof nor does it  elaborate much on the topic.

I just wanted to see a proof/let someone here elaborate about it/understand more strictly why there are so many more non-computable functions than computable ones.

The are countably many computable functions:

Each computable function has at least one algorithm.
Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\{0,1\}$.
The number of finite binary strings denoted by $\{0,1\}^*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$).

Therefore there can be at most countably many computable functions.
There are at least countable many computable function since for each $c\in \{0,1\}^*$, the constant function $f(x)=c$ is computable.

In other words, there is a correspondence between:

the set of computable functions,
the set of algorithms,
$\{0,1\}^*$, the set of finite strings from $\{0,1\}$, and
$\mathbb{N}$, the set of natural numbers.

On the other hand, there are uncountably many functions over strings (or natural numbers). A function $f:\mathbb{N} \to \mathbb{N}$ (or $f:\{0,1\}^* \to \{0,1\}^*$) assigns a value for each input. Each of these values can be chosen independently from others. So there are $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$ possible function. The number of functions over natural numbers is equal to the number of real numbers.

Since only countably many of functions are computable, most of them are not. In fact the number of uncomputable functions is also $2^{\mathbb{N}}$.

If you want to picture this intuitively, think about natural numbers and real numbers, or about finite binary strings and infinite binary strings. There are way more real numbers and infinite binary strings than natural numbers and finite strings. In other words $\mathbb{N} < 2^\mathbb{N}$ (for a proof of this fact see Cantor's diagonal argument and Cardinal arithmetic).


Is there an equivalence between "does this program halt" and "is this sentence provable"? It seems, intuitively, that determining if an program halts when running on a TM should be as difficult as determining if a sentence is provable within a finite set of logical rules. Furthermore, there are as many sentences as there are program and there are as many finite set of logic rules are there are TM (there are countably infinitely many of each).

Can we interpret a universal Turing machine executing programs as equivalent, in some way, as finding the proof for all theorems for all finite set of logic rules. If a program halts on a TM then it means that the program is a theorem of some logical system, and vice-versa.

If so, how? If not, why not?

If a Turing machine halts on a given input, then you can prove this in any reasonable propositional proof system. The idea is to list the halting sequence of configurations of the Turing machine, and prove, one by one, that these are the configurations encountered by the Turing machine when run on the given input.

In the other direction, if a sentence is provable in a reasonable proof system, then the Turing machine which goes over all proofs in the system and checks whether they prove the sentence, will halt, and its halting implies that the sentence is indeed provable in the proof system.

What this shows is that Turing machines with an oracle for the halting problem have the same power as Turing machines with a provability oracle for any reasonable proof system.


Why is C's void type not analogous to the empty/bottom type? Wikipedia as well as other sources that I have found list C's void type as a unit type as opposed to an empty type. I find this confusing as it seems to me that void better fits the definition of an empty/bottom type.

No values inhabit void, as far as I can tell.
A function with a return type of void specifies that the function does not return anything and thus can only perform some side-effect.
A pointer of type void* is a subtype of all other pointer types. Also, conversions to and from void* in C are implicit.

I am not sure if the last point has any merit as an argument for void being an empty type, as void* is more or less a special case with not much relation to void.

On the other hand, void itself is not a subtype of all other types, which as far as I can tell is a requirement for a type to be a bottom type.

In C, void is used for multiple unrelated things. Depending on what it's used for, its meaning may be a unit type, an empty type, or something else.

When void is used by itself (as opposed to void*, a pointer to void), it's a unit type, i.e. a type with a single value. Functions that return void are said to “return nothing”, but what this really means is that they don't return any information. They return $0$ bits of information, which means that they return a value of a type that contains $2^0 = 1$ distinct values, i.e. a unit type.

This is not an empty type: a function that returns an empty type cannot return a value, since there is no value of that type. A function whose return type is empty can only loop forever, or abort the program, or raise an exception (longjmp) (or otherwise arrange not to return, e.g. by transferring control to another thread or process using functionality beyond standard C). To keep things confusing, it is conventional in C to use void in lieu of an empty type (C doesn't have an empty type).

The void type requires $0$ bits of storage. Because C insists on every object occupying a whole, nonzero number of bytes of storage, it's forbidden to create an object of type void, and there's a special syntax to return the void value (a return statement with the value omitted). There's no syntax that yields the value of type void, but that value is there whenever a function whose return type is void returns.

C does not have a bottom type in the sense of allowing any possible type. Even incomplete types specify the general nature of its values, e.g. pointers or structs or unions or functions. But void* is a pointer to any non-function type: it's the least element of the algebra of object pointer types, i.e. it's the bottom object pointer type. Unlike the general case of T* where T is some non-void type, void* is not the type of pointers to a value of type void, but the type of pointers to a value of unspecified type.


NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components} Consider the following decision problems:

$CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components}

$E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected components}

I'd like to show this two problem are in $NL$. I Know it's possible to guess a vertex from each connected component and then verify the connectivity of the component (by guessing paths to other vertices). But how can I verify all guessed vertices are different, when it's impossible to hold $k$ vertices on the work tape?

We can assume without loss of generality that the vertex set is $1,\ldots,n$.
Let us say that a vertex is minimal if it has the minimal value in its connected component. You can check that a vertex in minimal in NL by checking that it is not connected to any smaller vertex.

A graph has at least $k$ connected components iff there is a list $v_1 < v_2 < \cdots < v_k$ of minimal vertices. This shows that CONN is in NL. Since NL=coNL, it follows that E-CONN is also in NL.

Morale: if you want to make sure that you guessed $k$ distinct vertices, guess them in increasing order.

Since undirected connectivity is in L, we can actually count the number of connected components in L, by just going over all vertices, and counting how many of them are minimal.


Coordinated Attack Problem On The Arbitrary Graph Let  consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack.

It's well known  that Two Generals' Problem represents a version of the Consensus Problem with unlimited number of the stopping failures, I think this is the only reason why Two Generals' Problem and Generals' Problem (with $n$ generals) don't have solution.

There is a proof of lacking solution for Two Generals' Problem (can be found in the textbook of Lynch).

The following is the exercise from the textbook of Lynch, that I have not solved so far.

Show that a solution to the (deterministic) coordinated attack problem (Generals' Problem) for any nontrivial connected graph implies a solution for the simple graph consisting of two processes connected by one edge. (Therefore, this problem is unsolvable in any nontrivial graph.)

Apparently, there is a reduction from an edge case to graph. But how to show it mathematically rigorous?

Addendum:

Can I say something like this?
When we are given the primary problem of Two Generals and they initial values $a_i$ (inclination whether to attack or not), we in arbitrarily add more dummy generals with the only requirement if $a_1=a_0=a$ for primary problem set all dummy's general input to $a$, otherwise set arbitrary input value $b \in \{0,1\}$. Find the solution on the graph, the solution on the graph is the solution for the primary problem.

The easiest way to do the reduction is to decompose your graph into two pieces $G_1,G_2$ arbitrarily, let one general "play" $G_1$, and the other one $G_2$. Details left for you.


How are programming paradigms classified? When I started to learn about imperative programming and declarative programming it raised many doubts, like, how are structured, modular and object-oriented programming classified: declarative or imperative?

Do not be too obsessed with it. It is often only buzzwords covering a
fuzzy trend (from structured to object oriented) towards better
organization of programs, with somewhat different realizations in
different languages. It can appear in any programming paradigm,
whether imperative or declarative. They are intended to improve
readability of programs, good programming practice, maintainability,
code reuse in various guises, independence of program parts,
information hiding.

What is a lot more important is to understand the specific techniques
that can be used, their costs and benefits, the constraints they
create and the freedom they provide. The more interesting techniques
are based on formal mathematical analysis.

It involves a variety of more precisely definable concepts, such as
environments, scoping and binding of variables, typing systems,
modularity and interfacing, parameterization of code and modules,
exception handling ...

I would think you will be better off concentrating on these identified
technical issues than on more popular but fuzzier concept.


Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1 Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.

But main problem is N (Number of nodes in tree is 100000) So is their any better solution than O(N^2) as I currently have O(N^2) approach to do this problem using LCA between 2 nodes of tree.

So given a tree with N nodes and N-1 edges can we have a better algorithm ?

If there are a lot of large numbers on the edges I do not know, but if the number of different prime factors on the edges is limited there seems to be an efficient algorithm.

The approach is as in Longest path in an undirected tree with only one traversal.

Make the tree rooted, so you can work bottom up. In each node $v$ keep for each possible number $d$ the number of successor nodes in the tree that have a path up to $v$ with gcd $d$. If we move up in the tree we extend the paths of the children (taking into account the values on the edges) to the parent, and count the paths that connect two successors that run via the parent (if the ggd's are $1$).

Each node is visited only once, but there is quite some work between edges at each node.

Example.

At node $g$ we store $1$ incoming path with gcd $3\cdot 5$, and  $1$ incoming path with gcd $3\cdot 7$: $[3\cdot 5\to 1, 3\cdot 7 \to 1]$.
At node $h$ we store: $[5\to 1, 5^2\to 1, 7 \to 1]$.
At node $i$ we store: $[3\cdot 7\to 1, 5\to 1, 5\cdot 7 \to 1]$.

With this information we obtain zero paths via $g$ with gcd $1$, two paths via $h$ with gcd $1$, and one path via $i$ with gcd $1$.

We now move the path info upwards. One new path from $g$ to $j$ with gcd $3^2\cdot 7$, and we add the info from $g$ after performing the gcd with the last edge:  $[3\to 1, 3\cdot 7 \to 1, 3^2\cdot 7\to 1]$.
One new path from $h$ to $j$ with gcd $2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[5\to 2, 1 \to 1, 2\cdot 5\to 1]$.
One new path from $i$ to $j$ with gcd $3^2\cdot 5$, and we add the info from $h$ after performing the gcd with the last edge:  $[3\to 1, 5 \to 2, 3^2\cdot 5\to 1]$.

Altogether we store at $j$:  $[3\to 2, 3\cdot 7 \to 1, 3^2\cdot 7\to 1,5\to 4, 1 \to 1, 2\cdot 5\to 1, 3^2\cdot 5\to 1$. This info is bounded by the possible divisors of the edge labels.

We finally compute the `via' count at $j$ by considering the lists at pairs of children. Quite some work. All paths from $g$ and from $h$ have gcd $1$, so we count $3\cdot 4 = 12$. I count $6$ between $h$ and $i$, and $3$ between $g$ and $i$.


Maximum flow with constraints In a flow network, suppose we add constraints of the following type:

The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$.

Is maximum-flow with such constraints still solvable in polynomial time?
Is it possible to reduce it to a standard maximum-flow problem?
NOTE: I found a recent paper that studies network flow with  constraints, however, the constraints studied there are different:

"A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"
"A positive disjunctive constraint forces that for certain pairs of arcs at least one arc has to carry flow".

First a quick note, the flow entering a vertex is equal to the flow leaving. I'll just refer to it as the amount of flow through a vertex.

Second, note that we can say $a \leq b \wedge b \leq a$, thus we can add the constraint $a = b$ for two vertices.

Then we can re-use the NP-hard result from the paper that you quoted:

  "A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"

The reduction is done by putting two proxy vertices in the middle of the respective arcs, let's call them $a$ and $b$.

We then also add two vertices $a'$ and $b'$, directly connecting to the source, and add the constraints $a = a'$ and $b = b'$. Finally we add vertex $c$, and connect it to $a'$, $b'$  and the sink. Note that the flow through $c = a' + b' = a + b$.

We finish the reduction by adding constraints $c \leq a$ and $c \leq b$. Now $a+b \leq a$ and $a+b \leq b$ implies that either $a=0$ or $b=0$ (or both).


Best improvements to do to the DPLL SAT algorithm As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select the next variable, it just loops an array and gets the next unused  one). I have been reading papers on ways to improve it, but I'm a bit overwhelmed by the amount of optimizations one can do. I'm not looking to make an extremely efficient solver; just something that works better than a plain basic DPLL one. I have read about 2WL, VSIDS, and a handful more. Which optimizations will give me the most performance without overcomplicating things? The input with the most variables that I have to solve is of the order of 300, with 1500 clauses, if that is of any interest.

I apologize if something similar has been asked before, but I haven't found anything. I would appreciate any other tips if you guys have. Thank you.

The most improvement with the least effort will come from adding rapid random restarts to your solver.  DPLL is known to exhibit heavy-tailed behavior, producing both short and long search times for instances depending on initial search conditions.  Random restarts allow the solver to bail out of exponentially long searches of unfruitful assignments and give the solver more chances to find one of those short searches sooner.

Implementing two-watched-literals will produce the next big improvement because it eliminates a major backtracking cost.  Backtracking is done exponentially often in the worst case, so any improvements there offer unequivocal improvements in search speed.  Implementing two-watched-literals will require a significant overhaul of your solver, but it will teach you a lot about how real-world SAT solvers work.


An exact solution for biclique vertex-cover problem on a bipartite graph The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs).

It has been shown that "Biclique Vertex-Cover" is not fixed-parameter tractable unless P = NP in Covering Graphs with Few Complete Bipartite Subgraphs.

Most of the work in the literature proved the hardness of the problem in general/special cases. However, I need an exact algorithm for solving this problem on bipartite graphs. An approximate algorithm with a guarantee is also good (I'm aware of "Clustering and the Biclique Partition Problem", but it provided an approx solution for "Biclique Vertex Partition" not vertex-cover i.e. the provided solution is for disjoint bicliques not possibly overlapped ones).

Is anyone aware of an exact algorithm for "biclique vertex-cover" problem? Potentially, with time complexity analysis?

A naive algorithm, perhaps, would be starting from the whole bipartite graph to check for a biclique that covers all vertices (covering with one biclique). If not successful, we check subsets by removing one vertex and investigate if there exist two bicliques in this set that cover all vertices (trying to cover with two bicliques), and so on (trying to cover with more bicliques until reaching "k").

If you have an exact algorithm for the partitioning problem (perhaps one is mentioned in the paper describing the approximate algorithm?), you immediately have an exact algorithm for the covering problem.

First, observe that a partition is a valid cover.  Now suppose the partitioning algorithm reports an optimal partition with $k$ bicliques, and suppose to the contrary that there exists a cover $C$ with fewer than $k$ bicliques.  But any cover can be turned into a partition easily: Whenever two bicliques in the cover contain the same vertex, delete the vertex from one of them.  (This works because bicliques are hereditary: every induced subgraph of a biclique is also a biclique.)  This will result in a valid cover with at most as many bicliques as there were originally (it may cause a biclique to have zero vertices: In that case, the original cover was not minimal).  Repeat this vertex deletion step until all bicliques are pairwise vertex disjoint.  If we apply this to the cover $C$, then because we started with strictly fewer than $k$ bicliques and never increased the number of them that we have, we now have a partition with strictly fewer than $k$ bicliques, contradicting the known optimal solution from the partition solver.  Thus the optimal partition must have also been an optimal cover.


Reccurence of recursive function with unequal sizes of subproblems Given pseudocode:

X is an array

function FUN(X)
    l = length(X)
    if l <= 1 then
        PRINT("Hello")
        return
    end if
    p = l / 3
    FUN(X[1...p])
    FUN(X[(l-p+1)...l])
end function

I now want to get the reccurence of this pseudocode. At the moment I have $$T(n) = 2 \cdot T(\frac{n}{b})\cdot O(1)$$

but the problem is that I don't know how to handle the fact that the first recursive call has a subproblem size of $\frac{1}{3}$ and the second has a subproblem size of $\frac{2}{3}$. What is $\frac{n}{b}$ then?

Your timing function is $T(n)=2T(n/3)+1$, namely two recursive calls to one-third size problems plus a constant amount of time for the if test and the assignments. If you know the Master Theorem, the answer is immediate, namely $T(n)=\Theta(n^{\log_32})$. If you don't know the MT, it's not too difficult to see the answer by expansion:

$$\begin{align}
T(n) &= 2T\left(\frac{n}{3}\right)+1\\
 &= 2\left(2T(\frac{n}{3^2})+1\right)+1=2^2\ T\left(\frac{n}{3^2}\right)+2+1\\
 &=2^3\ T\left(\frac{n}{3^3}\right)+4+2+1 &\text{and, in general, we have}\\
&\dotsc\\
&=2^k\ T\left(\frac{n}{3^k}\right)+\left(2^{k-1}+\dotsm +4+2+1\right)
\end{align}$$
Now let $n=3^k$ and the result follows with a little algebra.


What is the difference between a Top type and a Unit type Wikipedia defines a Top type: (edited for readability)

  The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top

However, the article goes on to say:

  In C++: The pointer to void type can accept any non-function pointer, even though the void type itself is not the universal type but the unit type.

I don't understand this. In particular, given these two functions:

void foo(T1, T2, T3);
SomeType bar(T1, T2, T3);

I'd expect bar to be accepted wherever foo is accepted (in function pointers, as virtual methods, etc); which makes me think void is being treated as a supertype of SomeType.

Leaving C++ aside, I'd expect the same semantics from any language: any logic that expects a void could logically accept any other type.

So, given its properties, why is void usually called a Unit type, and how is it different from a Top type?

Let me first give the mathematical counterparts of the unit and the top type:

the unit type is the type $U$ such that for every type $X$ there is a unique map $X \to U$
the top type is the type $T$ such that every type $X$ is a subtype of $T$, written $X \leq T$

Thus we cannot speak of the top type unless we have subtyping. Not all type systems have subtyping, and in those there is no top type to speak of.

The unit type $U$ must be very small: since there is only one map $U \to U$, if we have $a, b: U$ then the two maps $x \mapsto a$ and $x \mapsto b$ must be equal, whence $a = b$. We should be more precise about what "equal" means, and we should discuss non-terminating computations, but let's keep things simple. On the other hand, there must be at least one element of $U$, or else there can be no map $\mathtt{int} \to U$. (NB: We can only have a map $S \to \emptyset$ when $S$ itself is the empty set.)

The type called $\mathtt{void}$ isn C/C++ has the property of the unit type. It is a mistake to think that a function returning $\mathtt{void}$ "returns nothing". It actually returns precisely one thing, but because the unique thing that it returns is unique and does not carry any information beyond the fact that the function actually returned, we never make the thing explicit. Thus programmers never see it, and so they end up thinking it isn't there. There are programming languages in which the unique element of the unit type can be made explicit. Can there be a function that returns nothing? Yes, it's a function that does not return at all (if it did, it would have to return something) – it is a function which raises an exception! Raising an exception is not "returning".

The top type $T$ must be in some sense very large because every other type is a subtype of $T$. Note that $X \leq T$ does not necessarily mean that there is an injective map $X \to T$, nor does the fact that there is a map $X \to T$ imply $X \leq T$. There are many kinds of subtyping and it is really quite impossible to tell  more precisely what "large" means without knowing what sort of subtyping we are talking about.

For example, in some languages there is subtyping between numerical types, so that for instance $\mathtt{byte} \leq \mathtt{int} \leq \mathtt{float}$. Here $\mathtt{float}$ could be the top type, and it is the "largest" numerical type.

On the other hand, structural record subtyping says that the record type $R = \{\ell_1 : X_1, \ldots, \ell_m : X_m\}$ is a subtype of $Q = \{k_1 : Y_1, \ldots, k_n : Y_n\}$ when every field $k_j : Y_i$ has a corresponding field $\ell_i : X_i$ such that $k_j = \ell_i$ and $X_i \leq Y_j$. In words, $R \leq Q$ means that an $R$-record may be seen as a $Q$-record because it has all the fields that a $Q$-record should have, and possibly more. Under this view the top type is the empty record $\{\}$, which is isomorphic to the unit type!

You asked concretely about subtyping of functions. The basic rule there is: if $X_2 \leq X_1$ and $Y_1 \leq Y_2$ then $(X_1 \to Y_1) \leq (X_2 \to Y_2)$ (notice the reversal of inequality for $X_1$ and $X_2$). In your particular case we have $X_1 = X_2 = T_1 \times T_2 \times T_3$, $Y_1 = \mathtt{SomeType}$ and $Y_2 = \mathtt{unit}$ (I refuse to write "void" for something that is not the empty type and C/C++ can go sulk in the corner). So the question comes down to $\mathtt{SomeType} \leq \mathtt{unit}$, i.e., should the unit type be the top type? Well, this depends on what "subtype" means, as I tried to explain above. In C and C++ subtyping is expressed through a system of implicit coercions, so you'd have to open a book on C and find out whether there is supposed to be an implicit coercion from an arbitrary type to the unit type. It's a matter of language definition.


Ideal number of participants for evaluation of development approach / software architecture For my thesis, I have created a development approach (consisting of schemes, an application template and prototype code) that should make it easier to develop and adapt applications for a specific platform.

I have conducted interviews with developers of that platform to evaluate my approach. There have been 5 interviewees so far and the feedback that I got from them is sufficient for my scope, I would say.

However, in my thesis I would like to justify my decision that 5 evaluators are enough. Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?

I know Nielsen's work about heuristic usability evaluation which says that with 5 participants, you discover around 75% of all problems in software usability / UI testing.

But as I said, my approach is no specific software product that has to be evaluated, but only the model itself, which is why I'm looking for research in that area.

"Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?"

There is a statistical method to calculate the correct sample size for an experiment.
This method is called a "power analysis" [1]. It calculates the minimum sample size needed to verify that an experiment's results are statistically significant.  This approach assumes that you have at least two groups.  A control group and an experimental group (i.e. control group uses the platform without your modifications, experimental group uses the platform with your modifications).

Thus, while there is a scientific process to calculate the correct sample size this approach is probably overkill for your study. Nielsen [2] states that heuristic evaluation is just a "cheap and quick" method for easy evaluation. As such, I believe you can justify a sample size of 5 by citing Nielsen.  However, if you do want to standardize your evaluation process and use a statistical approach I encourage you to look into power analysis.

You may be interested in this online tool for calculating power.

http://en.wikipedia.org/wiki/Statistical_power
http://www.nngroup.com/topic/heuristic-evaluation/


Asymptotic approximation of a recurrence relation (Akra-Bazzi doesn't seem to apply) Suppose an algorithm has a runtime recurrence relation:

$   T(n) = \left\{
     \begin{array}{lr}
       g(n)+T(n-1) + T(\lfloor\delta n\rfloor ) & : n \ge n_0\\
       f(n) & : n < n_0
     \end{array}
   \right.
$

for some constant $0 < \delta < 1$. Assume that $g$ is polynomial in $n$, perhaps quadratic. Most likely, $f$ will be exponential in $n$.

How would one go about analyzing the runtime ($\Theta$ would be excellent)? The master theorem and the more general Akra-Bazzi method do not seem to apply.

One possible approach might be by analogy to differential equations.  Let $T'(n) = T(n)-T(n-1)$.  Here $T'(n)$ is a discrete analog of the first derivative of $T(n)$.  We get the following relationship:
$$T'(n) = T(\lfloor \delta n \rfloor) + g(n).$$
The continuous analog of this is the differential equation
$$t'(x) = t(\delta x) + g(x),$$
or, if you prefer to see it written differently:
$${d \over dx} t(x) = t(\delta x) + g(x).$$
That's a differential equation.

Now you could try to solve the differential equation for the continuous function $t(x)$, then hypothesize that a similar function will be the solution to your original recurrence relation, and try to prove your hypothesis.  At least, this is one general approach you could follow.

I've forgotten everything I once knew about differential equations, so I don't know the solution that differential equation, but maybe you will be able to solve it by reviewing all the techniques for solving differential equations.


approaching dynamic programing for problem I want to find a solution to a problem that asked before.
in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-edgest

I have a directed graph with colored edges (red & blue) that may contain cycles. The question is to write an algorithm given two vertices (s,t) that finds the path with the minimal number of color changes between s and t (if such path exists).
$

suggesting a reduction to solve the problem.
I want to find an optimal structure for the problem by:
$opt(v) = \min_{u \in In(v)}(opt(u) + f(u,v))$
$f(u,v)$ define:
$f(u,v) = \begin{cases}  1, & \text{the color of (u,v) same as the color that appears more}, \\
-1, & \text{the color of (u,v) the color different from the color that appears more}.\\
1, & \text{else}
\end{cases}
$
the problem with that formula is that the optimum of the neighbors, not gratitude the optimum solution for  $v$ because considering v that have 1 neighbor with a blue edge that has a path with the same blue and red edges and another path with 1 more red edge than my structure return 1 however there is a path with 0 alterations.
then I thinking to save for all the vertices 3 paths, optimum path most optimum path with more blue and path with more red but its seem to complicated to build a formula with that filed.

This problem is easily solved if you:

transform the input graph $G=(V,E)$ by either creating $n-1$  "levels", where each level is a copy of $G$ and edges go from one level to the next; or
consider the line graph $G'$ of $G$ instead (so that edges in $G$ become vertices in $G'$, and two vertices in $G'$ are adjacent if the corresponding edges in $G$ share an endpoint); or
For each color $c \in \{red, blue\}$, identify the maximal components $C$ of $G$ such that connectivity within $C$ is preserved using only edges of color $c$.

If you insist in using a dynamic programming algorithm, then the problem can be solved in $O(m)$ time using a Dijkstra-like algorithm.
Let's start with some definitions:
Given a color $c \in \{red, blue\}$, define a $c$-ending path as a simple path $P$ such that either 1) $P$ is empty, or 2) $P$ ends with an edge of color $c$.
Given a path $P$, let $\ell(P)$ be the number of color changes encountered when traversing $P$.
We will say a path $P$ from $s$ to $v$ is a shortest $c$-ending path if there exist no other $c$-ending path $P'$ such that $\ell(P') < \ell(P)$.
We will call $\eta(v,c)$ the value of $\ell(P)$, where $P$ is a shortest $c$-ending path from $s$ to $v$.
According to the above definitions $\eta(s, red) = \eta(s, blue) = 0$.
Moreover, the following suboptimality property holds:
Claim: Let $P$ be any shortest $c$-ending path from $s$ to $v$, let $u \in P$.
The subpath $P[s:u]$ of $P$ going from $s$ to $u$ is a shortest $c'$-ending path where $c'$ is the color of the incoming edge in $u$ (if $u=s$ then $c'$ is any color).
Proof:
Assume that $u \neq v$, otherwise the claim is trivial.
Let $c''$ be the color of the edge leaving $u$ in $P$.
Suppose towards a contradiction that $P[s:u]$ is not a shortest $c'$-ending path.
Let $P'$ be a shortest $c'$-ending path from $s$ to $u$, and notice that $Q = P' \circ P[u:v]$ is a (not necessarily simple) path from $s$ to $v$.
$Q$ ends with an edge of color $c$ and we have:
$$
\ell(P) = \ell(P[s:u]) + 1_{c' \neq c''} + \ell(P[u:v])
> \ell(P') + 1_{c' \neq c''} + \ell(P[u:v])
= \ell(Q),
$$
contradicting the fact that $P$ is a shortest $c$-ending path. $\square$
For each node $v$ we will maintain two upper bound $\tilde{\eta}(v, red)$ and $\tilde{\eta}(v, blue)$ on $\eta(v, red)$ and $\eta(v, blue)$, respectively. Initially $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue)=\eta(s, red) = \eta(s, blue) = 0$ while, for $v \neq s$, $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue) = +\infty$.
Finally, we will maintain a priority queue $Q$ in which keys are pairs $(v,c)$ where $v$ is an unmarked vertex and $c$ is a color, and the corresponding priority will be $\tilde{\eta}(v, c)$. Initially all pairs $(v,c)$ are in the queue.
The algorithm proceeds as follows: while $Q$ is not empty, extract $(u,c)$ from $Q$; for each edge $e=(u,v) \in E$ let $c'$ be the color of $e$ and set $\tilde{\eta}(v, c) = \min\{\tilde{\eta}(v, c), \tilde{\eta}(u, c) + 1_{c \neq c'} \}$ (thus possibly updating the priority of $(v,c)$, if such a pair is in $Q$).
It is clear by construction that all values $\tilde{\eta}(v, c)$ are upper bounds to $\eta(v,c)$ as claimed. We now prove that, when the pair $(v,c)$ is extracted from $Q$, $\tilde{\eta}(v, c)$ is also a lower bound to $\eta(v,c)$, thus proving that $\tilde{\eta}(v, c) = \eta(v,c)$.
Claim: When $i$-th pair $(v_i,c_i)$ is extracted from $Q$, $\tilde{\eta}(v, c) \le \eta(v,c)$.
Proof:
Let $i$ be the smallest value such that, when $(v_i, c_i)$ is extracted from $Q$ we have $\tilde{\eta}(v_i, c_i) > \eta(v_i,c_i)$.
Since the values $\tilde{\eta}(v_i, c_i)$ never decrease during the execution of the algorithm and cannot become negative we know that $v_i \neq s$.
Let $P$ be a shortest $c_i$-ending path from $s$ to $v_i$ and consider the last vertex $x$ such that the incoming edge in $x$ in $P$ has color $c_x$ (if $x=s$ let $c_x$ be any color) and $x=v_j$ and $c_x=c_j$ for some $j<i$ (notice such a vertex always exists since the above conditions are satisfied for $x=s$).
Let $y$ be the vertex following $x$ in $P$ and $c_y$ be the color of the incoming edge.
Since $(v_i, c_i)$ was extracted instead of $(y, c_y)$ we must have:
$$
\tilde\eta(v_i, c_i) \le \tilde\eta(y, c_y)
$$
Moreover, since $(x, c_x)$ was already extracted from $q$ we have:
$$
\tilde\eta(y, c_y) \le \tilde\eta(x, c_x) + 1_{c_x \neq x_y} = \eta(x, c_x) + 1_{c_x \neq x_y}
$$
And, by suboptimality:
$$
\eta(x, c_x) + 1_{c_x \neq x_y} =
\eta(y, c_y) \le \eta(v_i,c_i),
$$
which is a contradiction $\square$.
The sought quantity is then $\min\{\tilde\eta(t,red), \tilde\eta(t,blue) \}$.
Finally, notice that the the priority can only decrease in $Q$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are $\{0, 1, \dots, n\} \cup \{ +\infty \}$. Therefore it is possible to implement a priority $Q$ that requires $O(n+m) = O(m)$ time to perform all the required $O(n)$ insertions and $O(m)$ priority updates.


Given a Turing machine , How to construct a efficient boolean circuit? The proof of $P\subseteq P_{\\poly}$, Let $M$ is a Turing machine with $T(n)$ is running time and  goal here is to design a boolean circuit of size $O(T(n))$ (for more detail see Arora and Barak page no -105 ).

The idea is that you can compute configuration $c_i$ from configuration $c_{i−1}$ by examining the content of 3 adjacent cells  (i.e. by constant size circuit).

First Case :
Let us consider that snapshot is the configuration of Turing machine i.e. requires $O(T(n))$ size.

Number of variables $x_{i,j}$, where $i$ represents a row in table and $j$ represent the colum( cook -levin reduction proof)  are $T(n) \times T(n)$ many. Now when we combine the constant size circuits of all variables then size of the resultant circuit is going to be $T(n) \times T(n)$ ,which is polynomial but  my goal was to design a circuit of size $O(T(n))$.

Second case : Let us consider that snapshot is  machine's state and symbols read by all heads. let us consider they are $z_1,z_2 \cdots z_{T(n)}$ and size of each $z_i$ is constant string. To compute a snapshot $z_{i+1}$for this computation I need $z_i$, all old head positions and current head symbol .This all are constant size string, so I need only constant size circuit to encode the computation (current head position only depends upon the three symbol in the table in cook - levin theorem, or In other words, it is a map say $M$: $\tau^3 \mapsto \tau$, $\tau$ is a tape alphabet. So the total size of the circuit is $O(T(n))$

Question : To design a boolean circuit of size $O(T(n))$ for Turing machine $M$ with running time $T(n)$?

I'm not sure whether this can be done. However, using oblivious Turing machines, we can get a circuit of size $O(T(n)\log T(n))$. According to the proof sketch of Theorem 6.7 in the draft of Arora–Barak, given a Turing machine running in time $T(n)$ we can construct a Turing machine running in time $O(T(n)\log T(n))$ in which the head movements only depend on $n$. Such a Turing machine is known as an oblivious Turing machine. This means that you only need to update one specific cell per time step, and the result is a circuit of size $O(T(n)\log T(n))$ (details left to you).


A dynamic programming problema on containers and product We have two production lines - product and container (two integer arrays product_list[N] and container_list[M]).
If the volume of a container is equal or larger than that of a product, then we could put the product into that container.

We want to put as many products into containers as possible.

We can pick any initial position of products (any i in product_list array), and match each container one by one. We can't skip product but we can skip containers. No recurring of arrays i.e. product line won't go back if reach the end.

My solution is that, start from first product until last product (for i = 0; i < N), then match the container list from 1st to the last (for j = 0; j < M).
For each starting point i, count the number of matched products (count_array[i]+1 if container_list[j] >= product_list[i]).
Finally output the maximum of the count array.

I believe my algorithm isn't optimal, but I can't come up with a better way to do this problem in dynamic programming.

Any help will be appreciated! Thanks for everyone reading this problem!

Here is one approach, I could think of.

$T(x, y) = $ The maximum number of products which could be put into containers if we start at position $x$ in container line, whereas position $y$ in the product line.

If $size(C_x) >= size(P_y)$ we can either choose or skip the container. Else if the size of container is smaller, since we cannot skip the product, we would have to skip the container.

Hence, the recursion would be:
\begin{equation}
  T[x, y]=\begin{cases}
    max(1 + T[x+1,\hspace{1mm} y+1], \hspace{2mm} T[x+1,\hspace{1mm} y]), & \text{if $size(C_x) >= size(P_y)$}.\\
    T[x+1,\hspace{1mm}y], & \text{otherwise}.
  \end{cases}
\end{equation}

Starting from the end of both the arrays, $$max(T[1,i]) \hspace{2mm}: \hspace{2mm} 1<=i<=n$$ should have the required result.

http://ideone.com/3dsrZu


Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$?

Clearly, there are simple exponential time algorithms, but I'm wondering if any algorithms polynomial in $\log n$ are known, or at least polynomial in $i + \max \{a_j | 1 \leq j \leq i\}$. I was thinking along the lines of Yuval Filmus's answer, but could not make it work for the distinct integer case in polynomial time.

I'll show how to solve the case $k=2$ and without the constraint that all factors have to be distinct, and let you generalize and take care of the constraint. Each decomposition corresponds to a choice of non-negative integers $b_1,c_1,b_2,c_2,\ldots,b_i,c_i$ such that $a_j = b_j + c_j$. The number of such decompositions is thus $(a_1+1)\cdots(a_i+1)$.

There might be a slight problem with that, depending on what you mean by decomposition. Consider for example $n=2$. According to the count above, we get the two decompositions $1 \cdot 2$ and $2 \cdot 1$. Perhaps we want to count them as the same decomposition. In this case, we need to roughly divide the count above by 2. Why only roughly? Since if $n = m^2$, then the decomposition $n = m \cdot m$ only appears once. So if $n$ is a square, we need to divide the count above by 2, and add 1/2 (why?).

If we want to count the number of decompositions in which both factors are distinct, we need to check whether $n$ is a square, and then adjust our counts accordingly. Details left to the reader.

For general $k$, if you are OK with ordered decompositions (and ignoring the constraint that all factors be distinct), then all you need do is figure out how many non-negative integer solutions exist for the equation $a = b_1 + \cdots + b_k$. If you care about unordered decompositions (so $1\cdot 2$ and $2\cdot 1$ are considered the same) or require all factors to be distinct, you have more work to do. Inclusion-exclusion type formulas could be helpful.


Calculator for time complexity of recursive functions Is there an online tool that returns the time complexity of recursion functions?
For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$.
I tried using Wolfram Alpha, but it doesn't return the above result I was looking for.

Wolfram Alpha is giving you a more accurate estimate, $T(n) \sim 2n$. However, it can also give you the weaker estimate $T(n) = O(n)$ you are after:

Just click on Show weaker bound.


Creating a large tuple from smaller tuples via a monad or applicative Suppose I have a term $a :\alpha$ of the Simply-Typed Lambda Calculus (in the following, $\alpha, \beta, \gamma$ stand for arbitrary types) and I want to lift it to a term
$\lambda x_{\beta}. \;(x, \, a)$
I could use a function $\lambda z_{\alpha}, x. \;(x,\, z)$.
Suppose we then form $(b, a) : \beta \times \alpha$, by applying $\lambda x_{\beta}. \;(x, \, a)$ to $\,b_{\beta}$.
We might want to add $c$ to the beginning of this to form $(c, b, a) : \gamma \times \beta \times \alpha$. We could do this (here $\pi_1$ and $\pi_2$ are projections)) by having a function $\lambda z'_{\beta \times \alpha}, z. \,(z,\, \pi_1 z',\, \pi_2 z')$. And again, we could cook up a function to form $(d,\, c,\, b,\, a)$ and $(e,\,d,\, c,\, b,\, a)$ (so on and so forth).
I could do things in the way above; however, I wondered whether there was a way of doing this kind of operation via an applicative or a monad. Then I could (ideally) use the operations of the monad or applicative, to lift term $a$ (perhaps into $\lambda x.\,(x, \, a)$, and then form these tuples $(b, a), (c, b, a), (d, c, b, a)$, etc, by the operations of the monad or applicative.
If you know a way of doing this I would be very interested.

(Note, this requires a more sophisticated type theory such as System Fω to encode)
This idea is captured by the concept of an indexed monad (and in turn indexed applicative/functor).
Using Haskell as lingua franca, we talk about a typeclass:
class IxMonad (m :: n -> n -> * -> *) where
  ireturn :: a -> m i i a
  ibind :: m i j a -> (a -> m j k b) -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  ireturn :: a -> m i i a
  ijoin :: m i j (m j k a) -> m i k a
  -}

An action m i j a makes a connection "from" an index i "to" an index j, and wraps some type a. Actions can be composed only if the respective indices "line up". Sort of like how horizontal oidification turns a monoid into a category: morphisms can be composed only if their endpoint objects "line up".
Analogous definitions of an indexed functor and an indexed applicative can be made:
class IxFunctor (m :: n -> n -> * -> *) where
  ifmap :: (a -> b) -> m i j a -> m i j b

class IxApplicative (m :: n -> n -> * -> *) where
  ipure :: a -> m i i a
  iap :: m i j (a -> b) -> m j k a -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  iunit :: () -> m i i ()
  iprod :: (m i j a, m j k b) -> m i k (a, b)
  -}

Say we wanted to "output" entries of some type, while keeping a type-theoretic witness of how many entries there are, we could define an indexed writer monad.
Here's definitions of natural numbers used to track length, and a length-indexed "log" datatype:
data N = Z | S N

data Vec (n :: N) (a :: *) where
  Nil :: Vec 'Z a
  Cons :: a -> Vec n a -> Vec ('S n) a

In an indexed monad, the usual intuition is that the indices i/j describe the "state" of the system: an action brings the system from "state i" to "state j". Here we'll be using the index to track how many entries we've written to the "log", and for completely technical reasons (to do with making the typechecker happy in an easy way), the left index will be the output log length, and the right index will be the input log length:
type family Add (n :: N) (m :: N) :: N where
  Add 'Z m = m
  Add ('S n) m = 'S (Add n m)

data IxWriter w i j a where
  IxWriter :: Vec k w -> a -> IxWriter w (Add k i) i a

instance IxMonad (IxWriter w) where
  ireturn x = IxWriter Nil x
  ibind (IxWriter xs x) f = case f x of
    IxWriter fs y -> iwappend xs fs y
    where
      iwcons :: w -> IxWriter w i j a -> IxWriter w ('S i) j a
      iwcons p (IxWriter qs z) = IxWriter (Cons p qs) z

      iwappend :: Vec k1 w -> Vec k2 w -> a -> IxWriter w (Add k1 (Add k2 i)) i a
      iwappend (Cons p ps) qs z = iwcons p $ iwappend ps qs z
      iwappend Nil qs z = IxWriter qs z

Then we can define the "logging" action, and an interpreter for our effect:
itell :: Vec k w -> IxWriter w (Add k i) i ()
itell ps = IxWriter ps ()

runIxWriter :: IxWriter w i 'Z a -> (Vec i w, a)
runIxWriter (IxWriter Nil x) = (Nil, x)
runIxWriter (IxWriter (Cons p ps) x) = case runIxWriter (IxWriter ps x) of
  (qs, r) -> (Cons p qs, r)

With this we can keep track of exactly how many entries we've logged:
case runIxWriter $
  itell (Cons 1 Nil) `ibind` \_ -> itell (Cons 2 Nil) `ibind` \_ -> itell (Cons 3 Nil)
of (Cons a (Cons b (Cons c Nil)), x) -> (a, b, c, x)
{- pattern match is valid and complete because we
   statically know it's a Vec ('S ('S ('S 'Z))) Integer -}

Here we used the graded monoid of finite sequences (and thus all our logs are of the same type). In theory we could have used any monoid graded by any other monoid, (for example the monoid of heterogeneous lists, graded by the monoid of lists of types -- if we wanted to be able to talk about heterogeneous tuples)


Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy? For example:
This looks like a context free grammar:
 →
 →  |
 →  |
 →  | c

but it can be reduced to this regular language:
 →  |
 →  |
 →  | c

I want to know if it is possible or not and why

It is not possible: it is undecidable whether a context-free grammar describes a regular language. For a proof, see e.g. Undecidable Problems for Context-free Grammars by Hendrik-Jan Hoogeboom.


Defining if a language is regular $L_4 = \{ w | w \text{ does not contain symbol a immediately followed by symbol b} \} $

where: $ \Sigma = \{ a, b, c \} $

So far I believe I have a defined regular grammar for this language, however I am having trouble coming up with an equivalent regular expression.

$<Language\_4> ::= a <AOrC> $

$<Language\_4> ::= b <Language\_4> $

$<Language\_4> ::= c <Language\_4> $

$<Language\_4> ::= \epsilon $

$<AOrC> ::= a <Language\_4> $

$<AOrC> ::= c <Language\_4> $

$<AOrC> ::= \epsilon $

Via a standard regex grammar this could be done via a lookahead, however I don't believe that the lookahead operation is a valid regular language operation.  I'm having trouble proving that if it is true though.

This is for a homework assignment, so I'm not expecting a full answer just some pointers in the right direction.

Edit

I went through this set of answers:
How to convert finite automata to regular expressions?

I then used Arden's Lemma as it seemed the most straight-forward.

First I defined:

$Q_0 = aQ_1 \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

$ Q_1 = cQ_0 \cup aQ_1 \cup \epsilon $

Apply Arden's Lemma:

$ U = a $,
$ L = Q_1 $,
$ V = cQ_0 $

Then I get:

$Q_1 = a * c Q_0 \cup \epsilon $

By then substituting $Q_1$ into $Q_0$ I get:

$Q_0 = a[a*cQ_0 \cup \epsilon] \cup bQ_0 \cup cQ_0 \cup \epsilon $

$Q_0 = \underbrace{(aa * ac \cup b \cup c)}_U \underbrace{Q_0}_L \cup \underbrace{a \cup \epsilon }_V $

$Q_0 = (aa * ac \cup b \cup c)* a$

Is this a correct application of the lemma?

EDIT 2

I've tested the regex more and it doesn't match the desired language.  I think there may be an error in my application of the lemma. I'm going to try the application again in case I missed something.

Hint: Here are a few easier languages to practice on:

Every occurrence of the symbol $a$ is followed by a non-$a$ symbol. (Hint: every $a$ occurs in the context of $ab$ or $ac$.)
No occurrence of the symbol $a$ is followed by another $a$. (The only difference from 1 is that a word could end with $a$.)
Every occurrence of the symbol $a$ is followed by a non-$b$ symbol. (Hint: what are the possible contexts of $a$?)
Your language. (Combine the answers to 3 and 2.)


Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$ So I'm assuming everyone's familiar with the definition of Big-O:
\begin{align}
    ∃c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in N, n \geq n_0 ⇒ g(n) ≤ cf(n)
\end{align}

Here is a variation of this: $\text(Little-O)$:
\begin{align}
\text{Let $f, g : \mathbb{N} → \mathbb{R^{≥0}}$. We say that $g$ is little-oh of $f$, and write $g ∈ o(f)$, when:}\\ \forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)
\end{align}

As you can see, this is a stronger property than Big-O, in the sense that if $g \in o(f)$, then $g \in \mathcal{O(f)}$. Basically, we switch to universal quantification leading to a more powerful claim. In general, if the statement $\forall c \in \mathbb{R^+}, P(c)$ is true, then $\exists c \in \mathbb{R^+}, P(c)$ is also true. While $g \in \mathcal{O(f)}$ says (colloquially) that “it is possible to scale up $f$ so that it eventually dominates $g$,” $g \in o(f)$ says that “no matter how you scale $f$ (up or down), it will always eventually dominate $g$.” Or, in terms of rates of growth, $g \in \mathcal{O(f)}$ means that $g$ grows at most as quickly as $f$, while $g \in o(f)$ means that $g$ grows strictly slower than $f$. I hope you get my gist.

Can someone please prove the following challenge question for me? It would be much appreciated and I've been at it for a long time now.

Prove the following statements about Little-o:

Prove that for all positive real numbers $a$ and $b$, if $a<b$ then $n^a \in o(n^b)$.
Prove that for all functions $f, g : \mathbb{N} → \mathbb{R^+}$, if $g \in o(f)$ then $f \notin \mathcal{O(g)}$.

I see that in the $2^{nd}$ part they've restricted the range of $f$ and $g$ to exclude $0$ and that we are to use only the definitions of Little-o and Big-o in order to prove both statements.

For positive functions $f,g\colon \mathbb{N} \to \mathbb{R}_+$, you can show that

$f(n) = o(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
$f(n) = O(g(n))$ iff $\limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$.

Using this, it is not hard to prove the two statements. Once you have done that, try translating your proofs to the definitions you were given.


Time complexity of Prim's algorithm There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix).

As far as I have understood,that is because we have to ckeck all the nodes per every node, that is, when checking the first node's best edge, we have to check edges from the current node to all other nodes. That makes $(n-1)$ edges at most. We check this for all nodes, so it would be n*(n-1) edges to check at most.

So why is the time complexity $O(n^2)$?

In addition, why don't we consider the edges which create a loop and why don't we ommit them in the algorithm? Does that make any difference in the time complexity?

The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$

The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity

For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$


Solving the recurrence T(n) = 3T(n-2) with iterative method It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given:

$$T(n) = 3T(n-2)$$

My first step was to iteratively substitute terms to arrive at a general form:

$$T(n-2) = 3T(n-2 -2) = 3T(n-4)$$
$$T(n) = 3 *3T(n-4)$$

leading to the general form:

$$ T(n) = 3^k T(n-2k) $$

Now I solve $n-2k = 1$ for $k$, which is the point where the recurrence stops (where $T(1)$) and insert that value ($n/2 - 1/2 = k$) into the general form:

$$T(n) = 3^{n/2-1/2}$$
$$T(n) = O(3^n)$$

I'm not sure about that last step:

I would just "argue" that as $n \to \infty$ one can ignore $-1/2$ and $n/2 \to n$ ?
Is that assumption correct?

Note that $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. So the $-\frac 12$ indeed becomes a constant factor that is absorbed by the $O()$, but $\frac n2$ in the exponent changes the base and changing the base changes the $O$-class.

The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.


Is $EVEN-SAT$ $NP$-hard? I'm looking for an $NP$-hardness proof for the following variant of $SAT$:
$$
EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\}
$$
I've been playing around with gadgets for a while, but I haven't been able to construct a reduction. Still, I feel like there should be one. Help!

$\textsf{EvenSat}$ is $\oplus P$-Complete (pronounced "Parity $P$"). The way to see this is (i) that it is the complement of $\textsf{OddSat}$, which is "the" natural $\oplus P$-Complete problem in the same way $\textsf{Sat}$ is "the" natural $\mathcal{NP}$-Complete problem, and (ii) $\oplus P$ is closed under complement.
The Valiant-Vazirani Theorem gives a randomized Cook reduction (i.e., a many-one reduction) with a one-sided error probability of $\mathcal{O}(1/n)$ from $\textsf{Sat}$ to $\textsf{EvenSat}$. That is, $\textsf{EvenSat}$ is $\mathcal{NP}$-Hard under randomized reductions. This is why the Valiani-Vazirani Theorem is usually stated as $\mathcal{NP}\subseteq \mathcal{RP}^{\oplus P}$.
We have $\mathcal{RP}^{\oplus P}\subseteq P^{\#P}$, so VV's Theorem is a bit tighter than what you would get from Toda's Theorem.
It is unlikely that $\textsf{EvenSat}$ is $\mathcal{NP}$-Complete, because then the polynomial hierarchy collapses to the first level, $PH=NP$. It is an open question whether $NP$ and $\oplus P$ are comparable, so far there is only oracle evidence that they are incomparable. (I don't know whether it is generally conjectured that Valiant-Vazirani can be derandomized from $\mathcal{NP}\subseteq\mathcal{RP}^{\oplus P}$ to $\mathcal{NP}\subseteq \mathcal{P}^{\oplus P}$. In that case, since $P^{\oplus P}=\oplus P$, we would have $\mathcal{NP}\subseteq \oplus P$. If I read [1] correctly, then it is not generally conjectured, since it would collapse the polynomial hierarchy)
[1] Dell, Holger, et al. "Is Valiant–Vazirani’s isolation probability improvable?." computational complexity 22.2 (2013): 345-383.


$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1 $L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^R = w, |w| = n \}$

Informally x is palindrome of length n

where $\Sigma = \{0,1\}$

I'm having a hard time understanding this could someone please explain.

For $n = 1$

$L_1 = (0+1)^*(0+1)^*$ (Why? What does this mean?)

$L_1^c = ?$ (What would the compliment mean)

For $n = 2$

$L_2 = (0+1)^*(00+11)(0+1)^*$

$L_2^c = (10)^*(\epsilon + 1) + (01)^*(\epsilon + 0)$

I get how regexes work I just don't understand how $L_1$ is the regex for palindrome of length one. Not sure what the compliment means. Same for $L_2$

According to the description $w$ is a palindrome of length $n$, and not the complete string $x$. A palindrome is a string that will be the same when reversed. For each length $n$ there are of course finitely many palindromes (as there are only finitely many strings of that length).

The language consists of all palindromes with given length, with arbitrary strings before and after. The palindromes can be listed,  and "hard-wired" in the expression.

$L_1 = (0+1)^*(0+1)(0+1)^*$,
$L_2 = (0+1)^*(00+11)(0+1)^*$,
$L_3 = (0+1)^*(000+010+101+111)(0+1)^*$, ...

The complement is added to see how many strings are not of the given form. Any nonempty string will contain a palindrome of length 1 of course. Hence $L_1^c= \{\varepsilon\}$.

Strings that do not contain $00$ or $11$ must have alternating $0$ and $1$'s,hance the $(01)^*$ etc.