How to understand the SR Latch I can't wrap my head around how the SR Latch works.
Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q'$.

However, both R and S require input from the other's output, and the other's output requires input from the other other's output. What comes first the chicken or the egg??

When you first plug this circuit in, how does it get started?

A flip-flop is implemented as a bi-stable multivibrator; therefore, Q and Q' are guaranteed to be the inverse of each other except for when S=1, R=1, which is not allowed.  The excitation table for the SR flip-flop is helpful in understanding what occurs when signals are applied to the inputs.

S R  Q(t) Q(t+1)
----------------
0 x   0     0
1 0   0     1
0 1   1     0
x 0   1     1

The outputs Q and Q' will rapidly change states and come to rest at a steady state after signals have been applied to S and R.

Example 1: Q(t) = 0, Q'(t) = 1, S = 0, R = 0.

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 1)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

Since the outputs did not change, we have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 2: Q(t) = 0, Q'(t) = 1, S = 0, R = 1

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(1 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t))  = NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(1 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  =  NOT(0 OR 0) = 1

We have reached a steady state; therefore, Q(t+1) = 0, Q'(t+1) = 1.

Example 3: Q(t) = 0, Q'(t) = 1, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 1) = 0
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 0) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 0) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 4: Q(t) = 1, Q'(t) = 0, S = 1, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(1 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(1 OR 1) = 0

We have reached a steady state; therefore, Q(t+1) = 1, Q'(t+1) = 0.

Example 5: Q(t) = 1, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 1) = 0

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 0) = 1
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

We have reached a steady; state therefore, Q(t+1) = 1, Q'(t+1) = 0.

With Q=0, Q'=0, S=0, and R=0, an SR flip-flop will oscillate until one of the inputs is set to 1.

Example 6: Q(t) = 0, Q'(t) = 0, S = 0, R = 0

