Number of Function Calls In Recursive Code I am new to recursion. I am doing some practice questions and I was wondering what the technique is for going from some recursive code to identifying the number of function calls it makes.

function win(n)
   if n ≤ 3 let memo(n) = 'yes'
   if memo(n-2) = 'no' or memo(n-3) = 'no' let memo(n) = 'yes'
   else let memo(n) = 'no'
   let win(n) = memo(n)

  Roughly, what is the number of steps that this program uses to compute $\mathit{win}(n)$? Is $\mathrm{step}(n)$ linear in $n$, polynomial in $n$ or exponential in $n$? Is it feasible to use this code to calculate $\mathit{win}(1000)$ on a fast supercomputer? Justify your answer.

First, let me correct the program:

1 function win(n)
2     if memo(n) exists:
3         return memo(n)
4     if n ≤ 3:
5         memo(n) = true
6     else:
7         memo(n) = not win(n-2) or not win(n-3)
8     return memo(n)

Compared to your code, there are two main differences:

If the value of the function is already known, that it is immediately returned (lines 2–3).
Otherwise, we compute the value of the function recursively by invoking win rather than memo (line 7).

The running time of win depends on which values have already been calculated. For example, if you already computed the value of win on $n-2$ and $n-3$, then computing it on $n$ takes time $O(1)$. We can also bound the running time of win on input $n$ by $O(n)$, since lines 4–8 run at most once for every value of the input.

We could also implement win without any memoization:

1 function win(n)
2     if n ≤ 3:
3          return true
4     else:
5          return not win(n-2) or not win(n-3)

The running time of this implementation satisfies the recurrence
$$ T(n) = T(n-2) + T(n-3) + O(1), $$
with base case $T(n) = O(1)$ for $n \leq 3$. Using standard techniques, we determine that the running time is $\Theta(c^n)$, where $c \approx 1.3247$ is the unique real root of $c^3=c+1$.

Finally, let us take a look at some values of win:
$$
\begin{array}{c|cccccccccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\\hline
\mathit{win}(n) & T & T & T & T & F & F & T & T & T & F & F & T & T & T & F & F
\end{array}
$$
Notice the period of 5. We can easily prove the following formula by induction: for $n \neq 1$, $\mathit{win}(n)$ holds iff $n \bmod 5 \in \{0,1\}$. This gives an $O(1)$ algorithm for computing win.


How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free? This page on Wiki states that $\{a^nb^nc^nd^n \ | \ n > 0\}$ can not be generated by a CFG. This does not make sense to me as $\{$S $\to$ ABCD, A $\to$ aA | a, B $\to$ bB | b, C $\to$ cC | c, D $\to$ Dd | d$\}$ seems to be the desired CFG. By the Pumping lemma for CFG, I understand that it is not context-free but that seems very much contradictory.
Can someone clarify this? I got this doubt while I wondering if CFGs can generate all languages.

Your grammar generates the language $\{a^ib^jc^kd^\ell \mid i,j,k,l \geq 1\}$, which is larger than $\{a^nb^nc^nd^n \mid n \geq 1\}$. For example, your grammar generates $abcdd$, which is not of the form $a^nb^nc^nd^n$.
That said, you can generate $\{a^nb^nc^nd^n \mid n \geq 1\}$ using a context-sensitive grammar. Moreover, unrestricted grammar can generate all recursively enumerable languages.


affinity based static load balancing I am trying to find a good model the following problem:

Given a collection of work packets x, y, z, ..., and a collection of worker nodes A, B, C, ..., assign packets to nodes.

Each work packet has an affinity per worker-node, shown as a cost-value for how long a packet takes to process on a specific node. For example, packet x runs twice as fast on node B, and packet z cannot run on node C at all. We get an affinity table like this:

\begin{array}{c|c|c|c|}
 & A & B & C \\ \hline
x& 1& 0.5& 1\\ \hline
y& 1& 1& 1\\ \hline
z& 1& 1& \infty\\ \hline
\end{array}

Now I want to distribute all packets across all available nodes with the best total affinity possible. If each node would take any number of work packets, this is trivial, as each packet would just get assigned to the node it has the best affinity on. However, nodes process their work in parallel, and therefore I primarily want to minimize the maximum cost across all nodes.

For the example above, the solution looks like this:

A: z  cost: 1
B: x  cost: 0.5
C: y  cost: 1
      ----------
      max:  1    <-- needs to be minimized, primarily
      sum:  2.5  <-- should also be minimized

I could just brute-force a solution by permutating all possible combinations, but that isn't feasible for a larger number of nodes and/or packets.

Is there a model for this, which I can research into to find a good algorithm to solve this problem?

Yes, this can be solved efficiently using standard methods for bipartite matching and the assignment problem.  Let me build up to a solution, so you can see the ideas underpinning it.

If you want to minimize the maximum affinity, you can do that with binary search.  Pick a threshold $t$, and check whether there is a valid solution using only assignments that have an affinity $\le t$.  That check can be done by looking for a perfect matching in a bipartite graph, which can be done in polynomial time for a single value of $t$.  (The graph has an edge from a packet to a node if their affinity is $\le t$, otherwise the edge is absent.)  Now do binary search over $t$ to find the smallest $t$ for which such an assignment exists.

If you want to minimize the sum of the affinities, this is an instance of the assignment problem.  There are polynomial-time algorithms for the assignment problem, which you can use directly.

If you want to minimize the max of the affinities, but break ties by choosing the one with the lowest sum, then you can combine above two methods.  First, find the smallest $t$ such that there exists an assignment using only affinities $\le t$.  Then, create an instance of the assignment problem, using only affinities that are $\le t$, and solve the corresponding assignment problem.  This gives an efficient algorithm to solve your problem.


Show that kleene plus language is a regular language by describing how you build a DFA or NFA for it L ⊆ ∑* is a regular language. Show that L^+ (aka kleene plus) is a
  regular language by describing how you can build a DFA or NFA for the
  language.

I would build a NFA. That NFA must have exactly one starting state and one end state, where the starting state is never the end state.

The amount of characters of the given language equals the amount of states of the NFA +1.

Every state except for the end state has an (outgoing) arrow to the next state where every single character of the language occurs exactly once (ordered aka one after the other).

If the language is made up of just one character, do: The end state has an outgoing arrow to itself with that one character of the language.

Else do: The end state has an outgoing arrow to the second state (I mean that state where the starting state points at) with the first character of the language.

Here is an example:

Given is language (aba)^+ where ^+ means exponent +

The NFA for this language would look like this ("Beispiel" means example):

Do you agree with my idea and do you have any improvements?

For the case the language is made up of several pairs, for example (aba, ab, bb)^+ I would just do the entire procedure for every single. In the end you will have a NFA for language (aba)^+ another NFA for (ab)^+ and NFA for (bb)^+. Then concatenate all NFA to one entire NFA.

You can use Thompson's construction. It constructs NFA with $\epsilon$ moves. But remove the forward $\epsilon$-transition from the new start state into the new final state since you are interested in $L^+$ and not in $L^*$.

NFA with $\epsilon$ moves is a generalization of NFA and DFA. But you can systematically transform any NFA with $\epsilon$ moves into equivalent NFA without $\epsilon$ moves and DFA. Look here for more.


Is there an example of Dinitz's algorithm running with the worst time complexity? I am trying to find a network, where Dinic's algorithm makes $|V|^2*|E|$ steps. Clearly it cannot be a network with $3$ or less vertices, but I am not able to come up with a working example for quite a while now.

Any idea?

Dinic's algorithm runs in $O(|V|^2 \cdot |E|)$ time, so it might never make $|V|^2 \cdot |E|$ steps.
Finding a single example is insufficient, as any finite-size counterexample can be "hidden" as a constant in asymptotic notation. You will need an infinite sequence of networks of strictly increasing size with a lower time bound of $\Omega(|V|^2 \cdot |E|)$ to prove that the bound is indeed tight.


What's after EXPSPACE? As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE.

Thinking about this question, I came up with a couple thoughts of my own:

Maybe EXPSPACE = the set of all Recursively Enumerable problems, i.e. $\Delta_1$ in the arithmetical hierarchy. In this case, the rest of the arithmetical hierarchy would come after EXPSPACE.
Maybe there are problems with space requirements that need to be described by non-computatable functions. For example, take the Busy Beaver function, $BB(n)$, which returns the maximum number of steps an $n$-state Turing Machine could take before halting. $BB$ grows faster than any computable function -- so if a problem required $BB(n)$ space to solve, maybe that would put it in a complexity class after EXPSPACE? In other words, maybe after EXPSPACE there is one or more sets of problems that require a non-computable amount of space to solve.

EXPSPACE is not the most inclusive computational complexity class.  There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define).

The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but cannot be decided in space $o(f(n))$.  If we take $f(n)=2^{2^n}$ (say), then we find there are problems that can be decided in space $2^{2^n}$, but not in space $2^n$, and indeed, are not in EXPSPACE.  So, we can "make up" a complexity class, call it 2EXPSPACE, of problems that can be solved in doubly-exponential space; it follows that 2EXPSPACE is bigger than EXPSPACE.  And so on.  There is an infinite hierarchy of complexity classes, each bigger than the previous.

This also shows that EXPSPACE is not equal to RE (the recursively enumerable problems).


Finding Regular expression for FSM with more than one final state I am trying to find Regular expression for a FSM with more than one final state(in my case 2).

In this I am getting two different RE for state q4 and q5. So my question is If we get more than one different RE for one FSM with more than one final state, is it correct??

If we get more than one different regular expression for the same finite state machine with more than one final state, is it correct?

Rather than push the buttons mechanically, you have to understand what you're doing. Your task is to find a regular expression equivalent to a given FSM. This means that the language accepted by your regular expression has to be the same as the language accepted by the given FSM.

For every state $\sigma$ in the FSM, you can computer a regular expression $r_\sigma$ for the language $L_\sigma$ of all words upon reading of which the FSM ends up at the state $\sigma$ (this definition is valid in the deterministic case; for non-deterministic automata, it has to be slightly modified). The language $L$ accepted by the FSM consists of all words upon reading of which the FSM ends up at an accepting state. Given this data, you should be able to come up with a regular expression for $L$ using the regular expressions $r_\sigma$ for all accepting states — you just have to combine them in the correct way.


