Who needs linearizability? I've been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in which cases linearizability would be needed, even though it's stronger than serializability.

Could you come up with scenarios where such strong property would actually be necessary?

I've reread Herlihy and Wing many times over the past 15 years.  It is a very difficult read.  And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable.

In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering constraints between the transactions.  The goal is to allow you to reason rigorously about an individual atomic data structure rather than having to reason about the entire system all at once.

Linearizability is also easy to achieve: just associate a mutex with the object you want to linearize. Every transaction on that object starts by locking the mutex and finishes by unlocking the mutex.

Here are the definitions I'll use:

  A system is serializabile if given a set of transactions over a set of data, any result of executing the transactions is the same as if the transactions were executed in some sequential order, and the operations within each transaction are contained within their transaction in the order specified by the transaction's code.

Serializability disallows the appearance of interleaving of operations between different transactions, and requires that the chosen ordering of transactions satisfies causality (if transaction A writes the value x, and transaction B reads the value x that A wrote, then transaction A must precede transaction B in the chosen serial order.)  But it says nothing about any other constraints on the ordering of transactions (in particular, it says nothing about processes and the order in which processes perceive events.)

There is another related idea that does add in the constraints about the order in which processes executed operations (but doesn't talk about transactions only individual read/write operations):

  A system is sequentially consistent if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. (Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE T Comp 28:9(690-691), 1979).

Implicit in the definition of sequential consistency is that we only accept sequential orders where for each memory location (object) the induced sequential order of operations obeys the rule that the value returned by each read operation to location x must be the same value that was written by the immediately preceding write operation to location x in the sequential order.

Linearizability has the good intentions of (a) combining together the notion of transactions (from serialization) with the notion that processes expect the operations they issue to complete in order (from sequential consistency) and (b) narrowing the correctness criteria to talk about each object in isolation, rather than forcing you to reason about the system as a whole.  (I would like to be able to say that my object's implementation is correct even in a system where there are other objects that are not linearizable.)
I believe Herlihy and Wing may have been trying to rigorously define a monitor.

Part (a) is "easy": A sequential consistency-like requirement would be that the transactions on the object issued by each process appear in the resulting sequence in the order specified by the program.  A serialization-like requirement would be that the transactions on the object are all mutually exclusive (can be serialized).

The complexity comes from objective (b) (being able to talk about each object independently of all the others).

In a system with multiple objects it is possible that operations on object B place constraints on the order in which we believe operations were invoked on object A.  If we are looking at the entire system history then we will be constrained to certain sequential orders, and will need to reject others.  But we wanted a correctness criteria that we could use in isolation (reasoning just about what happens to object A without appealing to the global system history).

For example: suppose I am trying to argue about the correctness of object A, which is a queue, suppose object B is a memory location, and suppose I have the following execution histories: Thread 1: A.enqueue(x), A.dequeue() (returns y).  Thread 2: A.enqueue(y), A.dequeue() (returns x).  Is there an interleaving of events that would allow this implementation of the queue to be correct?  Yes:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

But now what if the history (including object B) is: B starts with value 0. Thread 1: A.enqueue(x), A.dequeue() (returns y), B.write(1).  Thread 2: B.read() (returns 1) A.enqueue(y), A.dequeue() (returns x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Now we'd like our definition of "correctness" to say that this history indicates that either our implementation of A is buggy or our implementation of B is buggy, because there is no serialization that "makes sense" (either Thread 2 needs to read a value from B that hasn't been written yet, or Thread 1 needs to dequeue a value from A that hasn't been enqueued yet.)  So while our original serialization of the transactions on A seemed like a reasonable one, if our implementation allows a history like the second one, then it is  clearly incorrect.

So the constraints that linearization adds are quite reasonable (and necessary even for simple data structures like FIFO queues.)  They are things like: "your implementation should disallow dequeue() a value that won't be enqueued() until some time in the future."
Linearizability is quite easy (and natural) to achieve: just associate a mutex with your object, and each transaction starts by locking and ends by unlocking.  Reasoning about linearizability starts to get tricky when you are trying to implement your atomicity with non-blocking or lock-free or wait-free techniques instead of simple mutexes.

If you are interested in some pointers to the literature, I found the following (although I think the discussion about "real-time" is one of the red-herrings that make linearizabilty more difficult than it needs to be.) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability


Binary cross Entropy derivative? I am just learning backpropagation algorithm for NN and currently I am stuck with the right derivative of Binary Cross Entropy as loss function.
Here it is:
def binary_crossentropy(y, y_out):
    return -1 * (y * np.log(y_out) + (1-y)*np.log(1-y_out))

def binary_crossentropy_dev(y, y_out):
    return binary_crossentropy(y, y_out) * (1 - binary_crossentropy(y, y_out))

def binary_crossentropy_dev2(y, y_out):
    return (y_out - y)/ (y_out * (1-y_out))

But when comparing both derivative above with real numbers, their results are differenct altough they should be the same.
What am I doing wrong with the above equations?
Thank you!

Here is the definition of cross-entropy for Bernoulli random variables $\operatorname{Ber}(p),\operatorname{Ber}(q)$, taken from Wikipedia:
$$
H(p,q) = p \log \frac{1}{q} + (1-p) \log \frac{1}{1-q}.
$$
This is exactly what your first function computes.
The partial derivative of this function with respect to $p$ is
$$
\frac{\partial H(p,q)}{\partial p} = \log \frac{1}{q} - \log \frac{1}{1-q} = \log \frac{1-q}{q}.
$$
The partial derivative of this function with respect to $q$ is
$$
\frac{\partial H(p,q)}{\partial q} = -\frac{p}{q} + \frac{1-p}{1-q} = \frac{(1-p)q-p(1-q)}{q(1-q)} = \frac{q-p}{q(1-q)}.
$$
This is exactly what your third function computes.
I'm not sure what your second function computes. Also, there is no reason to expect that the partial derivative with respect to one variable will be the same as the partial derivative with respect to another variable.


More than one NFA accepting a given language While going through certain problems. it seems that more than one NFA is possible for the given language. Is it so?

For example for drawing: NFA ending with 1 where $\Sigma=\{0,1\}$ is

and also we can draw one without 0 from the edge P to P!

Which one should be considered "more" correct?

There are many, many different NFAs accepting a particular language, or DFAs for that matter. You can just add branches that lead into dead ends at will, for example. Or add detours that give the same result as the main road, like in your automaton adding a new state $r$, with transitions from $p$ to $r$ on 1, and then from $r$ to $r$ on 0 and 1, and finally from $r$ to $q$ on 1.

In the given case, omitting the transition from $p$ to $p$ on 0 gives another language. You should convince yourself that the modified NFA doesn't accept anything containing zeros.


What's the vertex cover of the null graph? Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.

The minimum vertex cover for a totally disconnected graph is the empty set. A vertex cover is a set of vertices that covers all the edges, i.e. every edge in the graph needs at least one of its endpoints in the vertex cover, so if there are no edges in the graph, no edges need covering.


Iterated logarithm $\log^* n$ I am to come up with a function based on these premise:

Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$.

The answer is the iterative logarithm $\log^* n$, and I want to show each of these steps.

1) show that $\log^* n \leq \log^{k+1} n$

2) show that $\log^{k+1} n = o(\log^k n)$

3) show that $\log^* n = \omega(1)$

I am stuck on mathematics behind these step because of my lack of knowledge of the iterated Logarithm. Can I ask for assistance at this?

Let's assume the definition under which $\log^* 2 = 1$, $\log^* 2^2 = 2$, $\log^* 2^{2^2} = 3$, and so on. In order to show that $\log^* n = \omega(1)$, all you have to do is show that $\log^* n \to \infty$. Since $\log^*$ is increasing, it is enough to give a sequence of values $n_1,n_2,\ldots$ such that $\log^* n_i \to \infty$. Can you think of such a sequence?

In order to show that $\log^* n = o(\log^k n)$ for any fixed $k > 0$, find numbers $n_\ell$ such that $n \leq n_\ell$ implies $\log^* n \leq \ell$, and notice that for $n_{\ell-1} < n \leq n_\ell$, $\log^* n/ \log^k n \leq \ell/(\log^k n_{\ell-1})$. Perhaps you can show that $\log^k n_{\ell-1}$ is much larger than $\ell$ for large enough $\ell$. More concretely, you can try to show that $\log^k n_{\ell-1} \geq \ell^2$ (for example) for large enough $\ell$.


Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm? The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS.

You have a slow machine running at $x$ MIPS, and a fast machine running at $y$ MIPS. You also have two algorithms of the same class, but different running time complexities: one "slow" algorithm runs at $T(n) = c_1n^2$ whereas a "fast" algorithm runs at $T(n) = c_2n \log n$.

You execute the slow algorithm on the fast machine, and the fast algorithm on the slow machine. What is the largest value of n such that the fast machine running the slow algorithm beats the slow machine running the fast algorithm?

My solution so far:

Find the set of all $n$ such that $$\frac{c_2n\log n}{x} > \frac{c_1n^2}{y}$$ where $n$ is a natural number.

This is my work thus far:

$$\{n : \frac{c_2 n \log_2 n}{x} > \frac{c_1 n^2}{y}, n \in \mathbb{N}\} = \{n : n < \frac{c_2 y}{c_1 x} \log_2 n, n \in \mathbb{N}\}$$

The only solution that comes to mind now is to plug-n-chug all values of $n$ until I find the first n where

$$n < \frac{c_2y}{c_1x}\log(n)$$

no longer holds.

Consider your last inequality:

$\qquad \displaystyle n < \frac{c_2y}{c_1x}\log(n)$

Now, $C\log n$ with $C = \frac{c_2y}{c_1x}$ is a concave function. Therefore, there are at most two intersections, and only one of them is interesting for you; that is, solve

$\qquad \displaystyle n = C\log(n)$

and find out which algorithm is faster in which interval by simply calculating the respective function values at some point in the respective interval.

It is true that solving this equality explicitly is hard/impossible. For some fixed $C$, computer algebra gives you an expression in a well-known function; interesting (real) intersection turns out to be at

$\qquad \displaystyle n = e^{-W_{-1}(-\frac{\ln 2}{C})}$