State 1: Q(t+1 state 1)  = NOT(R OR Q'(t)) = NOT(0 OR 0) = 1
         Q'(t+1 state 1) = NOT(S OR Q(t)) =  NOT(0 OR 0) = 1

State 2: Q(t+1 state 2)  = NOT(R OR Q'(t+1 state 1)) = NOT(0 OR 1) = 0
         Q'(t+1 state 2) = NOT(S OR Q(t+1 state 1))  = NOT(0 OR 1) = 0

State 3: Q(t+1 state 3)  = NOT(R OR Q'(t+1 state 2)) = NOT(0 OR 0) = 1
         Q'(t+1 state 3) = NOT(S OR Q(t+1 state 2)) =  NOT(0 OR 0) = 1

State 4: Q(t+1 state 4)  = NOT(R OR Q'(t+1 state 3)) = NOT(0 OR 1) = 0
         Q'(t+1 state 4) = NOT(S OR Q(t+1 state 3))  = NOT(0 OR 1) = 0

As one can see, a steady state is not possible until one of the inputs is set to 1 (which is usually handled by power-on reset circuitry).


How can I show h(n) = O( √ n)? Is there any way to make recursion tree that satisfies the height
$h(n) = h(n−\sqrt{n}) + 1$ to show $h(n) = O(\sqrt{n})$?


Why when I unchecked DMA in Windows 7, the CPU usage was still very low? I am studying about PIO mode and DMA mode for accessing IO devices, and based on what I have read, in PIO mode the data transfer have to go through the CPU.

So I have unchecked DMA in Windows 7 (which I guess will enable PIO mode):

And I copied and pasted a large file to see the CPU usage, and the CPU usage was still very law (about 5%). Shouldn't PIO mode exhaust the CPU?

Your understanding of DMA is OK. But disk accesses are generally slow. So the CPU may spend is time on waiting for the disk to write the bytes on the disk, he is not stressed.
May be you can try to run something like CPU Burner that will stress the CPU and then measure the time to copy with/without DMA enabled.
Note that many things can interfere with your measurements, particularly HD caches.


PSPACE-complete problems can't be in NL using the space hierarchy theorem? I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this :
From the time hierarchy theorem I know that for every $t(n)$ there exists a language that is decidable in $O(t(n))$ space but not in $o(t(n))$ space. Then I want to assume that there exists $A \in PSPACE\text{-complete} \land A \in NL$ and take a language $L$ that is decidable in $O(n)$ time but not $o(n)$ time, reduce it to $A$, reduce it to $PATH$ and get that through that reduction $L$ is decidable in $\Theta (log(n)^2)$ time, a contradiction.

However my reasoning fails in that the reduction from $L$ to $A$ isn't necessarily a log-space reduction. What am I missing? How do I overcome this?

This question is currently open, since a positive answer (i.e. no complete problems for PSPACE can lie in NL) would imply $\mathsf{P}\neq\mathsf{PSPACE}$. This statement is actually equivalent to $\mathsf{P}\neq\mathsf{PSPACE}$ (as a PSPACE complete problem in NL obviously implies P=PSPACE).

Examine the equivalent statement, that $\mathsf{P}=\mathsf{PSPACE}$ implies there exists a PSPACE complete problem in NL. To see why this holds, note that if $\mathsf{P}=\mathsf{PSPACE}$ then every non trivial language $L\in\mathsf{PSPACE}$ (i.e. $L\neq \emptyset,\Sigma^*$) is complete for PSPACE. Now let $L$ be some non trivial language in NL (which is a subset of PSPACE), then $L$ is a PSPACE complete problem which lies in NL.


Intersection of languages using closure properties $L_1 \in \mathrm{CFL} \cap L_2\in \mathrm{CSL}$ is $\mathrm{CSL}$ because every $\mathrm{CFL}$ is $\mathrm{CSL}$ and by applying closure property of $\mathrm{CSL}$ under intersection, it's $\mathrm{CSL}$.
$L_1 \in \mathrm{ RL} \cap L_2 \in \mathrm{CFL}$ is same as $\mathrm{CFL} \cap \mathrm{CFL}$ . As $\mathrm{CFL}$ is not closed under intersection, we promote $\mathrm{CFL}$ to $\mathrm{CSL}$. So $\mathrm{CSL} \cap\mathrm{CSL}$ is $\mathrm{CSL}$.

But, we know that 2nd is guaranteed to be $\mathrm{CFL}$ (also $\mathrm{CSL}$).

Why I am not able to arrive at the answer ($\mathrm{CFL}$) using closure properties for 2nd case ? Can't we apply closure properties when considering regular languages?

One of the closure properties of CFL is that they are closed onder intersection with regular languages. This can be directly applied, rather than first promoting the regular language to context-free language.

In general, if we want to know the family in which the intersection (or whatever operation $\oplus$) of two languages belongs, then we look for the smallest families $\mathrm{X}$ and $\mathrm{Y}$ that contain the two languages and for which we know an applicable closure property.

In your terminology, we "promote" as little as possible, but enough to find a family/families for which the closure property is known.


DFA for Strings with third symbol from RHS as 1 How can we make a DFA for given condition in title from alphabets {0,1} (binary).

What can be the regular expression for this?

My calculated expression is (a+b)*a(a+b)(a+b) , please correct me if i'm wrong and help find the correct expression and it's DFA.

You probably want to substitute $a$ with $1$ and $b$ with $0$ but apart from that your solution is correct.

Finding an equivalent NFA is easy with Thompson, Glushkov etc. From that you can derive an DFA via powerset construction. However, for this short expression you also can just write the DFA down. Imagine the states as storage what the last 3 symbols were, and accept if the third last was a 1, i.e. name the states 000 to 111 where 000 is the initial state and all states with a leading 1 are accepting. A transition is just a shift-left with the last read symbol on the right, i.e. $\delta(abc, d) = bcd$, with $a,b,c,d \in \{0,1\}$.


Example of reduction in communication complexity Let us assume the standard situation in communication complexity with two players $P_1,P_2.$

We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to compute  $f(x,y)$ given that the first player only knows $y$ and the second player only knows $x.$ The communication complexity of $f$ is the smallest number $k$ such that $P_1,P_2$ can always compute $f(x,y)$ communicating at most $k$ bits of information to each other.

If $f$ is the equality function (that is $f(x,y) = 1$ if and only if $x = y$) then I know that $P_1,P_2$ need to exchange at least $\log_2{n}$ bits in order to be able to always compute $f.$

Consider now the function $h_n:[n]\times[n] \mapsto \{0,1\}$ such that $h_n(x,y) = 1$ if and only if $x+y = n.$ I would like to show that $P_1,P_2$ cannot compute $h$ using fewer than $\Omega(\log{n})$ bits and the idea is to use the fact about the communication complexity of computing  $f.$

Hence I am wondering how to make a reduction in this case?

Suppose we can compute $h_n(x,y)$ with fewer than $\Omega( \log{n})$ bits. Can we somehow simulate such a protocol in order to be able compute $f$ using less than $\Omega(\log{n})$ communication bits?

Player $P_1$ receives the string $y$ and $P_2$ the string $x.$ Now $x = y$ if and only if $x+y = 2x = 2y.$ Hence they could simulate the algorithm for computing $h_{2x}(x,y).$ The problem that I see here is that in this reduction $h_n$ is not fixed in advance and may not even define the same function for $P_1,P_2$  (if $x,y$ actually differ).

Hence I am wondering

  How can one show that $h_n(x,y)$ cannot be computed communicating fewer than $\log_2{n}$ bits ?

Assume that each player gets a number in $[n]$, and they can compute $h_n(x,y)$. Each player knows $n$, so if $h_n$ is computable with less than $log(n)$ communication, they can compute $h_n(n-x,y)$ in under $log(n)$ bits of communication. Since you have $h_n(n-x,y)=1 \iff x=y$ then you managed to compute $\delta_{x,y}$ in sub logarithmic communication, contradiction.


Minimum pumping length of (01)* Michael Sipser offers the definition:
The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p′ ≥ p. The minimum pumping length for A is the smallest p that is a pumping length for A.
Now, (01)* in set notation is {€, 01,0101,010101....}
Taking minimum pumping length = 1, according to the definition, we have the statement if a string in the language has length 1 or more, it can be pumped.
This statement is true for all elements of the above mentioned set, so can the minimum pumping length be 1?
p.s. the minimum pumping length for (01)* has been asked here before but it doesn't answer my doubt that since the condition holds for minimum pumping length = 1, why is it not the answer?

The minimum pumping length $\ell$ of $(01)^*$ is $2$.
First of all notice that there are no words of length $1$ in the language.
Then, if you look at a formal definition of the pumping lemma for regular languages (what you wrote is still informal) you'll find that the length $|xy|$ of the prefix $xy$ of a word in the language that can be pumped must be $\le \ell$.
This allows you to prove that the minimum pumping length $\ell$ must be $2$ by showing:

That there is a DFA for $(01)^*$ that uses at most $2$ states, implying $\ell \le 2$. This DFA is trivial to obtain.
That $\ell=1$ is not a valid pumping length. This is true since $|y|$ must be positive and, together with $|xy| \le \ell$, this implies $|y|=1$. In other words $x = \epsilon$ and $y=0$. It is easy to obtain a word not in the language by repeating $y$ either $0$ or at least $2$ times.


Amortized time complexity for double stack emulated queue Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many elements are in the $stack$, and can be accessed in constant time.

I want to emulate a $queue$ by using two stacks $queue = (stack_{push}, stack_{pop})$ with two operations $insert$ and $remove$

$insert(queue, e)$ is implemented as:

insert(queue, e) {
    push(stack_push, e)
}

$remove(queue)$ is implemented as:

remove(queue) {
    if (stack_pop.size > 0) {
        pop(stack_pop)
    } else {
        while(stack_push.size > 0) {
            push(stack_pop, pop(stack_push))
        }
        pop(stack_pop)
    }
}

It is obviously that $insert$ takes constant time and $remove$ takes $O(n)$ time in worst case. (where n is the size of the queue).

Now considering an sequence of queue operation with length $n$ (pop an empty stack is allowed), I want to get the amortized time complexity of this queue structure. My guess is that the amortized time complexity is $O(1)$, since it seems that the worst case of the sequence is first $insert$ n-1 elements then $remove$, so the total cost is $O(n)$ then the amortized time is $O(n)/n = O(1)$. However I cannot figure out how to prove it.

My question is that is the amortized time complexity of the queue's operation really $O(1)$ and how to prove it?

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$.

You can formalize the above argument in various ways. As an example, if you perform $A$ insert operations and $B$ remove operations, then the argument above shows that you push at most $2A$ elements and pop at most $A+B$ elements. Hence the total running time is $O(A+B) = A \cdot O(1) + B \cdot O(1)$.


Simple algorithm to select separated points in closed intervals Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = [a_1,b_1] \cup \cdots \cup [a_K,b_K].$$

Select $N \geq 2$ points $x_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min_{i \neq j} |x_i-x_j|.$$

In my case, the intervals are already disjoint and sorted ($a_1 \leq b_1 < a_2 \leq b_2 < \ldots  < a_K \leq b_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30.  Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C_i$ of the points are to be chosen from interval $[a_i,b_i]$, then

$$\sum_{i=1}^K C_i = N \\
\Delta = \min_{1 \leq i \leq j \leq K} \frac{b_j-a_i}{-1+\sum_{\ell=i}^j C_\ell},$$

ignoring the terms with denominator $0$ or $-1$.  And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a_1$ and $b_K$ can always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

First note that in any optimal solution we can always have $x_1 = a_1$ as we wish to maximize distances, and $x_1 = a_1$ unconditionally does that without sacrificing distance anywhere.

Secondly note that while our 'smallest differences' metric we want to optimize appears a global problem, it really is not if we also sort our $x$. We can have the equivalent definition:

$$\Delta = \min_{1 \leq i < K} \left( x_{i+1} - x_i \right)$$

Now suppose our candidate solution has value $\Delta$. Then given $x_i$ we can find the leftmost $x_{i+1}$:

$$x_{i+1} = \min_y \{ y \mid y \in S \wedge y \geq x_i + \Delta\} $$

So we find $x_1, x_2, \dots$ until we are done. Repeatedly finding which interval in $S$ (if any) will contain $x_{i+1}$ can be done in a combined $O(K)$ time during this process if you just keep track of the highest used interval so far. If there is no valid interval for $x_{i+1}$, it means $\Delta$ is not a valid outcome, but if we find al values up until $x_K$ it is.

So now we have a $O(K + N)$ time test to see whether a certain $\Delta$ is valid. But we can say with certainty that $\Delta \in [0, b_K - a_1]$. So we can do a binary search on this interval using our test to find a range which contains our optimal $\Delta$.

Since each step in this binary search halves the size of the interval that contains the optimal result, we can find optimal $\Delta$ (and corresponding $x_i$) up to a precision of $2^{-p}(b_K - a_1)$ in $O(p(K+ N))$ time.

If you're a bit smarter you can terminate early and exactly as an optimal solution will always contain a limiting sequence of steps of the minimum distance $\Delta$ starting at the left part of an interval and ending at the right part of an interval. Thus we have $a_i + k\cdot \Delta = b_j$. In other words, if our remaining interval contains only a single value of the form $\frac{b_j - a_i}{k}$ for some $i \leq j$ and $k$, then that is the optimal value and you can terminate the search.


prove language is Context-free and not regular I have to prove that $\left \{ a, b \right \}^{\ast} - \left \{ a^ib^i | i\geq 0 \right \}$ is a context-free language and it's not regular.

So far I've got that this language is not regular because regular languages are closed under complementation and $\left \{ a^ib^i | i\geq 0 \right \}$ is a well know context free language (by the way do you have a link with a formal proof that $\left \{ a^ib^i | i\geq 0 \right \}$ is context free?)

For the context-free I'm a little confused
I've thought about building a PDA that recognize $\left \{ a^ib^i | i\geq 0 \right \}$ (pushing a's on the stack and popping a's when a b is read works?) I think is deterministic CF so i can use the same reasoning (complement of a DCF is a DCF language?)

To prove that the language is Context Free, it suffices to give the Push Down Automaton, and that language is recognized by one of the simplest PDA.

To prove that the language is NOT regular, you don't only have to show that you can't find an appropriate Automaton (be it a FDA or FNA, they have equivalent expressive power), but that no one can.

That proof can't be shown with an example, because you want to prove that not a single FDA can recognize the language correctly. The proof shows a contradiction between having such FDA and that the FDA correctly rejects some words outside the language.

The idea is similar to the pumping lemma. Suppose that you have an FDA that recognizes the language, you are going to break it. That FDA is, as it name says, finite, let it's size (node count) be $N$. To recognize the words in $\left \{ a^ib^i | i\geq N \right \}$ it certainly has to do some loops.

By exploiting a loop of length $l$ (looping in it one time more than the expected), you can see that $a^{(i+l)}b^i$ should also be accepted by that FDA, so it fails to recognize the language, as it would accept words that are not in it.


Get indexes of unique elements in two different arrays in linear time I have two array of the same set of elements, say for exemple:
$a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$

Is it possible, in linear time, to construct the array $[(x_1, k_1), (x_2, k_2), …, (x_n, k_n)]$ so that $y_{k_i} = x_i$ ?

I found that with dictionnaries, I can get $O(n)$ in average and $O(n^2)$ in worst (hashtable) or $O(n\log n)$ in average and worst (balancing trees), but can't find a way to make it $O(n)$ in worst case.

We can suppose that the $x_i$ objects are integers, since it could represent memory pointers.

I found that it is possible if the set is $[\![1, n]\!]$ (just construct the array directly).

Thanks for your help.

Given the following assumptions:

Since the meaning of the $=$ operator was not defined, we assume

  $i≠j⇒x_i≠x_j$

  ...

  The $x_i$ values are not necessarily integers or string, but any type of elements.

are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each element is a single word, perhaps a distinct pointer to some arbitrary object.

We assume that, given an arbitrary address, reading/writing at that address takes constant time.
We assume that adding 2 addresses takes constant time.
We assume that a pointer to unbounded memory is available in n time.

Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space.

Then:

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine,
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result

...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of every non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.


Algorithm for determining minimal set of covering prefixes I have a set of strings.  My goal is to find a minimal set of longest prefixes which will match most of that set.

For instance, if my set is:

abracadabra
abracado
abramu
banana
bananasplit
bananaicecream
xylophone
zebra
zeitgeist
zello

I would want the output to be:

banana (len 6, matches 3)
abra (len 4, matches 3)
xylophone (len 9, matches 1)
ze (len 2, matches 3)

Now, this question isn't yet properly specified.  That's because I'm ranking my results on two dimensions: maximum matches, and maximum length.  My goal is to find prefixes that cover as much as of the set as possible, which are as long as possible and thus less likely to occur in strings that aren't in the set (all other things being equal, of course).

Ideally, I'd like to find a set of very long strings, ranked by how much of the set they cover.

That's my goal.  Now I'll present my work, and where I need help.

FIRST Let's specify the problem better.  We want a set of prefixes.  For each prefix, we compute its length, and the number of matches it has in the set, and order the prefixes by their product.  I'm then free to pick the top X prefixes.

I think that's a good specification.

NOW Comes an efficient implementation.  Brute force is to check every possible prefix against every string, which is complexity n * n * m (n being number of strings, m being average length of strings).

An efficient algorithm?
Something like this:

Build a prefix tree of the set
Each leaf has value 1
Work up the tree, with each parent equal to sum of its children , plus 1 if it has an entry
Now we know each prefix and how many matches it has - I believe complexity is n log n
Walk through the tree, counting length of each string (complexity n * m)
And collect all the entries, sort them by length * value (complexity n log n)

That algorithm is roughly n log n, which is efficient enough.  Will it work? How should it be improved? What's a simple way to implement it?

Finally: Since all the data is in a Postgres relational database, I believe it would be simplest to do the algorithm using relational algebra with aggregate functions. Comments on this?

Your algorithm will work. The information you will be looking for can be found in the prefix tree (trie) will hold the information you are looking for.

Despite similarity in names, the set cover and this problem are not similar. The first is NP-Hard. This one is not.

However (in relation to Point 3 of your algorithm), a tree node that is not a leaf may be the end of a word $w$ contained in other words (e.g. "be" contained in "bee" "behavior" etc .. ). You should take into consideration when counting.

Point 4: Now we know each prefix and how many matches it has - I believe complexity is $n \log n$ .. why ? I dont think so. It is $O(n m)$.

Point 6: I dont know though why you want to sort. You can find the max (which is $O(n)$).

If you are going to present the tree in a relational database, then make sure you present it in a good way. For instance, try to make the whole tree in a single page, or close nodes in the tree in the same page. This is to minimize the I/O cost.  How to do that ? I honestly don't know. For me, I would just put it the prefix tree in a single binary file. Or a seriazable data structure.


Determine if a line going through n rectangles exists I guess this is kinda like asking if 3 (or more) rectangles are collinear.

The question is, given n rectangles on the 2D plane (given as the rectangle's top-left corner coordinates and it's width/height), does there exist a line that goes through all of them?

Notes:

The rectangles' sides are perpendicular or parallel to the axes. So
basically,  none of the rectangle sides are slanted.
Rectangles themselves can intersect
Does not actually need to produce the line equation

I've been thinking through this for a good portion of today, and can't figure out (or find online) an answer. I keep finding edge cases and can't figure out a guaranteed method. The line of best fit for the mid-point or the corners of all n rectangles seem like a good heuristic for a line, should one exist, but I don't think it always works.

The corners of the rectangles seem like good starting points to determine the extreme slopes of a potential line, but it's still unclear to me how i'd use them to determine if a line exists for all n rectangles. I also know how I'd do this intuitively IRL, but not sure how to turn it into an algorithm.

Visual Example for 4 rectangles:

There is a line through the four rectangles if and only if you can pick one edge from each rectangle such that the line intersects each of those four edges -- or equivalently, if there is a point on each of those edges such that the resulting four points are colinear.  So a plausible algorithm is to enumerate all $4^4$ ways to choose one edge from each rectangle; then check whether there exists a line that goes through those four edges.

How do we do the latter test?  Let's suppose the endpoints of the first edge are the two points $P',P''$ (i.e., these are two adjacent corners of the first rectangle).  Then any point $P$ on that edge can be expressed as $P = (1-\alpha) P' + \alpha P''$ for some $0 \le \alpha \le 1$.  Similarly, we can express any point $Q$ on the second edge as $Q = (1-\beta) Q' + \beta Q''$ where $Q',Q''$ are the endpoints of the second edge, and similarly for the two remaining points $R,S$ on the two remaining edges.

We can express algebraically the condition that $P,Q,R$ are colinear (on the same line).  Let $P_x$ be the x-coordinate of the point $P$, and $P_y$ be its y-coordinate.  Then $P,Q,R$ are colinear iff

$$(Q_x-P_x)(R_y-P_y) = (Q_y-P_y)(R_x-P_x).$$

We can plug in $Q_x = (1-\beta)Q'_x + \beta Q''_x$, and so on, to get an equation in terms of the three $\alpha,\beta,\gamma$ unknowns.  Similarly, the condition that $P,Q,S$ are colinear can be expressed as an equation in terms of $\alpha,\beta,\delta$.  Now there exists a linear through these four edges iff there exists a common solution to these two equations such that $0 \le \alpha,\beta,\gamma,\delta \le 1$.  This reduces the problem to solving two quadratic equations over four real unknowns.  Now you can apply standard methods for solving such equations to determine whether a simultaneous solution exists.


Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$ I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.

I thought first to make a substitution: $m=\log n$. Then:
$$
T(2^m)=T(2^{m \over 2})+10\log m
$$
Let $S(m)=T(2^m)$:
$$
S(m)=S\big({m \over 2}\big)+10\log m
$$

Now we can use Master theorem.

Suppose it's the case when $f(m)=O(m^{\log_2 1-\epsilon})=O(m^{0-\epsilon})$. Let $\epsilon=0.5$ then:
$$
\lim_{n\to \infty}\frac{10\log m}{m^{0.5}}=0
$$
Hence according to the Master theorem $T(m)=\Theta(m^0)=\Theta(1)$.

Am I in the right direction?

An alternative solution still using domain transformation/change of variables.

$$T(n) = T(\sqrt{n}) + \log \log n$$

1. Let $m = \log n$

We can then define a new function $S$ based on how $m$ changes in $T$ and expand it:

$$\begin{align}
S(m) &= S\left(\frac{m}{2}\right) + \log m\\
&=S\left(\frac{m}{4}\right) + \log m -1 + \log m\\
& \vdots\\
& = \log^2 m - \sum_{i = 1}^{\log m} i \\
& = \Theta(\log^2 m) \implies T(n) = \Theta((\log \log n)^2)
\end{align}$$

2. Let $k = \log \log n$

We can then define a new function $R$ based on how $k$ changes in $T$ and expand it:

$$\begin{align}
R(k) &= R(k - 1) + k\\
& = R(k - 2) + k - 1 + k\\
& \vdots\\
& = \Theta(k^2) \implies T(n) = \Theta((\log \log n)^2)
\end{align}$$


References on teaching introductory programming courses As the new semester starts soon, I am interested in research regarding the teaching of introductory programming courses. I would like to improve my university course and I am looking for scientific papers on that topic.

One trend I have seen is that some students (a smaller group) are interested in computers or they have already some programming background. They are fine and learn a lot. But the majority of students struggle at the first step of programming (hard to set up Eclipse, a lot of errors at the beginning, etc.). Is this just my view or is this documented in literature?

I would like to make this 'first step' into programming as easy as possible for students. As a first start I found "A Gentle Introduction to the Art of Object-Oriented Programming in Java"

Here's a survey paper and there are others.

You might want to consider the inverted method also known as outside-in, which differs from the traditional bottom-up approach.

This article on the application of problem-based learning to first year programming reports some successful results, mainly in terms of secondary skills learned by students. The cost is a major investment and restructuring by those involved.


Finding the length of the longest increasing path in a matrix Problem:

Given a matrix, find the length of the longest increasing path. We can move up, down, left, or right.

Example:

$$
\begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}
$$

Output: 7

Longest path is 1, 2, 3, 4, 5, 6, 7

Question:

I am not sure if this post is relevant to this site. I having some trouble coming up with a system to solve this problem. I am not too advanced with programming, I am more of a mathematician by trade but I know some stuff about data structure and algorithms.

If possible, an ideal answer for me would be a step by step guide in solving this problem. My initial thought was to find the smallest number in the $(i, j)$ position and start with the first $(i,j)$ position that was found. Then check up, down, left, right to see which number is larger. But then I thought okay what if there are more than 1 position that is larger? I am pretty stuck with this so any help would be useful.

I found solutions to this online but reading other peoples code is nauseating and I don't find it useful at all.

Here is an $O(nm \log nm)$ solution, where $n,m$ are the dimensions of the matrix. Later we improve it to an optimal $O(nm)$ solution.

Let $A[i_1j_1],\ldots,A[i_{nm}j_{nm}]$ be the entries of $A$ in non-decreasing order; the indices $i_tj_t$ can be computed in time $O(nm\log nm)$. We will compute a new matrix $B$ with the same dimensions such that $B[ij]$ is the length of the longest increasing part ending at $A[ij]$. We compute the entries of $B$ in the order $B[i_1j_1],\ldots,B[i_{nm}j_{nm}]$, using the formula
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'],
$$
where $i'j' \sim ij$ means that $A[i'j']$ is a neighbor of $A[ij]$, and we set $B[ij] = 1$ if the maximum is over the empty set.

The answer is simply the maximum entry of $B$. You can find an actual longest increasing sequence by starting with a maximum entry of $B$, say equal to $\ell$, finding a neighbor equal to $\ell-1$, then a neighbor equal to $\ell-2$, and so on until hitting a neighbor equal to $1$. This gives you a longest increasing sequence in reverse order.

As an example, consider your matrix
$$
A = \begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}.
$$
We can order the entries as follows (there are many possible orders, since the entries are not distinct):
$$
A[1,1],A[1,2],A[2,1],A[2,2],A[3,2],A[1,3],A[2,3],A[3,1],\\A[3,3],A[1,4],A[2,4],A[3,4],A[4,1],A[4,2],A[4,3],A[4,4].
$$
We now compute $B$ in the same order:
$$
\begin{pmatrix}
1& & & \\
 & & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
 & & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2& & & \\
 & & & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2&1& & \\
 & & & \\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2& & \\
2&1& & \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1& & \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
 &1& & \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1& & \\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2& \\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3& \\
 & & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
 & & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5& &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&7
\end{pmatrix}.
$$
We conclude that the answer is $7$. Retracing our steps, we highlight the following path in $B$, which corresponds to the longest increasing sequence in $A$ (accidentally, having exactly the same values):
$$
\begin{pmatrix}
1& & & \\
2& & & \\
3& & & \\
4&5&6&7
\end{pmatrix}.
$$

We can implement essentially the same solution in time $O(nm)$ using DFS. We go over the entries of $B$ in some arbitrary order, attempting to use the same recurrence formula we had before:
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'].
$$
If we are trying to access an entry $B[i'j']$ which hasn't already been computed we compute it recursively. Conversely, once an entry $B[ij]$ has been computed, there is no need to compute it again.

This can be implemented using the following pseudocode:

compute-B-matrix:
  initialize B to be empty
  for 1 <= i <= n and 1 <= j <= m:
     if B[i,j] is empty, call compute-entry(i,j)

compute-entry(i,j):
  let S = { neighbors (i',j') of (i,j) such that A[i',j'] < A[i,j] }
  if S is empty:
     set B[i,j] = 1
  if S is non-empty:
    for every (i',j') in S:
      if B[i',j'] is empty, call compute-entry(i',j')
    set B[i,j] = 1 + max({ B[i',j'] : (i',j') in S })

This solution essentially amounts to computing a topological ordering of a digraph naturally associated with $A$. Details left to the reader.


Asymptotic expected runtime of Randomized Algorithm I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

Given input size $n$, with probability $3/4$ it moves on to solve an instance of size $n-1$
With probability $1/8$ it moves on to solve an instance of size $n-2$
With probability $1/16$ it moves on to solve an instance of size $n-3$
With probability $1/2^i$ it moves on to solve an instance of size $n-i$
Each instance pays a cost of $O(n)$, where $n$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$

$T(0) = O(1)$

I have calculated that the expected number of "jumps" at each stage is $\leq 1$. I did this by showing $\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $n$ gets smaller, although this hints the runtime is $O(n^2)$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$3/4$" probability for moving onto an instance of size $n-1$ should actually be larger than $3/4$ since the probabilities $1/2, 1/4, 1/8, ...$ only go on till $1/2^{n+1}$. If no jumps were made, the algorithm deterministically moves on to an instance of size $n-1$.

As you mention, it is easy to prove by induction that the overall runtime is $O(n^2)$. If we don't have any more information, that's (almost) all we can deduce. For example, suppose that at each instance we pay a cost of $O(1)$. The running time will then be $O(n)$. In order to make progress, we have to assume that at each instance we pay a cost of $\Theta(n)$. In that case, we can argue as follows:

Since each "jump" is $O(1)$, it takes $\Omega(n)$ steps (on average) to reach $n/2$.
At each of these $\Omega(n)$ steps, we pay a cost of $\Omega(n)$.
Hence the total expected cost is $\Omega(n^2)$.

This is not a rigorous argument, but it can be turned into one if you're careful enough.


Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism? As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?

What follows is taken from Tsuyoshi Ito's comment.

As rizwanhudda said, this problem is a special case of the graph isomorphism problem and therefore it is not known to be NP-complete. We cannot say “this problem can’t be NP-complete” because of that, because the graph isomorphism problem might be NP-complete. However, many complexity theorists believe that the graph isomorphism problem is not NP-complete (and therefore they will believe that your problem is not NP-complete, either) because the NP-completeness of the graph isomorphism problem would contradict the conjecture called “the polynomial hierarchy does not collapse.”


Can a Red Black tree be constructed of only black nodes using RB insert only? I am trying to construct a red black tree out of only black nodes.
I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders.
Is it possible?
I couldn't find a way to do so , so far even after trying to use the simulator.

*** exept of a root node being added to an empty tree.

Properties of Red Black Tree:

0) Every node is black or red. Ok, no problem.

1) Root is black. Ok, no problem.

2) All leaves (empty nodes) are black. Ok, no problem.

