Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free? Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$

As pointed out by sdcvvc, a word in this language can also be described as the concatenation of two words of the same length the hamming distance of which is 2 or greater.

I think it's not context free but I'm having a hard time proving it. I tried intersecting this language with a regular language (like  $ \ 0^*1^*0^*1^* $ for example) then use the pumping lemma and \ or homomorphisms but I always get a language that is too complicated to characterize and write down.

Note [2019-07-30] The proof is wrong ... the question is more complicated than it sounds.

After a failed attempt here it is another idea.

If we intersect $L$ with the regular language $L_{reg} = 0^*10^*10^*10^*$ we get a CF language.

Perhaps we can have more luck if we use $L_{reg}' = 0^*10^*10^*10^*10^*$ (a string with exactly 4 1s).

Let $L_1 = L \cap L_{reg}'$, informally $w \in L_1$ if it can be split in two halves, such that one half contains exactly $\{0,1,3,4\}$ $1s$  or both halves contain two $1$s but  their positions don't match.

Suppose that $L_1$ is CF and let $G$ be its grammar in Chomsky normal form, and let

$$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$$

We have $|u|=|v|$ (even length) and $d(u,v) \geq 2$

If we restrict our attention to the ways in which the four 1s of $w$ can be generated we have the three cases shown at the top of the figure 1. The central part of the figure 1 shows the first case (but the others are similar).

Figure 1 (the full picture can be downloaded here)

If we pick $a=e, c=2a$ and $b,d \gg a$ we see that the zeros between the two pairs of 1s must be independently pumpable (red nodes in the figure): in particular, for large enough $b \gg a$, we get a duplicate nonterminal node on a internal subtree (node X in figure 2)  or a repeated subsequence in the path towards the first or the second 1 (node Y in figure 2). Note that Figure 2 is a little bit simplified: there can be more nonterminal nodes between the two $X$s, and also between the two $Ys$ ($Y\to ... \to Z_i \to ... Y$ but with $Z_i$ that produces only 0s on the right of the first 1).

Figure 2

So we can fix an arbitrary $a = e = k, c = 2a$, then pick large enough $b$ to get an independently pumpable node on the sequence of zeros between first and second $1$. For the sequence of zeros between the third and fourth 1, we can choose $d = b! +b$.
But $0^b$ is independtly pumpable so there is a $p \leq b$ pumpable substring $y$, i.e. such that $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ and $xy^iz = b!+b$. The string we get is:

$$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$$

but $w' \notin L_1$. Thus $L_1$ is not CF and finally $L$ is not CF.

If the proof is correct (???) it can be extended to every language $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$

by this question I think $L$ is context-free and generated by the following grammar
$\qquad\begin{align}
  S &\to AXBY \mid BYAX \\
  A &\to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1 \\
  B &\to 1 \mid 0B0 \mid 0B1 \mid 1B0 \mid 1B1  \\
  X &\to 0 \mid 0X0 \mid 0X1 \mid 1X0 \mid 1X1 \\
  Y &\to 1 \mid 0Y0 \mid 0Y1 \mid 1Y0 \mid 1Y1  \\
\end{align}$


Algorithm for scheduling unit time tasks with arrival times and deadlines Suppose we have $n$ tasks to order over $n$ days.
Each tasks takes 1 day to be completed.
Each task has a start date when the task becomes available and a deadline when the task must be delivered.

Here is an example:

Is there an algorithm that can solve this problem with a worst case efficiency of $O(n)$ where $n$ is the number of tasks and days.

The more general version of your problem is the scheduling problem where we have $n$ independent tasks, each with an arrival time, a resource requirement (time), and a deadline. We define the Earliest Deadline First algorithm such that at every timepoint, we choose to process the task with the nearest deadline. While time is continuous, it is trivial to see that we can discretize time to be all points at which a task finishes or a new task arrives.

It is known that EDF is an optimal uniprocessor scheduling algorithm i.e. if there is a feasible schedule, EDF will find it and if EDF does not find a feasible schedule, then no feasible schedule exists. [1], [2]. However, this is not linear time if we aren't guaranteed an ordering of the deadlines of the arriving tasks. Let's use a priority queue to represent the waiting tasks. At every time point, which there are $O(n)$ of, we must insert and/or pull the next task from a priority queue sorted on deadlines. Each insertion is $O(\log n)$ time, thus resulting in $O(n\log n)$ time.

If your input was sorted by arrival, we could easily find whether or not there is a valid schedule by following the algorithm above, iterating through the days, adding tasks for that day to a priority queue and selecting the task with the nearest deadline from the queue. We fail if we ever try to assign a task to a day on or past its deadline.

As mentioned in the comments, we can sort the input by arrival time in linear time using counting sort or pigeonhole sort. The issue then is to somehow make the priority queue also linear time.

As each task has the atomic time step as duration, you can consider your scheduling problem as an assignment problem :

You have N tasks and N days and have to assign each task a day. Just consider a bipartite graph with N "task" nodes on a side and N "days" tasks on the other. There are edges between a task and a day when assignement is possible ($start \le day \le deadline$). The problem is now to select exactly N edges with one per task and one per day.

Then the best is probably to use an Hopcroft-Karp algorithm to look for the maximum cardinality assignment. If a perfect solution exists, it would be found else the number of "lost" task would be minimized.

This algorithm is $O(|E|\sqrt N)$ with $E$ the set of edges in the bipartite graph. If the time slots of the tasks are short with respect to the whole time horizon ($deadline - start \ll N$), then this algorithm is near-linear in the number of edges $O(|E|)$.


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

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

I understand the notion of:

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

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

8 1 9 3 5 7 6

Here, 6 is my pivot

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

8 1 9 3 5 6 7

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

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

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

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

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

Here is the code:

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

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

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

        return i+1;
    }

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

        printArray(arr);

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

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

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

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

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

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

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

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

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

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

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

“7 is larger than 6...”

Stop right there. You start looking for items larger than the pivot from the left. So you process 8, then you process 9.


Grammar that numbers of letters `c` is greater than number of letters `b` Exactly as stated in the subject. I look for grammar which use letters $a, b ,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$ is generated by the grammar.

I thought about:

$S \rightarrow aS \mid bS \mid SCS$

$ C \rightarrow cb \mid ca$

but not sure if it works. Could you help me, please.

Your grammar never accepts a word since you can't make the $S$ disappear.