if $C \geq e \ln 2$, with $W_k$ the analytic continuation of the product log function. This function does not have a nice closed form, but it can be evaluated numerically for given $C$; for instance, you get $\approx 116,74$ for $C=17$.


CLRS pseudocode involving both subscripting and property access of a data structure In Introduction to Algorithms, the stack data structure's enqueue operation has the following pseudocode

ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
    Q.tail = 1
else Q.tail = Q.tail + 1

I started writing it in Swift and figured the queue should be modeled as a structure

struct IntQueue {
    var items = [Int]()
    var head = 0
    var tail = 0
}

func enqueue(queue: IntQueue, item: Int) {

}

to be able to access the head and tail properties. However, I'm not sure why the pseudocode subscripts Q directly. Is this shorthand for subscripting a queue's nested array property rather than the queue type itself?

In pseudocode we can use whatever convention we want, as long as the reader understands what we mean.

That said, in languages like python and C++ you can actually define the subscript operator to access the underlying array, and for such languages the pseudocode could work literally.


Is this an example of parallelization? Not sure if this is the right exchange for this question. But you could definitely answer it. Note professor said this was “wrong” on their quiz.
Question: Identify a daily activity that can be speed up with  parallelization.
My answer: People driving their own car vs people taking a bus.
My reasoning: When people all take a bus they have to wait for all the destinations before theirs to pass. When people drive a car they go directly to their destination.
The professor said this isn’t a good example of a serial processor made parallel. I’m not convinced. Where am I wrong? I plan to argue my case..

If I want to go from A to B, that doesn’t get faster by taking a bus. But if I want to take 50 people from A to B that actually will be done much faster.
A simple example: How do you make six boiled eggs? And how do you make 120 boiled eggs if you have an oven with four flames, that will involve some pipelining as well.


L* is in P but L is not? I am trying to show that $L^* \in P $ does not necessarily mean that $L \in P$. My idea was to find a language $L \notin P$ , apply $*$ operator and show that $L^* \in P$ by showing that $L^*$ can be decided with a polynomially bounded Turing machine, which will be a contradiction to $L^* \in P \Rightarrow L \in P$. However, I am having trouble in finding such $L$. Is there a trivial $L$ that I'm not thinking of? Or should change my method? Any help will be appreciated.

Yes, your method is fine and, yes, there's a fairly trivial way to complete your proof attempt: it's easy to arrange that $L^*=\Sigma^*$, which is in P.


Equivalence between a TM and a changing TM Let a changing TM be a TM which is not able to write the same symbol which is being read.
Formal:  $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with  $q,q^* \in Q, a,a^* \in \Gamma, c \in \{R,L\}$ .
Now I need to proof that a changing TM is equivalent to a normal TM.

My guess was to create a multi-tape TM which is able to simulate the changing TM(and therefore a TM is equivalt to a changing TM, since every multi Tape TM has equivalent single tape TM), but I am unnable to finish(write it formal and unformal down).

It is clear that a TM can simulate a changing TM, so you only need to show the converse. Let me allow to use the "stay" movement in the changing Turing machine. It is easy (but tedious) to remove this assumption and keeping it makes the following argument more intuitive.

You can do the following: start from a TM $T$ with set of states $Q$ and tape alphabet $\Gamma$. Then, create a changing TM $T'$ with states $Q' = Q \cup (Q \times \Gamma \times \{L,R\})$ and tape alphabet $\Gamma' = \Gamma \cup \{ \gamma \}$.

Intuitively, state $q \in Q$ of $T'$ represents state $q$ of $T$, while state $(q, a, m) \in Q \times \Gamma \times \{L,R\}$ of $T'$ represents the fact that we plan to write $a$ on the current tape cell, then transition to state $q$, and move in the direction specified by $m$ (notice that this a state, not a transition, we are just keeping track of our future plans).

Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

