Pumping lemma with multiple of prime number + a constant Given the language
$$L = \big\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\} $$
show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be userful the pumping lemma of the language of prime numbers, you can find it here.

A counterexample must be a string $z \in L$ whose length $|z|$ is greater than a generic h such that for any the decompositions $uvwxy=z$ with $|v|+|x|\ge 1$ and $|vwx|<h$ exists an i such that $uv^iwx^iy \not\in L$. Generally we have to find a contraddiction of $|v|+|x|\ge 1$ or $|vwx|<h$.

There are five possible decompositions of the string. The only required case is the one with $v$ completely in the first part of the string and $x$ completely in the second part.

Now follows some failed attempts:

This one was posted as answer I deleted because incorrect. I took as string $z = 0^{2h}10^{5h}$ which is in the language for $m = 2h$ and $k = h$. The problem here is that $m$ is prime, so $m = 2h \iff h = 1$ which means $h$ is not a generic length anymore. Here it follows the incorrect attempt:

   $$ uv^iwx^iy = 0^{2h + |v|(i-1)} 1 0^{5h + |x|(i-1)} = 0^{m} 1 0^{2m+k} \in L $$
 The equation has solution iff has solution the system
 $$ \begin{cases} 2h + |v|(i-1) = m, m \text{ prime} \\ 5h + |x|(i-1) = 2m + k \\ \end{cases} $$
 For $i = h + 1$ we have $$ 2h + h|v| = h(|v| + 2) = m $$ But $m$ cannot be prime because it's a moltiplication of two terms $h$ and $(|v| + 2)$. Contraddiction!

We need to choose $m$ as something like $h$ or $ah + b$ in order to avoid this issue.
I took as string $z = 0^h 1 0^{2h+1}$ which is in the language for $m = h, k = 1$. We have
$$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{2h + 1 + |x|(i-1)} $$ We have to solve the system
$$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\
    2h + 1 + |x|(i-1) = 2m + k\end{cases} $$

Trying with $i = h + 1$ does not work: the first equation becomes

  $$ h + h|v| = h(1 + |v|) = m \text{ prime} \iff |v| = 0$$
  so the second equation results in
  $$ 2h + 1 + h|x| = 2h + k \Rightarrow |x| = \frac{k-1}{h} $$
  so the string results in $0^{m} 1 0^{2m+k} \in L$ with $m = h$, $k = h + 1$ from the decomposition with
  $$ |v| = 0 \qquad |x| = \frac{(h+1) - 1}{h} = 1$$

Trying with $i = 0$ leads to

  $$ \begin{cases} h - |v| = m \\ 2h + 1 - |x| = 2m + k \end{cases}$$
  which results in
  \begin{align*} 2h + 1 - |x| &= 2h - 2|v| + k \\ 2|v| - |x| &= k - 1 \end{align*}
  which results in as many string $\in L$ as you want (for example $k = 3, |x| = 0, |v| = 1$ gives $0^{h-|v|} 1 0^{2h-2|v|+1} = 0^{h-1} 1 0^{2h-1} \in L$)

I took the string $z = 0^{h} 1 0^{3h}$ which is in the language for $m = h, k = h$. We have
$$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{3h + |x|(i-1)} $$
We have to solve the system
$$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\
    3h + |x|(i-1) = 2m + k\end{cases} $$

Trying with $i = h + 1$ we have

  $$ h = m \qquad |v| = 0 \qquad 3h + h|x| = 2h + k$$
  which results in $ |x| = \frac{k}{h} - 1$; then we can take $k = 3h$ so $|x| = 2$, and the result is the string $0^{h} 1 0^{4h} \in L$

As you can see, I can't find a combination of string and $i$ that generates a contraddiction. How would you proceed?

Your error is that you assume that you must find one $i$ to satisfy all the subdivisions $uvwxy$ of the lemma. The lemma is actually much weaker in that you need to find any $i$ for every subdivision $uvwxy$ of a string $s$ in $L$ longer than $h$. Without loss of generality, I will assume that any given $h$ is prime, because if it were not, I would just substitude all next occurances with any higher prime number and everything would still work the same way (I never needed the condition $|vwx|\le h$).

That said you can take your second try from the question and then fork it into two cases where:

$v \neq \epsilon$ (where $\epsilon$ means empty string, I don't know if that's international notaion. It can be otherwise written as $|v|\neq0$ )
From your first equation $$h + |v|(i-1) = m, m \text{ prime}$$ with $i = h + 1$ you get $$h + |v|h = (1+|v|)h$$ which is composite number because of our assumption $v \ne \epsilon$, meaning the string is not from $L$.
$|v|=0$ where we can pick another $i$ because it is different division of the string $s$. Here we get $$|v|=0 \land |vx| \ge 1 \implies |x|\ge 1$$
And we can trivially chose $i=0$, because now we actually subtract from the second string of zeroes, which was originally $2h+1$ long. The new length will be shorter than that, meaning we'll get a string $0^{h}10^{g}$ where $g<2h+1$ thus the string is not from the language $L$.

On final note, if you were to use this as a rigorous proof, you would need to address all the other options including those, where the $1$ is part of either of the pumped strings, it is part of either $u$ or $y$ and so on. I covered only the two interesting options and the others should now be trivial to you (I assume that is why you never mentioned them in your question and assumed that 1 is part of the $w$ string).


Term for incorrect primary key From a database theory point of view, what term can be used to refer to a key that does not violate the rules of the engine within which it is implemented, but fails to conform to any sort of normalisation? For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

The reason for wanting to obtain a technical or academic term for this is to describe a situation where there is a primary key that has been technically successfully implemented, but is conceptually flawed.

For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

For this example I would simply state that the problem is that the uniqueness of values of timestamps, if it happens to hold, is only accidental: there is generally no fundamental reason that the same timestamp (even with very high precision) could not be assigned to 2 separate records.

For a primary key uniqueness should not be accidental but fundamental.


What is the point of an active shape model in facial recognition? From what I understood, the Active Shape Model (ASM) is used in facial recognition. I figured out how the ASM works but I don't get why we use it.

How this shape is suppose to be interpreted for facial recognition? Should it be compared directly to the database?

I have read many research papers about ASM and facial recognition but none of them explains the point of it.

The active shape model algorithm is used to locate precisely the eyes, eyebrows, nose and mouth of a person. It is also used to align faces that are tilted.
It is not used directly for face matching and it has nothing to do with databases. It is a preprocessing step.
You (I) will need another algorithm to match its result with a database. (ICA for example)


Ketama hash explanation (I originally posted this on stackoverflow but thought it would be a better fit here)

I'm trying to understand the Ketama hash code used in consistent hashing.

link and snippet below:

public static Long md5HashingAlg(String key) {
    MessageDigest md5 = null;
    try {
        md5 = MessageDigest.getInstance("MD5");
    } catch (NoSuchAlgorithmException e) {
        log.error("++++ no md5 algorythm found");
        throw new IllegalStateException("++++ no md5 algorythm found");
    }
    md5.reset();
    md5.update(key.getBytes());
    byte[] bKey = md5.digest();
    long res = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8) | (long) (bKey[0] & 0xFF);

    return res;
}

I think I understand what the code is doing, but I don't get why they're doing it. Particularly, I'm wondering why:

the code discards the least significant 8 bytes of the 16-byte MD5 and uses only the first four (bKey[0] through bKey[3]).
the code "flips" the significant bytes meaning that, of the 4 bytes from 1., the least significant now become the most significant (at least that's what I understand happens from the & 0xffs and left shifts).

I also came across another piece of code that uses the same logic as above, but in addition performs an & 0xffffffffL on the result to "truncate to 32-bits".

link and snippet:

case KETAMA_HASH:
    byte[] bKey = computeMd5(k);
    rv = ((long) (bKey[3] & 0xFF) << 24)
        | ((long) (bKey[2] & 0xFF) << 16)
        | ((long) (bKey[1] & 0xFF) << 8)
        | (bKey[0] & 0xFF);
    break;
    default:
    assert false;
}

return rv & 0xffffffffL; /* Truncate to 32-bits */

Could someone help me understand the rationale behind picking these particular bytes and re-arranging them in this particular fashion?

This is simply a way to generate 32-bit hash for the string.
Assuming that MD5 is a good cryptographic hash function, it doesn't matter which bits you take from the hash and in which order you arrange them (as long as they are different bits). The behavior of the bits should be equally unpredictable.

There's no explanation, why exactly 32 bits are required, though my guess is that it enables the use of simple integer types in the code.


Impossibility for Byzantine Generals Problem where $n \leq 3m$ Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance

In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the problem for $n \leq 3m$, where $n$ stands for the number of generals and $m$ stands for the number of traitors. The key of their proof this the impossibility of the case $n=3,m=1$. However, the method they used does not look like an information theoretic proof. Thus, it seems like that their result is not "impossibility of arbitrary protocol".

  My question: Is there a infomation-theory-based proof for the case $n=3,m=1$? More formally, is there a proof or counterexample for the proposition "there does not exist any kind of protocol, which solves Byzantine generals problem where $n=3,m=1$"?

Note: The typical protocol $\mathrm{SM}(m)$ (it works for arbitrary $n,m$) suggested by L. Lamport et al. is NOT a suitable counterexample, because it needs a signature mechanism, which is NOT perfect reliable in the sense of information theory, if we assume that traitors have infinity computing resources.

In the synchronous model of communication, there are $n$ agents which share a clock. In each round of communication, each agent sends an arbitrary message to each other agent, and then receives the message sent her by every other agent.

A protocol for byzantine agreement on $n$ agents supporting $m$ byzantine agents is a communication protocol for the agents satisfying the following properties:

Each agent receives an input bit.
The agents all start talking at time 0.
There are at most $m$ byzantine agents, whose behavior is arbitrary.
The other agents follow the protocol.
The protocol always terminates (this means that the non-byzantine agents always reach a special "terminate" state of the protocol, and then stop talking forever), with a return value which is also a bit.
The return values must all agree (note that this only applies to the non-byzantine agents).
If all input bits are the same, then the return values have to be the same bit.