3) Every red node must have two black childs. Ok, no problem.

4) Every path from any node to leaf has equal number of black nodes. It seems problematic.

So now comes problems: When you insert element it's color is red. (In fact this not comes from properties but observation that adding red node does not violate $4$th rule, so it is easier to implement).

So for start you add one element, let me say 10.
It is black root. Ok.

Now You add 13. It must be red, otherwise it violates rule 4.

Now you add 19. Depending on implementation you can leave all black, or recolor.

Now adding 12 gives recoloring and comes red.

And after several numbers

And now it starts nightmare, as you should propagate changes from one side of tree to another convincing somehow that you will change everything to black after insertion.

Basically I asked you about rules to obey, as it comes to mind that with $4$th can be fulfilled only in perfectly balanced trees.

So to answer your questions:

No you cannot with common implementations of RBT, but extending balance operation to recolor when it is possible - it does not violate rules, so it is possible. Also with extension that whenever there is $n = 2^k - 1$ nodes, restructure it to perfectly balanced tree and recolor everything to black, it would be also possible.

I did firstly answer "no" as purpose of balancing operation is to guarantee bound on worst case search / insert, and such extensions comes at price of time complexity. It does not violate rules, but is not implicitly implemented in standard RBT.

Given only root, you have it. Given three nodes inserted in order with implementation changing all to black (rather rare case and counterproductive), you can. But this is last one that is without deletions possible.