NP Complete Clique Variation I have the following problem I am trying to prove NP Complete.

Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ classes.

The tutors rent a large study room to offer help to students. But, note that ALL tutors for a specific class can't be in the study room. Otherwise, that class will have no one left to grade the exams.

Question is, can we have $k$ tutors in the study room?

Attempt at solution:

I feel like this is a set or vertex cover problem and have interpreted as follows.
We create a bipartite graph... connecting the left hand side (class) to right hand side (tutor). We have to see if we can choose $k$ tutors from the right hand side such that no left hand side vertex has all its edges used up.

For example, if $k = 1$ the answer is yes. Choose any person.
If $k = 2$ answer is yes. $\{A, D\}$ works but not $\{A, B\}$ because they make up the tutors for $C2$.
$k = 3, 4$ also do not work for the same reasoning.

I am trying to decide if I should approach this with set-covers, clique, independent set? I'm not entirely sure but feel this approach is on the right track.

You can prove this by a reduction from the Hitting Set problem (which is NP-Complete):

  Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set).

So suppose given an instance of the Hitting Set problem. For every element in $u\in U$, create a new TA $T_u$. For every set $S\in F$, create a new class $C_S$ whose TAs correspond to the elements in $S$. Let $k = |U|-q$.

Then if you interpret the TAs being left out of the room as the elements chosen in $H$ it is not hard to see that there exists a hitting set of size at most $q$ if and only if you can put $k$ TAs in the room. That is because putting $k = |U|-q$ TAs in the room is equivalent to leaving at most $q$ outside of the room. And hitting every set in $F$ is equivalent to having at least one TA per class left out of the room.

(I leave the formal proof up to you)


Properties of language that can be enumerated in a finite amount of time with an enumerator? Suppose an enumerator E can enumerate some language L in a finite amount of time (3 days, 3 hours, etc.). What properties does this language have?

My guess:

L is finite, so L is a context-free language.
Since L is a context-free language, L is also decidable
Since L is decidable, L is also Turing-recognizable and co-Turing recognizable

My Questions:

Is L also a regular language?
A theorem says that:

  A language is Turing-recognizable iff some enumerator enumerates it

Is there anything more or less we can say about L, compared to a Turing-recognizable language?

If the language can be enumerated in finite time, then the language itself is finite. Almost all natural classes of languages include all finite languages: they're regular, context-free, decidable, recursively enumerable, co-RE, ...

I'm not sure what else you'd want to say about finite languages compared to RE languages. It's enough to say that the language is finite; for any property you might be interested in, it's usually very straightforward to prove that finite languages do or do not have that property.


Size of Circular Queue I am Implementing a Queue using circular arrays in C language .The Implementation uses one empty position to indicate that the queue is full.That is if the rear is two position behind front. The condition is we cant use a variable to count the entries in the queue as we insert or delete . I have created this function to find the size of queue with Time Complexity Big-Oh(n) because it starts with front and goes upto rear in a loop .

int QueueSize(Queue *q)
{
    if(QueueEmpty(q))
    {
        return 0;
    }
    else{
        int count=0;
    for(int i=q->front;;i=(i+1)%MAXQUEUE)
    {
        count++;
        if(i==q->rear) break;
    }
        return count;
}
}

Is there a way to find the size of queue in constant time ?
Elements are inserted from rear and deleted from front !
My Queue starts from 0 and assume maximum queue size is 6 in below example

10 Appended at position 0
20 Appended at position 1
30 Appended at position 2
40 Appended at position 3
50 Appended at position 4
10 Removed from position 0
20 Removed from position 1
60 Appended at position 5
70 Appended at position 0
30 Removed from position 2
40 Removed from position 3
80 Appended at position 1
90 Appended at position 2
Queue Size:5
Position:4  Element:50 (front)
Position:5  Element:60
Position:0  Element:70
Position:1  Element:80
Position:2  Element:90 (rear)

Suppose that the queue consists of elements $Q[a],\ldots,Q[b]$, where $Q = Q[1],\ldots,Q[n]$ is an array of length $n$. If $a \leq b$ then the queue contains $b-a+1$ elements, and if $a > b$ then the queue contains $b-a+1+n$ elements.


How to determine offset bits when addressing CPU cache? I know that the offset is based off of the line size for a cache. I have seen the example: "32-btye line size would use the last 5-bits (i.e. 25) off the address as the offset into the line" but I do not understand the process used to determine this.

If you need to address a space consisting of $2^N$ values, then you need $N$ address bits.
In your example, $2^N = 32$ and $N = 5$.


Getting a tighter upper bound on the following function We have the following function which determines the Nth fibonacci number:

int fib(int n){
    if(n<=0) return 0;
    else if (n==1) return 1;
    return fib(n-1)+ fib(n-2)

}

Find the time complexity

I am currently reading the book "Cracking the coding interview" and the answer it gave is quite disappointing.  The book says that there are 2 branches per call, and we go as deep as N, therefore the runtime is $O(2^N)$ and it later explains that a tighter upper-bound is $O(1.6^N)$, but it doesn't go over it because the mathematics are "very complex. It doesn't even point out the place where we can find the approach to get the desired upper-bound. I don't want to defame "cracking the coding interview", but I think that more consistency must be shown. My question is, how do we get $O(1.6^N)$ for the algorithm?. It doesn't look like top notch math.

Let's count how many times we have to make a call into fib for each value of n. Let's call that number $f(n)$.

Then:

$$
\begin{align}
f(0) &= 1 \\
f(1) &= 1 \\
f(n) &= 1 + f(n-1) + f(n-2) \qquad \textrm{(for $n > 1$)}
\end{align}
$$

The first several values for $f$ are then 1, 1, 3, 5, 9, 15, 25, 41, 67, etc.

It turns out that if you add one to $f$ and half the result,(*) you get the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, etc.

That is, $f(n) = 2\cdot\textrm{fib}(n+1) - 1$

Since it is well known that the Fibonacci function is $O\left((\frac{1+\sqrt{5}}{2})^n\right)$, so is $f(n)$.

Note that since $\frac{1+\sqrt{5}}{2} \approx 1.618 > 1.6$, the book is actually technically incorrect when it says that $O(1.6^N)$ is an upper bound, and should be corrected to say $O(1.62^N)$ or something similar.

(*) Okay, I kind of pull that out of a hat. As for how to mentally jump from a recursion that's almost like one you know but off by a constant (as in this case, the recursion formula for $f$ looked like the recursion for fib but had that annoying $1+$ at the beginning) one technique is to say:

"What if $g$ were something that obeyed fib's  recursion rule, and $f(n) = g(n) + C$ for some constant $C$. What happens when I substitute that into my recursion equation?"

You then end up with:

$$ g(n) + C = 1 + g(n-1) + C + g(n-2) + C $$

Using $g(n) = g(n-1) + g(n-2)$, you find that $C$ is $-1$. From that you see "Oh, $1+f(n)$ should look kind of like the Fibonacci series, but it starts with "2, 2", so..." (and then it's straightforward to write a formula for $f(n)$).


Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number A set of numbers is stored in a max-heap. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ smallest element is greater than an arbitrary given number.

Here is an attempt at disproof:

Suppose we have a max-heap of $n$ elements such that $k<\log n$ and I inform you that the $k^{th}$ smallest element is at the greatest depth of the tree. Without this detail, it could be elsewhere in the tree, but if we cannot solve this special case in time $O(k)$, the more  general case will take at least as much time - otherwise, we could use the algorithm for the general case to solve this specific case.

Note that in a max-heap, no node will give a bound on how small its children will be (but rather only how large). Thus, if we know the $k^{th}$ smallest is at the greatest depth, no node except those at the greatest depth will provide any information as to the location of the $k^{th}$ smallest element. There are $\log n$ children at the greatest depth and no particular ordering among them (which is one of the key characteristics which differentiates a heap from a sorted binary tree). Thus, you'll need to check all $\log n$ elements before you can determine whether the $k^{th}$ smallest is greater than an arbitrary number.

Hence, no comparison based algorithm with time complexity less than $O(\log n)$ exists to determine for a given max-heap whether the $k^{th}$ smallest element is greater than an arbitrary number.


Determining if a context-free grammar produces even-length strings Given a context-free grammar, is there an algorithm to determine if the CFG will ever produce an even length string? Or is this undecidable?

There is an algorithm:

Recall that given a CFL $L$ and a regular language $K$, the language $L\cap K$ is also CFL (and a CFG for it is computable given a CFG for $L$ and a DFA for $K$).

Now, observe that the language $K=\{w: |w| \text{ is even}\}$ is regular.

From this we conclude that given a CFG $G$, we can construct a CFG for the language $\{w: |w|\text{ is even and }w\in L(G)\}$, and we observe that this language is nonempty iff $G$ generates a word of even length.

Since checking emptiness of CFG can be done in polynomial time, we can solve the problem in polynomial time.


Minimum number of cuts to divide a rectangle We're given a big rectangle, and a list of small rectangles contained inside it, with their vertex coordinates.

We want a list of  the minimum number of lines defined by a pair of points (x,y) that cut up the big rectangle into the small ones.

For example for this case:

The minimum number of cuts would be 7, and they are represented in the following picture.

Any idea to achieve this? (The rectangles are not always touching the borders.)

Each edge of an inner rectangle that (that isn't on the exterior of the big rectangle) is a line segment.  Your problem now becomes: given a collection of line segments, find the minimum number of lines to cover all of the line segments (and nothing more).

This problem can be solved as follows.  For each line segment, extend the line as far as you can in both directions, until it no longer is touching any line segment.  Add that line to your collection of lines.  Repeat until you've covered all of the line segments.  In other words, merge two line segments if they are touching and go in the same direction (since in that case they can be merged into a single line that covers both).  Repeat until you can't merge anything any longer.


Recurrence Relation Mergesort I was reading Algorithms 4th Edition by Sedgewick et al. and I found this statement when discussing about the analysis of mergesort:

  The number of compares is at most n and no less than $\lfloor n/2 \rfloor$.

The code they gave for the merge() routine is shown below:

private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi)
{   int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if (i > mid) aux[k] = a[j++];
        else if (j > hi) aux[k] = a[i++];
        else if (less(a[j], a[i])) aux[k] = a[j++];
        else aux[k] = a[i++];
    }
}