The impossibility result states that such a protocol exists if and only if $n > 3m$.

There is a different model in which an agent can sign a message, and this signature cannot be tampered with. In this model (which I will not specify formally) the problem can be solved for any $n,m$.

One of the difficulties in the area of distributed systems is the complicated nature of the computation model. If you want to understand the meaning of impossibility results, you have to familiarize yourself with these models in full detail (even more detail than the rather informal treatment in this answer).


$e^{-5}$ error using Taylor's series I am a student and I was reading Numerical Analysis by Burden. In one of the exercises, I have to calculate $e^{-5}$ in two ways.

The first is using the Taylor's series for $x=-5$, $( e^{-5} = 1 - 5/1! + 5^2/2!-...)$ and second way is calculating $e^5$ and then $e^{-5}=1/e^5$,  again using Taylor's series but this time for $x=5$. In his solution, he says second way gives better results because we avoid subtraction. I think that it has to do with the floating point system but I am not very sure so I thought someone could further explain it to me. (Sorry if I have made any mistakes. English is not my native language)

Use a spreadsheet and calculate $e^{-100}$ both ways. It will become totally obvious what is going on. "We avoid subtraction" is not the problem. The problem is that you are adding the sum or difference of large numbers, and each large number has a large rounding error. For one method, the rounding error is not large compared to the result. For the other matter, the rounding errors are huge compared to the result.


What is the purpose of Mark field in Fibonacci Heaps? In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already marked, the parent will be cut and inserted into the root list. I just wonder what the purpose of marking is? What happens if we cut the parent just the first time without marking it? Does it change the time complexity of the operations? How?

It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large.
We have two expensive operations, which are ExtractMin and DecreaseKey. Remember that the amortized analysis uses the potential function
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
If we call ExtractMin this might cost $O(\left|W\right|)$, however after the operation, the root list has only size $O(\log n)$, and we have charged most of the costs to the potential. The question now is how to charge-up the potential. Here come the DecreaseKey operations into play. They are responsible for a large root list $W$. Say, we add $k$ trees to the root list $W$ during the DecreaseKey operation. This means that we remove $k-1$ marks, and  we pay with the marks the costs of DecreaseKey and the change of the potential function (that is why we have a factor 2 for the marks in $\Phi$).
So what happens if we immediately put a vertex into the root list when decreasing the key. Then of course the root list might get large. But this is not the problem. The problem is, that you cannot show that after the repair-part of ExtractMin  $W$ has at most $O(\log n)$ elements. If I am not mistaken the size of $W$ can then contain up to $\Omega(\sqrt{n})$ elements. That means that if we delete directly the DecreaseKey operations are in $O(1)$ and their worst-case running time is even better than for Fibonacci heaps, but the ExtractMin is $O(\sqrt{n})$.
Another softer perspective is the following: The marks guarantee that you only delete one child for every node. Without deletion every tree in a Fibonacci heap is a binomial tree. The marks ensure that we do not diverse from the binomial tree structure too much.


Is Artificial intelligence simply taking decisions on the basis of values produced by a machine learning model I am researching on AI and its working. Whenever I try to search for AI algorithms, ML algorithms come up. Then, I read the differences between ML & AI. One of the key points mentioned was "AI is decision making" & "Machine learning is generating values and learn new things".

I come up with a conclusion that ML allows us to take generate some sort of values and using AI we can make decisions with those values.

But I am confused with "The weather forecast" problem. Our machine learning model will directly generate the decision that will it rain or not? Is our ML model lies in the AI domain or I am wrong? Help me!

Artificial Intelligence is a very broad area of Computer Science which is intertwined with many other fields, and someone might argue that its definition is the discipline that develops rationally acting systems.

When it comes to Machine Learning, the generally accepted definition is programming computers to perform a specific task without specific instructions about the problem.

Being that broad of a field, AI comprises Machine Learning problems, but the difference between the two areas relies on how you devise your system:

if you make use of problem-specific knowledge in your algorithm: you're outside the ML field;
if you formulate your problem in a general-enough manner and use a generic algorithm: most likely you're inside the ML field.

I'm sure you have already seen this image from Nvidia a million times already, but it's intuitive to understand what's the relationship between AI and ML: the latter is part of the former.


Does proving a problem is in P typically mean it will eventually be practically solvable? I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P and NP.

First he says:

  $P$ roughly corresponds to the class of problems that are realistically
  solvable on a computer.

He then continues a little further down the page:

  Of course, a running time of $n^{100}$ is unlikely to be of any practical use. Nevertheless, calling polynomial time the threshold of practical solvability has proven to be useful. Once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained and further reductions in its complexity usually follow, often to the point of actual practical utility.

So my question is the following: What are examples of problems that were proven to be in P but were intractable, but after some theoretical advances became tractable?

I'm also welcome to hearing about problems that were proven to be in P whose runtime was significantly advanced by some algorithmic improvements but perhaps was not advanced enough to be tractable.

One example in which the running time became significantly better but still not necessarily practical is submodular function minimization, which went down from $O(n^7)$ (Grötschel, Lovász and Schrijver, 1981) to $\tilde{O}(n^4)$ (Lee, Sidford and Wong, 2015). The latter paper (and the ones preceding it) has many such results.


Multiple Constraint Knapsack Problem Dynamic Programming Is there any way for solving the Knapsack problem when we are limited by several constraints?

Let's assume that we have a set of items in which we have value v that we want to maximize and we also have two constraints weight and volume that must be lower or equal than the values W and V respectively.

My question is, can this problem be solved using dynamic programming?

Yes. More precisely, for any fixed number of constraints (for example, weight and volume) the problem has a pseudo-polynomial time algorithm based on dynamic programming.

The idea in your comment (add one more dimension to the dynamic programming table) is essentially correct. In the classic knapsack, for any $i=0,\ldots,n$ and $w=0,\ldots,W$, you compute the highest profit that you can get with items of type $\le i$ and total weight $\le w$ (so you can get an $O(nW)$ time algorithm). In the generalization, you also need to iterate on the total volume $v=0,\ldots,V$, which means an $O(n W V)$ time algorithm.


Compound interest with varying compounding frequency Here is the problem I have attempted to solve.

  Given original principal $n$ and aggregate rate $r$, find the maximum final principal that can be yielded.

Though I know that the higher the compounding frequency is, the higher the final principal will be, a special condition applies:

  Intermediate principals are rounded down to the the nearest integer each time.

So for example $n = 10000$ and $r = 3$, I can choose to have

1% growth 3 times
a 2% growth then a 1% growth
or a 3% growth.

For case 1 n would grow as 10000 -> 10100 -> 10201 -> 10303.

For case 2 n would grow as 10000 -> 10200 -> 10302.

For case 3 n would grow as 10000 -> 10300.

So in this case the highest value would be 10303.

As another example, take $n = 10$ and $r = 10$. As it will not yield any changes to $n$ unless the growth rate is higher than 10%, the answer is 11.

So in mathematical terms it is to find $\max n\prod(1+r_i\%)$ where $\sum r_i = r$ with the rounding condition.

What I was trying to do is to find the minimum growth rate that would result in a change in $n$ and apply it immediately, then repeat the process until $r$ is used up, but it doesn't seem that it is getting the desired answer. Any hints would be appreciated. If you need any clarification please tell me.

    while(r > 0 && rate < r){
        rate++;
        if (n * (100 + rate) / 100 != n){
            n = n * (100 + rate) / 100;
            r -= rate;
            rate = 0;
        }
    }

$r_i$ must be positive integers.
This problem is adapted from A028:武器の強化 problem, which can be found here (on paiza, which is a Japanese-language coding contest site).

This problem is a good example of problems that can be solved by dynamic programming.

Given original principal $n$, the subproblems are, what is $p(t)$ for $0\le t\le r$, the maximum final principal that can be yielded if aggregate rate is $t$ . We have the following recurrence relation, where $//$ means the integer division, for example, $13 \operatorname{//} 5 = 2$.