If you want to create more $c$ than $b$ you just have to make sure that when you create a $b$ you create a $c$ with it (but be careful they don't need to be side to side). You can also generate as much $a$ or $c$ as you want.

If you need more indication please ask.

$S \rightarrow SbS \mid bSS \mid SSb \mid b \mid bX \mid Xb$

$X \rightarrow bB \mid cA$

$A \rightarrow cX \mid cAA \mid b$

$B \rightarrow cX \mid bBB \mid b$


If the two generals problem is unsolvable how can we human beings agree on things? If the two generals problem is unsolvable how can we human beings agree on things?

I mean, we communicate everyday and have the same limitations as any communication problem handled by computer science. Why doesn't it affect us?

I disagree with other answers that the communication channel needs to be modelled differently. Malice is irrelevant, simple lost messages with any non-zero probability are sufficient to create the two generals problem. e-mail and IM, for example, have a low but not zero chance of dropping messages. Phone calls can suffer interference, so as with the two generals problem you need to somehow confirm whether the other person heard what you said, ad infinitum. And yet I frequently use these channels to make agreements with other people.

What the insoluble "two generals" problem fails to solve, is to get guaranteed common knowledge. In real life we don't require formal common knowledge in order to proceed. Therefore the goal in most practical situations needs to be described differently from the goal in the two generals problem.

We settle for agreement being "sufficiently likely". I might not be willing to attack unless I'm certain you will attack, but I'm willing to walk to the coffee shop to meet you provided that the probability of a communications failure isn't grossly higher than the probability of you failing to arrive due to traffic. Unlike the generals, I'll take a chance on you meeting me.

If you've ever had someone explain something three times to you in different ways when you got it the first time, or ever had someone ask you to confirm something that you've already confirmed twice, then it's because you reached your threshold of "sufficiently likely" before they reached theirs.

Take your pick of psychology, philosophy, or evolutionary biology as the correct realm in which to look for an answer to the next question, why we don't really need a full guarantee of common knowledge :-)

It also relates back to practical problems in computing. For example when we use a single-error-correcting code to "validate" that a symbol in a message has arrived correctly, all we're doing is accepting that the probability of a double-error is negligible for the time being. Then later in the protocol we might have a CRC, to further reduce the probability of undetected error. None of this solves the two generals problem, but it is sufficient for me, my bank and a merchant all to "agree" that a credit card transaction has occurred, with a small probability that we disagree.

Can you give me the exact value of pi in decimal notation? We humans round-off and approximate when we know the exact value is unsolvable.


Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time? The worst case running time of insertion sort is $\Theta(n^2)$, we don’t write it as $O(n^2)$.

$O$-notation is used to give upper bound on function. If we use it to bound a worst case running time of insertion sort, it implies that $O(n^2)$ is upper bound of algorithm no matter what type of input is, means it doesn’t matter whether input is sorted, unsorted, reverse sorted, have same values, etc the upper bound will be same $O(n^2)$. But this is not the case of insertion sort. Insertion sort running time depends on type of input used. So when the input is already sorted, it runs in linear time and doesn’t take more that $O(n)$ time.

Therefore to write insertion sort running time as $O(n^2)$ is technically not good.

We use $\Theta$-notation to write worst case running time of insertion sort. But I’m not able to relate properties of $\Theta$-notation with insertion sort, why $\Theta$-notation is suitable to insertion sort.If $f(n)$ belong to $\Theta(g(n))$ we write it as $f(n)= \Theta(g(n))$, then $f(n)$ must satisfies the properties. And properties state that there exits constants $c_1$, $c_2$ and $n_0$ such that $0$$\leq$$c_1\cdot g(n)$$\leq$$f(n)$$\leq$$c_2\cdot g(n)$ For all $n>n_0$. How does the insertion sort function lies between the $c_1\cdot n^2$ and $c_2\cdot n^2$ for all $n>n_0$.

Running time of insertion sort as $\Theta(n^2)$ implies that it has upper bound $O(n^2)$ and lower bound $\Omega(n^2)$. I’m confused as to whether the lower bound on insertion-sort is $\Omega(n^2)$ or $\Omega(n)$.

You are confusing two different notions.
The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.

The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.

Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.

It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.

As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.

You can say the following: when you walk home, in the worst case you will walk exactly 10 km. This is true, and it implies that you always walk at most 10 km. But the former is a stronger claim, so why not use it?

In general you don't use the theta function for the worst case, but for an average one.

The insertion sort algorithm has a linear time when the array is already sorted: Ω(n); and a quadratic time when it's sorted in the opposite order: O(n^2).

An average case won't have many already sorted elements so it will be next to the worst case[*]; a better one, but within the same quadratic order: Θ(n^2).

As a conclusion, you should always use both Ω and O function for describing the algorithm but, if the majority of the cases is around a Θ function, is ok to use only it.

[*]: That's because is the inner cycle that bears on the resulting time.


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

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say "or more," I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?

Yes.  You can solve this in polynomial time.  The same strategy as in Are SAT problems with at most one false clause NP-complete? works.

Let $\varphi$ denote the CNF formula you care about, and $n$ the number of variables in $\varphi$.  Let $A_{i,j}$ denote the number of truth assignments that do not satisfy clauses $i$ or $j$ of $\varphi$, let $A_i$ denote the number of truth assignments that do not satisfy clause $i$ but do satisfy all other clauses of $\varphi$, and let $A$ denote the number of truth assignments that satisfy all clauses of $\varphi$.

These three cases are mutually exclusive.  Therefore,

$$\sum_{i,j} A_{i,j} + \sum_i A_i + A = 2^n,$$

where $n$ counts the number of variables in the formula.  In other words,

$$A = 2^n - \sum_{i,j} A_{i,j} - \sum_i A_i.$$

You can compute $A_i$.  Let $S_i$ denote the set of variables mentioned in clause $i$.  There is only one assignment to the variables in $S_i$ that will make clause $i$ false, so substitute in those values for the variables in $S_i$ and simplify the formula; the result is a CNF formula $\varphi'$ where we are guaranteed that every assignment to the remaining $n-|S_i|$ variables satisfies at most one clause, so https://cs.stackexchange.com/a/115849/755 tells us how to count the number of satisfying assignments to $\varphi'$, say $n_i$.  Then $A_i = n_i$.

You can compute $A_{i,j}$.  It is either $2^{n-|S_i \cup S_j|}$ or $0$, depending on whether there is any variable $x_k$ such that both $x_k$ and $\neg x_k$ appear in those clauses $i$ and $j$ of $\varphi$.

Therefore, you can compute $A$, the number of assignments that satisfy the formula.  Now, if $A \ne 0$, then you know that the formula is satisfiable; if $A=0$, the formula is not satisfiable.

It depends on the availability of data...

If you store the relaitonships between the data rather than trying to compute at runtime then it is an o1 operation with massive storage requirements...

Otherwise arbitrarily hard..


Can any recursion implementation be written as tail-recursion? Can any method that uses recursion be written as tail-recursion?

You can't rewrite all your recursive calls as tail recursive calls but you can rewrite your program in continuation passing style which is closely related and has the feature that every procedure call is a tail call (just not necessarily a tail recursive call.)

The way you do this is by recognizing that every time you make a procedure call you are implicitly specifying a return point.  Then you split your procedure into multiple procedures, each starting at a return point and ending at the next call point.  Continuation-passing style essentially makes the stack explicit.  Once the stack is explicit it is easier to apply certain optimization (like tail recursion elimination).

Example

procedure depth_first(t):
  if not-null(t):
    l = depth_first(t->left)
    r = depth_first(t->right)
    return l + r + 1
  else:
    return 0

The first step is to make every procedure take an extra parameter, k which is a continuation procedure (a procedure which you return to by calling it with the return value as its parameter).  Then you turn the procedure "inside out":

procedure depth_first(t, k):
  if not-null(t):
    depth_first(t->left,
       lambda(l):
         depth_first(t->right,
           lambda(r):
             k(l + r + 1)
  else:
    k(0)

Should you do it?  Well, if you're a compiler and you want to perform tail-recursion elimination optimizations, or generate machine code, then yes.  Otherwise probably not.  One of the joys of high level languages is that they have syntax that makes continuations much easier for humans to read and understand.  Let the compiler do what it's best at and concentrate on writing maintainable code.

Good practice, however understood, does have various style
implications, and encourages some programming paradigms over others,
but I do not know that using tail recursion is part of it. Some people
do prefer recursive style for various reasons, and that may result in
a lot of tail recursion.  That used to be very common in languages
like Lisp or Scheme, and their programmers were probably the first to
notice the issue below.

Tail recursion was identified originally (afaik) as a situation where
compilers could speed up execution by replacing them by a loop, and
saving on stack management. It is only what the name says: a tail
recursion, i.e. a recursive call that is the last thing done by the
function before returning.

It is a property of the source code. Object code does not have
recursion (other than possibly for high level virtual machines, not
for tangible hardware), only loops and memory management. Thus no
implementation of anything is written as recursion of any kind,
including tail recursion.

If that sentence was supposed to ask whether a non-tail recursion can
be compiled in the same way as a tail recursion is compiled, the
answer is no because non-tail recursion requires preserving existing
execution environments (so-called activation blocks) on the stack
(usually), for whatever code remains to be executed on return. Only
tail recursion can avoid that, since it will not have anything to do
on return (well, it is the general idea, some details are skipped).

Of course, all recursions can be transformed into loops with some
effort. That is precisely what the compiler does, since object code
has no recursion. Then the program has no recursions that are not tail
recursions, not having any at all (as David Richerby remarked). Furthermore, translating back in a language
rich enough, a loop can be replaced by a tail recursion (skipping many
details), so that you can have it all with tail recursion. But it does
you no good. It is only an intellectual exercise.

I cannot say this reply was not influenced by David Richerby very good
comment.


Building cycle in rectangle I have to build a cycle with fixed length $n$ that includes exactly $k$ corners inside $w$ x $h$ rectangle.

For example:
$w = 5\\h=3$

$n = 12\\k = 6$

I have already found out that I need at least $4$ corners and number of corners and number of non-corner elements needs to be even number.

Then I write an recursive algorithm that runs in exponential time complexity, but I have a strong feeling that this thing can be done much faster.

Problem is that I do not know which square will definitely be in the cycle so I run my algorithm on first $\frac w2$ fields to cover all chances, but I am aware that I search some branches multiple time.

I have also discovered that if the cycle exist it will start with corner in (0, 0) or corner in (0, 1)

Does anybody have an idea on how to speed this thing up?

Have a nice day!

your problem looks inherently exponential to me to find all the solutions. a rough sketch to show that is to create a large # of similar-looking objects. the objects are the same under translation and rotation. they (apparently?) can also be scaled. so in a rough sense there is no way to "speed it up" if you already have an exponential time algorithm. you ask for a better algorithm but also ask for general ideas. here are some ideas/ suggestions.

youve abstracted the problem but it might help to step back and describe the background that inspired it. is it from some field in particular? chances are there are papers that study the general area.
it looks like its in NP because its easy to verify solutions. think of solving it in terms of NP. a canonical problem in this area is the satisfiability problem. many problems have been converted to it and SAT solvers are "state of the art" for solving NP problems. SAT solvers can discover and handle the intrinsic symmetries in the problem not technically "efficiently" (in the sense of guaranteed P time) but in the "most efficient way known" based on heuristics, "best practices", and decades of optimization research/ theory. so consider translating it to SAT and studying it that way.
if you want a general idea of the algorithm behavior you can run it at different scales and graph the # of solutions to find basic scaling properties.
if you just want any solution, you might try a probabilistic approach where you lay down a simple starting shape say square/ rectangle and then randomly alter it until it gets closer to your requirements. see eg heuristics. genetic algorithms are also good for this. you can encode the shape in terms of genetic coding.
imagine a triangular shape that has 2 straight sides at right angles and then a 3rd that is diagonal and has any # of corners required. its not an "efficient" use of space because it has a large open area but it satisfies your criteria and can be created at any scale with arbitrary # of corners. you didnt specify any criteria about minimizing or maximizing space inside or outside. so maybe this is a bit underconstrained as stated.
actually think this might need to be described better. are you touching squares only at the edges squares and the squares touching those edge squares? what do you mean by "corners"? corners on your object? corner squares on the rectangle? you give only one example so think your description is somewhat ambiguous or subject to misinterpretation on closer inspection.


Are there deterministic and/or non-interactive zero-knowledge proofs? The Wikipedia page on zero-knowledge proof says

  Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.

Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?

Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.

Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies.  See Wikipedia for many references.

In reality, there is no point in this distinction, because, even a conventional proof is probabilistic since there will always be a small probability that a cheating prover found the right solution by chance.

If fact, the only difference, is that in conventional methods, there is one good answer, the prover must prove he knows it, and must have a very small probability of success if it's not the case. However, in zero knowledge, the same proving protocol can be repeated any time you want with different data and for that reason, the probability of success of one iteration can be much larger, but if you repeat it a sufficiently large number of times, you will get the same level of security.


Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess? The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and pick the best sequence of moves so far.

Let's suppose we remove this limit, and we search for the whole tree. Would this techinque always win? If the answer is no, would it ever lose? (so, would it only win+draw, or also lose?)

A good answer would include theoretical underpinnings of why or why not this would work, both from the game-theoretic aspects of chess and from the proprieties of the minmax algorithm.

By definition, minmax chooses the move that results in the best possible outcome if the adversary plays optimally, but within the bounds of what the evaluation function takes into account. More precisely, minmax results in the best outcome that can be guaranteed no matter how the adversary plays, as long as the adversary's behavior is no worse than what the evaluation function predicts.

If minmax searches on the whole tree, then it never calls the evaluation function, and therefore it models the adversary perfectly. So in this case, minmax achieves the best guaranteed outcome that can be guaranteed against an arbitrary adversary. This is true regardless of the game.

For chess, there are three possible outcomes: win, draw, loss (from best to worst). We don't know what the best guaranteed outcome for each player is. But whatever it is, if you can run minmax on the whole tree, you'll get that outcome or better (the outcome can be better if the adversary plays suboptimally). Of course, this is only practical near the end of the game when there are few pieces remaining in play.

Nobody knows if chess is a forced win for white, or even a forced draw for white.

If it is a forced win, then white with optimal gameplay will always win. If it is a forced draw, then white with optimal gameplay will always at least draw, and may win if black doesn't play perfectly. If it is neither a forced win nor a forced draw, then white with optimal gameplay will lose unless black makes a mistake.

If both white and black examine the complete game tree and always play optimally, then the outcome will always be the same (but we don't know if it will be white win, draw, or black win).

The answer to your question is quite trivial, nothing deep to see here or required.


Efficient algorithm to find subgraph I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.

My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

Provider nodes
Consumer nodes
Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).

OK, it sounds like your problem is the following:

  You have an undirected graph.  Each vertex is either a consumer or a producer.  Say that a consumer $c$ is connected to a producer $p$ if there is a path from $c$ to $p$ where all intermediate nodes are consumer nodes.  You want to output a list of pairs $(c,p)$ where $c$ is connected to $p$.

This problem can be solved in a straightforward, clean, and efficient manner, using an algorithm for connected components.  Here is the algorithm:

Remove all of the producer nodes, keeping only the consumer nodes and the edges from a consumer node to a consumer node.
Compute connected components on this smaller graph.  Let the connected components be $C_1,\dots,C_k$.
Now, back in the original graph, shrink all of the consumer nodes in the same connected component into a single node.  Thus, we get an edge from connected component $C_i$ to producer $p$ if there is any consumer $c$ in $C_i$ that has an edge to $p$.
This resulting graph now describes the connectivity relationship.  In particular, for each consumer $c$ and each producer $p$, $c$ is connected to $p$ if and only $C_i$ has an edge to $p$, where $C_i$ is the connected component containing $c$.

For instance, to output the list of all pairs $(c,p)$ that are connected, you can do the following:

For each connected component $C_i$, for each provider $p$ that has an edge from $C_i$ to $p$, for each consumer $c$ in $C_i$, output the pair $(c,p)$.

This algorithm runs in linear time.  The running time to compute the connectivity graph (produced in steps 1-3) is $O(m+n)$, where $n$ is the number of nodes and $m$ is the number of edges (interconnections) in the original graph.  The running time in step 4 could be as large as $\Theta(n^2)$, since there might be as many as $\Theta(n^2)$ such pairs.  However, here's what we can say.  If the correct output has length $\ell$ (i.e., there are $\ell$ pairs $(p,c)$ that are connected), then step 4 will have running time $O(\ell)$.

Therefore, the total running time is $O(m+n+\ell)$, i.e., linear in the sum of the size of the input and the size of the output.  This is as fast as you could possibly hope for.

If you don't need to output the set of all pairs $(c,p)$ explicitly, but you just want a compact representation of this connectivity information, you can use the graph computed in steps 1-3 as that compact representation.  Then the running time is $O(m+n)$.

(am going to take a stab at this with the partial information at this point & possibly modify it on further clarification by questioner.) the Djikstra shortest path algorithm (which basically adds the shortest weighted new edges in the "frontier set") can be run in parallel across multiple starting nodes (but havent seen a ref to this). it sounds like that would give you close to what you want. the starting nodes in your case are the providers. as the edge/vertex set expands, this will eventually "touch" all consumers, and the shortest path to any provider from any consumer can be calculated.


Difference between a turing machine and a finite state machine? I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one another.

Here's what I know it's different:

  FSM has sequential states depending on the corresponding condition met while Turing machines operate on infinite "Tape" with a head which
  reads and writes.

  There's more room for error in FSM's since we can easily fall on a non-ending state, while it's not so much for Turing machines since we
  can go back and change things.

But other than that, I don't know a whole lot more differences which make Turing machines better than FSM's.

Can you please help me?

The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory.

Intuitively, DFAs have no "scratch" memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.

Intuitively, TMs have a "scratch" memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.

A DFA may be thought of as a TM that neither changes any tape symbols nor moves the head to the left. These restrictions make it impossible to recognize certain languages which can be accepted by TMs.

Note that I use the term "DFA" rather than "FSM", since, technically, I'd consider a TM to be a finite-state machine, since TMs by definition have a finite number of states. The difference between DFAs and TMs is in the number of configurations, which is the same as the number of states for a DFA, but is infinitely great for a TM.

A Turing machine can store, as part of the tape, things it want to remember.


Difference between multitasking, multithreading and multiprogramming I was a little confused between these three terms Multitasking, Multithreading and Multiprogramming

Although every one means executing different lines of codes, and for every one we need something like Task State Segment or context to store data for that particular thread/task.

I am missing something, can anyone give me the basic difference between them and how they are actually executed in a processor

Edit: Actually I was a guy from Electronics background and I was poor at OS related issues. The main thing I understood between multiprogramming and multithreading is that in multiprogramming we execute two separate programs where as in multithreading the scheduler produces two different threads which can be executed independently. I think these are a form of multitasking implementation. Am I correct. I was really confused

The Wikipedia article Computer multitasking covers this well. In summary:

Multitasking: there is more than one process and the operating system somehow decides which to run next.
Multithreading: threads are essentially subprocesses, which share memory (separate processes cannot normally access each other's memory) but which are independently scheduled.
Multiprogramming: a form of multitasking in which a process keeps running until it tries to access an I/O device, at which point another process is chosen to run so the CPU doesn't idle waiting for a punched card reader or something.

Multitasking is a user-interface term; it means the computer system allowed the user to do multiple tasks at once. Multitasking has nothing to say about how it's actually implemented; it can even be implemented as a single threaded program.

Multithreading and multiprogramming are forms of the processor being able to execute multiple tasks at once. The difference between multithreading and multiprogramming is the level of isolation between threads and program; each threads in a multithreaded system shares a common memory address space, while each program in a multiprogram system are independent from each other and can only communicate with each other through explicit IPC.


Why is Turing completeness right? I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can perform any possible computation.

Of course, calculating machines of one kind or another go back to antiquity. People have built machines which for performing addition and subtraction (e.g., an abacus), multiplication and division (e.g., the slide rule), and more domain-specific machines such as calculators for the positions of the planets.

The striking thing about a computer is that it can perform any computation. Any computation at all. And all without having to rewire the machine. Today everybody takes this idea for granted, but if you stop and think about it, it's kind of amazing that such a device is possible.

I have two actual questions:

When did mankind figure out that such a machine was possible? Has there ever been any serious doubt about whether it can be done? When was this settled? (In particular, was it settled before or after the first actual implementation?)
How did mathematicians prove that a Turing-complete machine really can compute everything?

That second one is fiddly. Every formalism seems to have some things that cannot be computed. Currently "computable function" is defined as "anything a Turing-machine can compute". But how do we know there isn't some slightly more powerful machine that can compute more stuff? How do we know that Turing-machines are the correct abstraction?

Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the Entscheidungsproblem.

Although Church's paper was published slightly earlier, Turing was unaware of it when he developed his ideas, and Turing's approach proved to be more useful for the design of real-world machines. This was because he showed how to design a Universal Turing Machine that could be programmed to run any computation. This universal machine, with a concrete architecture based on the work of John von Neumann is the basic idea behind the machine on which you are reading my answer.

As you noted, computable is defined as "computable on a Turing machine" and all other reasonable models of computation have proven to be equivalent in their power. The belief that all reasonable models of computation are equivalent in what decision problems they can solve is known as the Church-Turing thesis. In its original form, it is almost completely believed by the learned community. In fact it is not completely clear what it would mean to prove/disprove the Church-Turing thesis; in a lot of ways it becomes an empirical question.

However, there is still the extended Church-Turing thesis which asks the slightly more subtle question of: what can be computed efficiently?. Many classical models, such as $\lambda$-calculus, Turing Machines, tag-based systems, cellular automata, etc are equivalent under the extended thesis as well. However, the recent development of quantum computing casts doubt on the extended thesis. Although most people who work on quantum computers (including me) believe they are more efficient that classical ones, the matter is subject to scholarly debate. Note that in terms of the coarse notion of what is computable (as opposed to efficiently computable) quantum computing is still equivalent to Turing's model.

There's a reason it's called a Turing Machine, and it's because it was invented by Alan Turing. He did a 1936 paper on it, establishing these concepts. If you want to know more about Turing Machines, check the paper. It was seriously doubted, before he designed and built one that cracked the Enigma, that this concept could actually work. However the British were pretty desperate and he was a genius, so they trusted him and it paid off massively.

However, when you think about it some more, it's really not that amazing at all. It was known long before Turing that all of mathematics could be reduced to some set of axioms. All you would have to do is give the instruction set the ability to perform these axioms, and off you go.


Branchless function equivalent Does every pure function have a branchless equivalent?

By pure function I understand a function that uses only its input values and no global state to produce the output.

By branchless function I understand a function that does not use if/else during its execution. A loop contains a branch with and unconditional jump. Constant loops can be unrolled.

As an example, here is the signum function:

function signum(x):
  if (x > 0) return 1;
  if (x < 0) return -1;
  return 0;

And here is a branchless version of the same function:

function signum(x):
  return (x > 0) - (x < 0);

The general answer to your question is no. Consider a function which measures the length of a linked list. How would you implement that without a branch?

But if you just stick with functions which (say) take a machine word and return a machine word (which your example does) then the answer is "yes, sort of". In fact, when analysing algorithms in the word-RAM model, we conventionally assume that any function which takes a fixed number of machine words and returns a fixed number of machine words is constant-time, because it could (in principle, at least) be implemented with a lookup table or a new CPU instruction.

Whether the branch-free version is more practical or not depends partly on the function and partly on the CPU's instruction set.

Don't forget, by the way, that pretty much all modern CPUs have a conditional move instruction. Some ISAs (e.g. ARM) can do conditional execution of all, or almost all, instructions. So there's even more ways to implement branch-free code there.

Here is a pure function which cannot be written without if/else. It takes one number and if the number is even it returns "EVEN" string or else it returns "ODD" string.

Also, in your second code sample the expression (x > 0) is internally a branching and it returns a boolean value and you cannot subtract boolean values.


What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss? The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted in the title seems a good read. Since the author states clearly in the preface that the book is suitable for an advanced data structures course or a 1st year graduate course on algorithm analysis, my question seems answered already. But I guess my real question is how much material is contained in the book and how advanced it is, say compared to the following resources:

Two MIT graduate-level courses - Advanced Algorithms (http://people.csail.mit.edu/moitra/854.html) by Ankur Moitra and Advanced Data Structures (https://courses.csail.mit.edu/6.851/spring12/) by Eric Demaine.

PS: I want to become a C++ programmer (generically speaking) with a strong algorithm and data structures background. Not really sure what material I should dive into. Any suggestions on this are also very welcome!

Once I skimmed through a dozen of textbooks, looking for ones better explaining sorting and data structures (i.e. no graphs, string algos and so on).

Weiss was the best one according to my criteria. In particular, it describes more advanced techniques for hash tables, which are heart of most real use cases. Although even this book doesn't include Robin Hood hashing - learn it from Wikipedia pointers.

More info: https://www.quora.com/How-do-I-learn-data-structure-and-algorithm-in-C++-I-know-the-basics-by-myself-Can-you-suggest-any-e-books-for-me-to-use/answer/Bulat-Ziganshin

Another extremely important topic: https://www.quora.com/What-are-good-resources-to-learn-concurrent-programming-in-C++/answer/Bulat-Ziganshin


Data structure to query intersection of a line and a set of line segments We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries:
Given a query line $l$, report how many line segments in $S$ does it intersect.

It is required that the query should be done in $O(\log{n})$ time. The data structure itself should take up to $O(n^{2})$ storage and be built in $O(n^{2}\log{n})$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit:
Yes it is in $\mathbb{R}^{2}$. By query point I mean the query line dualised into a point on dual plane.

HERE is the solution I did in the homework but it still lose three points on:
(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.


Find the centre of a circle given two points lying on it and its radius We have been given 2 points on a circle and its radius. Now I want to find out the centre point of such a circle. How can I code this efficiently without solving the quadratic equations?

\begin{align*}
  \mathbf{v} &= (\mathbf{p_2} - \mathbf{p_1}) =
  \begin{pmatrix} v_x \\ v_y \end{pmatrix} \\
  h &= \sqrt{r^2 - \frac{\lvert \mathbf{v} \rvert^2}{4}} \\
  \mathbf{u_h} &= \frac{1}{\lvert \mathbf{v} \rvert}
  \begin{pmatrix} v_y \\ -v_x \end{pmatrix} \\
  c_{1,2} &= \mathbf{p_1} + \frac{1}{2} \mathbf{v} \pm h\mathbf{u_h}\\
\end{align*}

The algorithm is obvious, it's complexity should be $O(n^2)$.


One element that differs in two arrays. How to find it efficiently? I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.

Let's say we have two arrays consisting of numbers that are unsorted. Array 2 contains a number that Array 1 does not. Both arrays have randomly located numbers, not necessarily in the same order or at the same indices. For example:

Array 1
[78,11, 143, 84, 77, 1, 26, 35 .... n]

Array 2
[11,84, 35, 25, 77, 78, 26, 143 ... 21... n+1]

What is the fastest algorithm for finding the number that differs? What is its running time? In this example, the number we would be looking for is 21.

My idea was to run through Array 1 and delete that value from array 2. Iterate until you are finished. This should be around $O(n \log n)$ running time, right?

I see four main ways to solve this problem, with different running times:

$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.
$O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a linear search to identify the distinct element. In this solution, the running time is dominated by the sorting operation, hence the $O(n \: log \: n)$ upper bound.

When you identify a solution to a problem, you should always ask yourself: can I do better? In this case, you can, making a clever use of data structures. Note that all you need to do is to iterate one array and perform repeated lookups in the other array. What data structure allows you to do lookups in (expected) constant time? You guessed right: a hash table.

$O(n)$ solution (expected): iterate the first array and store the elements in a hash table; then, perform a linear scan in the second array, looking up each element in the hash table. Return the element that is not found in the hash table. This linear-time solution works for any type of element that you can pass to a hash function (e.g., it would work similarly for arrays of strings).

If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by Tobi Alafin (even though this solution will not give you the index of the element that differs in the second array):

$O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction. Note that this solution can actually be generalized to any data type whose values can be represented as fixed-length bit strings, thanks to the bitwise XOR operator. This is thoroughly explained in Ilmari Karonen's answer.

Finally, another possibility (under the same assumption of integer arrays) would be to use a linear-time sorting algortihm such as counting sort. This would reduce the running time of the sorting-based solution from $O(n \: log \: n)$ to $O(n)$.

var shortest, longest;

Convert shortest to a map for quick referencing and the loop over the longest until the current value is not in the map.

Something like this in javascript:

if (arr1.length > arr2.length) {
    shortest = arr2;
    longest = arr1;
} else {
    shortest = arr1;
    longest = arr2;
}

var map = shortest.reduce(function(obj, value) {
    obj[value] = true;
    return obj;
}, {});

var difference = longest.find(function(value) {
    return !!!map[value];
});


Ordering of conditions in multi-way conditional constructs Most programming languages provide multi-way conditional constructs (like cond in Lisp, guards in Haskell, etc) that allow one to define program behavior according to different conditions.  But most of them also implies a default top-down ordering: the next condition is checked only when all preceding conditions are unsatisfied.  I wonder if there is any work on conditional constructs that does not follow this convention but rather automatically sort the conditions according to some order.  I can foresee how hard it is to get conditions independent.  Maybe it is not feasible anyway?

On what basis you want to sort out conditions conditions are not specific. If they are specific then you may sort out the conditions to not follow top down approach.

And conditions are the only thing that decide which condition next to be tested.
That is they handle the flow of your code and one condition is dependent on other.


What does the halting problem mean for a Babbage machine? I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example).

The way I imagine that is there is no finite method (i.e. algorithm) which would examine the Babbage machine, possibly by testing it, but most probably by dismantling it like a watch and concludes that it indeed computes logarithms.

Would that be a correct way of thinking the halting problem on the Babbage machine?

No. The undecidability of the halting problem for a particular model of computation means that there's no algorithm that takes as input a description of an arbitrary machine $M$ in that model and an input $x$ and determines whether $M$ halts when run with input $x$.

As a consequence, there's no algorithm that takes as input a description of a machine and determines whether that machine computes logarithms. However, that doesn't mean that you can't prove that a specific machine computes logarithms. Indeed, people do this all the time, as exemplified by Knuth's famous quote, “Beware of bugs in the above code; I have only proved it correct, not tried it” (emphasis mine). Proving the code correct requires proving that it terminates and computes the thing it's supposed to compute.

I read that the Java programming language is Turing complete.

That means, I can write a Java program such that your Turing machine would not always be able to decide, in a finite number of steps, whether my Java program would terminate after reading some arbitrary input.

It does not mean that every Java program has that property.  I can trivially write a Java program that always terminates, and if I do that, then you can construct a Turing machine that always says, "yes, it halts."  Or, I can write a Java program that never terminates, and you can construct a Turning machine that always says "no, it doesn't halt."

I don't know the design of Babbage's Analytic Engine, but if it is Turing complete, then that means there is at least one configuration of the engine for which you can not solve the halting problem; but it does not mean that every configuration of the engine has that property.

I don't know what you mean exactly by "computes the logarithm of its input."  Babbage's engine was a digital machine, and logarithm is a transcendental function.  No digital algorithm to compute the true logarithm of a given number could ever terminate.  In a practical configuration of the engine, it would do what my computer's floating-point hardware does:  That is, it would compute only the first n digits of the logarithm (for some small n).

I haven't tried asking my computer for the logarithms of every possible double value, but so far, it always has delivered a result in finite time for each of the countless millions of double values that I have tried.


Can you pop 2 elements at a time in a PDA My question is N(a)=2N(b) ; No of a's = 2 * No of b's . So for every symbol b can I pop 2 a's simultaneously

In the usual definition of pushdown automata, at every step the PDA pops a stack symbol and reads an input symbol, and based on that it pushes a string of symbols (zero or more) onto the stack, and transitions to a new state (possibly non-deterministically, i.e. there could be several or no choices). If you define PDAs according to this definition then you cannot pop two stack symbols in a single transition.

That said, you can simulate popping two symbols using epsilon transitions (exercise). Therefore, the variant of PDAs in which you are allowed to pop more than one stack symbol is equivalent in power to a standard PDA.

If you are using jflap, it will allow you to pop two stack items in just one transition. Theoretically, it is more logical to pop one item from the stack one item at a time


kth nearest vertex in a unweighted graph Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of special vertices and an integer $k$, I want to find the $k$th nearest special vertex for each vertex.  What algorithm can I use for this problem?

I'm actually thinking of algorithm for finding shortest paths from every vertex to all other vertices (like Floyd-Warshall algo, but in our case graph is unweighted and we need much better performance).

Letting $G = (V,E)$, and $|V| = N$, your problem essentially boils down to computing a portion of the shortest path tree for every vertex in $G \setminus S$, where the shortest path tree is truncated after the $k$th "special vertex."

You mention the Floyd-Warshall algorithm; however, that algorithm seems inappropriate here, since it's designed for weighted graphs, and only returns the lengths of the shortest paths between every pair of vertices.

A more natural approach might be to run BFS on every vertex in $G \setminus S$, halting when you reach the $k$th "special vertex." Since you'd be running BFS on every vertex in $G \setminus S$, your worst-case runtime would be $O(N' \cdot |E|)$, where $N' = N - |S|$. (I'm assuming you only want the $k$th nearest special vertex for the non-special vertices.)

You would be able to improve the performance slightly by caching the portions of the shortest-path trees you compute on each call of BFS, but those changes wouldn't shift the worst-case performance. I believe any known shortest-path algorithm will have complexity dependent on $|E|$, so I'm not sure that you could solve this problem in $O(NlogN).$


How does a hard drive knows what bit is the beginning of of a byte/word? I'm guessing I could replace the words "hard drive" with "random access medium" but let's be more specific here. Also for the sake of this question, let's not consider SSDs. Just plain old hard-drives with heads and magnetic discs.

I'd guess that the hard drive doesn't care about things as bytes and receives instructions from the OS on about where to move it's head, but that'd assume that the OS has knowledge of sectors, cylinders or whatever physical properties of the drive and it's stored data so that doesn't feel right.

So, how does this work?

Simplified, the operating system sees disk storage as a randomly accessible set of sectors, each sector containing some fixed number of bytes.  The OS asks the disk controller for a sector using some standard protocol and it is the responsibility of the disk controller to retrieve the sector with the bits and bytes in the same order in which they were written.  The communication protocol (e.g. SCSI) specifies both bit and byte order for reads and writes so there is no space for confusion about where the data starts and stops.

Operating systems can and do take into account the characteristics of storage media for the sake of efficiency, such as existence of onboard cache, rotational delays, and head movement, but those things have no bearing on where bytes and sectors start.

I think that you should first bear in mind that computer architecture is based on the mechanism of abstraction in order to make it easier, for instance, to manage and access data, and avoid the hurdle of having to take care of the specific hardware that needs be accessed.

Having said that, you can understand that the OS itself can't be allowed, also for efficiency reasons, to make distinctions between an USB or an hard disk access and so on. This premise is to confute the fact that the hard disk "doesn't care about bytes" and that the resolution of the data address is all on the OS. In fact, the hard disk DOES have an internal controller and circuitry that needs to identify and translate the address that the OS requests in the number of disk, cylinder and sector, the xyz coordinates in HD technology. The operating system instead interfaces with a file system that is built based on the disk content, without overweighting it with more "circuitry matters"


How does an NFA use epsilon transitions? In the picture below, I'm trying to figure out what exactly this NFA is accepting.

What's confusing me is the $\epsilon$ jump at $q_0$.

If a $0$ is entered, does the system move to both $q_0$ and $q_1$ (the accept state)?
If a $1$ is entered, does the system move to both $q_1$ and $q_2$?
Does the system only move to $q_1$ (accept state), if no input is given (empty string)?

Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you:

If the string is $\epsilon$ then your automata ends both in $q_0$ and $q_1$

If your string is '0' it'll be again in $q_0$ and $q_1$

If your string is '1', it'll be only in $q_2$, because if you look from the point of $q_0$, you have a '1' transition to $q_2$, but you have also to look at case you're in $q_1$(if you were in $q_0$ you always were in $q_1$ also) then there is no '1' transition, so this alternative path just "dies".

Just by looking at these cases its easy to see that your automata accepts $\epsilon$, $0^*$, and going from $q_0$ to $q_1$, the only way to reach $q_2$ is $0^*11^*1$, so, this resumes your automata to $\epsilon$, $0^*$, $0^*11^*1$

Hope this helped you, if you have any further doubts, just ask!

I tried construct DFA for this  NFA

$\sum$ - alphabet set

$Q$ -states set

$\sigma(Q\times (\sum  \cup {\epsilon} )) \to P(Q)$ state func

$q_0 = q_0$

$ F \subseteq Q, F = \{q_0\}$

Because every NFA has equal DFA  lets construct
DFA $M'$ for this given NFA.

alphabet  - the same

$Q' = P(Q)$  - states

Current state is $R \in P(Q)$

$E(R)$ - epsilon closure return set of states reachable over zero or more $\epsilon$ - connections for every $r \in R$

$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a)) $ -transitions

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Some compute on this FSM

$1.$ $\epsilon$ on input:  $q'_{0} = E(\{q0\}) = \{q_0, q_1\}$ initial state include $q_1$ so FSM accept $\epsilon$

$2.$ $0*$ on input: $ \sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) =
\{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$
so FSM accept $0*$

at least $\{\epsilon, 0*  \} \subset L (M')$

Thanks to David Richerby


Given a string, is it possible to determine which hashing algorithm has produced it, if any? Given a string, is it possible to determine which hashing algorithm has produced it, if any?

For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21.

Is it possible to determine whether the above hash is:

1) Indeed a genuine hash in some hashing algorithm, as opposed to a string of characters that is not a hash produced by one of some set of algorithms

2) a definite hash of a specific hashing algorithm?