From the code, it seems that the number of compares will be at most $\lfloor n/2 \rfloor$ since if there are $n$ elements and we only compare pairs of them, there will be $\lfloor n/2 \rfloor$ compares.

Then again, I'm sure that I'm just missing something.

Thanks for any help.

Please trace the following code.

Integer[] a = {2, 4, 6, 8,  1, 3, 5, 7}; // an array of 8 elements.
Integer[] aux = new Integer[a.length];
merge(a, aux, 0, 3, 7);

You will find the number of compares is $7= 8-1$.

Here is a fact about general situations.

(Number of compares) Let a be an array of distinct elements. The elements from a[lo] to a[mid] is sorted increasingly. The elements from a[mid+1] to a[hi] is sorted increasingly. Then the compare less(a[j], a[i]) will be run at most hi-lo times in the call merge(a, aux, lo, mid, hi). In particular, if there is $n$ elements in a, there will be at most $n-1$ compares. If we assume lo < mid and mid + 1 < hi, it will be run hi-lo times if and only if a[mid - 1] < a[hi] < a[mid] or a[hi - 1] < a[mid] < a[hi].

Proof of "only if ": Note that after each comparison, either j is increased by 1 or i is increased by 1. The value (j-(mid+1)) + (i-lo) is increased always increased by 1.

Consider the point of time when the last comparison less(a[j], a[i]) happens. The value (j-(mid+1) + (i-lo) = hi - lo - 1. Since j <= hi and i <= mid, we must have j=hi and i = mid.

Now consider the point of time when the second last comparison happens. After that comparison, if i will be increased by 1 and we will find that a[mid - 1] < a[hi] < a[mid]. Otherwise, j will be increased by 1 and we will find that a[hi - 1] < a[mid] < a[hi].

Proof of "if" is skipped.

Exercise 1. What if lo = mid or mid + 1 = hi?

Exercise 2. What if there are repeated elements in a?


Why are most mutex implementations unfair? My understanding is that most popular implementations of a mutex (e.g. std::mutex in C++) do not guarantee fairness -- that is, they do not guarantee that in instances of contention, the lock will be acquired by threads in the order that they called lock().  In fact, it is even possible (although hopefully uncommon) that in cases of high contention, some of the threads waiting to acquire the mutex might never acquire it.

This seems like an unhelpful behavior to me -- it seems to me that a fair mutex would yield behavior more in line with what a programmer would want/expect.

The reason given for why mutexes are typically not implemented to be fair is "performance", but I'd like to understand better what that means -- in particular, how does relaxing the mutex's fairness requirement improve performance?  It seems like a "fair" mutex would be trivial to implement -- just have lock() append the calling thread to the tail of the mutex's linked list before putting the thread to sleep, and then have unlock() pop the next thread from the head of that same list and wake it up.

What mutex-implementation insight am I missing here, that would explain why it was considered worthwhile to sacrifice fairness for better performance?

Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority thread is generally the one that should run.

However, there's a little-discussed secret of operating system implementation which you should be aware of, which is that occasionally operating systems run code as the user by hijacking a user thread. For safety reasons, most operating systems that do this only do it while a thread is blocked. When the operating system is done, the thread is re-suspended, and this typically has the effect of moving the thread to the back of the wait queue.

A typical example is a signal handler in Unix, an asynchronous system trap in VMS, or an asynchronous procedure call in Windows NT. These are all essentially the same thing: The operating system needs to notify the user process that some event happened, and this is is handled by running code in user space.

Many operating system services such as asynchronous I/O are often implemented on top of this facility.

Another example is if the process is under the control of a debugger. In that case, the debugging system may execute code as the user task for various reasons.


Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base? Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $ O(\log_t n) $ (where $t \in \mathbb{N}$ is the order of the tree).
There was one true/false question on exam which asks if the Big-O complexity of the operation mentioned in the example above is $ O(\log_2 n) $.
I am beginner in this topic but I understand that both $ O(\log_2 n) $ and $ O(\log_t n) $ belong to the same Big-O complexity category of $ O(\log n) $. The only thing which confuses me is whether it matters if the base of a logarithm is given as a constant or as a variable.
Additionally: Would the answer change if we swap the bases from the example and the question?
Edit (if relevant): The mentioned complexity is related to the number of disk accesses and it is not the time complexity.

Let's look at the root of question: we have  $\log_2 n=\frac{\ln n}{\ln 2}$ and $\log_t n=\frac{\ln n}{\ln t}$, so $\log_2 n = \frac{\ln t}{\ln 2} \log_t n$ and when $t$ is constant, then logarithms are in same complexity class.
Bit if $t=t(n)$, then we can ruin this relation and create any class $O(f(n))$ of complexity taking $t(n)=e^{\frac{\ln n}{f(n)}}$ we have $\log_t n=\frac{\ln n}{\ln t}=f(n)$.


Disconnecting a complete graph by removing edges randomly Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph.

I want to find out the minimum number of edges that I must remove randomly to disconnect the graph. Also the value of $p$ where I can disconnect the graph by removing the least number of edges.

For your first question, an empty graph becomes connected roughly when $n\log n$ random edges are inserted into it, in a way quantified in Erdős and Rényi's fundamental paper On the evolution of random graphs, and recounted in textbooks on random graphs.

Your second question is not stated precisely and so is difficult to answer.


Why is the VC dimension different on intervals and half intervals? As I read this lecture for being familiar with VC dimension we find on p. 8:

  VC(half intervals in $\mathbb{R}$ ) = 1    ....  no subset of size 2 can be shattered

  VC(intervals in $\mathbb{R}$ ) = 2         ....  no subset of size 3

It's not clear to me. I read on Wikipedia about the difference of  Half Interval and Interval and why VC dimension are different.

For example can this set be half intervals or intervals?

$$
\{ (-\infty \le x \le a) \, \left|\, a \in \mathbb{R} \right. \}
$$

Any direction or hint on this problem?

I assume a half interval $I_a$ is always of the form

$$ \{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\} $$

This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \{y,z\} \subset \mathbb{R}$ such that $y < z$. $S$ is not shattered, since it is impossible to find a half interval $I_a$ such that $S \cap I_a = \{z\}$ (if $z$ is included in the intersection, than $y$ has to be included as well).

When we consider intervals $I_{a,b} = \{(a \leq x \leq b \mid a,b \in \mathbb{R}\}$ in contrast to half intervals, we are able to find an interval $I_{a,b}$ such that $I_{a,b} \cap S = \{z\}$ (as well as for all other subsets of $S$). This makes the difference in the VC dimension.


Shortest subsequence containing all elements Given a sequence $a_1,\ldots,a_n$, find the shortest subsequence $a_i,\ldots,a_j$ such that $\{a_1,\ldots,a_n\} = \{a_i,\ldots,a_j\}$.

I came up with three solutions:
The most straightforward brute-force solution is $O(n^3)$.
We can optimizing brute-force solution, performing a binary search on subsequence length in the outermost loop in $O(n^2 \log n)$.
We can re-use idea from longest common subsequence problem by putting tree-based sets in the table (let's say, elements are comparable with $<$) with copy-on-write implementation. This would be $O(n^2 \log m)$, where $m$ is the number of different elements.
Could it be done better? Maybe, something like Z-functions for all different values in $O(nm)$?

Start by computing the set of all elements in the input sequence. This takes time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ using a hash table.
Suppose there are $m$ such elements $x_1,\ldots,x_m$. Initialize a histogram $H$ of length $m$ with zeroes, and a counter $C$ to $m$. Go over the elements in the sequence from left to right. When processing $a_i$, update $H[a_i] \gets H[a_i] + 1$ (the indexing operation takes time $O(\log n)$ if we are only allowed comparisons, and $O(1)$ using a hash table), decreasing $C$ if $H[a_i]$ were zero. Stop once $C = 0$. If we stopped at $a_j$, then this means that $a_1,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_1$.
Now update $H[a_1] \gets H[a_1] - 1$. If after the update $H[a_i] > 0$, then $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$. Otherwise, continue scanning the sequence, updating $H$ as before, until $H[a_1] > 0$. If we stopped at $a_j$, that $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$.
In this way we can find the lengths of all shortest subsequences containing all elements and starting at $a_i$, for each $i$. We output the length of the shortest one. The entire algorithm runs in time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ otherwise.
In the latter case, $O(n)$ is optimal, as a simple adversary argument shows (whenever the algorithm accesses an element, answer $1$; even after accessing all but one element, the algorithm cannot tell whether the correct answer is $1$ or $2$).
If we are only allowed comparisons, then we can get an $\Omega(n\log n)$ lower bound from Element Distinctness. Suppose that we could solve our problem using $T(n)$ comparisons. Given a sequence $a_1,\ldots,a_n$, consider the sequence $a_1,\ldots,a_n,a_1,\ldots,a_n$. If all elements are distinct, the shortest subsequence containing all elements has length $n$. Otherwise, if $a_i = a_j$ for $i < j$ then the subsequence $a_{i+1},\ldots,a_n,a_1,\ldots,a_{i-1}$ contains all elements and has length $n-1$. This shows that we can solve Element Distinctness in time $T(2n)$. The well-known lower bound $\Omega(n\log n)$ on Element Distinctness implies that $T(2n) = \Omega(n\log n)$, and so our algorithm is optimal. (Formally speaking, we also need to handle odd input lengths. We can do this by adding a fresh element between the two copies of the original sequence.)
Credit for the algorithm: https://www.glassdoor.com/Interview/Find-shortest-substring-in-a-string-that-contains-all-of-a-set-of-characters-QTN_66124.htm


Rod Cutting without using dynamic approach Question

I want to Implement Rod cutting Algorithm without Dynamic Programming Approach.

Let me Describe the problem statement.

  Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.

In cormen, the Algorithm is implemented as -:

CUT-ROD (p,n)
1 if n == 0
2 return 0
3 q = - inifinity
4 for i = 1 to n
5 q =max(q, p[i]+CUT-ROD(p,n-i))
6 return q

I got this algorithm , i may explain it with a example-:

Say we want to determine maximum revenue for $n=4$,

and the profit associated with each inches i.e $i=1,2,3,4$is given as follows-:

$p[1]=1,p[2]=5,p[3]=8,p[4]=9$

Now Moving to the algorithm ,if we want to find maximum revenue for Length 4 inch ,we need to call CUT-ROD$(p,4)$.How will it process , i mean what will be its sequence!?i can explain-:

  CUT-ROD$(p,4)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,3)$
  $p[2]+$CUT-ROD$(p,2)$
  $p[3]+$CUT-ROD$(p,1)$
  $p[4]+$CUT-ROD$(p,0)$

for $i=1,2,3,4$ respectively.

Now when $i=1$, it will encounter CUT-ROD$(p,3)$

  CUT-ROD$(p,3)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,2)$
  $p[2]+$CUT-ROD$(p,1)$
  $p[3]+$CUT-ROD$(p,0)$

for $i=1,2,3$ respectively.

  CUT-ROD$(p,2)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,1)$
  $p[2]+$CUT-ROD$(p,0)$