$$p(t) = \max( p(0) + p(0)* t \operatorname{//} 100,\ p(1)+p(1) * (t-1) \operatorname{//} 100,\ p(2)+ p(2) * (t-2) \operatorname{//}100,\ \cdots,\ p(t-1)+ p(t-1) * 1 \operatorname{//} 100)
$$

From $p(0)=p$ you can compute $p(1)$. From $p(0)$ and $p(1)$, you can compute $p(2)$. And so on. Finally you can will get $p(r)$, which is what you want.

I will left you figure out the actual implementation. By the way, the code in question, fails when the original principal is 23 and the aggregate rate r is 9.


Is an inverse homomorphism always a homomorphism? Given a homomorphism $h: \Sigma \rightarrow \Delta^*$ such that e.g. $\forall a \in \Sigma: h(a) = \delta$, where $\delta \in \Delta$ (i.e. all symbols from the alphabet $\Sigma$ have the same image $\delta$), is the inverse homomorphism $h^{-1}$ a homomorphism?

Since a homomorphism maps every symbol of the input alphabet to one word from the output alphabet, the inverse transformation to $h$ is a substitution $\sigma: \delta \mapsto \Sigma$ (which maps one symbol to a whole language - alphabet $\Sigma$).

What would be an inverse homomorphism to $h': a \mapsto \epsilon, \forall a \in \Sigma$ or would such a transformation even exist?

EDIT: The question should have rather stated: "Is there always an inverse homomorphism?" There obviously isn't since only isomorphisms have their inverse homomorphisms.

If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \{w\mid h(x) = w\}$ is only defined (nonempty) when $w\in\delta^*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse is a substitution, mapping the letter $\delta$ to the set $\Sigma$  and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one [meaning single valued], an inverse homomorphism in many cases is one-to-many [many-valued]. (If the inverse morphism is one-to-at-most-one [injective] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").


Size of address registers and data registers in relation with memory size Suppose that a processor can address directly up to 4 Gigabyte main memory and can operate words with size 32 bit. Find how big should be the size of the "MAR" (memory address registers), "MDR" (memory data registers) and accumulator registers in this computer?

My answer: MDR is 32 bit wide since it exchanges data not only via the data bus but with the CPU data registers. How about MAR and accumulator? how are they related to the 4 gigabyte main memory?

This question is not so simple to answer. At first sight, 32 bit address registers seem to perfectly match 2^32 byte = 4 GB of physical memory. However, with 32 Bit you can also address more than 4 GB, like Physical Address Extension (PAE) does. The opposite way round means that you can access 4 GB with less than 32 bit address register.

The data registers are not related to the memory size at all in my opinion. The data registers are mainly an indicator how much data can be transferred at one time. If you want e.g. to crack SHA-512, then you could design a CPU which benefits from transferring 512 bit of data at one time, so you have 512 data registers.

The same SHA-512 cracker CPU brings us to the accumulator: ideally the CPU would also process 512 bit numbers in one cycle, so the accumulator is also 512 bit.


A question regarding the Layered Architecture Consider the following general form of a layered architecture :

I need to check my understanding about the second layer from top . More specifically I need to check my understanding the regarding the meaning of "User interface management " . According to my understanding , UI management is the code that underlies the UI , for example it is the code for each button and each UI elements . So for example , let us consider that the user needs to generate a report from a system that uses this layered pattern as its architecture. So what happens is the user press the generate report button then the underlying code of this button knows that it need to run the code of generate report system functionality ( which exists in the third layer). After that the generate report code ( lets assume that it is implemented as a class) will refer to the database to get the required info to generate this report and then the info will "propagates upward" until it reaches the UI again to be viewed by the user. So is this right ?  In other words , is this what is the meaning of the User interface management ? and do I understand the mechanism of this architecture ?

"User Interface Management" does not have a standard accepted definition that I am aware of, so you'll have to work out what they mean by it based on context.


How does C++'s type checking work when passing overloaded or templated functions as parameter As I understand, C++ in general features 'one-way' type checking. That is checking the sub-expressions and get their types, and see if the types so far satisfy the constraints imposed by the current expression node. It's an algorithm progressing from bottom to top.

However, C++ also features overloading and template. When you pass such a function directly as the argument to another function, during type checking we cannot immediately get the type of the sub-expression since it is overloaded or using template. So how does it work?

It's possible that C++ does more than 'one-way' type checking. If that's the case, please explain to me how the feature is implemented.

Type checking occurs when the template is instantiated, so the compiler knows the types by then.

Overload resolution happens at call site. The sub-expressions are the arguments, when their types is known the resolution can occur, hence giving the type of the call expression (that is, the return type).

Neither templates nor overloaded functions are first-class citizen constructs than can be passed around, so I am not sure what you mean by "such a function".


Finding a non-boundary, local optimum of a non-convex function over a convex feasible region I have a reasonably smooth non-convex non-monotone function in high(ish) dimensional space, that I wish to find a local minimizer for, over a convex feasible region (the intersection of a ball with a set of halfspaces, so a "wedge" of the ball or a polytope), with the caveat that I want the minimizer to be away from the boundary of the feasible region.

Are there any sound ways, or even just good heuristics, for doing that?

Edit: If all minimizers (or regions looking like minimizers) are around the boundary, then is there a way to detect that?

One idea I had is to use barrier functions near the boundary and then just use gradient descent, but the barrier functions might create false local minima...

Thanks!

Your question is not well-defined yet.  You have described two criteria you want to optimize over: minimize the function, and be away from the boundary.  You often can't simultaneously optimize both; the way to minimize the function might be near the boundary, and points away from the boundary might not minimize the function.

So, before you can solve this problem, you first must figure out how to formulate it in a well-posed way.  Basically, you will have to decide how to trade off between your two goals.  One way would be to define an objective function $\Psi(x)$ that is a sum of your function and some penalty term, where the penalty is larger the closer to the boundary you are.  e.g.,

$$\Psi(x) = f(x) + 1/d(x),$$

where $f$ is your function and $d(x)$ is the distance from $x$ to the nearest point on the boundary of the feasible region.  Then, you could try to minimize $\Psi(x)$.  That's one possibility, but there are of course others.  (This particular approach is sometimes known as a barrier method.)

Once you have formulated the problem, then you can select an optimization algorithm.  Gradient descent would be a good starting point if the problem is high-dimensional and you can compute gradients.  If the number of dimensions is not too large, you can also consider second-order methods, like Newton's method, trust region methods, and many others.  The choice of method will depend on the properties of the function, and might also require some experimentation.

Alternatively, rather than treating both goals as soft goals to be balanced, you might decide that the "away from the boundary" is a hard requirement that absolutely must not be violated.  Then you would define the region $\mathcal{R}$ of points that are away from the boundary (e.g., distance at least $D$ from the boundary, for some constant $D$ of your choice), and then your problem becomes to minimize $f$ over the region $\mathcal{R}$.  There are a number of methods for doing that; you might start by trying projected gradient descent.

If you want to detect whether all minimizers are near the boundary, you can first find the absolute minimum within the feasible region (e.g., using gradient descent or projected gradient descent), then find the minimum within the region $\mathcal{R}$ of points that are away from the boundary (e.g., using projected gradient descent); if the latter is larger than the former, you know that all the minima are near the boundary (at least, up to the optimality of your optimization routine).

We can't tell you how to formulate your problem, because that depends on what you want to achieve, and only you know that.  You will have to decide what your goals and requirements are, and then choose a formulation that matches your needs and goals.


Can Euclidean TSP be exactly solved in time better than (sym)metric TSP? Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $\mathcal O(n^2 2^n)$.

See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962.

In Exact Algorithms for NP-Hard Problems: A Survey (PDF) Woeginger writes:

  This result was published in 1962, and from nowadays point of view almost looks trivial. Still, it yields the best time complexity that is known today.

Thus, this is the best known upper-bound.

Question:

  Are there any better results for Euclidean TSP? Or does that best-known bound apply to Euclidean TSP as well.

How is Euclidean TSP different? Well,

Euclidean TSP can be encoded into $\mathcal O(n \log m)$ space, where $n$ is the number of cities, and $m$ is the bound on the integer coordinates of the city locations. As opposed to (sym)metric TSP variants, which essentially require a distance matrix of size $\mathcal O(n^2 \log m)$. Thus, it might be easier to solve; for example, perhaps Euclidean TSP can be more easily encoded into k-SAT, because the distance function is implicit.
Contrary to popular notion, Euclidean TSP's reduction from k-SAT is quite different from (sym)metric TSP. UHC (undirected Hamiltonian cycle), symmetric TSP, and metric TSP are pretty directly related to each-other. But formulations of reductions from (sym)metric TSP to Euclidean TSP are not easy to come by. Paragraph, from interesting article, The Travelling Salesman’s Power by K. W. Regan (bold mine):

  Now the reductions from 3SAT to TSP, especially Euclidean TSP, are less familiar, and we ascribe this to their being far more “expansive.” Texts usually reduce 3SAT to Hamiltonian Cycle, then present the latter as a special case of TSP, but this does not apply to Euclidean TSP. The ${\mathsf{NP}}$-completeness of Euclidean TSP took a few years until being shown by Christos Papadimitriou, and a 1981 paper by him with Alon Itai and Jayme Luiz Szwarcfiter advertised a “new, relatively simple, proof.” This proof uses vertex-induced subgraphs of the grid graph in the plane, for which the shortest possible TSP tour and any Hamiltonian cycle have the same length. Despite this simplification, the gadgets involved are large—a diagram of one occupies most of one journal page.

Hunting down k-SAT $\rightarrow$ Euclidean TSP reductions is quite an adventure; so far I've found two of them. One $\rm k\text{-}SAT \rightarrow CircuitSAT \rightarrow PlanarCircuitSAT \rightarrow EuclideanTSP$, and another, even tougher one to find, $\rm k\text{-}SAT \rightarrow DHC \rightarrow UHC \rightarrow PlanarUHC \rightarrow EuclideanTSP$. The latter reduction can perhaps be seen to make Euclidean TSP parallel (sym)metric TSP.

One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in $O(n^{c \sqrt{n}})$ time, where $c$ is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis [1], Kann's PhD thesis [2], and Hwang et al. [3]. Each algorithm has a running time of $O^*(c^{\sqrt{n} \log n})$. This is much better than $O(n^2 2^n)$. As far as I know, it is still an open question whether the running time can be improved by say getting rid of the logarithmic term.

[1] W.D. Smith, Studies in computational geometry motivated by mesh generation. Ph.D. Thesis, Princeton University, Princeton.

[2] V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Kungliga Tekniska Högskolan, Stockholm, 1992.

[3] R.Z. Hwang, R.C. Chang, R.C.T. Lee, The searching over separators strategy to solve some NP-hard problems in subexponential time,
Algorithmica 9 (1993) 398–423.


If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular? Let $R \in REG$. Is it true that if $F\cap R \in REG$ and
$F \cap \overline{R} \in REG$ then $F \in REG$?

I took $R = \Sigma^{\ast}$ and because $F\cap R \in REG$, $F$ must be regular. Is this the right approach?

Here's a hint. First, show that for any two sets $A, B$, that $A = (A\cap B)\cup(A\cap\overline{B})$. Then use the fact that the union of two regular languages is regular.


Word Wrap Algorithm and Datastructure that supports modifications of text and window size I'm trying to find or create an algorithm for efficiently displaying text that is word wrapped.  All the algorithms (if they an even be called that) for word wrapping presume a given lot of text and window size, and compute word wrapping in $O(n)$ time.  That isn't realistic because text can be huge, users can modify text anywhere, and window sizes can change.  It is quite a problem to expect $O(n)$ modification time whenever something changes. When a user modifies the text or resizes a window, I'd like to be able to update the display in something like logarithmic time.
Here is how I formalize the a slightly simplified version of the problem:
$A$ is an array of positive integers that of length $n$.  It represents the lengths of words (and their trailing space).  $W$ is a positive integer representing window size.  For simplicity assume $W \ge \max(A)$.  Each query of $I_W$ represents fetching the word at the start of a line.  A modification of $A$ is like user modifying the text, and a modification of $W$ is like the window being resized.
I want to be able to repeatedly do queries and modifications of $A$.  A modification is the insertion, deletion, or modification of an integer in $A$.  A query is a request of $I_W[k] \in \mathbb N$, defined as

$I_W[0] = 0$
$I_W[k+1] = \text{ the biggest } z \text{ s.t. } \sum_{I_{k} \le j < z} A[j] \le W$

To describe $I_W$ another way, suppose $A$ is $[5, 3, 4, 6, 5, 1, 1, 4, 4, \cdots]$ and $W = 9$.  Then split $A$ into initial segments whose sums are $\le W$, so $[[5, 3], [4], [6], [5, 1, 1], [4, 4], \cdots]$, then $I_W(k)$ is the sum of the lengths of the first $k+1$ splits; that is, $I_W = [0, 2, 3, 4, 7, 9, \dots]$.
I'm looking for an algorithm and datastructure that would allow for linearithmic preprocessing on $A$ and something like logarithmic time modifications and queries.  I'd also like to be able to handle changes in $W$ quickly but that can somewhat be handled with threads and software design so it isn't as important.
The fact that even tiny modifications of $A$ can have a tiny or drastic impact on $I_W$ is making this fairly challenging for me.

I think you can handle single-word modifications in $O(d \log n)$ time, where $d$ (density) is the maximal number of words in a line, which is hopefully small for any reasonable $A$ and fixed $W$.
Let's take one of your sentences as an example. We want it to be wrapped with $W = 30$ characters like this:
I'm looking for an algorithm
and datastructure that would
allow for linearithmic
preprocessing on A and
something like logarithmic
time modifications and
queries.

First, let's find all possible lines. This can be done greedily in $O(n)$ using two pointers scanning through $A$. If one of these lines ends where the other begins, we connect them.

The path from node $1$ to the root of the tree represents $I_W$.
Now let's remove "an" from the first line, forcing all other lines to shift:
I'm looking for algorithm and
datastructure that would allow
for linearithmic preprocessing
on A and something like
logarithmic time modifications
and queries.

But here's one nice thing about the tree: any single-word change can only affect $O(d)$ edges. We find these edges by re-running the same pre-processing on a small window around the changed word. In our case, the changes are:

Edge 1-6 removed
Edge 4-8 removed
Edge 1-7 added

So, we need to be able to do these operations efficiently:

Add new edge into the tree
Remove existing edge from the tree
Find $k$-th ancestor of a given node.

All these operations can be done in $O(\log n)$ via Euler tour technique. I won't describe its implementation in detail, but feel free to ask a separate question about it.


Constant terms at each level of a recursion tree In CLRS, exercise 4.4-5 the following question is asked:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$

In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$
and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.
Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$
and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?

For each specific level $i$, it is true that the cost is $(3/2)^i n - O(1)$. However it would be misleading to state this in general. Suppose for example that the cost at level $i$ were $(3/2)^i n + 2^{2^i}$, and that there were $\log n$ levels. The dominant factor in the total cost would be the "constant" term.
However, in your case, you can say that the cost at level $i$ is at most $(3/2)^i$, which gives you the required upper bound.


How Reduction works in proving NP-Hard? A problem $X$ is $NP$-Hard if for all $Y \in NP$, $Y \leq_P  X$. Further, if a problem $Z$ is $NP$-Complete, and $Z \leq_P  X$, then I can prove (rather mechanically) that $X$ is $NP$-Hard.

I also found that, for a given X, say TSP, to prove it is $NP$-Hard, we often find a ($NP$-Complete) Z say $HAM-CYCLE$ (Hamiltonian-Cycle), and try to show that $HAM-CYCLE$ can be reduced to a $TSP$ in polynomial time.

My confusion is, why don't we try to show that for each instance of $TSP$, there exists a corresponding instance of $HAM-CYCLE$. Specifically, what if there exists an instance of $TSP$, for which there is no corresponding instance in $HAM-CYCLE$! In this case, how can the prior knowledge about the hardness of $HAM-CYCLE$ help in inferring on TSP's hardness!

Note: I also had similar concerns with proving $NP$-complete class. However, since all $NPC$ are also $NP$, I felt, similar reduction of a known NPC problem to a given problem, say Q, works. However, for $NP$-hard case, a given problem X need not to be $NP$ at all.

Apparently, you are expecting the reduction between any two $\mathsf{NP}$-complete problems $X$ and $Y$ to be a one-to-one map (e.g., a bijection). The idea of a reduction, however, is irrelevant to having instances "correspond" to others. What reductions do give us is a hardness relation between problems (and not between individual instances). If $A$ and $B$ are problems and $A$ is reducible to $B$, then we expect $B$ to be harder than $A$; the idea is that, if there is an efficient algorithm which solves $B$, then we can also solve $A$ by reducing it to $B$ and running said algorithm. Completeness, then, corresponds to the notion of hardness equivalence: $A$ is reducible to $B$ and $B$ is reducible to $A$; that is, if $A$ is hard (resp., easy), then so is $B$, and vice-versa.

To give an example why we cannot generally expect reductions to be injective, surjective, or even bijective, let again $X$ to be $\mathsf{NP}$-complete and consider the problem $Z = \{ (0, x) \mid x \in X \} \cup \{ (1, y) \mid y \in \{ 0,1 \}^\ast \}$. Naturally, we can reduce $X$ to $Z$ by mapping each instance $x$ of $X$ to $(0,x)$; this does not give us a surjective map. Further, note $Z$ is also reducible to $X$: map $(0,x)$ to $x$ and $(1,y)$ to $x'$ where $x' \in X$ is a fixed (i.e., hard-coded) instance. This reduction is surjective, though not injective. As you can see, there is really no relation between what we expect from a reduction and injectivity or surjectivity.


Can I construct a Turing machine that accepts only its own encoding? Is the set $S$ = $\lbrace M \mid M \text{ is a Turing machine and }L(M)=\lbrace \langle M\rangle\rbrace\rbrace$ empty?

In other words is there a Turing machine $M$ that only accepts its own encoding? What about a Turing machine that rejects only its own encoding?

The answer is yes.

See Kleene's second recursion theorem: for any  partial recursive function $Q(x,y)$ there is an index $p$ such that $\varphi_p \simeq \lambda y.Q(p,y)$.

Suppose that $M$ is a Turing machine that on input $\langle x,y \rangle$ accepts if and only if $x=y$; then, by the above theorem, exists $M'$ such that $M'(\langle y \rangle) = M(\langle M' , y \rangle)$ and we have $L(M') = \{ \langle M' \rangle \}$.

P.S. you can find a very clear proof of the recursion theorem in Chapter 6 of the M. Sipser's book "Introduction to the theory of computation".


What data is stored in the symbol table for a number token? I'm reading the Dragon Book. The following is from the start of Section 3.1.3.

  When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases additional information about the particular lexeme that matched. For example, the pattern for token number matches both 0 and 1, but it is extremely important for the code generator to know which lexeme was found in the source program. Thus, in many cases, the lexical analyzer returns to the parser not only a token name, but an attribute value that describes the lexeme represented by the token; the token name influences parsing decisions, while the attribute value influences translation of tokens after the parse.

From what I understand the symbol table stores the variable name and the some details like the type, scope etc. So if a character 0 is found by the lexical analyzer, it matches the pattern for a number so it uses the token name number so the token becomes <number, attrb>.

As per the snippet I have cited above, I don't understand what data is stored in the symbol table for numbers. Is the value of the number stored in the symbol table?

Typical lexers will return a sequence of pairs, where the pair consists of the token type and an optional value. For a token such as 12345, the token type will be something like "number" and the value will be 12345.  If the lexer only emitted the information that there was a numeric constant in the input, then the following phases of the parser would have no way to know which number it was, and that is obviously important.

I don't understand why you started talking about the symbol table in the end of your question, and I think you may be confused.  The quotation you gave says nothing at all about the symbol table, which usually belongs to a later phase of compilation. A symbol table maps symbols (that is, names) to values.  The quotation in your question is about tokens, not symbols.  Tokens are not usually stored in a symbol table, and there is no reason to store numbers in a symbol table.  Typically a parser will have a stack, and will push whole tokens onto the stack, and pop them off again as needed.


what is a compiler intrinsic function? I'm trying to understand what a compiler intrinsic function is. I did find a wiki article but I'm still kind of fuzzy on what it is exactly. If someone could provide a few concrete examples that would definitely clarify the issue.

Any help is appreciated.

One example of compiler intrinsic functions is the floating point math functions that are part of the standard C math library.  On CPU architectures with on-chip support for floating point trigonometric functions like sine and cosine, the compiler might replace the function calls with a series of instructions that achieve the same result but using the available CPU instructions instead.

Another example is replacement of calls to C low-level memory copying functions such as memcpy and memmove.  These might be implemented directly using SIMD instructions if available, copying the blocks of memory many times faster.

Note that "... an intrinsic function is a function available for use in a given programming language whose implementation is handled specially by the compiler." This is in contrast to operators like addition and subtraction; the compiler would be expected to implement floating point arithmetic operators even without an FPU since the C language specification demands it. Intrinsic functions go further and implement things that are properly part of the C library of hosted implementations.


Maximal subsets of a point set which fit in a unit disk Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$.
Moreover, each $P_i$ is maximal, i.e., no unit disk can cover a subset of $P$ that is a strict superset of $P_i$. Visually speaking, if we move a unit disk that covers $P_i$ to cover a point not in $P_i$, then at least one point which was inside that disk will become uncovered.
Here is an example:

In the above figure, there are three maximal subsets.
I don't know whether this problem has a name or was studied before, but here are my questions.

Can $k$ be exponential with respect to $n$?
If not, then can we find those maximal subsets in polynomial time w.r.t. $n$?

I think that there are exponentially many such subsets because of the following argument:
Suppose that the points are centers of some disks with radius $1/2$. If a subset of such points fit in a unit disk, then they form a clique. Since there are exponentially many cliques in a set of disks, then there should be exponentially many maximal subsets of this particular set of points that fit into a unit disk.

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by all intersections of unit disks, centered at points from the set $P$. This subdivision contains vertices (= intersection points), edges (= circular arcs) and faces (= pieces of the plane, where the function $f$ returns the same value). We'll say that these faces are labeled by this value.
We'll assume that the planar graph, defined by this subdivision, is a 4-regular one - it's a common assumption, meaning that all the points in $P$ are in general position (each intersection point belongs to exactly two circles). An example of such subdivision for $n=3$ is below, where the label for each face (including the external one) is shown in red color.

As far as I understand your maximal subsets $P_i$ can be associated with such faces of this subdivision, which have labels larger than all labels of their neighboring faces. It's kind of static interpretation of your "moving disk" semantics, which you used in your definition of the maximal subset.
The subdivision will contain as many faces as possible in the case when all the unit circles pairwise intersect each other. It can be shown, that in this case:

number of vertices is $n(n-1)$
number of edges is $2n(n-1)$
number of faces is $n(n-1)+2$

So, answers to your questions will be:

No, the number $k$ of maximal subsets is $O(n^2)$, because it can't be more than the number of all faces.
Yes, all the maximal subsets can be found in $O(n^3)$ time by naive scanning algorithm.

As for name of this problem - it looks like it may be related to some variations of the Unit Disk Cover problem.


NP-hardness does not imply lower bound, strictly speaking? A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.

Hardness is often intuitively explained as a lower bound. But it isn't, strictly speaking. For the sake of the argument, assume P=NP. Now the definition becomes:

A problem is P-hard iff every P problem can be polynomially-time reduced to it.

Because the above definition uses the polynomial-time reduction, the overall running time is polynomial (reduction + solving the resulting problem), no matter how easy is the resulting problem. Hence we could get an absurd result: a problem, which runs in constant time (hence lower bound is constant), is P-hard.

The definition makes total sense if we assume that NP>P. Do people assume NP>P?

The same question arises for the definition of PSPACE-hardness, where book authors use polynomial-time reduction, rather than something strictly easier than PSPACE.

I guess the answer to this question is simply "yes", sorry for the rant.

Yes, if P = NP then any decision problem is NP hard as long as there is one problem instance where the answer is "YES" and one where the answer is "NO".

Just check the definition of NP-hard (and check why problems where every instance has the answer YES or every instance has the answer NO are not NP-hard by that definition).


Should O(1) necessarily stand for a non-zero constant? I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant time, in essence, a non-zero constant time. Is there a broad acceptance that a function converging to zero belongs to $o(1)$ and not to $O(1)$?

$O(1)$ does not represent time. It represents a class of functions, which could be used to measure time, space or literally anything else.

$f(x)\in O(1)$ if, and only if, there is a constant $c$ such that $f(x)<c$ for all large enough $x$. There's no requirement that $f$ must be eventually non-zero. $f(x)\in o(1)$ if, and only if, $\lim_{x\to\infty} f(x) = 0$ so, in particular, for all large enough $x$, $f(x)<1$. Therefore, $f(x)\in O(1)$.


Reduction from 4COL to 3COL I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$.

Is there any elementary proof to do it?

Your question is answered in a blog post of Lance Fortnow. Solutions are given by Fortnow and by Lovász.


How does 0 have two values in one's complement? It is said that in 2's complement 0 has only one value, while in 1's complement both +0 and -0 have separate values. What are they?

In 1's complement you just invert all the bits.

Consider these 2 examples (assuming 8 bits):

$4 = 00000100$,  so $-4= 11111011$
$0 = 00000000$, so $-0=11111111$.

So you have 2 ways to represent the number 0

In 2's complement you add 1 to the 1's complement representation of the negative number

$-4$ that in 1's complement was $11111011$ becomes $11111100$
$-0$ that in 1's complement was $11111111$ becomes $00000000$ same as 0

So you have just one way to represent the 0 in this case

As you can see from the examples the difference is that:

in 1's complement, with 8 bits you can just express numbers from $-2^{7}+1$ to $2^7-1$ (from -127 to 127)
in 2's complement with 8 bits you can express numbers from $-2^{7}$ to $2^{7}-1$ (from -128 to 127), so one more number


Why aren't we researching more towards compile time guarantees? I love all that is compile time and I love the idea that once you compile a program a lot of guarantees are made about it's execution. Generally speaking a static type system (Haskell, C++, ...) seems to give stronger compile-time guarantees than any dynamic type system.

From what I understand, Ada goes even further with regards to compile time checking, and is able to detect a greater range of bugs ahead of execution. It's also considered fairly safe, given that, at some point in time, it was chosen for delicate fields (when programming errors may cost human lives).

Now, I wonder: if stronger static guarantees, leads to code that is more documented and safe, then why aren't we researching more in that direction?

An example of something that seems to be missing, would be a language that instead of defining a generic int type that has a range determined by the number of bits of the underlying architecture, one could have ranges (in the following example Int [a..b] describes an integer type between a and b included):

a : Int [1..24]
b : Int [1..12]
a + b : Int [2..36]
a - b : Int [-11..23]
b - a : Int [-23..11]

or (taking this from Ada):

a : Int [mod 24]
b : Int [mod 24]
a + b : Int [mod 24]

This language would select the best underlying type for the range and would perform compile time checking on the expressions. So that, for example, given:

a : Int [-3..24]
b : Int [3..10]

then:

a / b

will never be not defined.

This is just an example but I feel like there's a lot more that we can enforce at compile time. So, why there seems so little research on this? What are the technical terms that describe this idea (so that I can find more informations on this topic)? What are the limits?

I am not in a position to tell how much more research should be done on the topic, but I can tell you that there is research being done, for example the Verisoft XT program funded by the german government.

The concepts which I think you are looking for are called formal verification and contract based programming, where the latter is a programmer-friendly way of doing the first. In contract-based programming you first write your code as normal and then insert so called contracts into the code. A readily usable language which is based on this paradigm is Spec# by Microsoft Research, and the functionally similar but slightly less pretty Code Contracts extension for C# which you can both try out online (they also have similar tools for other languages, check out rise4fun). The "int with range type" you mentioned would by reflected by two contracts in a function:

Contract.Requires(-3 <= a && a <= 24);
Contract.Requires( 3 <= b && b <= 10);

If you want to call that function, you then have to use parameters which are ensured to meet these criteria, or you get a compile time error. The above are very simple contracts, you can insert almost any assumption or requirement about variables or exeptions and their relation which you might think of and the compiler will check if every requirement is covered by either an assumption or something that can be ensured, i.e. derived from the assumptions. That is why where the name stems from: The callee makes requirements, the caller ensures that these are met - like in a business contract.

Under the hood, code contracts are usually combined with knowledge about the inner workings (operational semantics) of the programming language into a list of verification conditions. This list represents basically one big logical proposition $P(x_1,x_2,...,x_n)$ with $n$ free variables - the inputs of your program. If the proposition $P$ is true for all possible variable assignments, then the program is considered correct. To check whether or not this is the case, an SMT Prover is used. From the CS side, those two are the critical parts of the process - the generation of verification conditions is tricky and SMT is an either NP-complete or undecidable problem, depending on the considered theories. There is even a competition for SMT solvers, so there certainly goes some research into this. Additionally, there are alternative approaches to using SMT for formal verification like state space enumeration, symbolic model checking, bounded model checking and many more which are also being researched, albeit SMT is, afaik, currently the most "modern" approach.

Regarding the limits of the general idea:

As previously stated, proving the correctness of the program is a computationally hard problem, so it might be possible that the compile time check of a program with contracts (or another form of specification) takes really long or might be even impossible. Applying heuristics which work well most of the time is the best one can do about it.
The more you specify about your program, the higher gets the probability of having bugs in the specification itself. This can lead to false positives (the compile time check fails even though everything is bug-free) or the false impression of being safe, even though your program still has bugs.
Writing contracts or specifications is really tedious work and most programmers are too lazy to do it. Try writing a C# program with code contracts everywhere, after a while you will think "come on, is this really necessary?". That is why formal verification is typically just used for hardware design and safety critical systems, like software controlling airplanes or automotives.

One last thing worth mentioning which does not quite fit the above explanation is a field called "Implicit Complexity Theory", for example this paper. It aims at characterizing programing languages in which each program you can write falls into a specific complexity class, for example P. In such a language, each program you write is automatically "ensured" to be of polynomial runtime, which can be "checked" at compile time by simply compiling the program. I do not know of any practically usable results of this research, however, but I am also far from being an expert.


What is the difference between regular trees and phylogenetic trees in terms of graph theory? If I am not mistaken, a tree is any graph that does not contain cycles.
However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you are given a phylogenetic tree with $n$ leafs, and then you run some algorithm that can do something trivial like simple traversing of the tree, and then you get a $O(n)$ time bound, without saying anything about the number of internal nodes.
However given a regular tree with $n$ leafs, the total number of internal nodes can be infinite.
For example the following is a tree with one leaf (two if you consider it to be rooted) and infinite number of internal nodes:

So what are phylogenetic trees that you can express the running time of various algorithms in terms of the number of leafs, even though your algorithm actually traverses the entire phylogenetic tree?

Phylogenetic trees are usually "full binary trees", that is rooted trees in which every internal node has exactly two children. A full binary tree having $n$ leaves has exactly $2n-1$ nodes.


Is there an intuitive proof for the existence of hard functions? I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by a circuit $C$ of size $\frac{2^n}{10n}$"

Can someone give a more intuitive proof of this than the one presented there?

For example he proof there at one point claims with little justification that there are at most $2^{0.92^n}$ circuits of size at most $\frac{2^n}{10n}$. Why? I couldn't reproduce this ``0.92" thing!

It seems that one even improve this theorem to  higher lower bound of $\frac{2^n}{n}$. Can someone kindly help do that? How much up can one get this?

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. We then compute the maximal $S$ such that $C_S < 2^{2^n}$, and conclude that there must be a function that cannot be computed by a circuit of size at most $S$. The answer is $S = O(2^n/n)$, and we usually really don't care about the hidden constant; we tend to abstract away constants in complexity theory.

The same argument shows, with very small modifications, that a random function has circuit complexity $\Omega(2^n/n)$ in expectation and with high probability.

How about an explicit function with complexity $\Omega(2^n/n)$? This is a difficult open problem. The best lower bounds we have for explicit functions are $\Omega(n^3)$ for Andreev's function (see Komargodski–Raz–Tal for the best result in this direction). I am told that obtaining anything better than $\Omega(n^3)$ would be difficult due to the natural proof barrier.


How to define (logically) the complement language? I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language:

$$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{l}M \text{ is a Non-Deterministic TM,}\\ \text{and it has an accepting run on }w\text{ of length }\leq |w|\end{array}\right\}\,.$$

When I've tried to find $L$-complement I did it like this:

  M isn't an NDTM OR it doesn't have an accepting run on $w$ of length $> |w|$.

My way of thinking is to change each one of the quantifiers. Is that OK? Someone can write the logic behind that (I want to understand for other cases as well, this language isn't critical right now)?

Thanks!

You aren't exactly correct in your example because of the redundant negation of the $\leq$ sign. In the most general sense, we always have:

$$\neg (x_1 \land x_2\land ...\land x_n)=(\neg x_1) \lor...\lor (\neg x_n)$$

Meaning: NOT (A AND B AND C...) equals (NOT A) OR (NOT B) OR (NOT C)...

In your case, we have two conditions with an AND between them:

M is a Non-Deterministic TM
M has an accepting run on $w$ of length $\leq |w|$

Finding the complement of the language requires negating these conditions, and therefore getting the language where either:

M isn't an NDTM, OR
M is an NDTM , BUT, it doesn't have an accepting run on $w$ of length $\leq |w|$

Notice the difference in the negation of the second condition - we changed it from having a run satisfying a certain property to not having a run satisfying the same original property.

From my experience, usually in these kinds of questions you have a language composed of TMs/Automata/etc' fulfiling a certain condition, and in such cases the negation would be everything which isn't a TM/automaton/etc', PLUS everything which is of the correct "type" but doesn't fulfill the original given condition.


Algorithm for finding all the combinations on a boolean array I have to design an algorithm to do the next task:

I have one array of booleans. For example:

Array:   [0 1 0 0 1 0 1 1]

I want to obtain all the existing combinations of 1's, having in mind that it is allowed only a maximum of one 0 between 1's.
For example, in the previous case, we would have the outputs (I am using the indices now):
[1] and [4,5,6,7].

But also it should include [4], [6], [7], [4,5,6], [6,7].

Another example:

Array:   [0 1 0 1 0 1 0 0 1]

The output would be: [1], [3], [5]. [8], [1,2,3], [1,2,3,4,5], [3,4,5].

Can you imagine any approach to solve this? The combination explosion could be quite big.

Thank you very much in advance.

The pattern you're trying to match is regular and can be matched by the regular expression 1(0?1)*.  A good strategy would be to convert the binary array to a string and do regular expression matches over substrings of it.

There aren't an exponential number of bit strings to check.  For a string of length $n$, you only have to check 1 string of that length.  You then check 2 strings of length $n - 1$, 3 strings of length $n - 2$ and so on.  In total there are $n(n+1)/2$ strings to check.


Complexity of cubic graph decomposition I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. Since a cubic graph has a decomposition into edge-disjoint claws if and only if it is bipartite.

  What is the complexity of deciding the existence of decomposition of a cubic graph into vertex disjoint claws? Is it NP-complete?

In the former problem, we partition the edge set into edge-disjoint claws while in the later one we partition the vertex set into vertex-disjoint claws.

It turns out that the problem is eqivalent to the 1-perfect code problem in cubic graphs. Therefore, Deciding the existence of decomposition of a cubic graph into vertex disjoint claws is NP-complete.


LTF circuits and $AC^0$ Do we know if all of $AC^0$ can be captured by polynomial sized depth $2$ LTF circuits? (with or without polynomially bounded weights).

For any vector $w \in \mathbb{R}^n$ and any number $c \in \mathbb{R}$ we define the LTF (x) gate as the function, $\{0,1\}^n \rightarrow \{0,1\}$ such that $LTF(x) =0$ if $c + \vec{w}.\vec{x} \leq 0$ or else $LTF(x) = 1$.

I doubt that AC0 can be captured by constant depth threshold circuits, but this hasn't been proved. In the case of small weights, perhaps existing methods suffice to rule out all of AC0 being captured by depth 2 threshold circuits. See Razborov's survey for several pointers, include exponential lower bounds for functions which, unfortunately, are beyond AC0

In the case of unbounded weights, we don't have any superpolynomial lower bounds. The best known lower bound for unrestricted depth two threshold circuits due to Kane and Williams, is $\Omega(n^{3/2})$.


Proving unsatisfiability of a propositional formula I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated.

I have a function which for a given formula $F$ and a given assignment $A$ checks if both $A$ and $\overline A$ evaluate to the same truth value. It looks like this:

boolean checkSymmetry (Formula F, Assignment A) {

    if (evaluate(A) == evaluate((not A)))
        return true;
    else
        return false;
}

Now I want to use method checkUnsatisfiability to check if a given formula $F'$ is "symmetric" as described above. Something like:

boolean checkSymmetryWithCheckUnsatisfiability (Formula F) {

    /* The checkSymmetry problem is reduced to the checkUnsatisfiability problem to which I have a solution. */
    boolean result = cleverUseOfCheckUnsatisfiability(F);

    // result is true if Formula F is "symmetric", otherwise false
    return result;
}

All right, so there is no way to reduce checkUnsatisfiability to checkSymmetry since that would mean reducing an NP-Complete to an easy one which is impossible unless $P = NP$, thanks to @xavierm02 and especially @chi for clarifying this.

Since checkSymmetry is easy and checkUnsatisfiability is hard It should be possible to reduce checkSymmetry to checkUnsatisfiability in polynomial time, is that correct? If so, how would I do that?

If we take the problem precisely as stated, the answer is negative, assuming $P\neq NP$. Indeed, checkSymmetry is trivially implementable in polynomial time, since it takes as input both the formula $F$ and the assignment $A$, so it can check those. Hence, if a reduction existed, that would imply that unsatisfiability is polynomially decidable, hence $P=NP$.

(Update: my guess below was not what the OP wanted, but I am leaving it here anyway.)

However, I guess your checkSymmetry is meant to take only $F$ as input, and check something equivalent to the validity of $F \iff \bar F$, where $\bar F$ is $F$ with every atomic formula negated.

Then, we can reduce checking validity of any propositional formula to checking symmetry.

Given any $F$, take $G := P \land \lnot F$, where $P$ is an atomic formula not occuring in $F$. We have
$$
\models F \iff \models (G \iff \bar G)
$$

($\Rightarrow$)
Assume $\models F$: we deduce immediately $\models \bar F$.

We need to prove that
$$
\models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F)
$$
but we know $F$ and $\bar F$ are true for all assignments, so the above simplifies to $\models \bot \iff \bot$ which is trivial.

($\Leftarrow$) Assume $\models G \iff \bar G$.
We need to prove $\models F$.
Let $A$ be an assignment for $F$. Extend it to $B:=A[P\mapsto \top]$.
We have
$$
B \models G \iff \bar G
$$
which is
$$
B \models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F)
$$
which, thanks to the choice of $B(P)$ simplifies to
$$
B \models \lnot F \iff \bot
$$
hence $B \models F$, and we also have $A \models F$ since $P$ does not occur in $F$.


What uses have been proposed for overlaid skewed associativity? In "Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB" (2004; PDF), André Seznec proposed using overlaid ways with different indexing functions with guaranteed avoidance of bank conflicts. This mechanism allows TLB look-ups for multiple page sizes to be done in parallel without the overheads of CAM-based TLBs or the capacity mis-match issues of a separate TLB for each size. (TANSTAAFL: This comes at the cost of reduced associativity for each page size and does not work well with a wide range of page sizes where less significant bits can not be used by all page sizes to determine the bank.)

I have termed multiple indexing functions sharing a single memory array "overlaying", though there might be a better name.

Mohsen Sharifi and Behrouz Zolfaghari proposed using multiple indexing functions with a single bank to reduce conflict misses ("YAARC: yet another approach to further reducing the rate of conflict misses", 2007, PDF)

"Skewed Compressed Caches" (Somayeh Sardashti et al., 2014; PDF) exploits unified storage to avoid conflict misses when a superblock of memory has variable compressibility.

(The merged-associative TLB proposed in Arkaprava Basu's PhD dissertation "Revisiting Virtual Memory" (2013; PDF 6.5MB) allows the OS to specify a page size by virtual address ranges that exclusively use that page size so that all banks of the TLB can be indexed in parallel. This does not overlay the banks, though it could be trivially extended to do so; similarly page-size prediction could be used (as probably presented in "Prediction-based superpage-friendly TLB designs", Misel-Myrto Papadopoulou et al., 2015, showing the similarity to hash-rehash).)

Despite the fact that Seznec proposed the idea over a decade ago, I have not found other explorations of its utility. Are there any other proposed uses for this mechanism of overlaying ways?

The following possible uses come to mind, though I am not aware of any academic exploration of these ideas.
Way Dueling
One possible use is to extend the range of set-dueling. Presented in Moinuddin K. Qureshi et al.'s "Adaptive Insertion Policies for High Performance Caching" (2007), the "Set Dueling mechanism dedicates a few sets of the cache to each of the two competing policies and uses the policy that performs better on the dedicated sets for the remaining follower sets." By linking policies with ways in an overlaid skewed associative cache the number of entries monitored can be extended without sacrificing capacity available to a given policy (though the associativity linked to a policy would be lower).
The number of policy-bound entries in a way could also be adjusted dynamically to trade off training sensitivity with associativity of the preferred policy. It is not clear if competition for the same entries would also have benefits; the degree of sharing of monitored entries could also be adjusted dynamically.
Virtual Non-Temporal Cache
With overlaid skewed associativity, it could be practical to associate one or more ways with non-temporal access and use indexing functions for such ways which induce conflicts. For example, by simply dropping bits 6..11 of the block number (indexing by bits 0..5,12..N), a 64-block region would conflict with itself 64-times in a stream. (By XORing specific middle and least significant bits, streams with power-of-two block-strides could be allocated densely while still providing self-conflict across groups of blocks.)
Such would have the advantage over a dedicated non-temporal cache of allowing the capacity to be used more flexibly and the advantage of potentially lower semi-reserved capacity compared to LRU placement of non-temporal data in a traditionally indexed cache (where effectively an entire way worth of data would be allocated to a stream of non-temporal data).
Since different ways (and different portions thereof) could have different degrees of inducing conflicts and less conflicting ways could be selectively used, the amount of capacity allowed to a stream could be somewhat flexible and conflicts between streams might be more easily managed.
While conflict-inducing indexing could be used with isolated ways, overlaying would allow capacity to be used more flexibly and allows conflict between ways to push out data that will not be re-referenced.
Variably aligned Blocks
By associating different ways with different alignments of cache blocks, larger blocks can be more practical when there is significant spatial locality but the chunk of data that is accessed together does not start at a highly aligned address. Such could facilitate the use of larger blocks with less unused capacity. Larger blocks can reduce tag overhead and increase the accuracy of way prediction (or the utility of way memoization).
Such might be especially useful for instruction caches (benefitting more from spatial locality and being more friendly to way prediction/memoization), especially branch target instruction caches. Certain trace-oriented pre-decode optimizations might be made more practical by reducing the number of entry points within a cache block. A smaller (faster, more energy-efficient) portion of an instruction cache could be preferentially used for branch targets, avoiding redirection delay like a BTIC but allowing the capacity to be used for non-branch target blocks.
(For data caches, unaligned storage might be useful for something like a signature cache, reducing the disadvantage of non-CAM tags.???)
Similarly, a branch target instruction cache placed after the instruction cache could exploit variable alignment of function entry points without the tag overhead of using multiple smaller blocks.
Stride-based Data Mapping
Similar to using ways to map to different alignments, it would also be possible to have different ways use different subblock strides. For example, a way could map data within a block such that alternating words are excluded, not only increasing utilized capacity when stride-of-two accesses are used but also potentially facilitating fixed-stride SIMD loads and stores.
It might even be practical to support configurable power-of-two strides as long as the stride does not change often.
(A data trace cache might benefit from both supporting different alignments and different chunk compositions (e.g., 32-bit address offset/compressed address vs. 64-bit address, address only vs. address plus N bytes of data). This ties in with intra-block NUMA.)
Binding storage-type to way groups
In a unified cache, one group of ways could be dedicated to instructions and another to data. Such grouping of ways would facilitate lower associativity in at least initial look-up.
This could also be applied to metadata interpretation, different ways storing different types of metadata. For example, some ways could use ECC (requiring read-modify-write on sub-word stores) and some use parity (for lower-overhead sub-word stores, but lower reliability); such could interact with storage reliability where, e.g., ECC-using blocks in high reliability SRAM might allow greater voltage reduction and parity-protected ways might only allocate clean blocks to less reliable SRAM arrays.
Way-based block size
While conventional non-overlaid caches could associate a tag with a pair of storage blocks, using additional ways dedicated to larger blocks would tend to require fewer tag checks. Skewed indexing, especially when overlaid, would reduce conflict increase from clumping of cached data have more spatial locality. In any case, extra tags could be used for dataless inclusion or other metadata, though the increased flexibility of allocation with overlaying would tend to increase opportunities for such alternative uses.
Variable Characteristics of Storage
By overlaying ways, a portion of each way can be mapped to a section of cache which provides faster (or more energy-efficient) access or different amounts of metadata (different types of metadata was mentioned earlier).
By increasing the independence of cache properties and data address via overlaid skewed associaitity, more direct indexing could be used while still supporting differences in characteristics of specific storage locations.
While not as flexible in allocation as a traditional Non-Uniform Cache Architecture (which uses a layer of indirection), such might make NUCA techniques more applicable to L1 caches. (The problem of scheduling dependent operations given variable L1 cache latency would still need to be addressed. In addition, the aliasing issues of L1 skewed associativity would have to be handled.)
(The way indication itself can provide some metadata when ways are reserved for or biased toward specific uses or policies.)
It might also be practical to have portions of the cache (whether specific ways or sections of various ways) use subblock NUCA where a portion of blocks have faster access (e.g., to accelerate pointer-chasing code). While always using fast subblock allocation (with different subblocks being selected by way and/or address) could be implemented in a somewhat straightforward way, variable allocation of fast storage (e.g., where 64-byte blocks might be mapped to four fast 16-byte storage units, one fast storage unit and three slow ones, or four slow storage units) would seem to be difficult.
Such separation could be accomplished in non-overlaid cache by the same association of way/address with cache characteristic, but flexibility of allocation would be lower.
Further Disconnecting Associativity and Capacity
With overlaying, conflict increasing squeezing of portions of ways can be mapped to different storage sections in different ways and accesses from different ways can compete for a given entry.
Partial overlaying provides another dimension of design flexibility. For example, a two-way associative cache might map one way such that half maps to an isolated section and half to an overlaid section and map the other way with its own isolated section (and the common shared section). This kind of partial overlapping might be useful for a Knapsack-like cache ("Knapsack: A Zero-Cycle Memory Hierarchy Component", Todd M. Austin et al., 1993) where a part of the storage could be dedicated to a restricted caching while another part can be used for other accesses as well (e.g., a two-way associative section could be used traditionally while also allowing the Knapsack region to be larger and somewhat sparse in the higher addresses; the amount of contention and the replacement preferences could be somewhat flexibly designed [some similarity might be noted to Brannon Batson and T. N. Vijaykumar's "Reactive-Associative Caches"]).
Isolated ways can provide separation of associativity and capacity by having some ways be smaller than others. However, overlaying provides slightly more flexibility in allocation of capacity. With isolated ways, a given block will always be in a higher conflict section (though this can be compensated by increasing the associativity of the smaller section).
Potentially Greater Virtual Machine Isolation
By overlaying and using different indexing functions for different virtual machines, cache capacity might be more readily provided to virtual machines with less side channel information being communicated.
Traditional skewed associativity with per-VM indexing adjustment would provide most of this benefit, but overlaying provides a little more flexibility in placement and in what mappings can conflict for different pairs of virtual machines.
Multithreading Conflict Containment
Partial overlaying could be used to isolate a portion of the data associated with a thread while still providing substantial capacity sharing. Such would provide more flexible allocation than assigning a traditional way or ways to a thread-specific storage area.
Partial overlaying would facilitate having higher associativity in a subset of cache, which could be advantageous in storage shared by more threads or used for allocations more likely to induce conflict misses or for which conflict misses are more expensive.
In a clustered design, overlaying could be useful for biasing placement to reduce inter-cluster communication when threads are biased or exclusively allocated to particular clusters.
Way Prediction Implications
While skewed associativity may increase the accuracy of partial-tag-based and recency-based way prediction (because spatially local blocks are likely to be mapped to different indexes for different address regions), overlaying may provide a slight further benefit.
(Likewise, biasing allocation to improve way prediction should increase the miss rate less with skewed associativity and especially overlaid skewed associativity than with simple modulo indexing.)
Defect and Block-locking Tolerance
While not a mechanism, it might be worth noting that using overlaying would reduce the impact of excluding certain blocks from allocation choices. While traditional skewed associativity increases conflict resistance in such cases, overlaying would provide a further benefit.
Similarly, locking a chunk of cache could provide the implementation simplicity of traditional way locking with less reduction in effective associativity. (As a side note, mapping a chunk of cache to a specific address to form a scratchpad memory would free the associated tag memory for other uses. For example, half normal size blocks could be supported for part of the remaining cache; overlaid skewed associativity might facilitate flexible allocation of small blocks.)
Reduced indirection overhead for NUCA
Using overlaying would allow different addresses to map to the same block, potentially avoiding the traditional indirection of traditional NUCA while still allowing substantial flexibility in allocation of cache entries into faster storage. Lack of indirection would facilitate placing tags closer to data clusters, at least for the faster storage area (it may be desirable to co-locate all tags to provide faster miss determination, though a cache shared by multiple cores or even just multiple access paths (e.g., instruction vs. data) might have distinct fast storage with associated tags). Even if indirection is used, overlaying would reduce the costs of less general indirection, reducing metadata storage overhead and potentially access latency.
A fixed but different slice for each way would have similar benefits in terms of allowing different addresses to be placed in fast storage with quick lookup, but overlaying increases allocation flexibility.


Applying Johnson's algorithm on undirected graph with negative edge weights Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-negative.

If we consider the undirected graph as bi-directed, then any negative-weight undirected edge will create a negative cycle in the bi-directed graph, and violate the prerequisite of Johnson's algorithm.

Is there any altered version of Johnson's algorithm can handle such scenario?

-- update 2017/12/30 --

Sorry, I forget to mention an additional constraint for the path: the path should be simple, which means one edge could only be travel for once.

Shortest simple paths

Finding the length of the shortest simple path is NP-hard, so there is no efficient algorithm.

Shortest paths (not necessarily simple)

The original version of the question didn't include the requirement that the path be simple.  Below I include my answer to that version of the question, for posterity:

Decompose the graph into connected components.  Solve the problem separately for each connected component.

If there is an edge with negative weight in the component, then for all pairs of vertices $u,v$ in the component, the distance from $u$ to $v$ is $-\infty$.  So, you can output $d(u,v)=-\infty$ for all pairs $u,v$ in the component.  You don't even need to run Johnson's algorithm.

(Why is that answer correct?  Well, suppose the edge $(a,b)$ has negative weight.  Then consider a path $u \leadsto a \to b \to a \to \cdots \to b \leadsto v$.  Such a path can have arbitrarily small length, by traversing the cycle $a \to b \to a$ sufficiently many times.)

If there is no edge in the component with negative weight, you can use Johnson's algorithm to compute the distance between each pair of vertices in the component.  Johnson's algorithm on this component will work fine, since this component has no negative-weight edges.

Finally, the distance between any two vertices that are in different components is $+\infty$, since there is no path between them.


Determine if items can be ordered grouping two simultaneous criteria For a set of items with two properties, how can it be detemined if they can be ordered in a way so that for every value of either property all items of that value are grouped together.

Obviously trying every possible ordering is out of the question.

For example, if each item has a number and a letter, the following sequence satisfies the condition:

A1->A2->A3->B3->B4->C4->D4
\---A----/  \-B--/  \-C--/
 1   2  \-3--/  \---4----/

But the following sets cannot possibly be ordered in this way:

A1, A2, A3, B1, C2, D3

A1, A2, B1, B2

I came up with a solution which is a little long to describe and seems to work, but I was curious:

Is this a known problem? Can it be reduced to a known problem?

There is a $O(n)$ time algorithm for your problem, using standard graph algorithms.  You basically reduce it to connected components decomposition, which can be done in linear time.

Build an undirected (multi-)graph, where we have one vertex for each letter in the input.  For each pair of items that share the same number, say Xi and Yi, add an undirected edge between X and Y.  This might introduce repeated edges.  That's ok.  Leave them as is; don't collapse them down to a single edge.

Once you have this graph, your items can be ordered if and only if every connected component of this graph is a simple path.  You can test this condition by decomposing into connected components using standard algorithms, then for each connected component, checking that no vertex has degree $\ge 3$ and that either (i) the component consists of only a single vertex, or (b) there exist exactly two vertices in the component with degree 1.  The whole thing can be done in linear time.

The idea here is that we're trying to find an ordering of the letters (the vertices), subject to some constraints: each edge (X,Y) represents a constraint that the letter X has to be adjacent to Y in the final ordering of letters.  The graph I defined above encodes exactly the constraints that apply, if we want to find an ordering of the items.  Notice that there exists a valid ordering of the items if and only if there exists a valid ordering of the letters that respects the edge-constraints: given an ordering of the letters, each letter represents the group of items containing that letter, and you can easily arrange what order to put the numbers in.

The key insight here is to build a graph with one vertex per letter rather than one vertex per item.  Once you do that, everything falls out more or less straightforwardly.

Credits: I thank Raphael for a crucial idea that helped me find this,  AlexDev for pointing out some subtleties that helped me work out the details, and reinierpost, whose answer helped me realize a few other tricky details.

By the way, you might notice that my solution ends up looking very similar to reinierpost's elegant algorithm.  Indeed, when the graph is connected, my solution is equivalent to his algorithm: his y[A] is just the degree of the vertex A in the graph I defined.  The difference comes when the graph is not connected; my algorithm handles that case correctly, but I think his algorithm gets a few corner cases wrong.  Nonetheless, the ideas are extremely similar -- and I hope my exposition helps understand the ideas behind his elegant algorithm.

This algorithm also generalizes to the case where you have more than two attributes.  For instance, suppose each item has a letter, a number, and a color.  Start by forming a graph with a vertex per letter and an edge (X,Y) whenever there are two items that share an attribute and whose letters are X,Y respectively; use the same techniques to look for a valid ordering of the letters.  Then, for each letter, you need to look for a valid ordering of the items containing that letter.  This can be done by a recursive call.  There is a slight twist, in that during recursive calls you might have an additional constraint indicating which item the sequence must start and/or end at, but it's easy to adjust the algorithm to take this into account.  In this way you get an algorithm whose running time is $O(kn)$, where $n$ is the number of items and $k$ the number of attributes.


Count subset divisible by 3 I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is anyone kind enough to give me the right approach to solve this ?

Problem: You are given $N$ boxes indexed from 1 to $N$. The number of boxes with 0, 1, or 2 coins is $n_0$, $n_1$, and $n_2$, respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

What is the probability that the total number of coins in a random subset is divisible by 3?

You can use generating functions. Let me switch notations to $a = n_1$ and $b = n_2$, noticing that empty boxes make no difference. The generating function for the total number of coins is
$$
\left(\frac{1+x}{2}\right)^a \left(\frac{1+x^2}{2}\right)^b,
$$
that is, the coefficient of $x^m$ is the probability that the boxes contain a total of $m$ coins. The trick is now to substitute cubic roots of $3$ for $x$, using the following observation, where $\omega = e^{2\pi i/3}$:
$$
\frac{1^m + \omega^m + (\omega^2)^m}{3} = \begin{cases} 1 & \text{if } 3 \mid m, \\ 0 & \text{otherwise}. \end{cases}
$$
Using this, we find that the probability that you're after is
$$
\frac{1}{3} + \frac{1}{3} \left(\frac{1+\omega}{2}\right)^a \left(\frac{1+\omega^2}{2}\right)^b + \frac{1}{3} \left(\frac{1+\omega^2}{2}\right)^a \left(\frac{1+\omega}{2}\right)^b.
$$

This formula is not necessarily so helpful. Instead, we can use dynamic programming, which can be succinctly expressed using matrices. Suppose that we open the boxes one by one (each one with probability $1/2$), and keep track of the vector of probabilities of the various residues modulo $3$, a column vectors whose entries correspond to the residues $0,1,2$. An opened box with one coin affects the vector according to the matrix (multiplying the vector on the left)
$$
\begin{pmatrix}
0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0
\end{pmatrix}.
$$
If instead we open the box with probability $1/2$, we get the average of this matrix with the identity matrix:
$$
\begin{pmatrix}
\tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2}
\end{pmatrix}.
$$
We can analyze boxes with two coins similarly, and over all the vector of probabilities is
$$
\begin{pmatrix}
\tfrac{1}{2} & 0 & \tfrac{1}{2} \\ \tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2}
\end{pmatrix}^a
\begin{pmatrix}
\tfrac{1}{2} & \tfrac{1}{2} & 0 \\ 0 & \tfrac{1}{2} & \tfrac{1}{2} \\ \tfrac{1}{2} & 0 & \tfrac{1}{2}
\end{pmatrix}^b
\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}
$$
You can get your probability by taking the first entry. The matrix expression above can be evaluated in many ways – by multiplying the vector matrix-by-matrix, using repeated squaring to compute the matrix powers, or by diagonalizing the matrices to obtain an even more rapid algorithm (which is identical to the formula obtained above using generating functions).

Finally, let me spell out the dynamic programming algorithm, which just implements the matrix-by-matrix approach hinted to above:

Initially, $(p_0,p_1,p_2) \gets (1,0,0)$.
Repeat $n_1$ times: $(p_0,p_1,p_2) \gets (\frac{p_0+p_2}{2},\frac{p_0+p_1}{2},\frac{p_1+p_2}{2})$.
Repeat $n_2$ times: $(p_0,p_1,p_2) \gets (\frac{p_0+p_1}{2},\frac{p_1+p_2}{2},\frac{p_0+p_2}{2})$.


Is the runtime for the general number sieve given in base 10, e or 2? When the runtime of the GNFS is given as e^(64/9*b(log b)^2)^1/3,
what base is the log?  I'm assuming its e, but other options would obviously be 10 and 2.

Wikipedia gives the running time as
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},
$$
where $n$ is the integer being factored. Here $\ln n$ is the natural logarithm (logarithm to base $e$).


How to show that $L=\{ wa^kw | w \in \{ a,b,c \}^* ,k \geq 0 \}$ is not regular using the pumping lemma for regular languages? I'm trying to show that the language in the title is not regular but I don't know how to chose a decomposition $x = abc$ to express the word in the language because the $w \in \{a,b,c\}^*$ is kinda tricky for me, I know it means $ \{ a,b,c\} \cup\{ a,b,c\}^2 \cup ... \cup \{ a,b,c\}^k $ but I don't know how to chose the decompositons for a word in the language and proove that is not in the language by pumping lemma. Any tips ?

After $n$ is fixed, you could choose $x = b^na^nb^n$. This string is clearly in $L$. By the Pumping lemma $x$ can be written as $uvw$, where $|uv| \leq n$ and $|v| \geq 1$. So for any choice of $u$ and $v$, $uv$ is a string consisting of only $b$s, and so is $v$. Thus $uv^iw = b...b(b...b)^ib...ba^nb^n$ which is not in $L$.

On @DavidRicherby comment:

The Pumping Lemma:

Let $L$ be a regular set. Then there is a constant $n$ such that if $z$ is any word in $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and for all $i \geq 0$, $uv^iw \in L$.

How to use

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$  in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = b^na^nb^n$.

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

In my proof the prefix of $z$ consists of $n$ $b$'s, so any choice of $u$, $v$, and $w$ implies that $v$ consists solely of $b$s.

5) You achieve a contradiction to the pumping lemma by showing that there exists $i$ such that $uv^iw \notin L$.

Just choose $i=2n$ and we have unequal number of $b$s on the left and right sides of the substring $a^n$: $b^{2n + d}a^nb^n \notin L$.

This is how we prove.


How are logical addresses of instruction operands mapped to physical addresses? Is address translation for all operands in single instruction done only once and then are all operands fetched continuously?

For example, consider any dummy instruction INSTR with two operatnds OP1 and OP2:

INSTR OP1, OP2

How does an operating system map logical addresses of these operands to their physical addresses? Is this address translation done only once for each instruction and then are all operands stored in consecutive memory locations? Or is address translation done separately for each operand and hence page tables are referenced for each operand separately?

Usually instructions are moved from RAM or from external memory to the processor’s instruction cache. Then the only address mapping is mapping a logical address to a cache line containing the instructions.

Most instructions are completely contained within one cache line, on processors with fixed instruction size each instruction is contained within one cache line. On processors with variable instruction length like intel processors the instruction decoder will read two cache lines if needed.