Possible methods:

1) For hashes susceptible to rainbow-table attacks, it would be viable to search for the hash in such a rainbow table for various algorithms, to find a match; if a match is found, we know which algorithm produced it.

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error".

In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, is there an input $x$ (and maybe a seed $s$) such that $A(x,s)=w$? You can try brute force, but if you have the source code, is there something more clever that you can do? If not, then your algorithm is a one-way function. Whether one-way functions exist is an open question. We know that if one-way functions exist, then $P\ne NP$, and therefore if $P=NP$, one-way functions do not exist, but that still leaves three possibilities.

Any good hashing algorithm will be able to produce any possible output of the right format so, for example, to test if a string is a valid MD5 hash, it should be enough just to check that it's a string of 32 hex digits.


Knapsack problem with the restriction on the number of items Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the standard knapsack algorithm so that it does the job? Thank you for your suggestions!

Iterative solution (recursive is very similar too):

Have a 2d array $mat[W][k]$ and let the columns be $0..k$ and the rows be from $0..W$. Let $mat[x][y] = 0 \;\forall \;0\le x \le W, 0\le y \le k$. Let $mat[0][0] = 1$.

Now run $i$ across $[1,k]$. Within the $i$ loop run another loop iterating $j$ across $[1,W]$. In every iteration of the inner loop, run through the set of elements and calculate this:

$${mat[i][j] = \sum_{l=1}^{|X|} mat[i-1][j-X_l] }\:$$

$mat[W][k]$ will store the final answer. Time complexity = $\mathcal{O}(W.k.|X|)$, and space complexity = $\mathcal{O}(W.k)$.


Undecidable problems limit physical theories Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual circuit based construction. Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt. This seems a triviality, but doesn’t this give us a weak sort of unpredictability without reference to quantum or chaotic considerations? Moreover we can strengthen the above argument by noting that there is nothing special about the circuit based UTM, so we have that the behavior of a physical system is in general undecidable at any level where a UTM can be constructed.

Edit: as pointed out by both Babou and Ben Crowell, my suggested circuit construction is merely an LBA. As I argued in the comments, I find it easy, and intuitive to imagine a machine which is physical but is not linearly bounded. Simply construct a machine (robot) which can mechanically move left/right on an input arbitrarily many times, and assume it has a finite, but non expiring power source. Now we also run into the problem that the universe is finite, but that lets us conclude either that the universe is finite, or the originally hoped for consequence must be true (that would still be a surprising conclusion to arrive at from the above argument).

This was initially intended as a comment, as it side-steps a bit the
question. But I think it does answer in its own way.

What is known, or attempted so far, shows that connecting computation theory with physics can
be a pretty subtle endeavour, and I am afraid that the approach
suggested in the question is probably a bit too crude. I am not sure it
is much better than the classical argument that, everything being
finite, all we need is finite state automata theory, and that studying
Turing machines is a waste of time.  (Not my view of things)