for $i=1,2$ respectively.

  CUT-ROD$(p,1)$ will be computed by

  maximum value of

  $p[1]+$CUT-ROD$(p,0)$

for $i=1$

CUT-ROD$(p,1)$=1,CUT-ROD$(p,2)$=$max(1+1,5)=5$

CUT-ROD$(p,3)$=$max(1+5,5+1,8+0)=8$

CUT-ROD$(p,4)$=$max(1+8,5+5,8+1,9+0)=10$

MY Doubt

I implemented the $C$ code,but it is giving wrong result.I don't know why!

I guess that the sequence of the function call is wrong .Here is the code.

#include<stdio.h>
int p[100];
int result=-9999;
int count=0;
int max(int x,int y)
 {
   return (x > y)? x : y;
 }
int recrsv_top_down(int sizee)
 {
   int i;
   if (sizee<=0)
   {
     return 0;
   }
   for(i=1;i<=sizee;i++)
   {
     result=max(result,(p[i]+(recrsv_top_down(sizee-i))));
   }
   return result;
 }
int main()
 {
    int size,i,result;
    printf("enter the size of rod\n");
    scanf("%d",&size);
    printf("enter the profit of assocaited length\n");
    for(i=1;i<=size;i++)
    {
     printf("enter profit assocaited with length %d \n ",i);
     scanf("%d",&p[i]);
    }
    printf("\n***************OUTPUT*****************\n");
    result=recrsv_top_down(size);
    printf("Maximum profit is %d\n",result);
    return 0;
}

Sorry for the long post , but i have no option!!!

Please help me out !

In recrsv_top_down, declare result = -1000 as a local variable.


How to tell if a grammar is LALR(1) formally? There is an “informal” definition of $\operatorname{LR}(k)$ (can be recognised by a parser that looks at $k$ symbols ahead) and a “formal” one (as a property of the set of rightmost derivations possible for the grammar). Is there a similar formal criterion of a grammar being $\operatorname{LALR}(k)$ or specifically $\operatorname{LALR}(1)$?
For context, I am interested in looking into grammar transformations that preserve the property of being $\operatorname{LALR}(1)$ (for example, does eliminating right recursion in an $\operatorname{LALR}(1)$ grammar result in a grammar that is still $\operatorname{LALR}(1)$?)

The answer to your first question is: Not that we know of.
A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton.
The good news is that the key complication is empty derivations. So, for example, if a $\hbox{LL}(1)$ grammar has no nonterminals that have only empty derivations (i.e. if every nonterminal has at least one non-empty derivation), it is $\hbox{LALR}(1)$.
See Beatty, On The Relationship Between LL(1) And LR(1) Grammars for further results. You may find something in there that's useful to you.


Exponential Time Classification If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time?

print([2,4,8,16]) #operations:1
print([1,4,8,16]) #operations:2
print([1,3,8,16]) #operations:3
print([1,2,8,16]) #operations:4
print([1,1,8,16])  #operations:5
print([1,1,7,16])  #operations:6
print([1,1,6,16])  #operations:7
print([1,1,..,16]) #operations+=1
print([..])       #operations+=1
print([1,1,1,1])  #operations: 2**(n+1)-2 :: O(2**n)?

Does one add the number of operations or the complexity of each operation?

Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

If the complexity is constant time would I need each operation to be O(2**n) for the algorithm to be classified as exponential time?  O(2**n)*(2**(n+1)-2) reducing to O(2**n) or would it reduce to double exponential time: O(2**(2**n))?

Here is some python code for such a naive algorithm:

orig_lst=[2,4,8,16]
out_lst=orig_lst[:]
ops=0
n=len(out_lst)
for ind,el in enumerate(out_lst):
    for dec in range(el,0,-1):
        ops+=1
        out_lst[ind]=dec
print(orig_lst,"->",out_lst,"number of operations:",2**(n+1)-2,"==",ops)

Which prints: "[2, 4, 8, 16] -> [1, 1, 1, 1] number of operations: 30 == 30"

Does one add the number of operations or the complexity of each operation?

This is a good question! And the answer is, "it depends".

In any model of computation, some type of operation is considered "fundamental", and this operation is considered to run in $O(1)$. For example, some models consider multiplication to be fundamental. But others consider multiplication exponential in the number of bits.

No matter what, though, your algorithm is going to be doing $2^n$ decrement operations on the last element of the list, so it's always going to be $\Omega(2^n)$ (where the omega means "at least", as opposed to omicron's "at most").

  Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

I'm not sure I understand this part of the question. $O(1) \times (2^{n+1}-2)$ is $O(2^n)$, not $O(1)$.

However, your time complexity certainly isn't double-exponential. As you noted, you're doing $2^{n+1}-2$ decrement operations, so if you consider decrement to be constant, the total time is $O(2^{n+1}-2) = O(2^n)$.

Even if you did an additional $O(2^n)$ operation for each decrement, the time complexity would only be $O(2^n) \times O(2^n) = O(2^{2n})$.


Is there an adjustment for Adler32 algorithm so it works well on short messages? The Adler32 algorithm has a shortcoming as noted on Wikipedia:

  Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very short messages. He wrote "Briefly, the problem is that, for very short packets, Adler-32 is guaranteed to give poor coverage of the available bits. Don't take my word for it, ask Mark Adler.  :-)"

If I am only computing a checksum on packets that are around 1,500 bytes long, is there an adjustment to Adler32 to make it work well in this case?  Alternatively, is there another algorithm that is as fast as Adler32 but does not have such weaknesses?  What about the Fletcher algorithm - does it suffer the same weakness?

In [1], the authors show that for 1500 bytes, the chance of an undetected collision with Adler32 is less than one in 100 billion.

In that paper, see Figure 13 which states:

  Comparison of 8-, 16-, and 32-bit Fletcher and Adler checksums using random data at a BER of 10-5. The data point values are the mean of 10 trials.

And shows probability of undetected error using Adler32 to below 10-11 for a 1500 byte message.

Therefore, as D.W. suggested above, no adjustment is needed.

[1] Maxino, Theresa C., and Philip J. Koopman. "The effectiveness of checksums for embedded control networks." Dependable and Secure Computing, IEEE Transactions on 6.1 (2009): 59-72.


In O(1) get the coordinate i,j of a diagonally ordered matrix Say you have a matrix like this:

[][]int{
    {0, 2, 5, 9, 14},
    {1, 4, 8, 13, 18},
    {3, 7, 12, 17, 21},
    {6, 11, 16, 20, 23},
    {10, 15, 19, 22, 24},
}

As you can see, it is diagonally ordered

Question:
In Order O(1) if I give you a number N, give me the position i,j.

For example, on a regular ordered matrix

[][]int{
  {0,1,2,3},
  {4,5,6,7},
  {8,9,10,11},
  {13,14,15,16}
}

The solution is

j := n % len(m)
i := n / len(m[0])

With that you get i,j.
Ex: N=9 -> 2,1

But how to get them for diagonals?