When you are about to insert element and want all tree to be black that would mean there is violated rule $4$ (so not possible) or you have to rebalance tree, which would recolor nodes, so it is not pure black anymore.

With deletions on the other hand ;)


Gap problems clarifation Here's a simple question which made me confused.

Please tell me if my analysis of the problem and my conclusions are correct.

For an optimization problem $\sf Gap-A[a,b] \in L$ for $b>a$. I want to discuss what I can know about $\sf Gap-A[a/2,b/2]$.

$\sf(i)$ Is it correct to say that $\sf Gap-A[a/2,b/2]$ is not in $\sf NP-Hard$ and it is easy only because the realtion $\frac{a/2}{b/2}=\frac{a}{b}$ and we already know that it is easy to approximate $A$ with  factor of $a/b$?

$\sf (ii)$ Is it true that I can't say though that $\sf Gap-A[a/2,b/2]$ is in $\sf L$ since there is no intersection between the gaps? In order that gap $B$ would be in the exact class that gap $A$ is in, we have to have $A \subseteq B$?

You are confusing NP and NP-hard. The fact that a problem is (say) in L doesn't preclude it being in NP, in fact, quite the contrary: any problem which is in L is a fortiori in NP, i.e. L$\subseteq$NP. On the other hand, it is not likely to be NP-hard (and assuming that P$\neq$NP, if it is in L then it cannot be NP-hard).