Why should such issues be addressed with caution

I should probably motivate the above comparison with the finite
automata argument. My perception is that
computability is, maybe even more than complexity, an asymptotic theory: what
matters is what occurs at infinity. But we do not know whether the
universe is finite or infinite. If it is finite, then what would be
the point of considering infinite computations. The following concerns
physics, and I am not a physicist. I do my best to be accurate, but
you have been warned.

We often see the Big Bang as a "time" when the whole universe was a
very tiny something, with a very small size. But if it had a size at
some point, how did it transform into something infinite at a later time. I am not trying to say it is impossible ... I do not have the
slightest idea. But it could be that it always was infinite.

Then, let us consider the universe as infinite. Does it help us? Well,
we have some problems with the speed of light. If we consider what may
be relevant here (where we are), we have to consider that we can be concerned only by
a part of the universe that is included in a finite sphere. The radius
$r$ of that sphere is such that the relative speed of two points at
distance $r$ due to expansion is equal to the speed of
light. According to what we currently know, without a future variation
in expansion speed, nothing outside that sphere will ever be of
concern to us. So the universe is finite for us for all practical
purposes. Actually, things are even worse if you consider the contents
of this relevant universe: it is shrinking (unless there is some
creation process). The reason is that the sphere is expanding beyond
its own diameter, carrying with it some of its content that becomes
irrelevant too. Remark: that sphere is not what is called the
observable universe (which is dependent on the age of the universe), it is much larger.