These are triangular numbers, so:
$i = \lfloor(-0.5 + \sqrt{0.25 + 2 * n}\rfloor - 1\\
triangular = \frac{i * (i + 1)}{2}\\
j = n - triangular - 1$

Minus one comes from indexing from 1.


Does the aliasing problem show up in a virtually indexed physically tagged cache? Basically, and as a simple method, we can access cache with Physical Address which is from the TLB.

But, as another method, we can access cache with Virtual Address. But, in this case, if the cache is not fully flushed between context switch(other process's datas can be exist in cache), there is an aliasing problem. Same memory can be directed from the different virtual address.

But in my text book, including these problem, many can be solved by virtually indexed physically tagged. I think this still can make an aliasing problem.

Am I wrong?

The Aliasing problem can be solved if we select the cache size small enough. If cache size is such that the bits for indexing the cache all come from the page offset bits , multiple virtual address will point to the same index position in  the cache and aliasing will be solved.

For example consider 32-bit virtual address 0xFFFF FFFF  , this system uses a page size of 64kB suppose which make the page offset bits 16 bits. Now if we select The index bits to be 10 (number of sets 1024) and block size as 64 Bytes. Then the index bits and the block offset bits both are accommodated in the page offset bits of the virtual address. Consider another address  0xEEEE FFFF  this address looks like it will cause aliasing but despite of having different virtual address the lower order bits force it to map to the same location in the cache  and there is no aliasing. Only drawback of this approach is cache size is limited by the page size.


Finding most likely tree over a semilattice If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees.

Now assume that each semilattice edge is annotated with a transition probability. In addition, let's assume that the probability of a tree over the semilattice is the product of the probabilities of all the edges that the tree uses.

How to find the most likely spanning tree, that is the most likely hypothesis how the nodes came to be? I am unsure whether this amounts to finding a maximum spanning tree of the semilattice.

I guess this has applications in probabilistic graphical models...

The maximum spanning tree is about summing weights; maximizing the probability is about multiplying weights.  To convert multiplication to sums, take the logarithm.

Hopefully that's enough for you to work out an algorithm for this task.


Why does this mergesort variant not do Θ(n) comparisons on average? A comparison sort cannot require fewer than $\Theta (n\log n)$ comparisons on average. However, consider this sorting algorithm:

sort(array):
    if length(array) < 2:
        return array
    unsorted ← empty_array
    i ← 0
    while i < length(array) - 1:
        if array[i] > array[i + 1]:
            push(unsorted, pop(array, i + 1))
        else:
            i ← i + 1
    return merge(array, sort(unsorted))

(push(array, element) puts the new element at the end of the array and increases the array’s length by 1. pop(array, index) removes the element at that index from the array, moving all the elements at greater indices and decrementing the array’s length, and returns the removed element. merge is the same as in mergesort.)

Instead of simply splitting the array in the middle like mergesort, it splits it so that one resulting array doesn’t need to be recursively sorted. Let $n$ be the length of the array to be sorted. Applying the Master Theorem gives us

$$\begin{align*}
    T(n) &= T(n / b) + \mathrm{splitComparisons}(n) + \mathrm{mergeComparisons}(n) \\
         &= T(n / b) + (n - 1) + n \\
         &= T(n / b) + 2n - 1\,,
\end{align*}$$

so $f(n) = 2n - 1$ and $a = c = 1$ in the statement of the Master Theorem.

$b$ is one over the probability that an element is greater than the next element and will go into the array to be recursively sorted. For example, if there's a 25% chance that array[i] > array[i + 1] (for all i), $b = 4$. $b$ is clearly greater than $1$, since the length of unsorted array grows smaller with every recursive call, so taking the logarithm with base $b$ of $1$ will always give us $0$, which is less than $c$. Then $T(n) = \Theta(f(n)) = \Theta(n)$.

But that can’t be true, so the Master Theorem isn't applicable for some reason; I suspect because $b$ isn't constant, but I don’t know how to prove that. The worst case of the sorting algorithm obviously requires a quadratic number of comparisons and the best case linear, so by analogy with bubblesort, insertion sort, etc, I’m guessing this algorithm also makes a quadratic number of comparisons on average.

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in unsorted.

In particular, there is no $b$ so that your ansatz describes the actual number of comparisions.

Assuming that the probability distribution of the length of the longest increasing subsequence survives your splitting, a proper ansatz would be of the form

$\qquad\displaystyle C(n) = C(n - 2\sqrt{n}) + \Theta(n)$

which does not seem to solve² to $C \in O(n)$.

In fact, it's even worse since you keep the "first" increasing subsequence, not the longest (in general); consider for instance $[1,n,2,3,4,\dots,n-1]$; you keep $[1,n]$ and recurse on $[2,3,\dots,n-1]$.

On the distribution of the length of the longest increasing subsequence of random permutations by J. Baik, P. Deift and K. Johansson (1999) [via Wikipedia]
I have not solved it explicitly, but plots suggest as much.


Why is the commit phase in PBFT necessary? I've read many papers and slides on Practical Byzantine Fault Tolerance (PBFT) but I'm still confused about why a COMMIT phase is required. Most material states that

PREPARE phase ensures fault-tolerant consistent ordering of requests within views
COMMIT phase ensures fault-tolerant consistent ordering of requests across views

Some tutorial glosses over that

  The PREPARE phase ensures that a majority of correct replicas has agreed on a sequence number for a client’s request. Yet that order could be modified by a new leader elected in a view change.

Can someone show me an example of how COMMIT interacts with view changes?

PBFT is a master piece, for its technical breakthrough and exquisitely precise language. Many descriptions on the protocol details worth reading multiple times to grasp all the nuances.
I will:

quote the original paper (some math notation expressed in Latex, I will use pseudo code instead)
add on my understanding/interpretation.
Q&A myself important questions
Answer your question directly by giving out an example

Pre-Prepare and Prepare phases

We define the predicate prepared(m,v,n,i) ....
The pre-prepare and prepare phases of the algorithm
guarantee that non-faulty replicas agree on a total order
for the requests within a view. More precisely, they
ensure the following invariant: if prepared(m,v,n,i) is
true then prepared(m',v,n,j) is false for any non-faulty
replica j (including i = j) and any m' such that D(m') !=D(m)
.

This means, once reached "prepared" stage (i.e. one replica has received more than 2f+1 PREPARE), this replica, if non-faulty, could be certain that, this message m in this view v is associated with this sequence number n.
Commit phase

The commit phase ensures the following invariant: if
committed-local(m,v,n,i)
is true for some non-faulty i
then committed(m,v,n)
is true. This invariant and
the view-change protocol described in Section 4.4 ensure
that non-faulty replicas agree on the sequence numbers
of requests that commit locally even if they commit in
different views at each replica.

^^^ This is the clue for me to go back and carefully read the definition of "commit-local" over and over:

and committed-local(m,v,n,i)
is true if and only if prepared(m,v,n,i)
is true and has
accepted 2f+1 commits (possibly including its own)
from different replicas that match the pre-prepare for m;
a commit matches a pre-prepare if they have the same
view, sequence number, and digest.

^^^ notice that? match the pre-prepare, not match the prepare, why? remember "PREPARE" gives certainty on ordering within a view, "PRE-PREPARE for m" emphasize on certainty of sequence number regardless of which view, as long as commit matches the pre-prepare.
Maybe you know why by not, but if it is still not clear, please read on.
Q:Why COMMIT phase necessary?

There are replicas (non-faulty or otherwise) that didn't receive enough (i.e. 2f+1) PREPARE messages, either due to lossy network or being offline for a while. For them, they can't reach PREPARED stage. But! But when they heard from 2f+1 replicas broadcasting COMMIT message, they could be certain to commit on (m,v,n,i)
Apparently, a obvious benefit for COMMIT stage is that it accelerate the agreement/consensus process. Intuitively, you could understand it as : I'm on my way to school, Bob told me school is closed today. I couldn't take one man's word as truth. But as I march on, I see many more classmates (who have already checked whether school is closed or not) returning back from school telling me school is closed. Up until majority told me so, I will take their word for it before reaching school myself.

Example of cross view COMMIT
There are 4 replicas in total. For a message m, I, the replica, received a COMMIT: (COMMIT, m, v, n, i=2), meaning in view v, node #2 told me he committed. But since I didn't receive any other commits, I couldn't reach "commit-local" stage.
Now, "NEW-VIEW" message has been passed around. During protocol redo: other replicas multicast PREPARE messages for each message between min-s and max-s, then later I receive another COMMIT (COMMIT, m, v+1, n, i=3)
Now, could I reach "commit-local"? since I have one commit in view v and another in view v+1.
Answer is yes. Because new primary issued a new PREPARE for m, and I had two matching commits -- 2 commits in a 4 replicas system. Good enough.
Hope it helps!
Any further comment is welcomed.
Cheers!


Gap between the average length of a Huffman code and its entropy Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and entropy is 0.72: (1- 0.72) = 0.28 -> 28% worse than optimal.

If both “average length” and “entropy” are 1, the compression is optimal.

But what does it mean if the result is negative value?

Note: entropy : -(pr*lg(pr)).
Average length: probability*number of bit

Shannon's source coding theorem shows that you cannot compress data more than its entropy, even if you encode chunks at a time. For the specific case of prefix-free codes (even uniquely-decodable codes), this follows from Kraft's inequality, which for a uniquely-decodable code with codeword lengths $\ell_i$ states that
$$ \sum_i 2^{-\ell_i} \leq 1, $$
and furthermore every code can be "improved" (by only decreasing its codeword lengths) so that equality holds.
Suppose that the probability of the $i$th symbol is $p_i$. The average codeword length is $E = \sum_i p_i \ell_i$.
We want to minimize $E$ given the constraint $\sum_i 2^{-\ell_i} = 1$, and furthermore $\ell_i \geq 0$ are integers. Relaxing integrality, we can find the optimum using Lagrange multipliers: it satisfies $p_i = \lambda 2^{-\ell_i} \log_e 2$ for some $\lambda$. Kraft's inequality forces the solution $2^{-\ell_i} = p_i$, and so
$$ E \geq \sum_i p_i (-\log_2 p_i). $$
The right-hand side is simply the entropy of the distribution.

This argument immediately gives a criterion for when Huffman's code reaches the entropy: this happens if $-\log_2 p_i$ is always an integer, that is, all probabilities are of the form $1/2^k$ (for integer $k$).


What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$? Note: I have not studied theoretical computer science, so this may be a trivial question.

I am interested in the general question: what restrictions are put on a machine $m$ (boolean circuit, TM, ...), by the assumption that $m$ solves a certain problem or class of problems? The question I'm asking in this post is: What field of theoretical CS should I read up on for this?

For example:

Can all problems be solved by a lookup table? Or does assuming that $m$ solves problem $X$ tell us that $m$ has to do particular types of computations?
If we have a boolean circuit $C$ that computes problem $f$, can we then always construct a boolean circuit $\tilde C$ that also computes $f$ but has only a depth of 2 layers (or something like this).

What should I look in to to get an insight in questions like this? (I'm not asking for answers to these specific two questions).

The computational power of machines / automata / programming languages and similar computational models, is usually studied in these theoretical fields:

Computability (for what can be computed at all)
Complexity (for what can be computed efficiently)
Formal languages (several kinds of automata exist, with different expressiveness)

You will find many textbooks about these topics, as well as university courses (some video lectures could even be available on the 'net)


Physical significance of pumping length in pumping lemma Would it be possible to explain the physical significance of pumping length $p$ in pumping lemma for regular languages?

Somehow, the physical significance of
pumping length $p$ in pumping lemma for regular languages escapes me.

I have explored a number of tutorials and presentations on this topic. The nearest I came to is, at some point, $p$ was assumed to be the number of states in the DFA recognizing the language. But the same presentation at some later point cautioned that $p$ is a property of the language, and not of the DFA.

When we prove a language to be not-regular, first of all, we assume it to be regular and thus having a pumping length $p$. We also assume the language to satisfy the conditions of pumping lemma. Later on, we find that the language fails to satisfy the conditions of pumping lemma and hence not a regular one.

So, such languages will not have any pumping length.

But what about regular languages? If I am given a regular language, there are many, just pick any one from this list, $10^*$, $1\Sigma^*$, $\Sigma^* 001$, would it be possible for us to point out the pumping length for that language?

First, in the Pumping Lemma as I know it, there is no such thing as the pumping length for a language. "For every regular language $L$ there exits a constant $p$ such that for any string  $w\in L$ with $|w|\ge p$ ...". In fact, if $L$ satisfies pumping length $p$ then it will also satisfy any pumping length larger than $p$. (This is not completely trivial, the requirements in the dots ... above mention $p$ again.)

So we can call the smallest length $p$ for which the pumping property holds "the" pumping length. This is indeed a property of the language. If I am right the pumping length for $L = a(aa)^*+b(bb)^*$ is three. Strings of length 3 and above can be "pumped".

As you observe yourself, every regular language can be pumped (well, that is what the Lemma states). And the proof may use any automaton for the language. Whenever a string is at least as long as the number of states in the automaton, its computation must repeat a state, and we can pump. We can use the smallest automaton for the language, to minimize the pumping length. That smallest deterministic automaton is in fact well-defined. Unfortunately this in general still does not fix the (minimal) pumping length. An automaton for $L$ above seems to use at least five states (and actually 6 if it must be deterministic).

But still the property seems tied to the regular language via a certain "minimal" automaton, and the length of strings that ensure repetition of states.

But hey, even non-regular languages might in fact be pumpable: the Pumping Lemma (or better Pumping Property) is not a characterization of the regular languages. See for instance "Languages that satisfy the pumping lemma but aren't regular?" where it is observed that languages of the form $c L\cup \{ c^k \mid k\neq 1 \}\cdot\{a,b\}^∗$ for any $L\subseteq \{a,b\}^*$ have the Pumping Property (for pumping length one or two, I believe).
I do not know a "physical" significance in the nonregular case.


Is an algorithm in pseudocode a reasonable way to establish complexity? We define the language

$$
L =  \{a^nb^n : n\geq0 \}
$$

and we want to prove the following

$$
L = \mathrm{DSPACE}(\log n)\,.
$$

So we have to prove that by using $\log n$ space on the work tape of a Turing machine we can decide this language.
In this case, do we have to describe the delta function in detail, or can we just use the Church Turing thesis and show an algorithm that uses $\log n$ space to decide this language, and thus claim that $L$ is indeed in $\mathrm{DSPACE}(\log n)$?

For example the pseudocode for the above language would be the following:

    number_of_as = 0
    number_of_bs = 0
    tmp = read()
    while(tmp == a)
          number_of_as++
          tmp = read()
    if(tmp == b) number_of_bs = 1
    tmp = read()
    while(tmp == b)
          number_of_bs++
          tmp = read()
    if(number_of_as == number_of_bs) "accept"
    else "reject"

we only use two counter and the tmp variable, for each variable we need $\log n$ space, so in total $3\log n$, so the problem is in $\mathrm{DSPACE}(\log n)$.

To state the obvious, you need to prove that the language is decided by some Turing machine that uses a logarithmic amount of space on its work tape.

Anything beyond that is a question of how rigorous the proof should be. A proof should be rigorous enough to convince an appropriately skeptical reader. How much skepticism is appropriate in a given situation?  Well, that's a largely social construct. If we were chatting during a coffee break at a complexity theory conference, I'd probably be convinced by "Oh, just use a couple of binary counters to remember how many $a$s and $b$s you've seen. The input has length $n$ so the counters only need $\log n$ bits each."  If I was marking your undergrad complexity theory exam, I'd expect rather more detail. For example, our conference chat didn't include the fact that the machine should reject if it finds an $a$ after the first $b$ and your pseudocode also misses this, so it accepts the string $aba\notin L$.

Expecting a full definition of the Turing machine is probably unreasonable. First, it would take a long time to produce. Second, and more importantly, it would be sufficiently complicated that it would be hard to verify that the Turing machine really does what you claim it does. A proof that is too complicated for anyone to understand isn't really a lot of use.  That being the case, you're pretty much going to have to use pseudocode. If I wanted to test that you could produce a formal description of a Turing machine, I'd use a simpler language, such as the strings with an even number of $a$s in them.

Is pseudocode on its own enough? Not quite. For example, you can't just invoke Church–Turing to convert your pseudocode into a Turing machine. Why not? Because Church–Turing preserves computability but not complexity. So, what does an answer need?  I would say the following.

Pseudocode for an algorithm.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode actually solves the required problem.
If it's not obvious, a proof (with an appropriate level of rigour) that the pseudocode can be converted into a Turing machine with the appropriate resource bounds.

Even if you think the two proofs are obvious, it's a good idea to write a sentence or two about them. Trying to explain as briefly as possibly why something is correct can often find bugs such as the $aba$ problem.


Is 2-SAT with XOR-relations NP-complete? I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination?

Example Input:

2-SAT part: (a or !b) and (b or c) and (b or d)
XOR part : (a xor b xor c xor 1) and (b xor c xor d)

In other words, the input is the following boolean formula:

$$(a \lor \neg b) \land (b \lor c) \land (b \lor d) \land (a \oplus b \oplus \neg c) \land (b \oplus c \oplus d).$$

Example Output: Satisfiable: a=1, b=1, c=0, d=0.

Both the number of 2-SAT clauses and the number of XOR clauses in the input are $O(n)$, where $n$ is the number of boolean variables.

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT.  Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $$(x_1 \lor \overline{y}) \land (y \oplus x_2 \oplus z) \land (\overline{z} \lor x_3)$$ with $y$ and $z$ as new variables.


Algebraic data types - unions Are there any programming languages where algebraic data types can be expressed not only by using intersection and disjoint union but also a standard set union (intersection + disjoint union)?

Do such types even make sense?

If so, could you provide practical example of use?

Yes, these type systems exist. They're generally referred to as "Set-theoretic Type Systems", and there's a good rundown of them here. They've been extended a lot, particularly with regards to subtyping and datasort-refinement types.

For a practical application of them, checkout their use in TypeScript.

Basically, union types correspond to untagged unions, and intersection types are a single value that matches two types. So we have rules that look like this:

If $v : T_1$, then $v : T_1 \cup T_2$ for any $T_2$
If $v : T_1$ and $v : T_2$, then $v : T_1 \cap T_2$

These are both commutative, so there's a symmetric union rule.

Note the difference between normal types: the unions here are untagged, and we have very little information when using a value of a union type, since we have no runtime way of determining which half of the union it is.

Likewise, a value matching an intersection type is not a pair, it's a single value that happens to typecheck against both of the types in the intersection.

Under this formulation, we can treat polymorphic and existential types as infinite intersections and unions:

$\forall a \ldotp T$ is $\bigcap_{S \in TYPE} [S/a]T$
$\exists a \ldotp T$ is $\bigcup_{S \in TYPE} [S/a]T$

That is, if a value typechecks against a polymorphic type, then it checks against any instance of that type. And if a value typechecks against an existential type, there must be some concrete type that it typechecks against.

As you might expect, introducing these usually makes type inference undecidable, though there is a lot of research going on in this area that I will not claim to be an expert in.


Given a binary matrix, how to find the starting coordinates of a sub matrix? Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from where the matrix was cropped from.

I encoded some lines at regular intervals. The position of the lines follow the equation $y = x^2$. This way when I find the difference between the distance of two lines i.e. $dy/dx = 2x$, I can calculate the value of x and y. This gives me the position of the pixel at that point. So I can subtract the offset and find the starting coordinates.

The multiple lines are for redundancy sake and colours for illustration.

In this way, I can find the coordinates of cropped images of a reasonable size. My question is, "Is there a proper way of doing it?" Also this technique does not work for lossy file compression techniques like jpeg, does a method exist that is more robust?

I have been reading into Space filling curves but I have no idea how to solve this problem using them.

EDIT: I found a thing called m-sequence. I will add it for future reference.

Here is one approach.  It won't survive JPEG compression, though, so probably you can do better.

Let $m$ be an integer large enough that $2^m$ is significantly larger than both the width and height of the matrix.  Choose a maximum-period $m$-bit LFSR; this generates a sequence of bits of length $2^m-1$, say $s_1,s_2,s_3,\dots,s_{2^m-1}$, where each $s_i \in \{0,1\}$.

Now, construct the original matrix as follows: at coordinate $(i,j)$, the value will be $s_i \oplus s_j$.

Given a submatrix, we can find coordinates as follows.  First note that given a consecutive range of the sequence $s$ of length at least $$, we can find where in the sequence it was taken from.  In other words, given $s_i,s_{i+1},\dots,s_{i+m-1}$, we can recover the value of $i$.  (How?  Simply trying all possible values of $i$ will work; one property of LFSR sequences is that the map $i \mapsto (s_i,s_{i+1},\dots,s_{i+m-1})$ is bijective, so $i$ will be uniquely determined.)

Now given the submatrix, we'll try to find the coordinates of its upper-left corner, say $(i,j)$.  We'll start by looking at the first row of the submatrix, and examine the sequence of values that appear in its grid.  This either takes the form $s_i,s_{i+1},s_{i+2},\dots$ or $s_i \oplus 1, s_{i+1} \oplus 1, \dots$ according to whether $s_j=0$ or $s_j=1$.  We can try both possibilities for $s_j$, and get two candidates for $i$.  Then we look at the first column of the submatrix, and obtain two candidates for $j$ in the same way.  This gives us two candidates for $(i,j)$, we can check which one is correct by looking at a few other positions in the submatrix.

Then, you can recover the coordinates of its lower-right corner in the same way.

All in all, this will enable you to recover the coordinates of the submatrix, as long as the submatrix is at least $m$ pixels wide and $m$ pixels high.

There are other ways as well.  For instance, one very simple approach is to fill in the original matrix randomly, and remember how you filled it in.  Then given a submatrix it is straightforward to find where it came from (e.g., by checking all possibilities; this can be sped up by precomputing a hash table).

In practice, if you plan to print out the original matrix and then take a scan or photo of it, then you might want a different approach that is more robust to the kind of transformations that will typically occur during printing and scanning.  That will lead to a very different kind of problem.  So if you want to know about how to do that, you should probably ask a separate question focused on those considerations.


$\mathsf{PP=RP}$ consequences We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level.

What are the other non-trivial collapses and consequences?

$\newcommand{\co}{\mathsf{co}\text{-}}$
$\newcommand{\class}[1]{\mathsf{#1}}$

If $\class{PP}=\class{RP}$ then you have a collapse to the first level, namely $\class{PH}=\class{NP}$.

Assume $\class{PP}=\class{RP}$, since $\class{PP}$ is closed under complement we have $\mathsf{RP}=\co{\class{RP}}=\class{ZPP}$, thus $\class{PP}=\class{ZPP}$.

Using Toda's theorem:

$\class{PH}\subseteq\class{P^{\class{PP}}}=\class{P}^{\class{ZPP}}=\class{ZPP}\subseteq{\class{NP}}$.

You actually get something stronger, if $\class{PP}=\class{RP}$, then the hierarchy collapses to $\class{ZPP}$.

In fact, you could show that the counting hierarchy collapses to $\class{ZPP}$, using simpler arguments than Toda's theorem, and acheive $\class{PH}\subseteq\class{CH}\subseteq\class{ZPP}$.

A tempting argument would be to say that since $\class{PP}=\class{ZPP}$, and $\class{ZPP}$ is low for itself, i.e. $\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ then $\class{PP}^{\class{PP}}=\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ and $\class{CH}$ collapses to $\class{ZPP}$. This is obviously false, since $\class{A}=\class{B}$ where $\class{A},\class{B}$ are sets of languages "decidable" by specific types of Turing machines (types $\class{A}$ and $\class{B}$), does not imply $\class{A}^{\mathcal{O}}=\class{B}^{\mathcal{O}}$ for any oracle $\mathcal{O}$. See this answer for further explanation.

What you actually need to show, in order to obtain $\class{CH}\subseteq{ZPP}$ (of course, under the original assumption of $\class{PP}=\class{RP})$, is that $\class{ZPP}$ is low for $\class{PP}$, i.e. $\class{PP}^{\class{ZPP}}=\class{PP}$. If this holds, then $\class{PP}^{\class{PP}}=\class{PP}^{\class{ZPP}}=\class{PP}=\class{ZPP}$, and thus $\class{CH}\subseteq\class{ZPP}$. Fortunately, this is not too difficult (and can even be strengthened to $\class{BPP}$ is low for $\class{PP}$).

Let $L$ be a language in $\class{PP}^{\class{ZPP}}$, then there exists a probabilistic polynomial time Turing machine with access to a $\class{ZPP}$ oracle $\mathcal{O}$, call it $M_{\mathcal{O}}$, such that:

$x\in L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]>\frac{1}{2}$, and

$x\notin L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\le\frac{1}{2}-\frac{1}{2^{n^c}}$.

Where $n^c$ is the running time of $M_{\mathcal{O}}$ (in the standard definition, the second inequality appears with $\le\frac{1}{2}$, however it can be improved to $<\frac{1}{2}$ and thus to the above).

Suppose that the Turing machine which decides $\mathcal{O}$ has expected runtime $n^d$. Now, let us look at the machine $M$, which replaces each oracle call of $M_{\mathcal{O}}$ by a $t$ steps simulation of the $\class{ZPP}$ machine for $\mathcal{O}$, and repeats this simulation $k$ times. If we come upon an oracle call, for which this process did not result in an answer (none of the $k$ $t$-steps simulations halted), then $M$ rejects.

Let $H$ denote the event that all of the simulations halted in the given time, then:

$\Pr\left[\text{M accepts x}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]+\Pr\left[\text{M accepts x}\Big| \overline{H}\right]\Pr\left[\overline{H}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]=\Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\Pr[H]$.

Thus, we have:

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\Pr[H]$, and

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le\left(\frac{1}{2}-\frac{1}{2^{n^c}}\right)\Pr[H]\le \frac{1}{2}-\frac{1}{2^{n^c}}$.

By Markov's inequality, a single simulation does not halt with probability $\le \frac{n^d}{t}$, so $k$ $t$-steps simulations do not output an answer with probability $\le \left(\frac{n^{d}}{t}\right)^k$. By the union bound we have $\Pr[H]\ge 1-n^c\left(\frac{n^{d}}{t}\right)^k\ge 1-\frac{1}{2^{n^c}}$, for $t=2n^d$ and $k=2n^c$. In this case $M$ acheives the following separation:

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\left(1-2^{-n^c}\right)$, and

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le \frac{1}{2}-2^{-n^c}<\frac{1}{2}-\frac{1}{2}2^{-n^c}$

Which proves $L\in \class{PP}$, since we can replace the constant $\frac{1}{2}$ with any function $f(x)\in \class{FP}$. See this question for a proof to why we can replace $\frac{1}{2}$ with any rational constant, and convince yourself that it generalizes immediately to any $f\in \class{FP}$.


Why are loops faster than recursion? In practice I understand that any recursion can be written as a loop (and vice versa(?)) and if we measure with actual computers we find that loops are faster than recursion for the same problem. But is there any theory what makes this difference or is it mainly emprical?

The reason that loops are faster than recursion is easy.
A loop looks like this in assembly.

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

A single conditional jump and some bookkeeping for the loop counter.

Recursion (when it isn't or cannot be optimized by the compiler) looks like this:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

It's a lot more complex and you get at least 3 jumps (1 test to see if were done, one call and one return).
Also in recursion the parameters need to be set up and fetched.
None of this stuff is needed in a loop because all the parameters are set up already.

Theoretically the parameters could stay in place with recursion as well, but no compilers that I know of actually go that far in their optimization.

Differences between a call and a jmp
A call-return pair is not very much more expensive then the jmp. The pair takes 2 cycles and the jmp takes 1; hardly noticeable.
In calling conventions that support register parameters the overhead for parameters in minimal, but even stack parameters are cheap as long as the CPU's buffers do not overflow.
It is the overhead of the call setup dictated by the calling convention and parameter handling in use that slows down recursion.
This is very much implementation dependent.

Example of poor recursion handling
For example, if a parameter is passed that is reference counted (e.g. a non const managed type parameter) it will add a 100 cycles doing a locked adjustment of the reference count, totally killing performance vs a loop.
In languages that are tuned to recursion this bad behavior does not occur.

CPU optimization
The other reason recursion is slower is that it works against the optimization mechanisms in CPU's.
Returns can only be predicted correctly if there are not too many of them in a row. The CPU has a return stack buffer with a (few) handfuls of entries. Once those run out every additional return will be mispredicted causing huge delays.
On any CPU that uses a stack return buffer call based recursion that exceeds the buffer size is best avoided.

About trivial code examples using recursion
If you use a trivial example of recursion like Fibonacci number generation, then these effects do not occur, because any compiler that is 'knows' about recursion will transform it into a loop, just like any programmer worth his salt would.
If you run these trivial examples in a enviroment that does not optimize properly than the call stack will (needlessly) grow out of bounds.

About tail recursion
Note that sometimes the compiler optimizes away tail recursion by changing it into a loop. It is best to only rely on this behavior in languages that have a known good track record in this regard.
Many languages insert hidden clean up code before the final return preventing the optimization of tail recursion.

Confusion between true and pseudo recursion
If your programming environment turns your recursive source code into a loop, then it is arguably not true recursion that is being executed.
True recursion requires a store of breadcrumbs, so that the recursive routine can trace back its steps after it exits.
It is the handling of this trail that makes recursion slower than using a loop. This effect is magnified by current CPU implementations as outlined above.

Effect of the programming environment
If your language is tuned towards recursion optimization then by all means go ahead and use recursion at every opportunity. In most cases the language will turn your recursion into some sort of loop.
In those cases where it cannot, the programmer would be hard pressed as well.
If your programming language is not tuned towards recursion, then it should be avoided unless the domain is suited towards recursion.
Unfortunately many languages do not handle recursion well.

Misuse of recursion
There is no need to calculate the Fibonacci sequence using recursion, in fact it is a pathological example.
Recursion is best used in languages that explicitly support it or in domains where recursion shines, like the handling of data stored in a tree.

  I understand any recursion can be written as a loop

Yes, if you are willing to put the cart before the horse.
All instances of recursion can be written as a loop, some of those instances require you to use an explicit stack like storage.
If you need to roll your own stack just to turn recursive code into a loop you might as well use plain recursion.
Unless of course you've got special needs like using enumerators in a tree structure and you don't have proper language support.


if $L \in NP$ then its mapping reducible to HALT? This is true because every language in $NP$ is decidable and therefore HALTS but how do I formally show this?

It depends what type of reduction you're talking about. But if you mean a "many-one reduction with no time constraints" (a Turing machine that transforms instances of problem $L$ to instances of problem HALT such that the answers remain the same), then yes.

The algorithm goes something like this:

Take an input $x$
Use brute force to decide whether $x \in L$ (in potentially exponential but still finite time)
If the answer is "yes", let $T$ be a Turing machine that always accepts
If the answer is "no", let $T$ be a Turing machine that always diverges
Return $\langle T \rangle$

Now, when $\langle T \rangle$ is passed to a HALT oracle, the oracle will accept if $x \in L$, and reject if $x \not \in L$.


Efficiently finding the min-cost path of an AVL tree It seems that in a full AVL tree, the left edge is always the minimum-cost path. For example, take the following full AVL tree:

The min-cost path would be 8-6-5. However this is not the case with other AVL trees. Take the previous tree with an additional 4 inserted:

Here the min-cost path would be 8-6-7 rather than 8-6-5-4.

What is the most efficient algorithm to find the min-cost path in any AVL tree? Given the characteristics of AVL trees, is this algorithm faster than it would be for a standard BST?

Searching in an AVL tree is anyways only at most O(log n) (see on @Wikipedia: https://en.wikipedia.org/wiki/AVL_tree?wprov=sfta1). If you do not care about the higher cost of rebalancing AVL tree instead of BSTree, this tree will have even the advantage of always maintaining the AVL-min-cost path on the left edge. Search the left edge has also O(log n) so no cheaper than other trees. Balancing a tree is only nesessary if building a tree can cause massive imbalance,  only than AVL has a marginal advantage above BST.

To your counter example on AVL tree with a not-left-edge min-cost: This is to my quick grasp the furthest imbalance one can find before need of rebalancing of AVL is needed. Hence no need to worry about finding the minimum cost path in AVL tree may be more difficult due to tree depth. So searching the minimum path within the left and not totally left path is O(log n +1) equaling O(log n). So it is basically not harder to find the actual minimum path than finding the obvious left edge.


Decidability of a language of Turing Machine descriptions Given the language

  $\{ <M> \mid\:$ M is a Turing machine           and there is some w ∈ Σ* for which the computation M(w) takes more than 10 transitions$\}$

How can one prove that this language is decidable?

Given a Turing Machine M (with its finite number of tape symbols,
finite number of states, etc...), how hard is it to prove that there
is an input on which it will run for more than 10 steps? How much of
the input will be read in 10 steps at most? How many different
computations have to be checked to see whether one takes more than 10
steps?

added later: I was editing this when the reference to question Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable? was given as comment.


How does this example violate Liskov substitution principle, which then causes violation of the open-closed principle? From Agile Principles, Patterns, and Practices in C# by Robert Martin,

  Listing   10-1.   A   violation   of  LSP causing a    violation  of  OCP

struct    Point   {double x,  y;}
public    enum    ShapeType   {square,    circle};
public    class   Shape
{
      private ShapeType   type;
      public  Shape(ShapeType t){type =   t;}
      public  static  void    DrawShape(Shape s)
      {
              if(s.type   ==  ShapeType.square)
                      (s  as  Square).Draw();
              else    if(s.type   ==  ShapeType.circle)
                      (s  as  Circle).Draw();
      }
}
public    class   Circle  :   Shape
{
      private Point   center;
      private double  radius;
      public  Circle()    :   base(ShapeType.circle)  {}
      public  void    Draw()  {/* draws   the circle  */}
}
public    class   Square  :   Shape
{
      private Point   topLeft;
      private double  side;
      public  Square()    :   base(ShapeType.square)  {}
      public  void    Draw()  {/* draws   the square  */}
}

  DrawShape() violates    OCP.    It
  must    know    about   every   possible    derivative  of  the  Shape  class,
  and it  must    be  changed whenever    new derivatives of   Shape  are
  created.

  The   fact    that     Square   and  Circle   cannot  be  substituted for Shape     is  a
  violation   of  LSP.    This    violation   forced  the violation   of  OCP by
  DrawShape . Thus,   a   violation   of  LSP is  a   latent  violation   of  OCP.

How does it violate Liskov substitution principle (LSP)?
(In particular, why can Square    and  Circle   not be  substituted for  Shape?)

How does violation of LSP cause violation of the open-closed principle (OCP)? (I can  see it directly violates OCP, but I can't understand how violation of LSP causes violation of OCP.)

Thanks.

The listing does not appear to be a good illustration of LSP violation, since no clear reason is given why the draw method couldn't be a virtual method of Shape. If it was, then there would be no need to do any type query in drawShape: calling draw would work for all subclasses of Shape.

The Liskov Substitution Principle is typically described in terms of contracts. For example: the contract of the square root function requires that the input is non-negative and ensures that the square of the output is equal to the input.

Hence, an overridden method in a subclass is substitutable for the corresponding method in the superclass if it:

requires no more of its input than the superclass contract
ensures no less of its output

A subclass is LSP-conforming if all its methods are LSP conforming.

Hence, a better illustration of LSP violation might be a rotate method, in which all shapes except Square can be rotated by any angle, but Square is only rotatable by some multiple of 90% (such a requirement would actually demonstrate that the Square should not be a subclass of Shape).

In general, LSP violation causes OCP violation because there is no meaningful action that a 'closed' function can take without needing knowledge of specific subclasses in the type hierarchy.

The standard example of this is to have a Circle class be a subclass of an Ellipse class that has a resize(xaxis,yaxis) method. Unless the semantics of resize are so diluted as to be largely useless ('maybe resize yourself or throw an exception') then subclasses can end up in a state that is inconsistent with anything meaningful/useful to the 'closed' function that is calling its methods.

A good discussion of the LSP (including the 'Circle-Ellipse' issue) can be found here


Why are programs executed in main memory? Why are programs kept in main memory for execution? As per my understanding, we need a memory management scheme to manage several processes in the main memory. These things can be done in secondary memory as well (I think). Just to improve performance, we need main memory or there is something more to it?

They are not.  On modern desktop/server OSes, the program generally mmapped (or equivalent) into virtual memory and the currently running parts are paged in as needed.  However, the remainder of the program can sit on secondary storage and never be accessed.

The reason for the currently executing parts of memory being paged in as opposed to running directly from secondary storage is performance.  In general, any read access to secondary storage tends to be cached in memory, either directly through virtual memory or indirectly through something like a disk cache.  In fact, in the main memory there's an extensive cache hierarchy (typically 3 layers on x86 Intel / AMD processors) so even the idea that the program is store in "main" memory is mostly a convenient simplification, not a complete description of reality.  What actually happens is that some parts of the program are paged into main memory (by the OS) and some parts of the the program from main memory is cached into the L3 cache (by the CPU) and some parts of that are cached into the L2 cache(by the CPU) and some parts of that are cached into the L1 instruction cache (by the CPU).

On embedded systems and more exotic architectures, deviations from this pattern definitely exist.  Execute-in-place was already mentioned but another example is Harvard architecture processors, where instruction and data memory are completely separate and code runs from the instruction memory which isn't addressable as data.  Small embedded microcontrollers like PIC and AVR are examples of such processors.


Constructing a NFA that accept complement of language L of another NFA if given a language $L$ recognized by NFA $N_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N_1$ that accept $L^C$ such that $L^C= \{w \in \Sigma^{*} |\mid w \notin L \}$?

Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I don't know, since the construction above can be exponential time in the number of states (because of the powerset construction).


What is the asymptotic complexity of the following code snippet? for (i = 2; i < n; i = i * i) {
  for (j = 1; j < i / 2; j = j + 1) {
    sum = sum + 1;
  }
}

I know that the outer loop can run for a maximum of $n^2$ times and the inner loop will run for $\frac{n^2}{4}$ times.

The second loop runs in $O(i)$. The first loop goes over the powers $2^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is
$$
O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}),
$$
where $m$ is the maximal integer such that $2^{2^m} < n$. We can bound
$$
2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} < 2n.
$$
Therefore the overall running time is $O(n)$.

In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log_2 \log_2 (n-1) \rfloor}})$, with a bit more work.


Why an error probability of 1/3 in BPP? BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.

But why was 1/3 chosen? If we have an algorithm with some error probability less than 1/2, then we can run it several times, taking the most common result, to obtain an error probability of less than 1/3 while still staying in the same complexity class.

So why isn't BPP instead defined as the algorithms which have an error probability of less than 1/2? Is there something special about 1/3?

The constant $1/3$ is completely arbitrary. Let's say that $\mathsf{BPP}_p$ is the class of problems solvable in polytime with error at most $p$. Then $\mathsf{BPP}_p = \mathsf{BPP}_q$ for any $0 < p,q < 1/2$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you can boost the success probability by running the algorithm several times and take a majority vote (details left to you).

Why do we like $1/3$, then? It's the "simplest" rational number in $(0,1/2)$: for example, it is the rational number in $(0,1/2)$ with the minimal possible denominator, and with the minimal sum of numerator and denominator.


defining the operational semantics of a concurrent language As big-step operational semantics is about evaluating an expression to a final value, can we state that for defining a concurrent language one needs small-step semantics, as concurrent programs need not result in a value?

Coinductive Big-Step Semantics for Concurrency by Tarmo Uustalu writes:

  Second, contrary to what is so often stated, concurrency is
  not inherently small-step, or at least not more inherently
  than any kind of effect produced incrementally during a
  program’s run (e.g.,  interactive output).  Big-step semantics
  for concurrency can be built by borrowing the suitable
  denotational machinery, except that we do not want to use
  domains and fixpoints to deal with partiality, but
  coinductively defined sets and corecursion.

So the answer is that it is stated throughout the literature, but it is not true.


Synchronization using serialization How can someone synchronize two or more threads using serialization? According to my professor's slides and code assignments you can use serialization to solve the synchronization problem. (He doesn't explain what serialization is).

I tried to do my research but serialization means that you put data in a specific order. I would understand that it means the same thing in this case (Running threads in a specific order). But what I most confused about is the syntax of the question. My question is:

Does serialization mean synchronization? How would one synchronize threads using serialization?

Two or more threads executing concurrently require synchronization if and only if at least one of the threads accesses and modifies one or more variables (write access) accessed by the remaining threads (either read or write access). Therefore, if all of the threads access the same set of variables only for reading their values (read access), no synchronization is needed. You probably know that the access to variables by multiple threads when at least one of them writes at least one of the variables, must happen in a so-called critical section (or critical region) of code. You then synchronize the access by providing mutual exclusion using for instance a Posix mutex lock. This permits concurrent execution of multiple threads, so that the execution preserves correctness when updating one or more of the variables involved.

Of course, concurrent execution of multiple threads is the most efficient way of writing code in general. However, you may also imagine a different execution, in which the operations associated to each thread are executed sequentially and not concurrently, one after the other, in an order that is strictly equivalent to a concurrent, correct execution. This is called serialization of execution. What does it mean "strictly equivalent" ? Serialization must provide as a requirement exactly the same results that will be provided by a concurrent,  correct execution. Note that there are multiple possible concurrent and correct executions, but the outcome must be one and only one.

Now, do you really want to use serialization to synchronize your threads ? The answer is no, because a serialized execution is in general slower than a concurrent execution (obvious, since execution is sequential and not concurrent). In practice, serialization just gives you a criterion for correctness. You want your threads to execute concurrently, for performance reasons, however, you must ensure that the outcome is correct independently of the actual concurrent execution that took place.

As an example imagine two threads accessing a variable which is the amount of money you have deposited in your bank. If both threads just want to read that amount of money, no issue arises. However, if one or both the threads want to modify that value, a problem arises and you need to synchronize the access. For instance, one thread may be depositing money to your account (you in your bank), and the other thread ma be withdrawing money from your account (your wife from an ATM). In these cases, access to the variable holding the amount of money must be synchronized. Serialization in this case is simple: you must either first withdraw the money and then add the money, or, vice-versa, you first add the money to your bank account and then withdraw the money. In both cases, serialization provides the correct outcome. To grant a correct outcome in the case of a concurrent execution, you must instead protect the variable using a mutex lock, so that access to the variable is mutually exclusive for both the threads. Otherwise, the value of the variable when accessed from both threads without proper synchronization is actually undefined, which is very bad for your money! You may, for example loose part or all of of your money.

Another type of synchronization is not related to mutual exclusion. Imagine, for instance, that one thread can execute its operations only after another thread has completed. Another example: a thread can execute only when a specific condition is true, and this condition depends on another thread (this includes the previous example, but is a more general requirement, based on the evaluation of a predicate).
For instance, you may synchronize threads in this way by using Posix mutex locks and condition variables.

Serialization has been thoroughly studied in the context of database transactions. A serialized schedule provides a criterion for correctness of execution of concurrent transactions in databases, and there are protocols that ensure proper synchronization (e.g., two-phase locking). But the concept applies equally well to threads as well.