Another mistake you're making is that a problem which is approximable can't be NP-hard (or rather, its decision version can't be NP-hard). Considering MAX-3SAT, there is a trivial 7/8-approximation algorithm (pick a random assignment; this can be derandomized), yet the decision version 3SAT is NP-complete.

You're right that GAP-A$(a,b)$ being easy doesn't imply that GAP-A$(a/2,b/2)$ is easy. One example (replacing $1/2$ with an arbitrary $c$) is MAX-2SAT. GAP-2SAT$(a,1)$ is easy for any $a<1$, yet there exist some $b,c$ for which GAP-2SAT$(b,c)$ is NP-hard. (Unfortunately, $c=1/2$ doesn't work, since every 2SAT instance can be $1/2$-satisfied.)


Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless? Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where I feel way out of my league, so I will definitely appreciate some clarity on the matter :)

Long story short, I am faced with the following type of a problem, which I would like to illustrate here with an example for the sake of better clarity:

Let $S:=\{1,2,...,42\}$ be a set of integers and let $N\subset\{T\in 2^S:|T|=3\}$ be fixed (pre-generated in a specific way). Typically, $|N|$ is in the order of 1500-2000. I would like to construct all 7-el. partitions $\Sigma=\{S_1,S_2,S_3,S_4,S_5,S_6,S_7\}$ of $S$ (i.e.$S_i\neq\emptyset$ for $i=1,...,7$ and $\cup_i S_i=S$) s.t. $|S_i|=6$ and $S_i$ contains exactly one element of $N$ as a subset, $i=1,...,7$. (*)

My question is, is this computationally feasible (e.g. a few days of number crunching on a modern workstation) by using an optimized routine/algorithm? And if yes, how?

In the particular example from above, a straightforward approach to obtain all 6-el. subsets of $S$ that contain exactly one element of $N$ as a subset yielded ~ 470 000 different subsets (also see this SO thread), which does not seem aproachable by a straightforward solution of the exact cover problem. Furthermore, in another example with $|S|=48$ and $|\Sigma|=8$, it yielded ~1.5 Mil different subsets.

Note that constructing all partitions, even with fixed block size, for sets with as many elements is kinda out of reach (cfg. Bell number or Stirling number of the 2nd kind). However, conjecturally, because of the specific nature of $N$ and the additional restriction on the blocks of the partition, it is expected that there are only very few such valid partitions (probably no more than 1 or 2). In other words, I am hoping that imposing the additional restriction (*) could be still used to obtain a suitable algorithm.

Since the underlying math for a potential proof or disproof may well be out of reach for now, I am hoping to at least get some computational verification for "larger" numbers before even attempting an attack on the mathematical part.

Thanks!

Here's an approach that I suspect will work very quickly.

I suggest you start by enumerating all possible values for an $S_i$, i.e., all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset.

How many such sets do you expect to find?  By a crude back-of-the-envelope estimate, I estimate there will be only a handful, maybe 10 of them are so.  This estimate might be wrong, but this would be easy for you to test.

Let $\alpha$ be the number of possible such sets (i.e., $\alpha$ counts the number of ways to choose a 6-element subset of $S$ that contains exactly one element of $N$, i.e., there are $\alpha$ possible values for each $S_i$).  I am predicting you'll find $\alpha \approx 10$, or something similarly small.

If this prediction is accurate, this suggests a simple, naive algorithm to enumerate the partitions: namely, enumerate all ${\alpha \choose 5}$ ways to choose five valid possibilities for the $S_i$, and check whether those five sets forms a partition.  The running time of this algorithm is $O(\alpha^5)$.  If $\alpha$ is very small, say $\alpha=10$, this will be plenty efficient.

If it turns out that $\alpha$ is a bit larger, you can optimize this naive algorithm a bit.  Enumerate all ${\alpha \choose 2}$ ways to choose two out of these $\alpha$ 6-element sets, say $S_4,S_5$.  Filter out pairs that have an overlap (i.e., an element of $S$ in common).  Now store them in a hashtable, keyed by $S_4 \cup S_5$.  The hashtable will contain $O(\alpha^2)$ entries and can be constructed in $O(\alpha^2)$ time.  Next, enumerate all ${\alpha \choose 3}$ ways to choose $S_1,S_2,S_3$.  If $S_1,S_2,S_3$ are pairwise disjoint, look up $S \setminus (S_1 \cup S_2 \cup S_3)$ in the hashtable to see whether there is pair $S_4,S_5$ that can be combined with $S_1,S_2,S_3$ to form a full partition of $S$.  The running time of this optimized algorithm will be $O(\alpha^3)$.

And note that if $\alpha$ is indeed small, say $\alpha=10$ as I'm predicting, then it will be easy to enumerate all $\alpha$ possible values for an $S_i$.  You just enumerate all possible elements of $N$, then try extending each with three more elements of $S$, one by one, testing each one to make sure that the resulting set does not contain any other element of $N$ as a subset.  (In other words: select an element $T$ of $N$; select an element $x$ of $S \ T$, and check that $T \cup \{x\}$ does not contain any other element of $N$ as a subset; select an element $y$ of $S \setminus (T \cup \{x\})$, and check that $T \cup \{x,y\}$ does not contain any other element of $N$ as a subset; select an element $z$ of $S \setminus (T \cup \{x,y\})$, and check that $T \cup \{x,y,z\}$ does not contain any other element of $N$ as a subset.  Each step is pretty easy to do, and the overall running time should be very fast, assuming that $\alpha$ is indeed small as I expect.)

So, I suggest you start by running a little experiment to measure $\alpha$, then see if any of these algorithms is fast enough.  If it's not, edit your question to provide more details, including the value of $\alpha$.

Why do I estimate that $\alpha$ might be about 10?  Here's my crude back-of-the-envelope calculation.

First off, there are ${30 \choose 6} \approx 2^{19}$ ways to choose a 6-element subset of $S$, and ${30 \choose 3} \approx 2^{12}$ ways to choose a 3-element subset of $S$.  Therefore, $N$ contains about half of the possible 3-element subsets of $S$: in other words, if we pick a random 3-element subset of $S$, it'll be in $N$ with probability about 50% (roughly).

Also, for any 6-element subset $S_i$ of $S$, there are ${6 \choose 3} = 20$ ways to choose a 3-element subset of $S_i$, and each one has about a 50% chance of being an element of $N$.  We want there to be exactly one 3-element subset of $S_i$ that is in $N$.  This is like doing 20 coin flips, and we want to get exactly one heads (and the rest tails).  The probability of that is ${20 \choose 1} \times 2^{-20}$, i.e., $20/2^{20}$.  So, if we pick a 6-element subset of $S$, it will have probability about $20/2^{20}$ of being a valid possible value for some $S_i$.

Finally, there are $2^{19}$ possible 6-element subsets.  So, we expect that about $2^{19} \times 20/2^{20} = 10$ of them will be a valid possible value for $S_i$.  So, I'd expect $\alpha \approx 10$, using this crude argument.

This is a very crude estimate, because it assumes everything behaves randomly.  It is not rigorous, both because your set $N$ might not be random; and also because I made independence assumptions all over the place, even though things are not independent.  So, you will need to check empirically whether this estimate turns out to be accurate or not -- fortunately, that should be pretty easy to do.


Similarly structured loops with different big-O time complexities? I have a function:

int sum = 0;
for (int i = 1; i < n; i*= 2)
  for (int j = 0; j < n; j++)
    sum++;

From my understanding this is $O(n\log(n))$ because the inner loop runs $n$ times for every time the outer loop runs, and the outer loop is running $\log(n)$ times. Putting them together gives me $O(n\log(n))$, which I understand. However, the following loop:

int sum = 0;
for (int i = n; i > 0; i/= 2)
  for (int j = 0; j < i; j++)
    sum++;

I see this as $O(n\log(n))$ because the outer loop is running $\log(n) + 1$ times still and the inner loop runs $n + n/2 + n/4...$ whose sum will be some coefficient $c$ times $n$. Together with the outer loop simplifying to $O(n\log(n))$ but it turns out it is actually $O(n)$ however I don't see how it is?

In the second algorithm, the total number of increment operations would be $$\sum_{i=0}^{\lceil\lg n\rceil } \frac{n}{2^i}$$, which is $\leq 2n$. See this Wikipedia article about infinit geometric series and the inequallity should be clearer.


Is the prime factorization problem not an instance of the change making problem? When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can be used to make the total. But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete. Can anyone explain why this is?

When using as the set of coins all logarithms of the prime numbers or numbers in general

The change-making typically assumes a finite set of coins.

You can, of course, extend it to infinite sets of coins but then you get a different problem. Depending on the exact formulation, it seems plausible that integer factorization would reduce to that new problem.

  But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete.

Careful with your terminology there.

The general change-making problem is certainly in NP since it can be solved by integer programming. I do not know if it is NP-hard, but the common algorithms do not show that it is in P since they are only pseudo-polynomial. This shows, at least, that the problem is not strongly NP-hard.

Real-world change-making usually deals with canonical sets of coins for which a simple greedy algorithm works; it runs in constant time assuming a constant set of coins and the uniform cost model.

Integer factoring, on the other hand, is not known to be in P nor NP-hard; it's an open problem, and if P ≠ NP it may be in neither (but in NPI instead).


How do I structure hexagon edge data? In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.

I want to know how many blue tiles are accessible from a certain starting tile and a series of "roads." In this example, three blue tiles can be reached.

How would I represent roads? This is what I would need to know about it:

how it is rotated (for drawing)
which hexagons it borders
which other roads it touches, if any
where it should be drawn

I assume I could use recursion to to count the accessible blue squares if the above conditions are met.

Let us first calculate the coordinates $C(m,n)$ of the center of hexagon $(m,n)$. We assume that the origin is at the center of hexagon $(0,0)$ and that the hexagon radius (distance from center to vertex) is $r$.  A short calculation shows that hexagon $(1,0)$ has its center at $$C(1,0) = a = (\sqrt{3} r, 0)$$ and hexagon $(0,1)$ has its center at $$C(0,1) = b = (\sqrt{3} r/2, 3 r/2).$$
Therefore, hexagon $(m,n)$ has its center at
$$C(m,n) = m \cdot a + n \cdot b = (\sqrt{3} r (m + n/2), 3 r n / 2).$$
Notice that we should allow negative $m$ and $n$ if we want to cover the whole plane.

To get from the center $C(m,n)$ to one of the adjacent centers we need to add to $C(m,n)$ one of the vectors $a$, $b$, $-a$, $-b$, $a - b$, or $b - a$. (If we add $a + b$ or $-a-b$ we go too far). If we travel half the distance we will end up exactly in the midpoint of a side. Therefore, midpoints of sides have coordinates of the form
$$C(m+1/2, n), C(m,n+1/2), C(m-1/2,n), C(m,n-1/2), C(m+1/2,n-1/2), C(m-1/2,n+1/2).$$
We have discovered how to encode sides: just use half-integer coordinates. But this is silly, it is better to multiply everything by two, which leads to the following system.

We represent both hexagons and sides as pairs of integers $(m,n)$. When $m$ and $n$ are both even this encodes a hexagon whose center is at $$C(m/2,n/2) = (m \cdot a + n \cdot b)/2.$$
If either $m$ or $n$ is odd then $(m,n)$ represents a side of a hexagon whose midpoint is at $C(m/,n/2)$.

It is also easy to tell which two hexagons a given side belongs to: the side $(2 i + 1, 2 j)$ belongs to hexagons $(2 i, 2 j)$ and the side $(2 i + 2, 2 j)$, while the side $(2 i, 2 j + 1)$ belongs to hexagons $(2 i, 2 j)$ and $(2 i, 2 j + 2)$.

Similarly, the sides of hexagon $(2 i, 2 j)$ are: $(2 i + 1, 2 j)$, $(2 i - 1, 2 j)$, $(2 i, 2  j + 1)$, $(2 i, 2 j - 1)$, $(2 i + 1, 2 j - 1)$ and $(2 i - 1, 2 j + 1)$.

We now have a good system for representing hexagons and sides as pairs of integers. We still need to solve the original problem, namely which blue hexagons are reachable from a starting hexagon by traveling along certain "black" paths. This is a graph-theoretic reachability problem if we think of sides as edges in a graph and their endpoints as vertices of a graph (as we reach each black side we verify whether it belongs to a blue hexagon). Many algorithms are known on how to solve this. Let me know if you need more details.


Elimination rule for the equality type aka J axiom I'm implementing a interpreter for lambda calculus,
and now I want to add the equality type.
The introduction rule for it is easy,
but the elimination rule is rather obscure for me.
I found this stackoverflow thread, but it explains the J axiom only in one sentence. How can it be understood intuitively?

A complete understanding of what J was actually saying and why has only come fairly recently.  This blog post discusses it.  While thinking in terms of homotopy and continuous functions provides a lot of intuition and connects to a very rich area of mathematics, I'm going to try to keep the discussion below at the logical level.

Let's say you axiomatized equality types directly (these are groupoid operations and laws):
$$\frac{\Gamma\vdash x:A}{\Gamma\vdash \mathbf{refl}_x : x=_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=_A y}{\Gamma, x:A, y:A\vdash p^{-1} : y =_A x} \qquad \frac{\Gamma, x:A, y:A\vdash p : x=_A y \quad \Gamma,y:A, z:A\vdash q : y=_A z}{\Gamma, x:A, y:A, z:A\vdash p\cdot q : x =_A z}$$
$$(p^{-1})^{-1} \equiv p \qquad p\cdot p^{-1} \equiv \mathbf{refl} \qquad (p\cdot q)^{-1} \equiv q^{-1}\cdot p^{-1} \\ \mathbf{refl} \cdot p \equiv p \equiv p \cdot \mathbf{refl} \qquad (p \cdot q) \cdot r \equiv p \cdot (q \cdot r)$$
We have substitution which is functorial.
$$\frac{\Gamma, z : A\vdash F(z) : \mathbb{U}\qquad\Gamma,x:A,y:A\vdash p : x=_A y}{\Gamma, x:A,y:A\vdash \text{subst}(F,p) : F(x) \to F(y)}$$
$$\text{subst}(F,\mathbf{refl}) = \text{id} \quad \text{subst}(F,p\cdot q) = \text{subst}(F,q)\circ\text{subst}(F,p)\\\text{subst}(\lambda x.c=_A x,p)(q) = q\cdot p$$
Finally, we would have congruence rules for everything, saying everything respects this equality.  Here is one of the most important congruences.
$$\frac{\Gamma, x:A, y:A\vdash p : x=_Ay \quad \Gamma,z:A\vdash B(z) : \mathbb{U}}{\Gamma, x:A, y:A, b : B(x)\vdash \text{lift}_B(b,p) : \langle x,b\rangle =_{\Sigma x:A.B(x)}\langle y,\text{subst}(B,p)(b)\rangle}$$

Now let's consider a special case of substitution.
$$\frac{\Gamma\vdash c:A \quad \Gamma,t:\Sigma x\!:\!A.c=_Ax\vdash C(t):\mathbb{U} \quad \Gamma\vdash b : C(\langle c,\mathbf{refl}_c\rangle)}{\Gamma,y:A,p:c=_Ay\vdash\text{subst}(C,\text{lift}_{\lambda z.c = z}(\mathbf{refl}_c,p))(b) : C(\langle y,p\rangle)}$$

This is J.  We can use currying to get the nicer looking form:

$$\frac{\Gamma\vdash c:A \quad \Gamma, y:A, p : c=_A y \vdash C(y,p): \mathbb{U}  \quad \Gamma\vdash b : C(c,\mathbf{refl}_c)}{\Gamma, y:A,p : c=_A y\vdash J_{A,c}(C,b,y , p) : C(y,p)}$$

Of course, if we start with J we can rederive all the other structure I defined.

Now if we have $p : x =_A y$ and $q : y =_A y'$ then $\text{lift}_{\lambda z.x=z}(p, q) : \langle y,p\rangle = \langle y',p\cdot q\rangle$.  So if we have $\langle y', p' \rangle$, there's no way to get to it from $\langle y,p\rangle$ via a pre-selected $q$ in general unless $p \cdot q = p'$. (From the homotopy perspective, $p \cdot q = p'$ says we can fill in the triangle with edges $p$, $q$, and $p'$.)  To make it more blunt, set $p = \mathbf{refl}_x$ (and $y=x$) and we get $q = p'$ being the required equality which is not true in general (because a value of type $x =_A y'$ can represent an arbitrary equivalence and there's nothing saying two equivalences have to be the same, or, equivalently, because we know groupoids can be non-trivial). The point of this is to demonstrate that things can be equal in more than one way, i.e. one value of $y = y'$ is not as good as another in general.

A key thing to understand is that J says the type $\Sigma y\!:\!A.x=_Ay$ is inductively defined, and says little about the type $x=_Ay$ for fixed $x$ and $y$.  One way to see this, and why J is the way it is, is to look at what congruence at equality types with matching endpoints looks like.  We have the following rule (ignoring the proof term, it's expressible with $\text{subst}$ or J):
$$\frac{\Gamma, x:A\vdash p : x=_Ax}{\Gamma, x:A, q : x =_A x\vdash \_ : q =_{x=_Ax} p \cdot q \cdot p^{-1}}$$  With $\text{lift}_{\lambda z.x=z}$ we have the option of doing $\text{lift}_{\lambda z.x=z}(p, p^{-1}\cdot p') : \langle y,p\rangle = \langle y',p'\rangle$ so every point was equivalent to every other point (though not necessarily trivially).  With both endpoints matched, we don't have the flexibility of choosing the equalities to first cancel out the input equality and then performing an arbitrary equality.

While J carefully respects the non-trivial groupoid structure of equality types, in typical dependently typed languages there's no way to actually define a non-trivial element of an equality type.  At this point you hit a fork in the road.  One route is to add Axiom K which says that the groupoid is actually trivial which makes many proofs much simpler.  The other route is to add axioms that allow you to articulate the non-trivial groupoid structure.  The most dramatic instance of this is the Univalence Axiom which leads to Homotopy Type Theory.


What is the regular expression for the following language? What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say  $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??

I claim that $L$ is equal to the set of all strings of the form $a\gamma b\gamma$, where $a,b \in \{0,1\}^+$ and $\gamma \in \{0,1\}$. Indeed, a string of this form clearly belongs to $L$. Conversely, if $acbc \in L$ and $c=d\gamma$, then $acbc = ad\gamma bd\gamma$ belongs to the new set. The new set is clearly described by the regular expression
$$ (0+1)^+0(0+1)^+0 + (0+1)^+1(0+1)^+1. $$


3SAT to 3SAT-WITH-MAJORITY reduction I've been struggling with reduction while solving this exercise and I would really appreciate some help if not the solution.
Problem: [3-SAT-WITH-MAJORITY]
Input: A set of clauses $C = {\{c_1, \dots, c_k}\}$ over $n$ boolean variables $x_1, \dots, x_n$ where every clause contains exactly three literals.
Output: YES if there is a truth assignment to the variable such that both

every clause is satisfied under the assignment
there are at least k/2 clauses in which all 3 literals are set to true under the assignment.

NO otherwise.
Show that this problem is NP-complete.

Hint: Take a SAT instance $C$ with $k$ clauses and introduce $3k$ new variables $\top^i_1, \top^i_2, \top^i_3$ for $i \leq k$ and construct $k$ new clauses $c^\top_i = \{ \top^i_1,\top^i_1,\top^i_3 \}$.  Let $C' = C \cup \bigcup_{i=1}^k c^\top_i$ be the input to 3SAT-WITH-MAJORITY.


Negative edge weight cycle SSSP Why are we interested in negative edge weight cycles when finding out SSSP. In a path, we are not allowed to traverse a node more than once.

In a simple path, no node can be traversed more than once. However, paths in general can. The SSSP asks for single-source shortest paths, without specifying that the paths need to be simple. This allows the paths to contain cycles. Thus, negative cycles are a concern as they may allow arbitrarily "short" paths, and so the definition of a "shortest" path falls apart. This is because if a path contains a node on a negative cycle, we can always lower the cost of the path by going around the negative cycle.

Of course, this also depends on how you define a path, and how the SSSP has been presented to you. The above explanation assumes typical definitions of both, so if you have different definitions, please leave a comment.


When are invariants true inside of a loop? I am new to the idea of invariants and hope to find more information about it.

It can make an algorithm or loop show a high level of certainty / confidence that the code is correct, such as in the case of a binary search, as described in the book Programming Pearls, 2nd Ed.

Are invariants true at most part of the loop and can be untrue at some part? That is, in the middle of the loop:

while a <= b
    if (...)
        // Point A
    else
        // Point B
    end
    // Point C
end

is it true that at Point A or Point B, something can change that cause the invariants to break, and it depends on the next iteration to "correct the invariants"?  The same with Point C, something can change that can cause the invariants to break?

Maybe Point C is more likely the place where the invariants may break, as it is getting ready for the next iteration? So if it is a for-loop:

for(i = 0; i < n; i++) {
    // ...
}

then the i++ is a place where the invariant may break? I am looking if there is any rule that says what time may invariants not hold true, or should they always hold true?

It seems for binary search, the invariants are always true, while for mergesort or quicksort, the invariants are only true at a certain point, such as for mergesort, the array is divided into 2, and it is in sorted order, but this invariant is only true only after the code recursively calls itself to sort both the left and right subarrays. But this is recursion, so I don't know if there is any difference between that or just a loop.

Are invariants true at most part of the loop and can be untrue at some part?

Invariants hold prior and after each execution of the loop body; there are no requirements for what happens in between its statements. Not only that, I would even say it is quite the norm that invariants are broken during the loop. Fixing them is actually a sort of programming paradigm; it gives you a way of determining what the values for variable assignments in a loop should be. In fact, this is a quite natural concept if your design approach is based on invariants (e.g., if you are writing programs which are annotated with JML as in design by contract and similar ideas based on formal proof systems).

For instance, consider the following toy example in which we want to sum over the elements in an array $A$ and save the result in the variable $s$:

$$\begin{align*}
&s \gets 0  \\
&i \gets |A| \\
&\textbf{while } i > 0 \textbf{ do} \\
&\quad i \gets i - 1 \\
&\quad s \gets s + A[i] \\
&\textbf{done}
\end{align*}$$

The invariant is $s = \sum_{j=i}^{|A|-1} A[j]$, and it holds prior and after each execution of the loop body. However, after $i \gets i - 1$ is executed, the invariant no longer holds, that is, we then have $s = \sum_{j=i+1}^{|A| -1} A[j]$. Hence, the next instruction updates $s$ so that the invariant holds again.


If a solution to Partition is known to exist, can it be found in polynomial time? In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete.
Suppose we are given an instance and we know that it admits an equal-sum partition. Can this partition be found in polynomial time (assuming $P\neq NP$)?
Let's call this problem "GuaranteedPartition". On one hand, apparently one can prove that GuaranteedPartition is NP-hard, by reduction from Partition: if we could solve GuaranteedPartition with $n$ numbers in $T(n)$ steps, where $T(n)$ is a polynomial function, then we could give it as input any instance of Partition and stop it after $T(n)$ steps: if it returns an equal-sum partition the answer is "yes", otherwise the answer is "no".
On the other hand, the GuaranteedPartition is apparently in the class TFNP, whose relation to NP is currently not known.
Which of the above arguments (if any) is correct, and what is known about the GuaranteedPartition problem?

I think the whole misunderstanding comes from an incorrect definition of TFNP. TFNP is for problems like factoring, where there is always a solution. Every integer has a prime factorization, so you don't have to make any restrictions on what inputs are allowed - i.e., every input string of bits represents a number that has a factorization. This is different from a promise, which is more like what you're describing.
Unlike integers and factorizations, there are sets that do not have equal-sum partitions. And if you change the input format to be some strange representation of sets of integers such that every set represented always has a valid partition, then you change the problem entirely. A program that solves this new problem probably couldn't be used to solve the original NP-hard Partition problem.
(GuaranteedPartition is also not a decision problem, so it's not NP-hard either - although a machine that solved GuaranteedPartition could be used to solve anything in NP, as you point out.)


Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the predicate $P$, but we would like to sample or choose an element uniformly at random from $S' = \{ i \mid i \in S \wedge P(i) \}$.

The naive approach is to scan $S$ and for example record all the integers or indices for which $P$ holds, then choose one of them uniformly at random. The downside is that in the worst-case, we need $|S|$ space.

For large sets or in say a streaming environment the naive approach is not acceptable. Is there an in-place algorithm for the problem?

The following approach is often referred to as reservoir sampling. Start scanning the set $S$ and maintain an index $j$ to the set. The first element you encounter satisfying the predicate, set $j$ to it with probability $1/1$. Update your choice for $j$ when you encounter the second such element with probability $1/2$. When you encounter the $k$th element satisfying the predicate, set $j$ to it with probability $1/k$.

The algorithm works in $\Theta(n)$ time and in constant space. For correctness, it should be shown that every item has an equal probability of being chosen and that the events they are sampled are independent. The second claim of independency is obvious: our decisions are not based on whether we have previously sampled items. The first claim (equal likelihood) can be proven quite easily with induction.

For details, see J. S. Vitter, Random Sampling With a Reservoir, algorithm R. For a more compact presentation, see for example these slides.


CNF-SAT reduction problem variant I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to proceed:

Define 1/3-CNFSAT as follows: given a set of boolean variables and clauses in Conjunctive Normal Form, (this isn't 3-CNF SAT, as each clause may contain an arbitrary number of variables), does there exist a set of assignments to each variable such that exactly one-third of the clauses are satisfied?

Prove via reduction that 1/3-CNFSAT is NP-complete.

My initial thought process: Reduce CNF-SAT to 1/3-CNFSAT (Given: since any SAT formula can be reduced to CNF form, CNF-SAT is NP-complete).

So I was thinking, given some formula in CNF form, which contains C number of clauses, I was thinking we could add to it an additional 2C clauses, all of which are unsatisfiable. Then CNF-SAT would be satisfiable IFF 1/3-CNFSAT would be satisfiable.

Please let me know if my thoughts thus far are incorrect.

My problem now is how to come up with an additional 2C clauses all of which are false, and express each of them in CNF form. Obviously, something like the following clause would be inherently false:

(x1 AND ~x1)

But if I were to express it in CNF form, I'd have to do something like the following:

(x1 OR x1) AND (~x1 OR ~x1)

Or, even more simply:

(x1) AND (~x1)

But the problem is, only one of the above clauses is false for some given boolean assignment to x1. So, how do I come up with 2C false clauses and express them all in CNF form?

I hope this question makes sense. Thanks for help.

1/3-CNFSAT is very much similar to HALF-SAT, where instead of satisfying exactly half of the total number of clauses you are satisfying exactly one third of it. So the reduction from 3SAT is also quite similar. We reduce 3SAT instance, $\phi$, to a 1/3-CNFSAT instance as follows.

Let $z$ be a new variable not in $\phi$. Let there be $m$ clauses in $\phi$. We add $(z \lor \lnot z)$ and $2m+2$ copies of $(z)$ to $\phi$. In every exactly 1/3-satisfying assignment $z$ must be false.

Let $\phi \land (z \lor \lnot z) \land (z) \land (z) \land ... (2m+2) $ copies $...\land (z) = \phi'$. The following claim is easy to prove.

Claim: $\phi$ is satisfiable iff $\phi'$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq_P$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete.


What is a linearization point? With respect concurrent programming, what is a linearization point?

They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here.

  All function calls have a linearization point at some instant between their invocation and their response.

Okay that's fine, they occur somewhere within a function call, but what are they?

  All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition.

Occur instantly at their LP's??? I don't understand this.

I also read through this which attempts to prove LP's. I am having trouble finding any solid definitions. Could anyone help?

Sounds like you are reading The Art of Multiprocessor Programming.

  "All function calls have a linearization point at some instant between their invocation and their response"

    Okay that's fine, they occur somewhere within a function call, but what are they?

Side effects of the functions. http://en.wikipedia.org/wiki/Side_effect_(computer_science):

  A function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

In C/C++ side effects are basically writing to memory that is not on the function stack.

  "All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition"

    Occur instantly at their LP's??? I don't understand this.

It means that memory writes become visible to other CPUs in the system at that point. Imagine a function of 100 instructions. Instruction 90 is CAS which is a linearization point. Once the instruction has completed the effects of preceding memory writes become visible to other CPUs instantly (release semantics). This happens some time after the function has been called but before it returned (on instruction 90 of 100).

Note, that memory writes may not always be visible to other CPUs in the system if linearization points are not employed.


Creating a CFG from a specific CFL I am pretty desperate finding the correct context free grammar for the following language:
$$L=\{a^lb^mc^n \mid l,m,n \in \mathbb{N}_0, \, l\geq 2n+m\}$$

I would really appreciate if anyone could tell me how to generate the CFG from this language as I am stuck on this one for 2 days now.

I can't find a solution for adding the right amount of $b$'s and $c$'s to a generated string.

At the moment I have:
$$ \begin{align*}
S &\rightarrow aS \mid T \mid U \mid \varepsilon \\
T &\rightarrow aTb \mid \varepsilon \\
U &\rightarrow aaUc \mid \varepsilon
\end{align*}$$

It might be easier than you have been thinking.

$$\begin{aligned}
S&\rightarrow aS\mid U\\
U&\rightarrow aaUc\mid T\\
T&\rightarrow aTb\mid \epsilon
\end{aligned}$$

The idea is to identify the language that could be obtained by a fixed operation that peels off some symbols. Peeling off $a$'s, we shrink words in $S$ to words in $U$. Peeling off some $a$'s and $c$'s, we shrink words in $U$ to words in $T$.
$$\begin{aligned}
S&=\{a^ka^{2n}a^mb^mc^n \mid k,m,n \in \mathbb{N}_0\}\\
U&=\{a^{2n}a^mb^mc^n \mid m,n \in \mathbb{N}_0\}\\
T&=\{a^mb^m\mid m \in \mathbb{N}_0\}
\end{aligned}$$


Recurrence relation with sum This is a question about recurrence relation that contains sum inside the recursion.I am totally stuck. Can anyone help?

The problem asks to solve the following recursion $T(n)=\frac{1}{n} \sum_{i=1}^{n-1}(T(i)+T(n-i))+cn$. The problem also warns that unwrapping is going to be the wrong approach and the right strategy would be to guess the solution and prove it by induction. As the first step it suggests to start with $nT(n) -(n - 1)T(n -1)$.

The trick here is to get rid of the sum. Note that the sum is up and down, it can be replaced by twice up:
$$
\begin{align*}
  (n + 1) T(n + 1) &= 2 \sum_{1 \le k \le n} T(k) + c (n + 1)^2 \\
  n T(n)           &= 2 \sum_{1 \le k \le n - 1} T(k) + c n^2 \\
  (n + 1) T(n + 1) - n T(n) &= 2 T(n) + c (2 n + 1)
\end{align*}
$$
This is a linear, first order, non-homogeneous recurrence.

Update: Solution to the recurrence.

The recurrence can be written:
$$
\frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1} = c \frac{2 n + 1}{(n + 1)(n + 2)}
$$
This reduces to a sum:
$$
\begin{align*}
\frac{T(n)}{n + 1} &= T(0) + c \sum_{0 \le k \le n - 1}
                                 \frac{2 k + 1}{(k + 1) (k + 2)} \\
                   &= T(0) + c \sum_{0 \le k \le n - 1}
                                 \left(
                                   \frac{3}{k + 2} - \frac{1}{k + 1}
                                 \right) \\
                   &= T(0) + 3 c (H_{n + 1} - 1 - \frac{1}{2}) - c (H_n - 1) \\
                   &= 2 c H_n + (T(0) - 2 c) + \frac{3c}{n + 1} \\
T(n)               &= 2 c (n + 1) H_n + (T(0) - \frac{7 c}{2}) (n + 1) + 3 c \\
                   &\sim 2 c n \ln n
\end{align*}
$$
Here $H_n$ is the $n$-th harmonic number:
$$
H_n = \sum_{1 \le k \le n} \frac{1}{k}
    = \ln n + \gamma + O(1/n)
$$

The recurrence $x_{n + 1} - a_n x_n = f_n$ can always be reduced to a telescoping sum at the left side by multiplying by the summing factor:
$$
(a_n a_{n - 1} \ldots a_0)^{-1}
$$
$$
\frac{x_{n + 1}}{a_n a_{n - 1} \ldots a_0} - \frac{x_n}{a_{n - 1} \ldots a_0}
   = \frac{f_n}{a_{n + 1} a_n \ldots a_0}
$$


How can, e.g., Dijkstra find all shortest paths in linear time? As I understand one can modify BFS for unweighted graph or Dijakstra for weighted graph to find all possible shortest paths from $s$ to $t$ in linear time. But how can this be, when there are $O(2^n)$ such paths?
What am I missing here?

As you (almost) observe, there can be $2^{\Theta(n)}$ shortest paths between a pair of vertices:

       *   *           *
      / \ / \ /     \ / \
    s*   *   *  ...  *   *t
      \ / \ /       / \ /
       *   *           *

With $k$ cycles, this graph has $3k+1$ vertices and there are $2^k = 2^{n/3-1}$ shortest $s$–$t$ paths: you can go clockwise or anticlockwise around each cycle, independently of the others.

The simple answer to your question is that you are mistaken.  It is impossible for any algorithm to output all shortest paths in linear time (time $O(n)$), just because it is impossible to output an exponential amount of data in a polynomial number of steps: a Turing machine can only write one character of output per step.

Outputting all shortest paths is an example of an enumeration problem. Typically, we use different measures for these problems because it seems "unfair" to say that an algorithm is slow just because it has a lot of work to do.  The usual standard for enumeration algorithms is to look at the number of steps between each successive output. Using modified Dijkstra will (I assume) have polynomial delay: there's a constant $c$ such that, for any large enough graph on $n$ vertices, the algorithm will output some shortest path after at most $n^c$ steps and, after each output, there will be at most $n^c$ more steps before the algorithm outputs another shortest path or terminates.


How to describe algorithms, prove and analyse them? Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only about orders of growth. The TAOCP thoroughly changes my mind.

TAOCP uses English mixed with steps and goto to describe the algorithm, and uses flow charts to picture the algorithm more readily. It seems low-level, but I find that there's some advantages, especially with flow chart, which I have ignored a lot. We can label each of the arrows with an assertion about the current state of affairs at the time the computation traverses that arrow, and make an inductive proof for the algorithm. The author says:

  It is the contention of the author that we really understand why an algorithm is valid only when we reach the point that our minds have implicitly filled in all the assertions, as was done in Fig.4.

I have not experienced such stuff. Another advantage is that, we can count the number of times each step is executed. It's easy to check with Kirchhoff's first law. I have not analysed the running time exactly, so some $\pm1$ might have been omitted when I was estimating the running time.

Analysis of orders of growth is sometimes useless. For example, we cannot distinguish quicksort from heapsort because they are all $E(T(n))=\Theta(n\log n)$, where $EX$ is the expected number of random variable $X$, so we should analyse the constant, say, $E(T_1(n))=A_1n\lg n+B_1n+O(\log n)$ and $E(T_2(n))=A_2\lg n+B_2n+O(\log n)$, thus we can compare $T_1$ and $T_2$ better. And also, sometimes we should compare other quantities, such as variances. Only a rough analysis of orders of growth of running time is not enough. As TAOCP translates the algorithms into assembly language and calculate the running time, It's too hard for me, so I want to know some techniques to analyse the running time a bit more roughly, which is also useful, for higher-level languages such as C, C++ or pseudo codes.

And I want to know what style of description is mainly used in research works, and how to treat these problems.

There is a huge variety of feasible approaches. Which is best suited depends on

what you are trying to show,
how much detail you want or need.

If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can be said for analyses: if you need a rough upper runtime bound you proceed differently from when you want precise counts of statements.

I will give you three examples for the well-known algorithm Mergesort which hopefully illustrate this.

High Level

The algorithm Mergesort takes a list, splits it in two (about) equally long parts, recurses on those partial lists and merges the (sorted) results so that
the end-result is sorted. On singleton or empty lists, it returns the input.

This algorithm is obviously a correct sorting algorithm. Splitting the list and merging it can each be implemented in time $\Theta(n)$, which gives us a recurrence for worst case runtime $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$. By the Master theorem, this evaluates to $T(n) \in \Theta(n\log n)$.

Medium Level

The algorithm Mergesort is given by the following pseudo-code:

procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

We prove correctness by induction. For lists of length zero or one, the algorithm is trivially correct. As induction hypothesis, assume mergesort performs correctly on lists of length at most $n$ for some arbitrary, but fixed natural $n>1$. Now let $L$ be a list of length $n+1$. By induction hypothesis, left and right hold (non-decreasingly) sorted versions of the first resp. second half of $L$ after the recursive calls. Therefore, the while loop selects in every iteration the smallest element not yet investigated and appends it to result; thus result is a non-increasingly sorted list containing all elements from left and right. The reverse is a non-decreasingly sorted version of $L$, which is the returned -- and desired -- result.

As for runtime, let us count element comparisons and list operations (which dominate the runtime asymptotically). Lists of length less than two cause neither. For lists of length $n>1$, we have those operations caused by preparing the inputs for the recursive calls, those from the recursive calls themselves plus the while loop and one reverse. Both recursive parameters can be computed with at most $n$ list operations each. The while loop is executed exactly $n$ times and every iteration causes at most one element comparison and exactly two list operations. The final reverse can be implemented to use $2n$ list operations -- every element is removed from the input and put into the output list. Therefore, the operation count fulfills the following recurrence:

$\qquad \begin{align}T(0) = T(1) &= 0 \\
T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

$\qquad \begin{align}T(0) = T(1) &= 0 \\
T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

By the Master theorem, we get $T \in \Theta(n \log n)$ which extends to the runtime of mergesort.

Ultra-low level

Consider this (generalised) implementation of Mergesort in Isabelle/HOL:

types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

This already includes proofs of well-definedness and termination. Find an (almost) complete correctness proof here.

For the "runtime", that is number of comparisons, a recurrence similar to the one in the prior section can be set up. Instead of using the Master theorem and forgetting the constants, you can also analyse it to get an approximation that is asymptotically equal the true quantity. You can find the full analysis in [1]; here is a rough outline (it does not necessarily fit the Isabelle/HOL code):

As above, the recurrence for the number of comparisons is

$\qquad \begin{align}f_0 = f_1 &= 0 \\
f_n &= f_{\left\lceil\frac{n}{2}\right\rceil} + f_{\left\lfloor\frac{n}{2}\right\rfloor} + e_n\end{align}$

where $e_n$ is the number of comparisons needed for merging the partial results². In order to get rid of the floors and ceils, we perform a case distinction over whether $n$ is even:

$\qquad \displaystyle \begin{cases}
f_{2m}   &= 2f_m + e_{2m} \\
f_{2m+1} &= f_m + f_{m+1} + e_{2m+1}
  \end{cases}$

Using nested forward/backward differences of $f_n$ and $e_n$ we get that

$\qquad \displaystyle \sum\limits_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f_k = f_n - nf_1$.

The sum matches the right-hand side of Perron's formula. We define the Dirichlet generating series of $\Delta\kern-.2em\nabla f_k$ as

$\qquad \displaystyle W(s) = \sum\limits_{k\geq 1} \Delta\kern-.2em\nabla f_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits_{k \geq 1} \frac{\Delta\kern-.2em\nabla e_k}{k^s}}_{=:\ \boxminus(s)}$

which together with Perron's formula leads us to

$\qquad \displaystyle f_n = nf_1 + \frac{n}{2\pi i} \int\limits_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$.

Evaluation of $\boxminus(s)$ depends on which case is analysed. Other than that, we can -- after some trickery -- apply the residue theorem to get

$\qquad \displaystyle f_n \sim n \cdot \log_2(n) + n \cdot A(\log_2(n)) + 1$

where $A$ is a periodic function with values in $[-1,-0.9]$.

Mellin transforms and asymptotics: the mergesort recurrence by Flajolet and Golin (1992)
Best case: $e_n = \left\lfloor\frac{n}{2}\right\rfloor$
Worst case: $e_n = n-1$
Average case: $e_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$


3 dimensionnal matching to partition transformation We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set $M = W \times X \times Y$, but I don't know why they add two other elements $b_1$ and $b_2$ with definition
$$
s(b_1) = 2 (\sum_{i=1}^{k} s(a_i)) - B \\
s(b_2) = (\sum_{i=1}^{k} s(a_i)) + B
$$

with $B$ being:
$$
 B = \sum_{j = 0}^{3q - 1} 2 ^ { pj}
$$
and $p = [log_2(k)] + 1$ and $q$ is the number of elements in $X$ (Y, W also have the same number of elements) and also $k$ is the number of triples in $M$.

It would be very nice if anyone could clarify this transformation.

What they actually do is a composition of two reductions (and some optimization). The first is from 3DM to SUBSET-SUM, and the second is from SUBSET-SUM to PARTITION. For the first part, I have it written down here, and the second reduction is quite well known, e.g. here.

Note that there is a small caveat in the first reduction, where we assume that the numbers are encoded in base $|X|+1$, while SUBSET-SUM requires the numbers to be in binary. The reduction you mention does the conversion explicitly, which accounts for the strange $p$ you encountered (which is just the base-conversion constant).


How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive? I am trying to prove that the language

$$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$

belongs to Co-RE but not R.

Showing $\overline{L}\in$ RE is pretty much straightforward, but I also want to show that $L\notin$ R.

My idea was a reduction $\overline{H_{\text{TM}}}\le_mL$ but I struggle to figure out how to do it.

Any help/guidance will be much appreciated.

Preparation

Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148).

Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never halts.

You have done the initial analysis correctly, pointing out a reasonable solution could be constructing a reduction $\overline{H_{\text{TM}}}\le_mL$. That is, for a TM $N$ and a word $w$, we should construct a Turing machine $M_{N,w}$ such that
 $$N(w) \uparrow\  \Leftrightarrow\  \langle M_{N,w}\rangle\in L.$$

For simpler notation, we will write $M$ to mean $M_{N,w}$.

Outline of the construction

Basically, we will let $M$ on input $x$ simulate $N$ on $w$ for $|x|$ steps. In case when $N$ on $w$ halts eventually, we will let $M$ run forever when the input is long enough.

Detailed explanation

The basic intuition is that $M$ will have to simulate $N$ on $w$ in some way since the only way to find whether $N$ on $w$ halts eventually is to run $N$ on $w$.

The first problem is the input to $M$ can be any word, which has probably nothing to do with $w$. On the other hand, how long $M$ may run depends on the length of the input.

Here is a simple approach. We will let $M$ compute how long the input is but ignore the actual content of the input otherwise. Moreover, $w$ will be encoded in the specification of $M$ so that $M$ will be able to put $w$ on the tape, which can be treated as the input to the simulated $N$.
The next problem is how to ensure $\langle M\rangle\in L$ if $N(w) \uparrow$. Assume $N(w)\uparrow$.

For short input, $M$ cannot be running too long for $\langle M\rangle$ to be in $L$.

The idea to prevent $M$ from running too long is simple. $M$ will halt once it has done reading the input if the input is not long. More specifically, let $M$ have state $s_0$, $s_1$, $\cdots$, $s_{t}$ for some $t$ where $s_0$ is the start state. When $M$ in state $s_i$ reads a cell, it halts if the cell means the end of input. Otherwise it advances to the next cell, updating its state to $s_{i+1}$. So, on every input $x$ of length at most $t$, $M$ will halt in $|x|+1$ steps, which is less than $4|x|^2$ steps.

Note that we can set $t$ to an arbitrary positive integer.

Also note that the action above will be performed regardless of whether the input is short or not, since $M$ doesn't know whether the input length is less than or equal to $t$ beforehand.
The next problem is how to prepare $M$ for simulating $N$ on $w$ once it has reached state $s_t$, which will happen if $|x|>t$.

$M$ should store the length of input while erasing the input. Here are the details.

First it goes back to the start of the input. We will refer this cell as $S$.
Write 0 to the left of $S$.
Switch direction to erase the first symbol of the input.
Switch direction to change 0 to 1.
Switch direction to erase the first symbol of the remaining input.
Switch direction to change 1 to 10, which is 2 in binary representation.
Switch direction to erase the first symbol of the remaining input.
Switch direction to change 10 to 11, which is 3 in binary representation.
And so on until $M$ passes the end of the input, at which time the non-blank symbols to the left of $S$ is the length of the original input in binary representation.
$M$ goes back to $S$. Switch direction to write $w$ on the tape. Switch direction to go to $S$.

All 10 items above can be done by $M$ in $c(x)<|x|^2+O(|x|)$ steps for input $x$. We can set $t$ to be large enough so that $c(x)+|x|+1<\frac32|x|^2$ for all input $x$ with $|x|\gt t$. The "$|x|+1$" at the left hand side of the inequality comes from the previous item.
How should $M$ simulate $N$ on $w$ as well as maintain the number to the left of $w$ on the tape so that $M$ will not be running too many steps?

Thanks to the number $|x|$ to the left of $w$ on the tape, we can let $M$ simulate $N$ on $u$ for $|u|$ steps and then halt. Note that at the end of item 2.2.10, $M$ should be in a state that corresponds to the start state of $N$. The head of $M$ is on the top of $S$, which is the first of the cells whose content is $w$. Now we let $M$ loop the following.

Read the current symbol.
If the current symbol is the last binary digit of that number, it means the simulated $N$ is supposed to read a blank symbol. So, let $M$ move all symbols to its right one cell to the right as well as setting $S$ to the blank symbol at last. Now $M$ should be on top of $S$, a blank symbol. Let $M$ read $S$, the (new) current symbol.
Simulate $N$ on the current symbol. Mark the (new) current symbol.
Move to the left of S. Decrease the number by 1.
If the number is 0, break the loop. Otherwise, go back to the marked symbol and start a new round of the loop.

This stage, stage 3 can be done in at most $\frac52|x|^2$ steps.

In summary, $M$ will run at most $4|x|^2$ steps regardless whether $|x|\le t$ or $|x|\gt t$, as long as $N(w)\uparrow$.
The last problem is how to ensure $\langle M\rangle\notin L$ if $N(w) \downarrow$.

$M$ must always be run as specified in item 2 above since $M$ does not know whether $N$ on $w$ will halt eventually or not beforehand. However, what $M$ should do is not specified at the moment when the simulated $N$ on $w$ halts. That will happen when the length of the input to $M$ is larger than the number of steps $N$ will have run before halting. Well, in that case, we will let $M$ just loop forever, which ensures that $\langle M\rangle\notin L$.

Exercises

Exercise 1. Explain that the reduction above can be algorithmic. In particular, the value of $t$ in item 2.2 can be determined algorithmically.

Exercise 2. Explain why $L_{2019}=\{M\mid M$ $\text{is a TM and for all}$ $x\in \Sigma^*$, $M\text{ on }x$ $\text{runs at most}$ $\max(2019,\dfrac{|x|^2}{2019})$ $\text{ steps}\}$ is also undecidable.

Exercise 3. Show that $\{\langle M\rangle\mid M$ $\text{is a TM that halts in }$ $O(n^2+1)\text{ steps where}$ $n$ $\text{ is the length}$ $\text{ of the input}\}$ is undecidable.