Thus, not only "our" universe is finite, but its resources might be
shrinking.  It is possible that in so many billions
years, only our galaxy might be still relevant to us (assuming we
still exist), with the Andromeda galaxy which will hit the Milky Way
before then.

Well, I do not know what is considered established at this time, but
it shows at least that assuming infinity is a big assumption.

However, is it the case that physical limitations prevent us from
using computability theory.  All that can be concluded from the above
is that it may be unreasonable to draw physical conclusions from the
theoretical work on Turing Machines and the halting problem.

However the concerned techniques may also give useful results when
applied to devices or formalisms that are not Turing-complete. I would
not try to go into details, if only because algorithmic complexity is
not my area, but I would guess that, if the structure of the universe
is discrete, complexity could be in some form relevant to the behavior
of some phenomena. Of couse, this is only wild speculation on my
part. Some of the research I reference below is related to such
discreteness issues.

Some examples of work relating physics and computation theory

There is a significant body of work trying to tie computation and
physics, most of which I barely know of.  So, please, do not rely on anything I
might say, but simply take it as pointers to search for potentially
relevant work.

A good part of that work is concerned with thermodynamic aspects, such
as the possibility of reversible computing with no energy cost. I
thinks this ties with functional programming as it is side-effects
that cost energy (but do not trust me). You may take wikipedia as an
introduction, but Google will yield many references.

There is also work trying to tie Church-Turing thesis and physics,
involving information density among other things. See for example:

The physical Church-Turing thesis and the principles of quantum
theory
Around the Physical Church-Turing Thesis:
Cellular Automata, Formal Languages, and the
Principles of Quantum Theory,
Physics and Church-Turing Thesis.

I vaguely recall seen other
interesting takes on this, but it escapes me right-now.

Then you have Lamport's work on clocks synchronization and relativity
in distributed systems.

And, of course, you have quantum computing that apparently changes
some (achievable) time-complexities, though it does not affect
computability.

Another take is Wolfram's work on modelling physical laws with
cellular automata, though the real benefits of this work seem
disputed.

I think that trying to understand all this work could get you closer
to understanding how you can tie some computability knowledge with (as implying)
theoretical limitations of the physical world, though the trend so far
was more to tie limitations of computability to (as consequences of)
properties of the physical universe.