$(q, a) \to ( (q', b, m), \gamma, S)$, and
$( (q', b, m), \gamma) \to (q',b, m)$

Intuitively, this replaces the writing of a symbol $b$ on the tape with two operations: 1) we write $\gamma$ without moving the head, and 2) we overwrite $\gamma$ with $b$, move the head in the intended direction $m$, and transition to the corresponding state $q'$ of $T$.

This is a tedious simulaton of a TM with a changing TM if the "stay movement" is not allowed.
Define $\Gamma' = \Gamma \cup \{\gamma_1, \gamma_2\}$ and $Q'= Q \cup (Q \times \Gamma \times \{L,R\} \times \Gamma')$.
Replace each transition $(q, a) \to (q', b, m)$ of $T$ with the following transitions in $T'$:

$(q, a) \to ( (q', b, m, \gamma_1), \gamma_1, R)$,
$( (q', b, m, \gamma_1), x) \to ( (q', b, m, x), \gamma_2, L)$ $\quad \forall x \in \Gamma$,
$( (q', b, m, x), \gamma_1) \to ( (q', b, m, x), \gamma_2, R)$ $\quad \forall x \in \Gamma$,
$ ( (q', b, m, x), \gamma_2) \to ( (q', b, m, \gamma_1), x, L)$ $\quad \forall x \in \Gamma$,
$( (q', b, m, \gamma_1), \gamma_2) \to (q', b, m)$

What we are doing is the following: 1) We write $\gamma_1$ and move right,   2) we store the current tape symbol $x$, replace it with $\gamma_2$, and move left, 3) we replace the tape symbol $\gamma_1$ with $\gamma_2$ and move right, 4) we write back the stored type symbol $x$ in place of $\gamma_2$ and move left, 5) we finally write $b$, move according to $m$, and transition to state $q'$.


Table-driven lexers in Engineering a Compiler 2nd Edition Recently, I am reading Engineering a Compiler 2nd Edition.

But I am struggling to understand the following pseudocode.

Can anyone help me to explain the pseudocode in a simple and plain English?

Why NextChar does take a char input?
Why lexeme is the result 0f lexeme + char?
What is the result of Delta[state, cat];?

Let me answer your questions very quickly:

NextChar(char) reads a character and assigns it to the variable char.
The new character is appended to the current lexeme being built via the command lexeme = lexeme + char.
The table Delta implements the transition function $\delta$ of a DFA (sometimes called an FSM). There is a lot of information on DFAs on the web and even on Computer Science.

I was able to answer these questions via a combination of common sense and a very rudimentary knowledge of how lexers work. More generally, when faced with code or pseudocode which you don't quite understand, you should try to figure out what the code is trying to accomplish, and how. For example, NextChar surely reads a character. You might expect it to return it, but from the context it is clear that it is actually stored in its argument. The fact that it is adjoined to lexeme significantly strengthens this guess.


When to use DFS and when use BFS? Preparing for an interview.

I see two cases where each one is specially suited

BFS:  When you need to find shortest path between vertices (if one exists).

DFS:  If you need to find cycles in a directed graph:

Uses-case where both can be used:  Finding cycle in undirected graph, Is there a path from one vertex to another

Are there any other specialized or common cases?

In general DFS is considered to be simpler (though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion). So, if both can be used for a use-case, use DFS?

Bfs and Dfs both are good state space search algorithms. If search space is infinite then its good to use Bfs because dfs can be lost in infinite space and will not return any result.
Also, Bfs searches result in neighbors and then go neighbor by neighbor on other hand dfs searches for answer branch by branch. If you search key is near starting point then go for bfs


proving that a problem is in P I read online that this problem is in P:

Problem = {a^n, where n is a primary number}

I can't find any algorithm that decides if a word w in {a}* is in Problem, can someone help me because I'm not really convinced that this problem can be solved in polynomial time.

Hint: does being in P have something to do with the length of the input?


Solving a maze with DFS vs "wall following" Consider a problem where a "robot cleaner" is placed on a room modeled as a grid. Each cell in the grid can be empty or blocked and all accessible cells are connected, meaning, all empty cells will be accessible by the robot regardless of its starting position.

We are told that the robot cleaner can only take one of four actions:

move forward
turn left (90 degrees, without moving)
turn right (90 degrees, without moving)
clean the current cell in the grid

We are asked to design an algorithm for the robot to clean the entire room.

My question is: Can this problem be framed as a maze solving problem? I mention this because a common strategy (if the maze is simply connected) for maze solving is to be a "wall follower" (e.g. always try right, or always try left), and I wonder if wall following would work here.

More generally, why would "wall following" be a good strategy for either problem? Isn't it enough to do DFS (with backtracking) even if we pick an arbitrary order of directions that are "left to explore" from each grid position? (or explore directions at a given position in any order?)

Try it on some simple examples.  You'll quickly see why wall following is not sufficient.


Length of shortest word accepted by exactly one of two DFAs Let $M_1$ and $M_2$ be two deterministic finite automata with $M_1$ having $n$ states, and $M_2$ having $m$ states, over the same alphabet $\Sigma$. Show that if $M_1$ and $M_2$ are not equivalent, then there is some string $\omega \in \Sigma^*$ of length at most $n \times m$ that is in exclusively $M_1$ or $M_2$.

It is clear to me that since they are not equivalent, there is some string that is in exclusively $M_1$ or $M_2$. But how can we show that there is some string that does not exceed the required length?

Construct the product automaton $M = M_1 \times M_2$, which contains $nm$ states. Since $L(M_1) \neq L(M_2)$, the automaton $M$ contains a state $(q_1,q_2)$ reachable from its initial state such that $q_1$ is an accepting state of $M_1$ and $q_2$ is not an accepting state of $M_2$, or vice versa. Since $M$ contains $nm$ states, this state is reachable from the initial state of $M$ by a path of length at most $nm-1$. This corresponds to a word of length $nm-1$ which is in $L(M_1)$ but not in $L(M_2)$, or vice versa.

Using the method of this answer, we can improve the bound to $n+m-2$. This is tight for $m=1$, as the example of $L(M_1) = \sum_{k=0}^{n-2} \Sigma^k$ and $L(M_2) = \Sigma^*$ shows.


What is the time complexity of this "reverse words" algorithm? I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']. I found an algorithm that I think I am happy with, but unfortunately, I do not know how to compute its running-time.

The algorithm essentially has two stages. First, I reverse the entire string. Then, I scan that string to find words, and when I find a word, I reverse only that word. In terms of message, the first time we reverse we will do (n/2) steps. Then, for each word we find, we'll do (m / 2) steps, where m is the length of the word (m is not constant). How do I express the Big O notation for this?

function reverseWords(message) {
  // reverse entire string
  reverseStrArr(message, 0, message.length - 1);

  let wordStart = 0;
  let wordEnd = null;

  for (let i = 0; i < message.length; i++) {
    const char = message[i];

    if (char === " ") {
      wordEnd = i - 1;

      reverseStrArr(message, wordStart, wordEnd);

      // reset
      wordStart = wordEnd + 2;
      wordEnd = null;
    }

    if (i === message.length - 1) {
      reverseStrArr(message, wordStart, i);
    }
  }
}

function reverseStrArr(stArr, minIdx, maxIdx) {
  const midIdx = Math.floor((minIdx + maxIdx) / 2);

  for (let i = minIdx; i <= midIdx; i++) {
    const tailIdx = maxIdx - (i - minIdx);

    const temp = stArr[tailIdx];
    stArr[tailIdx] = stArr[i];
    stArr[i] = temp;
  }
}
```

This algorithm runs in linear time in the size of the input $O(n)$.

To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.


Are the words "expression" and "term" interchangeable in programming language theory? When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of programming languages?

The two words expression and term have largely the same sets of possible meaning, but in a specific presentation, they may not be synonyms.

In rewriting theory, a term is something that conforms to a certain syntax, and for which a notion of computation (rewriting) is defined. In programming language theory, term can mean specifically one of the two aspects. And so can expression. Which means which depends on the author, and not all authors use both words in this way.

One possible meaning of the word is “something that can be computed”. In this sense, if the computation terminates, you end up with a value.
Another possible meaning of the word is “something that conforms to a certain syntax”. There is often a computation mechanism defined over this syntax, but not always.

In the theory of a programming language, there are often multiple syntactic objects: the core language, types, kinds, objects, classes, modules, interfaces, … Something like function x : int => x + 1 may be a core term which contains the type term int, or a core expression which contains the type expression int. It's common but not universal to use one of the two nouns to mean “core” (and “core” is my choice of terminology), e.g. “function x : int => x + 1 is an expression” or “function x : int => x + 1 is a term”. Different authors use different words; communities of a specific language tend to align on terminology, but that isn't systematic.

For example, in the world of ML, “expression” with no qualifier is normally reserved for the core language, and there are additionally “module expressions” in the module language, as well as “type expressions” and “signature expressions”. A “term” can be anything conforming to one of the syntactic forms, although many authors (e.g. the SML definition) don't use “term” at all.

But in Coq, a “term” is the most important syntactic form. Due to the nature of the language, the syntax of types is the same as terms. The Coq manual uses “expression” to designate any family of syntactic form.

If you're reading a text on programming languages, the meaning of the words should be explained or (in less formal texts) clear from context. If you're writing a text, try to use the terminology that's common in your community, and always make sure that the definitions you use are clear.


What is difference between nondeterministic polynomial time and exponential time? I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank you

Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.


Type-0 grammar and terminal symbols The question is pretty short, but I've been thinking about it quite some time:
Are terminal symbols that are not in the defined alphabet still valid?

No. The grammar is defined like this:

G = (V,SIGMA, R, S) where V is your set of variables (non-terminals) and SIGMA is your alphabet (terminals). All the symbols you are allowed to use in the substitution of a rule are the union of V and SIGMA. If you simply cannot use a symbol out of that set, since it does not exists in the context of your grammar.


Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$
How to prove that $L$ is irregular by using Myhill–Nerode theorem?

At other languages with $\Sigma >1$ we can usually separate the word or something like this with combination and this how we can show that two words are not at the same equivalent class....
But what we can do at this case?

Here what I tried:
Assuming that $i\ne j$, then $0^{2^i+1}$ is not at the same equivalent  class with $0^{2^j+1}$, why?
Let mark: $p$ - the amount of $0$'s that we need to add to $0^{2^i+1}$ to be $0^{2^{i+1}}$, $q$ - same thing but with $j$ instead of $i$.
Of course $p\ne q$, hence:
$0^p\in 0^{2^i+1}$ but $0^p\notin 0^{2^j+1}$.

I'd like to know if I'm right at my and I should continue or try a different way...

Thank you!

Your idea is basically correct, but your argument could be written in a clearer way. You want to say that if $i \neq j$ then $0^{2^i+1},0^{2^j+1}$ are inequivalent. You propose to consider adding the word $0^{2^i-1}$ to both, obtaining $0^{2^{i+1}},0^{2^i+2^j}$. The first word is clearly in $L$, whereas the second isn't, though an argument is required (left to you). This shows that the infinite set $\{0^{2^i+1} : i \geq 0\}$ consists of pairwise inequivalent words (modulo $L$), so $L$ is not regular.

In fact, all words $0^n$ are pairwise inequivalent modulo $L$ – see if you can prove that. (The argument is very similar.)

For languages over a unary alphabet there is a simpler characterization. Let $L = \{0^n : n \in I\}$. Then $L$ is regular if and only if $I$ is eventually periodic, which means that for some $m \geq 1$, $n + m \in I$ iff $n + 2m \in I$. The set of powers of two is not eventually periodic since it has arbitrarily large "gaps". (A formal argument is similar to your proof.)


Party optimization: maximum weight independent set in a tree/graph From Cornell

  Suppose we want to throw a party for a company whose organization
  chart is a binary tree. Each employee has an associated fun value, and
  we want the set of invited employees to have the maximum total fun,
  which is the sum of the fun values of the invited employees. However,
  no one has fun if some employee and that employee's direct superior
  are both invited, so we never invite two employees who are directly
  connected in the organization chart. (The less whimsical name for this
  problem is the maximum weight independent set in a tree.)

I was trying to think of an analogous statement if the problem were a graph rather than a tree. Might we say that now we want to throw the largest possible party with ex-girlfriends/ex-boyfriends such that no one's ex-partner is invited?

In this case an edge between two members denotes a ex-relationship. We want to find the largest set such that no two members share an edge.

Is this a correct interpretation of the graph problem and is there a known polynomial time algorithm?

You can interpret a graph problem in whatever way you wish. Note that your interpretation makes sense only for bipartite graphs.

Maximum independent set, even with all weights the same, is (almost) NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any fixed $\epsilon > 0$ (here $n$ is the number of vertices); the actual hardness assumption is NP$\not\subseteq$BPP rather than P$\neq$NP (see for example Anupam Gupta's lecture notes). Under the exponential time hypothesis, any $r$-approximation algorithm must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ for any $\epsilon > 0$ (see Chalermsook, Laekhanukit and Nanongkai).


Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)? I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane.

the polygons are either convex or star-shaped with a non-singular kernel
if multiple polygons, they touch each other (have at least a side in common with another polygon of the set)
the point moves accoring to a phisical process, so it will not "jump" in the plane, but its movement in the plane will be continuous
another system will keep the point within the area defined by the union of said polygons, but this might occasionally fail
I need to know which polygon is bounding the point
Polygons are given in advance and output of a pre-process that can be expanded

I know these solutions, in particular the "draw a line starting from your point and count the intersections" and the "sum the angles for each subsequent pair of vertices and check if it is 2$\pi$", but:

both solutions require a lot of computation if one has complex polygons and several polygons
those solutions are for the general case, where there is no dynamics involved, but a static point in a static polygon.

Is there a computationally optimal solution for the scenario I am considering? I think that leveraging the solution of the previous timestep should help in skipping/avoiding some computations in the next cycle, meaning that a "full" solution needs to be computed only at initialization.
Or am I stuck with running a full check at each cycle?

I can list three candidate approaches.  I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation.
Approach #1: sweepline algorithm
This can be solved with a straightforward application of a sweepline algorithm.
Sweep a vertical line from left to right, with increasing $x$-values.  At any value of $x$, you'll have a binary search tree that, given $y$, lets you look up which polygon the point $(x,y)$ is contained in.  There are two key ideas in sweepline algorithms: you only need one tree for each interval of $x$-values between two adjacent "events" (here each event is an intersection of two line segments from the exteriors of the polygons), so you only need only $O(n)$ binary search trees; and, each binary search tree differs from the previous one by a single insertion or deletion, so you don't need to store all of them separately, but you can store them jointly using a persistent data structure.
Now this makes it easy to solve your problem.  At any moment in time, we know the $(x,y)$ position of the point and can look up which polygon it is contained in and a trapezoid inside that polygon it is contained in.  As the point moves, once it leaves that trapezoid, we can query the data structure again.  Each lookup into the data structure takes $O(\log n)$ time, so will be efficient.
Approach #2: Graph of polygons
As a precomputation, build an undirected graph of polygons, where each polygon is a vertex, and two polygons are joined by an edge if they are adjacent (overlap in a point or line segment).  Store this graph in an adjacency list representation.  Also, find the polygon that contains the initial position of the point by any algorithm (e.g., linear scan over all polygons).
Note that you can answer point-in-polygon queries (given a point and a polygon, is the point inside that polygon?) in time linear in the number of vertices of the polygon.
Now, the algorithm is simple.  Watch the movement of the current point, and as soon as it leaves the current polygon, check which polygon it has moved into by doing a point-in-polygon query on each adjacent polygon.  Thus, when it leaves the current polygon, the work is proportional to the number of neighboring polygons, not to the total number of polygons.
There are various optimizations and improvements available:

Optimization 1: We can speed up the process of finding when the point leaves the polygon it is currently inside.  If we are guaranteed that once the point leaves a polygon, it will never come back to it, then we can use binary search over time to find the first instant when it has left the polygon.  Each iteration of binary search requires one point-in-polygon query and we do logarithmically many iterations.  If we don't have that guarantee, but we have an upper bound on the speed and/or acceleration and/or turning radius for the movement of the point, we can compute a lower bound on the time to leave the current polygon and return to it (based on the current position of the point and the polygon it is contained within), and use a modified binary search where we avoid jumping further into the future in any one step than given by that bound.

Optimization 2: We can sort each adjacency list.  Consider the adjacency list for polygon $P$.  Suppose the perimeter of $P$ has length $\ell$.  If you walk along the perimeter of $P$ starting at some point on the perimeter and returning to it, this maps each point on the perimeter to a number in the range $[0,\ell)$, which gives a total order on points on the perimeter.  This yields a total order on the polygons adjacent to $P$: map each neighboring polygon to the points of intersection on the perimeter of $P$, map those to numbers/intervals in $[0,\ell)$, then sort by that.  (We can resolve ties as follows: if two neighboring polygons both overlap with $P$ at the same point $p$, where $p$ is on some face of $P$, then imagine extending outward by a tiny bit $\epsilon$ from that face and look at the intersection with those two polygons.)  So, sort each adjacency list in this way, as part of the precomputation/setup phase.
This now speeds up the process of determining which new polygon the point has entered, when it leaves the current one: instead of using a number of point-in-polygon tests that is linear in the number of neighboring polygons, it goes by the log of the number of neighboring polygons.

Optimization 3: Compute the bounding box for each polygon.  Now, before doing a point-in-polygon test, you can first check whether the point is in the bounding box, which will enable quickly rejecting some polygons.
You could also use this to speed up finding the polygon the initial position is within. Store all bounding boxes in some appropriate data structure (e.g., a quadtree).  Now, given a point, use that data structure to enumerate all bounding boxes it is contained in, then test each with a point-in-polygon test.

Approach #3: Graph of triangles
During a precomputation, triangulate each polygon, i.e., decompose it into a union of triangles.  Now combine all these triangles, build a graph of triangles, and proceed as in approach #2, but using triangles instead of objects.
This replaces each point-in-polygon test with a point-in-triangle test, which is much faster; but because the point will traverse many more triangles than polygons, the number of iterations might be much larger.  I'm not sure which approach will be faster in the end.
Also, the type of triangulation used might affect performance.  I'm not sure whether it is better to choose a triangulation that minimizes the variance of the degrees in the graph or one that maximizes the variance (e.g., a fan decomposition).


Is it a good idea to determine coordinates of object on images with regression algorithms? I am doing doing one of getting started competitions on kaggle, the one which requires you to find coordinates of different objects on images.

I know that the usual method for this is to use sliding window and predict whether some piece of image is that object. But I wonder, what if I just use values of all pixels as features and try to teach a regression algorithm how to predict the coordinates of the object on that image? What kind of regression algorithm would be best?

It is possible to train a neural network to solve a regression problem.
See facial keypoints challenge
You should note that training a network for regression is harder then training towards a classification problem.
The network is more prone to unnormalised, different deviation values per feature, weight initialisation etc.
Try following the tutorial and then you'll have a better grasp on using ConvNets for regression.

Good luck!


Learning Quadratic Functions I have seen in some ML tutorial that functions of the form $f(\vec x) = \vec x^T A \vec x$ ($\vec x \in \mathbb{R}^n$ and $A$ is an $n\times n$ real matrix) can be PAC learned.

Can anyone point me to a reference to this fact?

One approach is to use linear regression.

The matrix $A$ has $n^2$ entries; treat each of those entries as an unknown, so you have $n^2$ unknowns.  Now when $x$ is known, $f(x)$ is a linear function of those unknowns.  If you have a set of equations $f(x_i)=y_i$ that are all known to be exactly correct, then you can solve for the unknowns by using linear algebra.  If they are known to be approximately correct (e.g., $||f(x_i)-y_i||_2$ is small), you can use least squares to find the solution for the unknowns that minimizes the sum of the squared errors (that minimizes $\sum_i ||f(x_i)-y_i||_2$).  If a $1-\epsilon$ fraction of them are approximately correct, where $\epsilon \ll 1/n$, then you can pick a random subset of $n$ of them, guess that all of the ones in the subset are correct, use least squares to solve for the unknowns, and check whether that solution seems valid given the remaining equations, and repeat until you find a good solution.


Decide if a language has a word of a given size Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:

$$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ such that } |w'| \leq |w| \}$$

I.e., $w \in L'$ if $L$ has some word with length smaller than $|w|$.

The way I was thinking to show that is observing that $L \cap\Sigma^{|w|}$ is finite, and $(L \cap \Sigma) \cup (L \cap \Sigma^2) \cup \ldots\cup (L\cap \Sigma^{|w|})$ is finite too, hence decidable. But the main thing I am struggling with is how can any algorithm for $L'$ know if some $u \in L$? this is undecidable, so it's unclear to me how any algorithm for $L'$ can verify that indeed some word is in $L$

There are two cases:

$L$ is empty. In this case, $L' = \emptyset$ is trivially decidable.
$L$ is non-empty. Let $m$ be the minimum length of a word in $L$. Then $L'$ consists of all words of length at least $m$, and is again trivially decidable (in constant time!).

As you can see, you never actually need an algorithm for $L$.

Similarly, the following language is always decidable:

$$L'' = \{w \in \Sigma^* \mid \text{ there exists a word $w' \in L$ such that $|w'| \geq |w|$}\}.$$

There are now three cases:

$L$ is empty. In this case, $L'' = \emptyset$ is trivially decidable.
$L$ is infinite. In this case, $L'' = \Sigma^*$ is again triviall decidable.
$L$ is finite. Let $M$ be the maximum length of a word in $L$. Then $L''$ consists of all words of length at most $M$, and is again trivially decidable (in constant time).

These are examples of non-constructive proofs, which you might not like. Instead of starting a discussion here, I refer you to this question.


Would limiting the number of operations in a transaction prevent SQL injection? In my understanding all SQL injections need to add another operation to the one intended by the programmer.

For example, a badly written query:

query="Select * from Table where name="+name;

User inputs name as: foo; Delete from Table; and this would be an SQL Injection.
But if the programmer would be able to limit the number of operations in a transaction to 1 (the Select in this case) or how much operations he intends to use the SQL Injection would be impossible. Is there a way we can limit the number of operations in most programming languages? Would this be enough to stop SQL Injection?

It could help avoiding some attacks. However, allowing the adversary to inject a part of the SQL WHERE clause is already quite dangerous.

E.g. injection can change this

SELECT * WHERE name="username"

into

SELECT * WHERE name="Bah!" or true or "too easy!"="x"

The sane thing would be to avoid injection completely. Ideally, in a typed language, the type of a SQL query should NOT be a string, so to prevent concatenation with user data. It should be a query template, to be filled with a special function. Something like

query = new Query(...);
fill(query, { "username": username })

Type systems excel for imposing these constraints of the programs. On the other hand, their use require some thoughtful library design. Sometimes it feels simpler to provide a more low-level solution (like using strings for everything), which is also simpler to use, and possibly document the potential security issues "programmers: don't do this", which can then be ignored by busy programmers, which would often take the shortest path to their goals. Types here would simply block the quick path, forcing the programmers to separate the "query template" part from the "user data" part.

Some languages still use strings for templates, but at least encourage programmers to avoid concatenation, and favor some fill-like function.

fill("SELECT * WHERE name=@username", { "username": username })

The above is doable even in an untyped language.

Moral: let the library perform all the string-escaping for you. The library always checks for special characters, and handles them correctly. You likely won't cover all the tricky cases.

Don't try to patch against an attack by imposing restrictions on just that attack. Consider all the variants for that attack which can pass the restriction. If injection is the problem, prevent injection at the root.


Is there no sorting algorithm with all specific desired properties? On the Sorting Algorithms website, the following claim is made:

  The ideal sorting algorithm would have the following properties:

  Stable: Equal keys aren't reordered.
  Operates in place, requiring $O(1)$ extra space.
  Worst-case $O(n\cdot\lg(n))$ key comparisons.
  Worst-case $O(n)$ swaps.
  Adaptive: Speeds up to $O(n)$ when data is nearly sorted or when there are few unique keys.

  There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

My question is, is it true that

  there is no [sorting] algorithm that has all of these properties

and if so, why? What is it about these properties that makes all of them simultaneously impossible to fulfill?

WikiSort and GrailSort are two fairly recent algorithms that do in place, stable, worst case $O(n\ lg(n))$ key comparisons.  Unfortunately I don't understand them well enough to know if they approach $O(n)$ swaps or are adaptive so I don't know whether they violate the fourth and fifth conditions you have.

From looking at the paper "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner linked to by the WikiSort GitHub page, Kim and Kutzner claim to have a 'merge' operation that is $O( m (\frac{n}{m} + 1))$ (WikiSort is a variant of Mergesort) but I'm not sure if that translates to WikiSort having $O(n)$ swaps.  GrailSort is claimed to be faster (in the WikiSort GitHub page) so I could imagine that it's likely they both have worst case $O(n)$ swaps and are adaptive.

If anyone does manage to understand WikiSort and/or GrailSort I would appreciate them also answering my open question about it


How to find the distance between two nodes in an undirected graph, from a neighborhood matrix? Given a distance-1 neighborhood matrix representing an undirected graph, I'm trying to calculate the distances between two nodes so I can work out the distance-2 matrix, then the distance-3 matrix, and so on...

How to find this distance?

Any help would be appreciated.

I assume that by distance-$2$ matrix you mean the matrix $A$ such that $A_{ij}=1$ if there is a path of length exactly $2$ between node $i$ and node $j$.

Let us call $B$ the distance-$1$ matrix, then remember that $B^2$ is such that $(B^2)_{ij}$ is the number of paths of legth $2$ between $i$ and $j$. So all you have to do is to check whether an entry of $B^2$ is $0$ or not.


How to check if a language is not regular? I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "Pumping Lemma" that it is not regular

it is regular if, it can be represented by a finite state automata (FSA)

or, if it can be represented by a regular expression
L = { a^2 b^n c^m , where n,m >= 0 }  Alphabet is {a,b,c}

My thoughts:
At first glance, i thought this language is regular because it can be represented by a regular expression. The regular expression that i would propose would be a^2 b^* c^*, is this correct?

Yes your answer is correct.
Language L generates strings that begin with 2as followed by any number of bs then followed by any number of cs
Your regular expression represents L correctly
It is also worth reminding how the pumping lemma works , if a string in a language L cannot be pumped , then L is non-regular , however some languages can still fool the pumping lemma
Consider the language F = {a^i b^j c^k| i,j,k ≥ 0 and if i = 1 then j = k}. Which appears as a regular language in pumping lemma but is actually non-regular
This is why there are other methods to prove that a language is non-regular
For example to prove F is non-regular you should remember that regular languages are closed under complement (if F is regular then F' is regular too ) , then by the pumping lemma you can show that F' is non-regular and thus F is non-regular , sometimes closure under intersection is useful too
Finally you should try to get an intuition on the language , clearly L needs only finite memory to check the number of as , there can be any number of bs and cs and the FA does not need to remember the number of bs and cs , an intuition is a good first step .


Improve Java Experience In exactly a month I will face a Java exam. My problem is that even if I know all Java theory (the exam won't face GUI), I have problems creating programs: sometimes I can't understand how to make a fast program or how to implement what I want my program to do. So how can I improve my Java habilities? What kind of exercises should I work on? Should I follow some guides or tutorials? Should I re-study all the theory till I understand better?

P.S. If this isn't the right Stack to post this on I will just close the question and look better for the right one

I'm going to go ahead an assume that it's a Java 101 type of exam.

The best way to go about studying for it, in my opinion, is to practice applying the basics. Things such as Data Types, Conditional Statements, using Arrays, etc. A good place that has stuff like this is CodingBat as it gives you answers too. You could even just have a read through a beginner's Java book (a quick google search will bring up loads which you can find a PDF easily).

Then if you want to work on general problems that encompass everything you could do the problems at places like HackerRank (Which is also good practice for coding interviews as many companies use this) or the easy problems at reddit.com/r/dailyprogrammer. There are tonnes of other resources out there but if you would like some more just comment on this.

Good luck in your exam and I hope this helps you a little bit.


Why this Nondeterministic Finite accept this string? I am reading in my book that this NFA machine accept the string 10100. If we follow the execution, we will find our self in branch with the state final q0.

The only answer for me is that when we are in state q0 after 1010 and 0 is coming we can't move any more so this branch will die even it is in the final state. Am I right?

When a transition doesn't exist for current (state, input) pair, the NFA halts and the computation path rejects the input string. Or if an empty string transition is defined, it can be used to go into a garbage state for undefined transitions and the computation path rejects the string. See What does an NFA do if there's no transition with the correct symbol? for really good information.

In addition, this source that says the string is not accepted: http://people.cs.nctu.edu.tw/~wgtzeng/courses/FL2013SpringUnder/2.%20Finite%20automata.pdf slide 15.


Prove the red blue separation problem is NP-complete Consider the following problem: given a set of $m$ red points and $n$ blue points in the plane, find a minimum length cycle that separates the red points from the blue points. That is, the red points are inside the cycle and the blue points are outside the cycle, or vice versa. This problem is called the red blue separation problem.

I am trying to reduce the Traveling Salesman Problem (TSP) to this but I am getting nowhere. Can you please help me with this? Any help is appreciated.

A separating polygon separating a set of points $S$ from a set of points $T$ is a simple polygonal circuit $P$ for which every point of $S$ is interior or on the boundary of $P$, and every points of $T$ is exterior or on the boundary of $P$. Let $D(P)$ denote the perimeter of a polygon $P$, that is, the sum of the Euclidean lengths of the edges of $P$. If $P$ is a separating polygon for $S$ and $T$ with minimum value of $D(P)$, then $P$ is called a minimum separating polygon.
The problem you describe is known as the minimum separating polygon problem (MSP), formally:

Instance: Two finite point sets $S$ and $T$, and an integer $k$.
Question: Is there a separating polygon $P$ for the sets $S$ and $T$ such that $D(P) \leq k$?

MSP is NP-hard. The hardness was first shown by Eades and Rappaport by a reduction from TSP, see [1], Section 2 for the reduction.

[1] Eades, Peter, and David Rappaport. "The complexity of computing minimum separating polygons." Pattern Recognition Letters 14.9 (1993): 715-718.


Maximum chromatic number of sparse graphs It is well-known that the chromatic number of a graph can be as high as $n$.

But what is the maximum chromatic number of a graph with $m = O(n)$?

A graph with $O(n)$ edges has chromatic number $O(\sqrt{n})$, and this is tight.

Suppose first that a graph has $m = O(n)$ edges and chromatic number $\chi$. Take a $\chi$-coloring of the graph. Any two color classes must be connected by an edge, since otherwise we can identify them. Therefore $m \geq \binom{\chi}{2} = \Omega(\chi^2)$, and so $\chi = O(\sqrt{n})$.

To show that this is tight, consider the union of a clique on $\sqrt{n}$ vertices and an independent set on $n-\sqrt{n}$ vertices. This is a graph with $n$ vertices and $\binom{\sqrt{n}}{2} = O(n)$ edges, and chromatic number $\sqrt{n}$.


Complexity of deciding the satisfiability of a quasi-monotone CNF formula A quasi-monotone CNF formula is a formula where each variable appears at most once as a positive literal (and any number of times as a negative literal).

What is the complexity of deciding its satisfiability?

Obviously this can be solved with the same complexity as boolean SAT. The question is, can we do better. The answer is no: this problem is NP-complete.

You can show it is NP-complete by reducing a regular CNF formula to "quasi-monotone" CNF, as follows:

Since you cannot use positive terms in general, what you want is a new, equivalent, variable in-place of the positive terms. So let $\Phi = {\LARGE\bigwedge}C_i$ be a general boolean sat formula. We will replace all non-negated $x_j$ terms with new variables called $\neg n_{x_j}$. Then, we need to constrain $n_{x_j} = \neg x_j$; so we introduce the following clauses:

$$\left(n_{x_j} \implies \neg x_j\right) \wedge \left(\neg x_j \implies n_{x_j}\right)$$

This essentially means that $n_{x_j} = \neg x_j$. Written in CNF:

$$\left(\neg n_{x_j} \vee \neg x_j\right) \wedge \left(x_j \vee n_{x_j}\right)$$

These two clauses will effectively allow you to replace all your other non-negated terms, and they only leave behind a single non-negated term for each literal (within these clauses), which is allowed in "quasi-monotone" CNF as defined by the question.


Data flow equations to determine value dependencies I need to define the data-flow analysis equations to determine the value dependencies of an statement.

For example:

a = 9
b = a + 7
c = b * 2

the value of c depends on the value of a.

I'm sure this is a well known problem in data flow analysis, can any one point to the equations solving this? Static Single Assignment (SSA) form can be used.

Well, it seems that this can be reduced to the Reaching Definition problem, who's equations are:

$REACH_{in}(S) = \bigcup_{p \in pred(S)} REACH_{out}(p)$

$REACH_{out}(S) = GEN(S) \cup (REACH_{in}(S) - KILL(S))$

$GEN[d: y \rightarrow f(x_1, .., x_n)] = {d}$

$KILL[d: y \rightarrow f(x_1, .., x_n)] =DEFS(y) - {d}$


Number of cycles in a graph? Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?

I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.

Assuming you mean simple cycles (otherwise the number is infinite) - yes, of course the number can be exponential: consider the complete graph on $n$ vertices, then every sequence of distinct vertices can be completed to a simple cycle. So you get at least $n!$ cycles.

Even if you ignore cyclic permutations of a cycle, this is still exponential: you can take only cycles of length $n/2$, and you have more than ${n\choose n/2}$ such cycles.


Definition of RP/poly is not clear! In Motwani and Raghavan's textbook, p38-39, they states:

A sequence $C_1, C_2, C_3, \dots$ of circuits is a circuit family for function $f_n\colon {0,1}^n \rightarrow \{0,1\}$ if $C_n$ has $n$ inputs and computes $f_n(x_1, x_2, \dots, x_n)$ at its output for all n-bit inputs $(x_1, x_2, \dots, x_n)$. The family $C$ is said to be polynomial-sized circuits if the size of $C_n$ is bounded above by $p(n)$ for every $n$, where $p(\cdot)$ is polynomial.

It is clear that this is the definition of P/poly. And the next paragraph is the definition of RP/poly.

A randomized circuit family for $f$ is a circuit family for $f$ that, in addition to the $n$ inputs $x_1, x_2, \dots, x_n$, takes $m$ random bits $r_1, r_2, \dots, r_m$, each of which is equiprobably 0 or 1. In addition, for every $n$, the circuit $C_n$ must satisfy two properties:

If $f_n(x_1, x_2, ..., x_n)=0$, then the output of the circuit is 0 regardless of the values of random inputs $r_1, r_2, \dots, r_m$.
If $f_n(x_1, x_2, ..., x_n)=1$, the the output of the circuit is 1 with probability at least $\frac12$. In other words, at least one half of the $2^m$ choices of the bits $r_1, \dots, r_m$ will result in the circuit evaluating to 1. We will refer to such $m$-tuples $r_1, r_2, \dots, r_m$ as witnesses for $(x_1, x_2, \dots, x_n)$, in that they testify to the correct value of $f_n(x_1, x_2, \dots, x_n)$ when it is 1.

Question: I don't understand what is relationship between $n$ and $m$ or $r_1, \dots, r_m$ and $f_n(x_1, x_2, \dots, x_n)$? For example, we have n inputs, i.e. $x_1, x_2, \dots, x_n$. But, in second property, they states that at least one half of the $2^m$ choices of the bits $r_1, \dots, r_m$ will result in the circuit evaluating to 1. Now, how did we bring $r_1, \dots, r_m$ to $f_n(x_1, x_2, \dots, x_n)$?

The circuit $C_n$ has $n+m$ inputs, $x_1,\ldots,x_n,r_1,\ldots,r_m$. Its size is polynomial in $n$, so without loss of generality, $m$ is polynomial in $n$. What we want is:

If $f_n(x) = 0$ then $\Pr_r[C_n(x,r) = 0] = 1$.
If $f_n(x) = 1$ then $\Pr_r[C_n(x,r) = 1] \ge 1/2$.

Here $x$ is shortcut for $x_1,\ldots,x_n$, and $r$ is shortcut for $r_1,\ldots,r_m$.


How to understand the storing mechanism used in external merge sort I was reading about external merge sort from the wikipedia article link, according to it:

  External sorting is required when the data being sorted do not fit
  into the main memory of a computing device (usually RAM) and instead
  they must reside in the slower external memory (usually a hard drive).
  External sorting typically uses a hybrid sort-merge strategy. In the
  sorting phase, chunks of data small enough to fit in main memory are
  read, sorted, and written out to a temporary file. In the merge phase,
  the sorted subfiles are combined into a single larger file.

Suppose we have a RAM which can only hold 2 chunks of data and we have 6 chunks of data to sort. Please see the below diagram:

Since our memory can hold 2 chunks of data so the first step 1 sounds plausible since we are sorting only pairs of numbers (5,6), (3,4) (1,2). In the step 2 we merge the data and now our chunk size is 4. My question is how do you now load this 4 chunk of data into memory now? Since your memory cannot accept more than 2 chunks of data then how do you load and sort them? How did you sort while merging chunks of data here? I have visited several links, but not able to understand this concept.

You must be performing some kind of sorting while merging the data as well right?

How do you load that entire list into memory?  You don't.  You have a bit of a misunderstanding about how Merge works, in this setting.

It's tempting to think that Merge should work as follows: load both input lists into memory, in their entirety; merge them; then write the result back out to storage.  But that wouldn't work -- we won't have enough memory to load the entire lists into memory.

Instead, Merge works without loading either input list into memory all at once.  Take a look at the pseudocode for Merge, and you'll see that it only needs to have two list items in memory at a time: one list node from somewhere in the first list, and one from somewhere in the second node.  Merge finds which one of those two items is smaller, outputs it, and then loads the next item from the input list it came from.  You can see that Merge only needs $O(1)$ memory to merge two sorted lists, even if the sorted lists are stored in external storage -- it never needs to load the input lists into memory in their entirety.


A home assignment. C language Help would be much appreciated.

"Receive a number and reorder it from the largest to the smallest.
Input: 13252
Output: 53221
Cant use arrays...
Only while, for, if/else  ...

any idea? i'm clueless.
Thanks for the help.

Oh my word! Coding that did take a while. The logic however, is quite simple. Recall the number system.

First, determine the length of the number entered by the user. You can do so by dividing the number repeatedly by 10 until the quotient becomes zero.
Then, the maximum value of a digit in decimal number system is 9. So compare each digit in the number with 9. The modulo division operation comes handy in here. See if there's a match. If there's no match go to the next smaller digit, 8 and continue this until you get to zero.
Multiply the first match found using this procedure with 10^(length-1) i.e. you are making it your most significant digit (number systems)
Reduce the length length--
Continue this procedure until length becomes zero
A little tip for efficiency, note down the matched digit each time and make that the slab for comparing the remaining digits in the number i.e. if you found out 5 is the first match, and thus the greatest digit found in your number, there's no point starting your comparisons from 9 again for the next digit. Start at 5. Don't be overly smart and start at 4 though. Remember there can be multiple 5's in a number.

I wrote a working piece of code for this. So this algorithm works. Hope that helps. Ways to improvise the performance are appreciated. However, don't suggest the usage of arrays or strings as they are forbidden in the question.


Lower bounds: queues that return their min elements in $O(1)$ time First, consider this simple problem --- design a data structure of comparable elements that behaves just like a stack (in particular, push(), pop() and top() take constant time), but can also return its min value in $O(1)$ time, without removing it from the stack. This is easy by maintaining a second stack of min values.

Now, consider the same problem, where the stack is replaced by a queue. This seems impossible because one would need to keep track of $\Theta(n^2)$ values (min values between elements $i$ and $j$ in the queue). True or false ?

Update: $O(1)$ amortized time is quite straightforward as explained in one of the answers (using two min-stacks). A colleague pointed out to me that one can de-amortize such data structures by performing maintenance operations proactively. This is a little tricky, but seems to work.

Yes, it can be done in amortized O(1) time (enqueue, dequeue, minimum). Have a look at the code and explanation given here.

Here are the most relevant parts quoted from the above link (emphasis mine; and of course, all credits for the solution go to the original author, Keith Schwarz):

  A FIFO queue class that supports amortized O(1) enqueue, dequeue, and
  find- min.  Here, the find-min returns (but does not remove) the
  minimum value in the queue.  This is not the same as a priority queue,
  which always removes the smallest element on each dequeue.  The
  min-queue simply allows for constant-time access to that element.

  The construction that enables the min-queue to work is based on a
  classic construction for creating a queue out of two stacks.
  ... we apply this construction to two min-stacks instead of
  two regular stacks. The minimum element of the queue can then be found
  by looking at the minimum element of the two stacks taken together.


Define a DFA that accepts all even length binary strings that don't contain the substring "111"? I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly appreciated!

Keep in mind that DFA has a "finite" memory, each state knows something about what you've read so far.
$A$ remembers that so far, you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$.
$B$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$.
and so on...

Now you can duplicate the states to have the following properties:
$A_{even}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$ or $\epsilon$, and you've read even number of letters.
$A_{odd}$ means that so far you've read $w0$ for some $w \in \{0,1\}^*$, and you've read odd number of letters ($\epsilon$ has even number of letters, so it's not included here).
$B_{even}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$, and you've read even number of letters.
$B_{odd}$ remembers that so far, you've read $w01$ for some $w \in \{0,1\}^*$ or $1$, and you've read odd number of letters.

And so on.
You need to re-define your transition function and and accept states to match with the definition of these new states

Edit: I misread the question as accepting '111' as a substring, so the definition of A,B that i showed are a bit off, but the answer to your question is similar in concept.


Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36 I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%.

But its not clear how we arrived at that number.

Can someone explain it?

Unlike in the regular ALOHA protocol, where other nodes can send messages that interfere with ours at any time, in the Slotted ALOHA protocol, the only other time a message can be sent to interfere with ours is if it's sent at the exact time ours is sent (since in Slotted ALOHA messages can only be sent at specific intervals, like every 5 seconds for example)

Therefore, the probability that our message will be the only one, and have no interference is the probability (in a Poisson Process) that only 1 message on the system (ours!) is sent on the mark

$$P[(N(t + 1) - N(t)) = 1]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}}  = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

This gives us a function of the throughputs for all $\lambda$s.

To find the $\lambda$ with the highest throughput (that is, what expected rate gives us the highest throughput) we take the derivative and set to zero:

$$e^{-\lambda} - \lambda e^{-\lambda} = e^{-\lambda} (1 - \lambda) = 0  $$

$$\therefore \lambda = 1$$

In other words, when $\lambda$ is $1$, our throughput is highest. How high exactly? Just plug it back into the function we came up with, $\lambda e^{ - \lambda}$ and get:

$$ 1 * e^-1 = \frac{1}{e} = 0.36787....$$

Here's nice graph comparing the two ALOHAs, made by Reuven Cohen.


Why is Adleman's molecular algorithm for Hamiltonian Path linear? In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability.

He claims that "The number of different oligonucleotides required should grow linearly with the number of edges", and this makes sense given the molecular encoding of the edges described in the paper, but he also claims that "the number of procedures required should grow linearly with the number of vertices in the graph".
Why is this last claim true? In other words, why isn't the assembly of edge molecules counted towards this calculation? If it were, the complexity of lab procedures would be $O(|V|^2)$, as the number of edges in a graph is bound by this function.

Thank you.

You are right that in the coding of the graph one needs a possibly quadratic number of strands to represent the edges.

My guess is that Adleman likes to distinguish the two kinds of operations. First there is the coding of the input graph, which may be very complicated to avoid accidental combinations. Then there is the number of laboratory steps to actually check the presence of Hamiltonian paths.

I think this might be explained by the way he envisions how molecular computing can be used. Given a big "database" of available strands one performs a number of laboratory steps to find the solution to a  problem. This is then the same operation performed in parallel to zillions of molecules. This I read from the way how he explains the number of operations performed per second.


What's wrong with my beta reduction of pred c_0 on Church numerals? I'm trying to calculate $\text{pred}\, c_0$, where $\text{pred}$ is the previous church encoded number and $c_0$ is the number $0$ ($\lambda s. \lambda z. z$).

The formula for $\text{pred}$ is $\lambda n. \lambda s. \lambda z. n (\lambda g. \lambda h. h (g s))(\lambda u.z)(\lambda v.v)$

My $\beta$ reduction looks like this so far (I've underlined the function and the applied parameter)

$$
\text{pred}\, c_0 \to \lambda s. \lambda z. c_0 \underline{(\lambda g. \lambda h. h (g s))}\text{ }\underline{(\lambda u.z)}(\lambda v.v) \to $$

$$\lambda s. \lambda z. c_0 (\lambda h. h (\underline{(\lambda u.z)}\text{ } \underline{s}))(\lambda v.v) \to$$

$$\lambda s. \lambda z. c_0 \underline{(\lambda h. h z)}\text{ }\underline{(\lambda v.v)} \to$$

$$\lambda s. \lambda z. \underline{c_0}\text{ } \underline{z} \to$$

$$\lambda s. \lambda z. (???)$$

$$ \mathrm{pred}\, c_0 \to \lambda s. \lambda z. c_0 \underline{(\lambda g. \lambda h. h (g s))} \; \underline{(\lambda u.z)}(\lambda v.v) $$

Nope, that's not a redex.

You have a term of the form $c_0 M N P$. That's $c_0 M N$ applied to $P$. It could be parenthesised as $((c_0 M) N) P$. This is how lambda calculus encodes functions with multiple arguments: by applying the function to one argument, and then applying the result to the next argument, and so on. Since this construction is very common, parentheses are omitted: function application associates to the left.

Once you expand the abbreviations, there is only one redex in $\mathrm{pred}\,c_o$, which is $(\lambda n. []) c_0$. This is very intuitive: $\mathrm{pred}$ is a function that takes a numeral as an argument, and the first thing you to to kick off the calculation is to apply the function to the numeral.


Converting a digraph to an undirected graph in a reversible way I am looking for an algorithm to convert a digraph (directed graph) to an undirected graph in a reversible way, ie the digraph should be reconstructable if we are given the undirected graph. I understand that this will come in expense of the undirected graph having more vertices but I do not mind.

Does one know how to do this or can suggest any references? Thanks in advance.

Update: Regarding the answer of AdrianN below. It might be a good starting point but I don't think it works in its current form. Here is an image of why I think it doesn't:

Update after D.W.'s comment: I consider the vertices of the graphs to be unlabeled. If a solution involves labeling the vertices (like AdrianN's does), then it should give the same (isomorphic) undirected graph no matter how the labeling is done. My definition of "isomorphic" for graphs with labeled vertices is that there is a permutation of the labeling that relates the two graphs, but I am not sure of the exact definition for unlabeled graphs...

David Richerby's answer (which was accepted) is good.

I followed his instructions on a simple example digraph, and hope it helps someone.

(I would have posted this as a comment on David's answer, but I do not have the reputation points required.)


Determining whether a relation is the "union" of two other relations Given a relations $P$ and $Q$ on $S$, what are the most efficient algorithms to find whether the relation satisfy the constraints $P \cup Q = S \times S$ and $P \cap Q = \emptyset$?

If it helps, for my application the elements of $S$ are strings. Apologies if my question is not up to standard, this is my first question on Stack Exchange and it's been several years since I've done any formal math.

The following should suffice:

for each (x,y) in P:
    if (x,y) in Q, print "nope" and quit
for each (x,y) in Q:
    if (x,y) in P, print "nope" and quit
count the number of pairs in P and Q.
if this sums to |S|^2, output "yup, otherwise output "nope".

You could use any method.  For instance, you could compute $P \cup Q$ directly, then compute $P \cap Q$ directly (say, using mergesort-like methods), and check that each has the desired value.

All of these will have essentially the same asymptotic running time.


Balanced Weight Distribution in Bins/Buckets Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which is the sum of all the weights present in $b_j$.
What is the optimal way to distribute all the weights $w_i$ into the buckets $b_j$ to minimize the metric $\max T(b_j) - \min T(b_k)$ for some $j,k \leq n$?

I know that this seems to be a variant of the bin packing problem and I have found some heuristics such as the ones described here.
But is this problem really equivalent to the one in the link? My problem does not have an upper limit on the capacity of each bucket, which makes it quite different from the routine bin-packing problem.
If anyone has an optimal solution and if it's NP-hard, an approximation algorithm, I'd love to hear it.

It seems that this is exactly the $k$-partition problem, which is NP-hard even in the $k=3$ case.

There are decent approximation algorithms, though:

Greedy provides a $\tfrac{4}{3} - \tfrac{1}{3k}$-approximation (a PTAS).
FPTAS exist.


Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$ I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it?

Possible errors:

It first prove the case $\text{height(x)=0},$ then it says "For inductive steps, consider a node $x$ that has positive height".

From my understanding of inductive proof, the base case should be able to trigger the inductive statement. I mean: the "first domino" should trigger the next one, so the statement should be something like non-negative height.
It says "each child has a black-height of either $\text{bh}(x)$ or $\text{bh}(x)-1$", but when applying, only the latter is used: $(2^{\text{bh}(x)-1}-1)+(2^{\text{bh}(x)-1}-1)+1=2^{\text{bh}(x)}-1$.

Paragraph from the book:

The proof seems correct to me.

1) The base case proves the claim when the height of the subtree rooted at $x$ is $0$. The inductive step proves the claim for every subtree rooted at $x$ of positive height $h$ assuming that the claim is true for all subtrees of heights from $0$ to $h-1$. So the inductive step for $h=1$ is able to prove the claim for all subtrees of height $1$ using the fact that the claim is true for the base case, i.e., for all subtrees of height $0$. This is a standard proof by structural induction.

2) Each subtree $T_u$ rooted in a child $u$ of $x$ has a black-height $bh(u)$ of either $bh(x)$ or $bh(x)-1$ but, in any case, the height of $T_u$ is smaller than the height of the subtree $T_x$ rooted in $x$. This means that the induction hypothesis can be applied, showing that the number of internal nodes is at least:

$2^{bh(x)}-1$ if $bh(u)=bh(x)$; or
$2^{bh(x)-1}-1$ if $bh(u)=bh(x)-1$.

In any case the number of internal nodes of $T_u$ is at least the smaller of the above two quantities, i.e., $\min\{ 2^{bh(x)}-1, 2^{bh(x)-1}-1 \} = 2^{bh(x)-1}-1$.
This means that the number of internal nodes in $T_x$ is at least:

$$
2 \cdot ( 2^{bh(x)-1}-1 ) + 1 = 2^{bh(x)}-1.
$$


Brute force Delaunay triangulation algorithm complexity In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the notion of illegal edges -- edges that may not appear in a valid Delaunay triangulation and have to be replaced by some other edges. On each step, the algorithm just finds these illegal edges and performs required displacements (called edge flips) till there are no illegal edges.

Algorithm LegalTriangulation($T$)
Input. Some triangulation $T$ of a point set $P$.
Output. A legal triangulation of $P$.
while $T$ contains an illegal edge $p_ip_j$
do
$\quad$ Let $p_i p_j p_k$ and $p_i p_j p_l$ be the two triangles adjacent to $p_ip_j$.
$\quad$ Remove $p_ip_j$ from $T$, and add $p_kp_l$ instead.
return $T$.

I've heard that this algorithm runs in $O(n^2)$ time in worst case; however, it is not clear to me whether this statement is correct or not. If yes, how can one prove this upper bound?

A Delaunay triangulation can be considered as the lower convex hull of the 2d point set lifted to the paraboloid. Thus, if you take your 2d point set and assign to every point $(x_i,y_i)$ a $z$-coordinate $z_i=x_i^2+y_1^2$, then the projection of the lower convex hull into the $xy$-plane gives you the Delaunay triangulation.

Using this perspective, what does it mean for an edge $(p_i,p_j)$ to be illegal? First of all, for every triangulation $T$ we can use the parabolic map to get a 3d (triangulated) surface that projects down to $T$. Of course, this surface is not necessarily convex, if it would be convex, $T$ would be the Delaunay triangulation. Simply speaking, the edge $(p_i,p_j)$ is an obstruction for the convexity of the surface, a concave edge. When flipping this edge we change the situation on the lifted surface only locally. So lets look at the 4 points $p_i,p_j,p_k,p_l$. In 3d they form a tetrahedron, that projects down to quadrilateral. Since the two triangles $p_ip_jp_k$ and $p_ip_jp_l$ define the the concave edge $(p_i,p_j)$, the triangles $p_kp_lp_i$ and $p_kp_lp_j$ define the a convex edge $(p_l,p_k)$. Therefore, flipping an illegal edge corresponds to replacing a concave edge by a convex edge in the lifting. Notice that this flips might turn other convex edges to concave edges.

Remark: The image is not geometrically correct and should only be considered as a sketch.

Let $T'$ be the triangulation after the flip. The lifted surface of $T'$ "contains" the surface of $T$. By this I mean that if you watch the two surfaces from the $xy$ plane you see only triangles from the surface of $T'$ (or triangles that are in both surfaces). You could also say that the surface of $T'$ encloses more volume. Also, the edge $(p_i,p_j)$ lies now "behind" the lifted surface induced by $T'$ when watching from the $xy$ plane.

During the flip sequence we get a sequence of surfaces with strictly increasing volume. Thus, the edge $(p_i,p_j)$ lies "behind" all these surfaces. Hence, it can never reappear during the flipping process. Since there are only $n$ choose 2 possible edges, we have at most $O(n^2)$ flips.


What helpful solution does the Halting Problem give to computing? What problem does the halting problem solve in computing, whether theoretical or practical?

It is very easy to debug code which loops forever, just signal the debugger to break if the program is running for too long? What purpose / good is the halting problem? Why was Turing praised for it?

The halting problem is an example of a problem that a computer cannot solve. On the face of it, it might seem that computers can do anything, given enough resources and time. However, Turing showed that this intuition is false. Later on this was made more tangible by showing that a computer cannot decide whether a given Diophantine equation has solutions in the positive integers.

This is similar to Gödel's incompleteness theorem, which shows that the axiomatic method doesn't provide an answer to all possible questions. In fact, no finite list of axioms is enough to determine the truth of every statement regarding the natural numbers. Later on, a natural example emerged in the realm of set theory, namely the continuum hypothesis.


The control in the Turing Machine My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the tape.

The following is an excerpt from Michael Sipser's Theory of Computation, the passage is about how a Turing Machine can find the leftmost Cell. What is written is pretty straight forward. But what I don't understand is the part written in bold.

  "A trickier method of finding the left-hand end of the tape takes
  advantage of the way that we defined the Turing machine model. Recall
  that if the machine tries to move its head beyond the left-hand end of
  the tape, it stays in the same place. We can use this feature to make
  a left-hand end detector. To detect whether the head is sitting on the
  left-hand end, the machine can write a special symbol over the current
  position while recording the symbol that it replaced in the control.
  Then it can attempt to move the head to the left. If it is still over
  the special symbol, the leftward move didn’t succeed, and thus the
  head must have been at the left-hand end."

What does he mean by this exactly? What does recording a symbol in the control mean? Isn't the only (and infinite) memory of the TM the tape?

The state of the machine can be used as a finite memory. You can use the state to remember (or, if you prefer, "encode") what the last character you saw was, since there are only finitely many possibilities. If necessary, you can remember the last two characters, or ten or a million, as long as you fix the number at the time when the machine is designed.

What you can't do is remember an unbounded amount of information in the state. So you can't remember, for example, all the characters you've passed over since you last saw an '$a$', or even the number of characters since then.


If a problem is complete for NP, is its complement complete for co-NP? I am trying to prove that for a NP problem that is complete, its complement co-NP should be complete as well.

We know that a decision problem A $\in$ NP-complete if a) it is in NP and b) if every other NP problem is polynomial-time many-one reducible to it. There is a similar relationship between co-NP-complete and co-NP problems.

By definition, the complement of a problem is the same decision problem but instead of looking to validate the answer, we are looking to negate it. So it should be "common sense" to say that if a problem is NP-complete, then its complement is co-NP-complete, but how do you prove this? I know it should be easy to prove but I'm out of proofs or ideas.

Let $L\in \text{NPC}$. For any $L' \in \text{coNP}$ we have $\overline{L'} \leq_P L$ and therefore $L' \leq_P \overline{L}$ (by the same reduction).


Is this context-free grammar correct for this regular expression? I have created a context-free grammar

$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \mid bS_4 \mid \epsilon
\end{align*}
$$

for this regular expression

$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*) $

Is the grammar correct or am I missing a certain route?

One way to check whether you have got correct grammar is to use plain English or regular expression to characterize each non-terminals, starting from the more basic blocks.

$$S_4 \to aS_4 \mid bS_4 \mid \epsilon$$
This rule says $S_4$ is the words any words made up by zero or more $a$'s and $b$'s or, what is equivalent, $(a\cup b)^*$.

$$S_3 \to aS_3 \mid \epsilon$$
This rule says $S_3$ is the words any words made up by zero or more $a$'s or what is equivalent, $a^*$.

$$S_2 \to bS_4$$
This rule says $S_2$ is all words that are $b$ followed by zero or more $a$'s or $b$'s or what is equivalent $a(a\cup b)^*$.

$$S_1 \to aS_3bS_4 \mid \epsilon$$
These two rules says $S_1$ is $aa^*b(a\cup b)^*$ or the empty string.

$$S \to S_1 \mid S_2$$
This rule says $S$ is $aa^*b(a\cup b)^*$ or the empty string or $a(a\cup b)^*$.

The given regular expression for $S$ is
$$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*). $$
Can you see the difference between the given regular expression and the above description of $S$? Yes, the extra empty string. That is the single difference.

If the given regular expression is more complex, we might need to design some algorithm and implement it in some programming language. For the simple ones like this, the above step by step analysis should be enough. Be careful, of course.


How to build/recognise a deadlock-free order of resources I have been faced with a problem where three concurrent processes X, Y ,Z execute three different code segments that access and update certain shared variables. Before entering the respective code segments :

Process X executes the P operation on semaphores a,b and c;
Process Y executes the P operation on semaphores b,c and d;
Process Z executes the P operation on semaphores c,d and a.

After completing the execution of its code segment, each process invokes the V operation (i.e, signal) on its three semaphores. All semaphores are binary semaphores initialized to one.

How do I recognise a deadlock-free order of invoking the P operations by the processes ? For illustration, the given examples are the following

X: P(a)P(b)P(c) Y:P(b)P(c)P(d) Z:P(c)P(d)P(a)
X: P(b)P(a)P(c) Y:P(b)P(c)P(d) Z:P(a)P(c)P(d)
X: P(b)P(a)P(c) Y:P(c)P(b)P(d) Z:P(a)P(c)P(d)
X: P(a)P(b)P(c) Y:P(c)P(b)P(d) Z:P(c)P(d)P(a)

Preventing deadlocks can be achieve by removing one of the Coffman condition, one being the  circular wait condition.

For this we need to build a partial ordering of the resources.

From Wikipedia a partial ordered (poset) set is :

  A (non-strict) partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., which satisfies for all a, b, and c in P:

  a ≤ a (reflexivity);
  if a ≤ b and b ≤ a then a = b (antisymmetry);
  if a ≤ b and b ≤ c then a ≤ c (transitivity).

For the processes, there is no interest in the first two clauses, resources are distinct and unique. All we care about is the transitivity. Assuming a given order of resources, we then must ensure that each process never claims a lower resource before a higher one.

Building a deadlock free order is as simple as ordering the resources. This choice is arbitrary.

To solve your examples, we need to find what order has been chosen, if one exists, and verify it is a poset.

is not a poset since $a > c$ (from X) and $c > a$ (from Z) contradicts the transitivity.
is a poset since $b > a > c > d$ in all groups.
is not a poset since $b > c$ (from X) and $c > b$ (from Y) contradicts the transitivity.
is not a poset since $a > c$ (from X) and $c > a$ (from Y) contradicts the transitivity.

Conclusion, only 2 is a deadlock free order as the circular wait condition is removed.


Does This Prove $P \neq NP$? (Randomly Populated Binary Tree) Suppose a binary tree with $n$ levels and exactly $2^n-1$ nodes.

The nodes are random and their value does not determine their position in the tree at all. This isn't demonstrated in the picture, because I couldn't find a better image to use.

The task is to find the path to a given node. Since the nodes are random, we'd have to visit each node until we find the target. This should be $O(2^n)$ with the best case being $\Omega(1)$ (the target node is the root node). The output is at most an $n$-bit value, each bit specifying whether to traverse the left or right child node. When there are no more bits to be read, we know we've reached the target node. Therefore, the output can be read and verified in $O(n)$. Are there any flaws with this?

No, it doesn't. Your input size is exponential in terms of n. So the proper way to look at it would be to define k=2n-1 and solve the problems in terms of k.


Understanding Martin Farach's suffix tree algorithm I feel stuck at this point. I have spent several days trying to get my head around the algorithm, but both resources I have [1] [2] seems to skip over whatever details that would make me comfortable trying to explain/implement it. I'm going to hope that someone here knows Farachs suffix tree algorithm, but I'll link to the paper below.

I get the individual mechanisms of the algorithm, but I don't understand how to put it all together. By starting at the first step:

(1) Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

(2) Farach mentions that the suffix tree for g' needs to be computed recursively. Is this the only step of the algorithm that needs recursion?

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.4336&rep=rep1&type=pdf

[2] https://www.amazon.com/Computing-Patterns-Strings-William-Smyth/dp/0201398397

Not a complete answer but I hope this helps.

re :

  Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

Let,

$l$ - list

$g$ - ranks of elements of $l$ in $sorted(l)$

You can easily recover $sorted(l)$ using $l$ and $g$. You just put $i^{th}$ element of $l$ at position $g[i]$ in some new array $A$, like this,

for i = 0 to len(l):
   A[g[i]] = l[i]

Fill out following $A$ to see it.

l = [3, 2, 4]

g = [2, 1, 3]

A = [ , , ]


How to create a LR(k) grammar for an arbitrary k Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?

Here's one pattern for an LR(k) grammar which is not LR(k-1).
I didn't fill in the definition of $A$; there's nothing particularly special about it. It might have an empty right-hand side, or it might match any LR(k) subgrammar. $a^k$ represents $k$ instances of $a$.

$$
\begin{align}S&\to B a^{k-1} b\\
S&\to C a^{k-1} c\\
B&\to A\\
C&\to A\\
A&\to \text{see above}
\end{align}
$$

Clearly, it is not possible to determine whether $A$ should be reduced to $B$ or to $C$ without knowing what the $k$ following token is. So the grammar is not LR(i) for any $i \lt k$. The reduction can be determined using $k$ lookahead tokens, so the grammar is LR(k) provided that $A$ is.


What does it mean "given a NFA and its accepted language L build the DFA that accepts L*"? Supposing we have either a NFA or a DFA with accepted language $L$, what is $L^*$? And how can I build an automaton that accepts it?

$L^*$ is the Kleene closure of $L$. This is the language of all strings that can be made by taking a finite number of (not necessarily different) strings from $L$ and concatenating them.  More formally,

$$L^* = \{\varepsilon\}\cup\{w\in\Sigma^*\mid \exists k\geq 1\,\exists w_1, \dots, w_k\in L \text{ such that } w = w_1\cdot\dots\cdot w_k\}\,.$$

Or, if you prefer, for $k\geq 1$, let
$$L^k = \{w_1\cdot \dots \cdot w_k\mid w_1, \dots, w_k\in L\}$$
and then $L^* = \{\varepsilon\}\cup L^1 \cup L^2 \cup L^3 \cup\cdots\,$.

As for how to produce an automaton that accepts that, I suggest you think about it some more yourself, now that you know what it is you're trying to do. A hint would be to use nondeterminism to "guess" where the words $w_2, \dots, w_k$ begin.


Why do we need so many transistors in a chip, and how are they managed? My knowledge is very vague as all we have are visual diagrams etc, but we have memory address and registers, the ALU being the heart(apparently). Single core CPUs process one instruction at a time AFAIK and multi-core have parallelism to some degree. So where do the millions of transistors come in and how do 32 registers manage everything. We have FPU's I know, how many transistors would these use roughly. Any way to get a fairly simple idea of what the bulk of the transistors do, why more means faster and how the registers 'manage' everything.

This is a huge question. To fully answer it would take far more space than you'd want to read (not to mention that I suspect that there's a limit on the length of any SE answer), but I'll try to give you an idea of what goes on in the CPU.

First, a transistor (when used in a CPU) is essentially a switch, like a light switch except that you don't have to turn it on or off manually. Rather, it is controlled by an electrical current. The most important thing to understand is that modern computers are two-state devices: the only thing that really matters is whether a wire has a current or not.

One then begins the process of chip design by, for example, deciding how an integer (or other data) will be represented. For integers, say, the chip designers generally decide to them by ganging wires together in a logical unit, so with a collection of four wires it would be possible to represent 16 possible patterns: $\mathtt{0000}, \mathtt{0001}, \dots \mathtt{1111}$, where a pattern like $\mathtt{1101}$ would represent a voltage in wires 1, 2, and 4, and no voltage in wire 3 and this collection might be interpreted as the number 13. In this example, we'd have what's known a a 4-bit chip. A modern computer would have either 32 or 64 wires treated as a unit.

It happens that with a suitably-connected collection of switches (aka transistors), one can do things like add two numbers, compare two numbers for equality, decide whether a number is zero or not, and so on. Often, all of these operations are often done at once, simultaneously, and the relevant one is chosen by the current instruction, which determines which of the various results to use, and where that result will be sent. All of this traffic control is also controlled by switches, depending on what the current instruction is (in the program being executed). In addition, things like memory and registers which store information can also be implemented by these switches.

To get a feel for the number of transistors used, an adder circuit in a $n$-bit computer might require about, say, $20n$ transistors, an $n$-bit register might require $50n$ transistors, and the traffic control circuitry to sent the results to the right place might require several hundred more for each bit. It's not hard to imagine that with a lot of functionality and a wide data path (the number of wires ganged together) a modern CPU could easily take millions of transistors.

As to why "more [transistors] means faster", the answer is "not necessarily", but in general, doubling the width of the data path, say from 32 bits to 64, gives you the ability to manipulate larger numbers in a single instruction at the cost of requiring more transistors.

Finally, the registers don't really "manage everything". A register is simply a very fast storage unit, capable of storing and retrieving information far faster than, say RAM memory. For that reason, things like the current instruction are often stored in a special register (called the instruction register), simply because access to its bits is very fast. The current instruction actually "manages everything", and it's stored in a register for speed.

This is a very abbreviated explanation---I've left out a ton of detail and glossed over a lot of technical matters, but I hope it at least gives you a sense of what goes on in a modern computer. [entering duck-and-cover mode in expectation of howls of complaints from computer engineers]