One possible problem in all this is the self-embedding of all our
theories (mathematics, computation, physics, ...) within the limits of
concepts that are syntactically expressible (i.e. by a language)
which might set a limit on the expressive power of our science. But I
am not sure whether the preceding sentence has meaning ... sorry about
that, it is the best I can do to express one nagging doubt.

As an account of personal disappointment, I would add that physicists
(at least on http://physics.stackexchange.com) are not very amicable to discussing what other sciences could have to say
about physical issues (though they are quite willing to discuss what
physics may have to say about other sciences).

Does the existence of undecidable problems immediately imply the non-predictability of physical systems?

No.

  first we construct a physical UTM, say using the usual circuit based construction.

A universal Turing machine is a Turing machine. A Turing machine has an infinite (or infinitely extensible) tape. Therefore you can't build one out of circuits. What you can build is a linear bounded automaton (LBA).

  Then there can be no decidable physical theory which can determine, given any input setting of the circuits, whether the circuit will halt.

The halting problem is decidable for an LBA, so your argument fails.


What is the difference between Babbage's analytical and difference engine? What is the difference between Babbage's analytical and difference engine? Can they even be compared?

They would be different from each other in a very significant way. In the comments there is a link to the Wikipedia articles on both machines - which are quite informative - but I'll assume they weren't useful to you.

You can think of the Analytical Engine basically as a regular computer, which would have a program coded in punched cards, that were attached to each other forming a chain (there would actually be three kinds of cards, each with its own reader, check this out). The machine also had a control unit whose job was to decode the instructions of this program and perform them on the data that was stored in a memory capable of holding a thousand numbers.

The Difference Engine, on the other hand, would have been exactly a calculator, and one that could perform just one kind of operation, repeatedly, on a sequence of numbers. In the "Sketch of the Analytical Engine", authored by Luigi Menabrea, and famously translated by Ada Lovelace, the nature and general applicability of this operation is detailed:

  The theorem on which is based the construction of the machine we have just been describing, is a particular case of the following more general theorem: that if in any polynomial whatever, the highest power of whose variable is m, this same variable be increased by equal degrees; the corresponding values of the polynomial then calculated, and the first, second, third, &c. differences of these be taken (as for the preceding series of squares); the mth differences will all be equal to each other. So that, in order to reproduce the series of values of the polynomial by means of a machine analogous to the one above described, it is sufficient that there be (m+1) dials, having the mutual relations we have indicated. As the differences may be either positive or negative, the machine will have a contrivance for either advancing or retrograding each needle, according as the number to be algebraically added may have the sign plus or minus. (emphasis added)

By calculating series of values of polynomial functions many useful calculations can be approximated, including those of trigonometric and logarithmic functions. This method has its limits, though, which are explained a bit further in the document. In doing that, the justification for the construction of the new machine is given:

  We see that its use is confined to cases where the numbers required are such as can be obtained by means of simple additions or subtractions; that the machine is, so to speak, merely the expression of one particular theorem of analysis; and that, in short, its operations cannot be extended so as to embrace the solution of an infinity of other questions included within the domain of mathematical analysis. It was while contemplating the vast field which yet remained to be traversed, that Mr. Babbage, renouncing his original essays, conceived the plan of another system of mechanism whose operations should themselves possess all the generality of algebraical notation, and which, on this account, he denominates the Analytical Engine. (emphasis added)

the main difference between those two engine is difference engine can only do one mathematical operation that is addition on the other hand analytical engine can do the four basic mathematical operation (addition,division,multiplication ... )...


If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.

By the definition of $\leq_m$ we can construct the following statement,

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.

I don't know how to phrase this correctly, or if I'm even on the right track.

As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.

$A \leq_m B$ means there is a total computable $f$ s.t. for all $w$,

  $w \in A \leftrightarrow f(w) \in B$.

By the argument above, this is the same as

  $w \notin A \leftrightarrow f(w) \notin B$.

Or equivalently

  $w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.

And therefore, the same $f$ shows that $\bar{A} \leq_m \bar{B}$.

$A \leq_m B$ does not implie $w \in A \leftrightarrow f(w) \in B$ only the other way is true
if $w \in A \leftrightarrow f(w) \in B$ then $A \leq_m B$ but not reciprocaly


Why do we use big O rather than $\Omega$ when discussing best case runtime? When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ of an algorithm, we also attempt to bound $T(n)$ above and use $O$ notation.

Why don't we instead attempt to bound the best case runtime from below? Wouldn't it make more sense to put an upper bound on the worst case runtime and a lower bound on the best case runtime, as this will then give us upper and lower bounds on all cases?

I understand that both $O$ and $\Omega$ notations can be useful for discussing best/worst/average case runtime., and that we can put upper and lower bounds on the worst or best case runtimes, respectively. My question is about the convention in the field to list an upper bound rather than a lower bound for the best case runtime (for example, see here and here).

The symbols $O$, $\Omega$ and $\Theta$ mean at most, at least and exactly, respectively. What these bounds are about, is an entirely separate issue. They can be about best-case or worst-case performance, but you can use these symbols throughout mathematics. To describe a function, one of the things you can do is to give $O$ and $\Omega$ upper and lower bounds, independent of whether your function is related to computer science.

For example, to describe an complicated algorithm (or language) for which you don't have precise bounds yet, but for which you do have rough preliminary bounds, you can say: the best-case of this algorithm runs in $\Omega(n^2)$ and $O(n^3)$ (meaning no better than $n^2$ but no worse than $n^3$) and the worst-case runs in $\Omega(2^{\sqrt{n}})$ and $O(2^{n^{2}})$. This means: I don't know what the worst-case running time is exactly, but my analysis thus far puts it between $2^{\sqrt{n}}$ and $2^{n^{2}}$. Later, it may turn out that the worst-case running time was in fact $\Theta(2^{n})$, and then your $O(2^{n^{2}})$ upper bound, while correct, was not strict.

Big O is used mostly because we want to make sure that the best case time complexity $T(n)$  will never exceed the upper bound time complexity $Cg(n)$. It would be meaningless to talk about big $\Omega$ notation because what we want is a upper bound on $T(n)$.


How can I get index of combination from element indices An array of combinations is generated from two arrays,
               indices:  0   1   2   3   4   5
               array 1: [a,  b]
               array 2: [A,  B,  C]
     repeating array 1:  a,  b,  a,  b,  a,  b
     repeating array 2:   A,  B,  C,  A,  B,  C
          combinations: [aA, bB, aC, bA, aB, bC]    length = LCM(2, 3)

INPUT : a, C
OUTPUT: 2, which the index of aC in the generated combinations.

Say, when a and C are given whose indices are already known as 0 and 2 in the original arrays, how to find the index of aC, which is 2? Is there any algorithmic way to do this?
For detailed background information, please check version 1 of this question.

(BTW, I think the code in the first edition of the question was the issue -- not the background info with respect to the sexagenary cycle, which is actually good to include to understand the motivation for the problem).
To put the problem a bit differently, you have the sets $\mathbb{Z}/m\mathbb{Z}$ =  $\{0,1,...,m-1\}$ and $\mathbb{Z}/n\mathbb{Z} = \{0,1,...,n-1\}$, and you start with the pair (0,0), then (1,1), etc., basically applying the mapping $(x,y)\mapsto(x+1 \mod m,y+1 \mod n)$, until you wrap back around to $(0,0)$. In the easy case where $m=n$ then, you can see that $(i,i)$ was the $i$-th term in the sequence  (0-based). In general, if you are asking about the index of $(i,j)$, then you are effectively trying to solve the system of congruences
\begin{align*}
x &\equiv i \mod m \\
x &\equiv j \mod n
\end{align*}
for $x$. Here $x$ represents how many times you did the $(+1,+1)$ operation starting with $(0,0)$.
When $m$ and $n$ are coprime, the Chinese remainder theorem gives you an algorithm to compute the solution.  When they are not coprime, then that system in general may not have a solution, but in the case where the system was created by the above construction, it does. This math.stackexchange answer shows you how to find the (unique) solution in the range $[0,LCM(m,n))$.

Yes, there is. Because everything is given, you only want to solve a specific instance of a more general problem. The solution is:
return 2;


Context free grammar construction My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \{a^m b^n \mid m \le n \le 2m \}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.

Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.

Here is an EBNF description that yon can convert to BNF.

$S\to aSb[b] \mid \epsilon$

Hint: Each $a$ corresponds to either one $b$ or two $b$s. Form a hybrid between grammars for $a^n b^n$ and $a^n b^{2n}$.


O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question Question:  Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice.  The second buy has to come after first sell.

Solution:  There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array.  Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?

Here's an O(1) space, O(n) time algorithm with Java code.
Logic:

Let $P_i$ denote the price of the stock on day $i$.

Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.
If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.
In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add
day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.

public int maxProfitWith2Transactions(int[] prices) {
    if (prices.length == 0) return 0;

    int minPrice                      = prices[0];
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int i = 1; i < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        minPrice                    = Math.min(p, minPrice);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.
public int maxProfitWith2Transactions(int[] prices) {
    int minPrice                      = Integer.MAX_VALUE;
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int p : prices) {
        minPrice                    = Math.min(p, minPrice);
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3.
Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).
$$\begin{array}{l|r r r r r r r r}
\text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline
\text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline
\text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\
\text{till day $i$} \\  \hline
\text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\
\text{bought at lowest} \\
\text{price before day $i$}  \\
\text{and sold before}  \\
\text{or on day $i$}  \\ \hline
\text{Max Profit left if} & \text{x} & \text{-8} &  \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\
\text{2nd buy is done on} \\
\text{day $i$.} \\
\text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline
\text{Max Profit if 2nd} &  \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\
\text{stock is sold before} \\
\text{or on $P_i$} \\
\text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline
\end{array}$$

denote d[n] as array. index from 0 ~ e  where e = (n - 1)
trans(i, j) = max(d[k2] - d[k1])  subject to:  k2 > k1 and k2 <= j  k1 >= i
k1, k2 = argmax(trans(i, j))  k1 means buy point   k2 means sold point
split(k) = trans(0, k) + trans(k+1, e)
we need to get max(split(k), subject to: 0 <= k <= e)

(1) caculate: i, j =  argmax(trans[0, e])
note the property:
     d[k] > d[i]  when k < i
     d[k] < d[j]  when k > j
     d[i] < d[k] < d[j] when i < k < j

(2) easy to prove:
    split(k) <= split(i) when k <= i
    split(k) <= split(j) when k >= j
    caculate: trans(0, i-1) and trans(j+1, e)

(3) caculate  split(k)  when  i < k < j
   split(k) = trans(0, k) + trans(k+1, e)
   consider:
   trans(0, k) , A if sold before i,  trans(0, k) = trans(0, i-1)
                 B if sold after i, must buy  i

   consider:
   trans(k+1, e), C if buy after j, trans(k+1, e) = trans(j+1, e)
                  D if buy before j, must sold j

   consider  all casees:
   split(k) = max( A + C, A + D, B + C, B + D)
   A + C = tran(0, i - 1) + trans(j+1, e)
   B + D,  a similary problem:   sold max and buy min between d[i+1] , d[j-1], will token o(n) time complexity
   A  + D /  B + C   we   iterate on all possible k


Decidable properties of computable reals Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?

Does this correspond in some direct way to the connectedness of the reals?

Yes, Rice's theorem for reals holds in every reasonable version of computable reals.

I will first prove a certain theorem and a corollary, and explain what it has to do with computability later.

Theorem: Suppose $p : \mathbb{R} \to \{0,1\}$ is a map and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then there exists a Cauchy sequence $(x_i)_i$ such that $p(\lim_i x_i) \neq p(x_j)$ for all $j \in \mathbb{N}$.

Proof. We construct a sequence of pairs of reals $(y_i, z_i)_i$ as follows:
\begin{align*}
(y_0, z_0) &= (a, b) \\
(y_{i+1}, z_{i+1}) &=
\begin{cases}
(y_i, (y_i + z_i)/2) & \text{if $p((y_i + z_i)/2) = 1$} \\
((y_i + z_i)/2, z_i) & \text{if $p((y_i + z_i)/2) = 0$} \\
\end{cases}
\end{align*}
Observe that for all $i \in \mathbb{N}$:

$p(y_i) = 0$ and $p(z_i) = 1$
$|z_i - y_i| = |b - a| \cdot 2^{-i}$
$|y_{i+1} - y_i| \leq |b - a| \cdot 2^{-i}$
$|z_{i+1} - z_i| \leq |b - a| \cdot 2^{-i}$

Thus the sequences $(y_i)_i$ and $(z_i)_i$ are Cauchy and they converge to a common point $c = \lim_i y_i = \lim_i z_i$. If $p(c) = 0$ then we take $(x_i)_i = (z_i)_i$, and if $p(c) = 1$ then we take $(x_i)_i = (y_i)_i$. $\square$

Corollary: Suppose $p : \mathbb{R} \to \{0,1\}$ and $a, b \in \mathbb{R}$ two reals such that $p(a) = 0$ and $p(b) = 1$. Then every Turing machine either runs forever or it does not run forever.

Proof.
By the theorem, there is a Cauchy sequence $(x_i)_i$ such that $p(x_j) \neq p(\lim_i x_i)$ for all $j \in \mathbb{B}$. Without loss of generality we may assume that $p(x_j) = 1$ and $p(\lim_i x_i) = 0$.

Let $T$ be a Turing machine. Define a sequence $y_i$ by
$$y_i =
\begin{cases}
x_j & \text{if $T$ halts in step $j$ and $j \leq i$}\\
x_i & \text{if $T$ does not halt within $i$ steps}
\end{cases}
$$
The sequence is well-defined because we may simulate $T$ up to $i$ steps and decide whether it has stopped or not within that many steps. Next, observe that $(y_i)_i$ is a Cauchy sequence because $(x_i)_i$ is a Cauchy sequence (we leave this as an exercise). Let $z = \lim_i y_i$. Either $p(z) = 0$ or $p(z) = 1$:

if $p(z) = 0$ then $T$ runs forever. Indeed, if it stopped after $j$ steps, then we would have $z = x_j$, and so $p(z) = p(x_j) = 1$ would contradict $p(z) = 0$.
if $p(z) = 1$ then $T$ does not run forever. Indeed, if it did, then we would have $z = \lim_i x_i$, and so $p(z) = p(\lim_i x_i) = 0$, contradicting $p(z) = 0$.
$\square$

Now we can explain why this gives us Rice's theorem for real numbers. The proofs are constructive, therefore they yield computable procedures. This is true of any model of computability and any compute structure of reals that deserve to be so called. In fact, you can go back and read the proof as instructions for building a program -- all the steps are computable.

Thus, if we had a computable map $p : \mathbb{R} \to \{0,1\}$ and computable $a, b \in \mathbb{R}$ such that $p(a) = 0$ and $p(1) = 1$, then we could apply the computable procedures arising from the constructive proofs of the theorem and the corollary to create the Halting oracle. But the Halting oracle does not exist, therefore, every computable map $p : \mathbb{R} \to \{0,1\}$ is constant.

Supplemental: There was also a question about whether Rice's theorem is related to connectedness of the reals. Yes, it is essentially the statement that the reals are connected.

Let us first observe that a continuous map $p : X \to \{0,1\}$ (we take the discrete topology on $\{0,1\}$) corresponds to a pair of disjoint clopen (closed and open) sets $U, V \subseteq X$ such that $U \cup V = X$. Indeed, take $U = p^{-1}(\{0\})$ and $V = p^{-1}(\{1\})$. Because $p$ is continuous and $\{0\}$ and $\{1\}$ are open, $U$ and $V$ will be open, disjoint, and they obviously cover all of $X$. Conversely, any pair $(U,V)$ of disjoint clopens that cover $X$ determines a continuous map $p : X \to \{0,1\}$ that maps elements of $U$ to $0$ and elements of $V$ to $1$.

From this we learn that a space $X$ is disconnected if, and only if, there exists a continuous map $p : X \to \{0,1\}$ and $a, b \in X$ such that $p(a) = 0$ and $p(1) = b$ (we need $a$ and $b$ so that we get a non-trivial decomposition of $X$). There is another way to say the same thing: a space $X$ is connected if, and only if, all continuous maps $X \to \{0,1\}$ are constant.

In computable mathematics we have a basic theorem: every computable map is continuous. So, as long as we are within the realm of computable objects, Rice's theorem does in fact state that a certain space is connected. In the case of the classic Rice's theorem the space in question is the space of partial computable functions $\mathbb{N} \to \mathbb{N}$.

No.  Or, at least, the proof isn't trivial, since you can choose among the (generally many) possible ways to compute a real, and may be able to choose one with a structure that is total w.r.t. the chosen property so that you don't reduce testing the property to the halting problem.

Also, I think I need a better understanding of what "nontrivial" means w.r.t. the properties of numbers.  For Rice's theorem, "nontrivial" is basically non-syntactic and not implied by syntax.  However each computable real number isn't a single program, but rather an equivalence class full of programs.