Complexity of a set partition derived problem I am stuck at the complexity of the following problem:
Given a multiset $S = \{x_1,..., x_n\}$ of $n$ integers and a natural number $k$. Can $S$ be partitioned into multisets $S_1,... S_j$ such that for all $S_i \subseteq S$ there is $\sum_{ s \in S_i} s = k?$

I have found out that this may be somehow related to the EqualSubetSum Problem or the partition problem. But is this problem really $NP$-complete or exists a polynomial algorithm depending on $k$ and $n$ to decide this problem?

A set is a multiset (in which every element occurs once) and your partition problem can be used to find a subset of $S$ whose sum is $k$. [Note 1] So if there were a polynomial-time solution to your partition problem, it could easily be used to solve the subset sum problem in the same amount of time.
So the problem is NP-complete, but that doesn't stop it from having a pseudo-polynomial time solution. There are well-known DP algorithms to solve the subset sum problem which are polynomial in the magnitude of the inputs. Time complexity is always expressed as a function of the size of the inputs, as measured (for example) by the number of bits it takes to represent the input. The magnitude of a number is exponential in the size of the number (eg, a number represented in 100 bits could be as large as $2^{100}$). So time complexity polynomial in magnitude is still exponential in problem size.
In your problem, $n$ is a measure of problem size, whereas $k$ only measures numeric magnitude. So they are very different kinds of parameter.
Here's another longer explanation of pseudo-polynomial time in a StackOverflow answer.

Notes

Let $S$ be a set for which we seek a subset whose sum is $k$. Without loss of generality, we can assume that $\Sigma S \le 2k$ (because a solution for $k' = \Sigma S - k$ leads directly to a solution for $k$ using the set difference from $S$.) If $\Sigma S = 2k$ then a solution to the multiset partition problem yields two solutions to the subset sum problem. Otherwise, we form the multiset $S' = S \cup \{2k - \Sigma S\}$.  Obviously, $\Sigma S' = 2k$ and the element we added has a value less than $k$. We then compute the multiset partition of $\langle S', k\rangle$, which must be a partition into two pieces, at most one of which is a multiset (because there is at most one repeated element in $S'$, the one we added). If the first subset in the partition does not include the element we added, it is a solution to the original problem; otherwise, the second subset is.
Computing $\Sigma S$ and examining the result of the multiset partition solution are both linear time. So if the multiset partition algorithm were polynomial time, so would be the derived subset sum algorithm.


Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random? A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as in this question.

I've noticed that when solving such tasks, any algorithm for calculating the number of such combinatorial objects via a recurrence relation can be transformed into an algorithm to generate such combinatorial objects. My question is, is there a name for this technique? Is there a theorem which says when this is true?

For example, suppose I want to generate a random sequence of $n$ $1$s and $0$s, where there are no two adjacent $1$s. I can begin by letting $a[n]$ be the number of such sequences, and observe that
$$
a[n] = a[n-1] + a[n-2].
$$

(This is the Fibonacci relation.)
This allows me to efficiently calculate a table of $a[i]$ for $i = 1$ to $i = n$.
Now if I want to generate a random such sequence, all I have to do is:

Step 1: Generate a random value $r$ from $1$ to $a[n]$.

Step 2: Use the recurrence relation to locate a sub-term which corresponds to the $r$th sequence:

If $r \le a[n-1]$, recursively find the $r$th sequence counted by $a[n-1]$, and append a $0$.
Otherwise, if $a[n-1] < r \le a[n-1] + a[n-2]$, set $r' = r - a[n-1]$, and recursively find the $r'$th sequence counted by $a[n-2]$, and append a $01$.

What seems to be going on here is that, given any recurrence relation for $a[n]$, I can transform this into a recursive algorithm which returns the $r$th object counted by $a[n]$. I'm assuming this is well-known, so I would be interested in any references or classic results about this. In particular, this isn't just specific to the example $a[n]$, but should be true for any recurrence relation satisfying certain properties.

Also, I think this may be related to some research on random testing.

These are known as ranking and unranking functions.  You are right about the correspondence between recurrence relations for counting and unranking algorithms.


What is the transitive and reflective closure of the derivation relationship? This question is asked during a class of Computer Science.

  What is the transitive and reflective closure of the derivation
  relationship?

I know that if $R$ is a relationship on $A^2$, a transitivive and reflective relation on $R$ is the following $R^*$

$$R^* = R^+ \cup \{<x,x> \mid x \in A\}$$

but I don't now how to apply it to the concept of derivation

If $R\subseteq A\times A$ is a binary relation, it can be imagined as a directed graph: the elements in $R$ are the edges. The graph however might be infinite. The elements in $R^*$ represent (finite) paths, following zero, one or more of the consecutive edges. Zero edges because of reflexivity, two or more because of transitivity.

In case of a grammatical derivations the relation $\Rightarrow$ considered is a binary relation in $\Sigma^*\times\Sigma^*$ for some alphabet $\Sigma$, defining a single step as defined by the grammar. Then  $\Rightarrow^*$ consists of all pairs of strings the first one of which can be rewritten into the second, using zero, one or more steps.

In other words, $x \Rightarrow^* y$ iff there exist steps $x= w_0 \Rightarrow w_1 \Rightarrow \dots \Rightarrow  w_n=y$.
Again, this includes the case of zero steps $x= w_0 = w_n=y$.

This notation can then be used to define the language of the grammar. Usually [but not always] this looks like $L(G) = \{ x\in\Delta^* \mid S \Rightarrow^* x \}$; the set consisting of all terminal words ($x\in\Delta^*$) that can be derived from the axiom ($S \Rightarrow^* x$).


Fewest traversals to visit all vertices of DAG I want to find the fewest traversals to visit all vertices of a DAG.  To take a very simple case:

Boston -> New York   -> San Francisco or Las Vegas, both to -> LA
       -> Pittsburgh -> San Francisco or Las Vegas, both to -> LA

There are lots of ways to traverse this graph, but to visit every vertex, you only need:

1. Boston -> New York   -> San Francisco -> LA
2. Boston -> Pittsburgh -> Las Vegas     -> LA

I have no preferences in how the graph is visited, and it's fine to visit the same vertex multiple times during different traversals.

(Real application: I am generating test cases for human testers and want them to help them perform their tests at every 'vertex' with as few run-throughs as possible.)

I think you can solve this problem by reducing it to a minimum-cost circulation problem.

Let $G$ be your graph.  Replace each vertex $v$ with two vertices $v_\text{in},v_\text{out}$; replace each edge $u \to v$ into $v$ with an edge $u \to v_\text{in}$ and each edge $v \to w$ out of $v$ with an edge $v_\text{out} \to w$, and add the edge $v_\text{in} \to v_\text{out}$.    Add a new source vertex $s_0$ and a new sink vertex $t_0$.   For each vertex $v$ in your graph, add an edge $s_0 \to v_\text{in}$ and an edge $v_\text{out} \to t_0$.  Finally, add an edge $t_0 \to s_0$.  All edges have cost 0, lower bound 0, and upper bound $\infty$, except that all $v_\text{in} \to v_\text{out}$ edges have lower bound 1 and the $t_0 \to s_0$ edge has cost 1.

Now, find the minimum cost circulation in this graph.  There are polynomial-time algorithms to do this.

I claim that this minimum-cost circulation corresponds to the minimal set of paths to cover all the verticies.  In particular, if the minimum cost circulation has cost $c$, then that means there will be $c$ paths that cover the vertices.  This circulation will have total flow $c$, so you can trace where each of the $c$ units of flow go starting from $s_0$ to $t_0$, and that will trace out a path; take those $c$ paths as your collection of paths.  By the way I defined the lower bounds, this ensures that each vertex will be covered by at least one of these $c$ paths.


Could program verification techniques prevent bugs of the genre of Heartbleed from occurring? On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April:
'"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a kernel of a certain operating system has been rigorously verified with a modern program verification system. Could hence bugs of the genre of Heartbleed be prevented from occurring via application of program verification techniques today or is this yet unrealistic or even principally impossible?

To answer your question in the most concise way - yes, this bug could have potentially been caught by formal verification tools. Indeed, the property "never send a block which is bigger than the size of the hearbeat that was sent" is fairly simple to formalize in most specification languages (e.g. LTL).

The problem (which is a common criticism against formal methods) is that the specifications you use are written by humans. Indeed, formal methods only shift the bug-hunting challenge from finding the bugs to defining what bugs are. This is a difficult task.

Also, formally verifying software is notoriously difficult due to the state-explosion problem. In this case, it is especially relevant, since many times in order to avoid the state explosion, we abstract away bounds. For example, when we want to say "every request is followed by a grant, within 100000 steps", we need a very long formula, so we abstract it to the formula "every request is eventually followed by a grant".

Thus, in the heartbleed case, even while attempting to formalize the requirements, the bound in question could have been abstracted away, resulting in the same behavior.

To sum up, potentially this bug could have been avoided by using formal methods, but there would have had to be a human specifying this property in advance.


Proving time-complexity analysis for merge-sort-like algorihtm I have this algorithm, which is exactly like merge-sort, but instead of halving the array each recursion, it actually splits it into $1/4$ and $3/4$ parts. Other then that, it does exactly the same operation as merge-sort.

The thing is, I can't understand the exact way to calculate a closed form solution to my recursive formula, which I think is: $$T(n) = T(\frac{1}{4}n) + T(\frac{3}{4}n) + O(n)$$

I've gone through the proof of the standard merge-sort implementation recursion closed-form formula (as seen in a khan academy article) and have noticed that as a way to develop intuition on how the recursive formula acts, a binary tree has been drawn. So I decided to try it for myself and the recursion formula I'm trying to prove. What I got was something like the following:

Where $(\frac{3}{4})^Hn$ is the height of the tree.

Because the tree is not complete, I'm confused on how I should calculate that $H$ value (the height of the tree), so I could use it in my worst-case merge-sort-like algorithm analysis. The confusion, in my estimation, lies in my low confidence with $log$ operations. Just can't seem to wrap my head around them. How do I start writing an induction proof for a closed form formula, and how do I even come up with one?

Help is as always, greatly appreciated. Moreover, if there is a source of further learning and something worthwhile reading that might help in this subject, please write that down for me so I could explore by myself. Thanks!

There is no reason to calculate a closed form solution to this recurrence. Indeed, this is not even possible, due to the following reason:

$O(n)$ is not a closed form function. It just signifies that the recurrence holds with $O(n)$ replaced by some function $f(n)$ which belongs to the class $O(n)$.
It is not clear what happens when you plug in $n$ which is not divisible by 4.
A related issue is that there are no initial conditions - the recurrence seemingly never bottoms out.

Any reasonable way to address the latter two concerns will lead to a recurrence which is amenable to the Akra–Bazzi method. According to this method, we first need to calculate the value of $p$ satisfying
$$ (1/4)^p + (3/4)^p = 1. $$
The solution to this equation is $p = 1$. The asymptotic solution is then
$$
T(n) = O\left(n\left(1 + \int_1^n \frac{O(u)}{u^2} \, du \right)\right) = O(n\log n).
$$


algoritm to convert a monoid into an automaton In literature, is there an algoritm to convert a monoid into an atomaton?

I am looking for references/applications.

Short answer. See the Cayley graph of the monoid as an automaton.

Details.
Let $L$ be a language recognised by a finite monoid $M$. Then
there is a morphism $\varphi:A^* \rightarrow M$ and a subset $P$ of
$M$ such that $L = \varphi^{-1}(P)$. Take the right representation of
$A$ on $M$ defined by $s \cdot a = s\varphi(a)$. This defines a
deterministic automaton $\mathcal{A} = (M, A, \cdot, 1, P)$. Now, a
word $u$ is accepted by $\mathcal{A}$ if and only if $1 \cdot u \in P$. Since
$1 \cdot u = \varphi(u)$, this condition means $\varphi(u) \in P$ or $u
\in \varphi^{-1}(P)$. Since $L = \varphi^{-1}(P)$, we conclude that
$\mathcal{A}$ recognises $L$.


Could PRNGs make use of more internal state? In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing):

  Pseudo-random number generators (PRNGs) must have a period since they only have finitely many internal states.

At least for the PRNGs we see in the class, this is certainly a valid argument (assuming a finite target interval). But it begs the question: why do they not use more memory resp. internal state?

Going through this list, it seems to be the case that all PRNGs do indeed use only a few numbers from the target interval (plus some magic constants).

Most use one to $\approx$ 5 of the most recently generated numbers.
Some have parameter that controls how many values to store ("$r$-lag").
A few use rather many numbers (but still constantly many).

The one I can't quite place is Naor-Reingold; I can't tell how it would be used to generate an actual sequence of pseudo-random numbers.

So while the memory usage (i.e. internal state size) of known/used PRNGs depends on the target interval and internal constants, it does not on the amount of (already) generated numbers.

Have there been any attempts to use more memory in order to obtain better generators? If so, why does it not help or not work at all?

Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, [insert your favorite argument about why $2^{19937}$ is a somewhat large number here].


How to memorize Master Theorem? I know the maths behind, I know if I do the algebra I can get the result of the 3 cases. I also have an intuition of the 3 cases: Quora

However, I just cannot memorize this "simple" 3 cases whenever I need to apply them in real life problems.

I don't know if it is a shame that a CS graduate has to Google this theorem, which I learnt at the first year in University, just because I cannot memorize it. (Or is it actually no need to memorize it, please tell me, I will close the question at once)

So assuming this basic theorem is important and I have to memorize it just like how we memorize F = ma in physics field, is there any way to aid memorizing these 3 cases in long term speaking?

A way may means visualization, better intuition with clear reasoning behind, or even just die hard memorizing it, I just want to know how other CS people memorize this theorem.

The key to memorizing the master theorem is to simplify it. There's an approximation to reality that is correct in 99% of the cases. A good (but not technically correct) summary of the Master Theorem is as follows:

If $T(n)=aT(n/b) + f(n)$ then compare $n^{log_b a}$ with $f(n)$

If $f(n) < n^{log_b a}$, then $T(n)=n^{log_b a}$

If they are equal, then $T(n)=f(n)\log n$

If $f(n) > n^{log_b a}$, then $T(n)=f(n)$

Basically, you compare $n^{log_b a}$ with $f(n)$ and the larger of the two is your running time; however if they are equal (for some strange definition of equal) then you get an extra $log$-factor in the running time. This sentence is all you really need to know.
Caveats
The most important one is in the meaning of "equal". For the purpose of the master theorem $f(n)$ is equal to $n^{log_b a}$ if the difference between them is less than polynomial. So, for instance, if $f(n)=n^{log_b a}\log n$ or $f(n)=n^{log_b a}\log^3 n \log \log n$ this would still count as "equal". The difference needs to be at least a factor $n^\epsilon$ for some $\epsilon>0$.
Another caveat is that for the third case ($f(n)$ exceeds $n^{log_b a}$ you also need a condition that $f(n)$ does not grow "too quickly". This is rather pathological and not likely to be an issue in practice, but something you should be aware of. The formal condition is that $af(n/b)$ should be less than $f(n)$ (for sufficiently large $n$, and where "less" is interpreted as "there is a $k<1$ such that $af(n/b)\leq kf(n)$).


the problems that could exist if halting problem is solved What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is there

"Exists" is a weird word to use here; I assume you're asking about what problems would be solvable if we were suddenly able to solve the halting problem.

Phrasing things in terms of sets of natural numbers for simplicity (as is the general approach here) you're asking for a characterization of the sets which are Turing reducible to $0'$. It turns out that this is a very robust notion. For example, the following three properties of a set $X$ are equivalent:

$X\le_T0'$.
$X$ is limit computable: there is a computable total function $f(x,s)$ such that for each $n\in\mathbb{N}$ we have $\lim_{s\rightarrow\infty}f(n,s)$ exists and is $1$ iff $n\in X$ and is $0$ otherwise.
$X$ is $\Delta^0_2$-definable: there are formulas $\varphi_1(z)\equiv\forall x\exists y\theta_1(x,y,z)$ and $\varphi_2(z)\equiv\forall x\exists y\theta_2(x,y,z)$ where $\theta_1,\theta_2$ use only bounded quantifiers such that $$X=\{n:\varphi_1(n)\}=\{n:\neg\varphi_2(n)\}.$$

Meanwhile, some problems which are not Turing reducible to the halting problem include:

Does a given Turing machine halt on all inputs?
Do two Turing machines accept the same language?
Is a given c.e. set actually computable?

The first two have Turing degree $0''$, while the third has degree $0'''$. It's worth noting that while there are sets which are not "iterations of the halting problem," and in particular there are always lots of degrees between ${\bf d}$ and ${\bf d'}$, there is strong evidence that no "natural" examples of such sets. (There's also a lot of stuff "off to the side" - for example, the set of problems which are Turing-incomparable with $0'$ has full measure and is comeager.)


Is every planar graph a possible dual graph of a voronoi diagram? My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar graph?

No. The dual graph of a Voronoi diagram is the Delaunay triangulation of its point set so, in particular, every interior face of it is a triangle. But there are plenty of planar graphs (e.g., the $4$-cycle) that have non-triangular interior faces.


Solving Recurrences Using Master Method Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences:

$T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$
$T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$
$T(n) = 2T(\frac{n}{3} + 1) + n = \Theta(n\ln(n))$

I understand the Master Method (I think, largely from: https://stackoverflow.com/questions/13430256/understanding-master-theorem) and from my CLRS Text.

Problem 1:
Would be case 1, but I don't understand how to use it in this case? What would my ɛ be in this case to perform the logarithmic function? I know that ultimately, my time complexity will be $\Theta(n^{1.58})$, but I don't know how to prove that without knowing ɛ

Problem 2:
I have no idea.

Problem 3:
I believe this is false, because this can be rewritten as  $T(n) = 2T(\frac{4n}{3}) + n$, which would be Case 2, and therefore give me a time complexity of $\Theta(ln(n))$.

This is my first time taking anything this granular with algorithms, and despite reading CLRS and looking at videos online, I am a bit lost, and would appreciate any help. Thanks in advance.

1) $T(n) =  3T(\frac{n}{2}) + n \in \Theta(n\ln(n))$

a = 3, b= 2 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_2 3} > n^{\log_2 2}  = n = f(n) \therefore f(n) \in \Theta(n^{\log_2 3})$

(Case 1) Proved False

2) It is not in the Master Theorem format $T(n) =  aT(\frac{n}{b}) + f(n) \therefore$

It is not possible to say if the statement is true or false using the Master Theorem

3)  $T(n) =  2T(\frac{n}{3}+1) + n  = 2T(\frac{n+3}{3}) + n \in \Theta(n\ln(n))$

a = 2, b= 3 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_3 2} < n^{\log_3 3}  = n = f(n) \therefore$

Case 3.

Now we could check if it is the case that $T(n) \in \Theta(f(n))$, but we don't need to, because the only way it would be $\Theta(n\log n)$ was if it was case 2.


Degree conditions sufficient for Hall's theorem Let $G=(L,R,E)$ be a bipartite graph, are there conditions on the degree of the vertices under which the condition of Hall's theorem is surely satisfied? (meaning a perfect matching exists in the graph).

Konig's theorem proves that every $k$-regular bipratite graph has exactly $k$ edge disjoint perfect matchings, so the answer is obviously yes for any $k$-regular bipartite graph with $k>0$ (it's not hard to see why hall's condition is satisfied in this case).

Is there a wider rule?

For example: Let $|L|=|R|=n$, What is the minimal degree as a function of $n$ of every vertex in the graph such that the graph must admit a perfect matching?

I'm also wondering if these conditions will hold in general graphs (satisfying Tutte's theorem), and if not, then are there similar conditions for general graphs.

Are you by any chance looking for Hall's theorem ? It gives a complete characterization of when a bipartite graph admits a perfect matching. Specifically:

G admits a perfect matching if and only if for all subsets $S \subset L$, we have
$$ |\Gamma(S)| \ge |S|$$ where $\Gamma(S) \subset R$ is the set of neighbors of vertices in $S$.


Basic doubt in converting PDA to DPDA This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism.
When we have input a with Z at the bottom of the stack, then at the beginning it can do $(a,Z/aZ)$ or $(\epsilon,Z/Z)$ and go to final state, so automaton has 2 choices which can lead to 2 different states.

How do I convert it to DPDA ? How do I remove that $\epsilon$ transition from first state to make the PDA deterministic?

Here, the stack symbol is $Z$ and the transition $(a,Z/aZ)$ means on seeing input $a$ with $Z$ at the top of the stack, push $aZ$.

The DPDA could be constructed by adding explicit states and dropping too permisive epsilon transition.

I will denote accepting state by paranthesis around the name.

$(q_0, \epsilon, Z, (q_f), Z) \text{ accept empty string}$
$((q_f), a, Z, q_a, a)\text{ add initial a (or after cancellation occurs)}\\
((q_f), b, Z, q_b, b)\text{ add initial b (or after cancellation occurs)}\\
(q_a, b, a, q_a, \epsilon) \text{ even out two symbols}\\
(q_b, a, b, q_b, \epsilon) \text{ even out two symbols}\\
(q_a, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_b, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_a, a, a, q_a, aa)\text{ add another a to stack}\\
(q_b, b, b, q_b, bb)\text{ add another b to stack}$


While using K-means, how do I represent IP addresses and languages on the coordinate axis? I'm using K-means for unsupervised learning, using data vectors with an IP address and a language. I need to represent them in an abstract way, so that I can use this algorithm.

If your data doesn't map in an obvious way onto vectors of continuous real numbers, don't use K-means.

To use K-means clustering you need to have a well defined distance between any two points in the space.  To do that you need to have a notion of distance for each axis.

Typically discrete classifications like "language" don't have any natural mapping onto real numbers.


QuickSort Dijkstra 3-Way Partitioning: why the extra swapping? Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens:

Scenario: i -> "X", "X" > "P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Why don't we just decrement gt until gt points to a value that is < the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.

So if we do that for the scenario mentioned above, we'll do:

1. gt--
2. gt--
3. swap("X", "C"), gt--;
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Is this excessive swapping needed for the algorithm? does it improve performance in some way?
If it does improve performance, how?

If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.

Also, would the second method I mentioned affect performance in any way? please explain why.

P.S. "Affect performance" as used above means either improve/degrade performance.

In order to know that you may just decrement gt, you have to compare the element at position gt to the pivot.

For illustration, here is the relevant part of the code from the slides you took your illustration from:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) exch(a, i, gt--);
   else              i++;
}

Your modification would look like this:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (a[gt].compareTo(v) > 0) gt--;
      exch(a, i, gt--);
   }
   else              i++;
}

If the element is larger, we save a swap, as you illustrated. Furthermore we won't have to compare that element again. If, however, the element is not larger, we will compare it to the pivot twice, once before the swap and once after the swap.

So with your modification we save a swap for each element that is larger than the pivot and on a position that ends up to the right of the pivot, while we introduce an additional comparison for each element in such a position that is not larger than the pivot.

Averaging over all inputs we can expect the  number of elements smaller resp. larger than the pivot to be equal. So the performance will depend on the number of elements equal to the pivot (and the cost of a swap vs. a comparison). Your modification will have the better relative performance, the smaller that number is. But 3-way partitioning was developed with inputs with many equal keys in mind, so the original choice seems reasonable.

Taking a second look at the modified algorithm, we note that if we compare an element twice, there is no other comparison happening between these two. So it seems worthwhile to remember the result of the comparison. However, if we want to keep the structure of the code, this means a lot of control structure overhead:

Boolean doComp = true;
int cmp;
while (i <= gt)
{
   if (doComp) cmp = a[i].compareTo(v);
   doComp = true;
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (cmp = a[gt].compareTo(v) > 0)
      {
         gt--;
         doComp = false;
      }
      exch(a, i, gt--);
   }
   else              i++;
}

My gut feeling is that even though it combines the advantages of the previous two versions in terms of number of comparisons and swaps, it will perform worse due to the overhead of the additional control structures.

Not only have we introduced additional operations (checking conditions, maintaining the flag), we also introduced (compared to Dijkstra's version) two additional conditional jumps (for if and while), that will often but irregularly switch between taken and not taken. The latter is a problem on modern processors, since they rely on branch predictions for optimal performance and such branches will lead to a high number of mispredictions. (The branch corresponding to the outer loop is an opposite example: Always predicting that the loop will be entered is wrong only once.)

With these considerations in mind, we can try to optimize the code. The following should perform quite well:

while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if (cmp > 0)
   {
      while ((cmp = a[gt].compareTo(v)) > 0) gt--;
      exch(a, i, gt--);
   }
   if (cmp < 0) exch(a, lt++, i++);
   else         i++;
}

This version makes as many comparisons as Dijkstra's version and as many swaps as your suggested version without introducing too much overhead: For each comparison we have one branch based on cmp > 0 and possibly one based on cmp < 0. This is the same as for Dijkstra's version except that the role of the two comparisons is exchanged.

So, summing up / answering your final questions explicitly:

The additional swaps you point out can be avoided without introducing other costs. So, as you suspected, they degrade performance compared to the final version in this answer.
The version you suggest removes the unnecessary swaps, but introduces additional comparisons. So it will too perform worse than the final version in this answer.
As I pointed out, the realitve performance of the original and your version will depend on the input at hand and the relative costs of swaps and compares. (Since usually compares are faster than swaps, I'd expect your version to be faster on average.)


What's wrong with this grammar $L = \{ w : w  \in \{a, b\}^* \land |w|_a = |w|_b\}$ where $|w|_a$ means number of $a$ in string $w$.

I came up with this grammar:

$S \rightarrow aSb \ |\ bSa \ | \ \epsilon .$

Can someone please tell me what is wrong with it?

Consider the string $w= abba $.
$w$ clearly belongs to $L$ as $|a|=|b|$ but there's no derivation which allows you to generate $w$ given your CFG.

In practice, your rules only deal with the imbalance in the number of $a$'s and $b$'s.
 You need to make sure to generate every string $w \in (a+b)^*$ with the same number of $a$'s and $b$'s.

A CFG grammar for your language can be the following:

$S \rightarrow \epsilon\ |\ aSbS \ | \ bSaS $


subsets of infinite recursive sets A recent exam question went as follows:

  $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
  Let $C$ be an infinite recursive subset of $A$. Must $C$ have a subset that is not recursively enumerable?

I answered 1. already. Regarding 2., I answered affirmatively and argued as follows.

Suppose that all the subsets of $C$ were recursively enumerable. Since $C$ is infinite, the power set of $C$ is uncountable, so by assumption there would be uncountably many recursively enumerable sets. But the recursively enumerable sets are in one-to-one correspondence with the Turing machines that recognize them, and Turing machines are enumerable. Contradiction. So $C$ must have a subset that is not recursively enumerable.

Is this correct?

It is correct.

Every infinite set has an undecidable subset, you can use the cardinality argument: $\aleph_0\leq C \implies \aleph_0 < 2^C$. In fact most of its subsets are undecidable (and you can replace undecidable with any countable class of languages, e.g. c.e., arithmetical, analytical, ...).

The bad thing about this argument is that it doesn't give any information about how difficult the subset is. We usually want a subset which is as easy as possible. One way to get this is using a diagonalization similar to the cardinality argument using the fact that $C$ is decidable:

Define $D = \{ i \in C \mid i \notin W_i \}$, where $W_i$ is the $i$th c.e. set. Obviously $D \subseteq C$. Moreover $D$ can be solved with an oracle for $C$ and $K = \{ i \mid i\notin W_i\}$. So if $C$ is decidable then $D$ is a co-c.e. language.


what is the k-line-connected graph definition What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems on a 3-connected cubic planar graph and their applications" where it comes without definition. Unfortunately for me I couldn't get the definition from the context given in its authors' proofs.

Judging from the proof of Lemma 1 in the paper, 3-line-connected is the same as 3-edge-connected; line is probably a translation from Japanese.


Are most metaheuristic algorithms different metaphors for the same method? Most times I encounter this random metaphors for metaheuristic optimization they seem like a modified genetic algorithm to me. What do you think? Is there a way to remove the analogies/metaphors to better compare algorithms?

Comparing ideas

If you want to compare the ideas involved on the various metaheuristics, a good starting point for the comparison is to think of them as Population based vs Trajectory based. Population based metaheuristics works with the concept of create a solution that mix components of good solutions. Trajectory based metaheuristics works with the concept of creating a solution and iteratively do improving modifications(moves) on it. With the image below, you can visualize this dichotomy and other possibles parameters for comparison.

Comparing performance

To compare performance, a common approach is to use time to target. Given a known solution and its objective value, how fast my metaheuristic achieve this value? This site provides a tool that helps in this task.


Is it correct to say that an algorithm ALG is an O(1)-approximation algorithm? I read it in not only one place. People write theorems of the form:

  Theorem: ALG is an O(1)-approximation algorithm

It means that ALG is a constant factor approximation algorithm but is it safe to say that? I mean it misleads. Why am I asking?

Because, many problems I know of do not have an $\alpha$-approximation algorithm where $\alpha<\gamma$, unless P=NP. For example, the k-center problem does not have an $\alpha$-approximation algorithm where $\alpha<2$, unless P=NP. Well, there is a simple greedy algorithm that is 2-approximation algorithm for the k-center problem. Can we say that this greedy is O(1)-approximation algorithm for the k-center problem? I mean, if it is an O(1)-approximation algorithm for the k-center problem, it is, for example, an 1.9-approximation algorithm, no?

When we say that ALG is an $O(1)$-approximation algorithm, we meant that there exists a constant $C$ such that ALG is a $C$-approximation algorithm. Sometimes we don't care about the exact value of $C$, which is why we use the $O(1)$ notation.

You don't get to choose the constant – rather you are only given that such a constant exists.


Label Assignment Problem I try to solve an exercise in Distributed Algorithm described as follow.

Let's define a label assignment problem as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't have any clue about $n$ - number of vertices nor about network topology ). The labels assigned to vertices must be distinct and there is no limitation on the length of the label. The initiator is given. Show the algorithm for solving the problem in asynchronous model with time complexity $\text{O}(D)$ and using $\text{O}(m)$ messages (where $D$ is the diameter of graph and $m$ number of edges), prove that the labels are indeed distinct. Show the changes in complexities if the algorithm is executed on the synchronous network.

Let's say that the initiator is the node A, wlog assign it $A_{id} = 1$, broadcast $A_{id} = 1$ to all children of $A$ by flooding algorithm, any node $B$ by receiving message from it's parent for the first time will assign $B_{id} = PARENT_{id}+1$ and send $B_{id}$ to it's children, if $B_{id}$ is already defined, drop the message. $T=\text{O}(D)$ - time complexity, $M=\text{O}(m)$ - message complexity for broadcast.

It seems like on synchronous network the complexities will be the same, just becasue broadcast and convergecast on synchronous and asynchronous network run in $T=\text{O(D)}$ and $M=\text{O}(m)$.

If there are any change in complexities on the synchronous network? Does the above algorithm look good?

I dont know the solution of your problem: especially as we dont have a limit on the ID's. My "guessing" is that you cannot solve this problem with complexities you listed.

I will only answer your following question:

Does the usage of randomized leader election is eligible in the case of graph as described above?

I dont suggest using leader election. Its lower bound does not meet your requirement (it is still an open problem to solve the election problem with $O(D)$ time and $O(m + n \log n)$ message, Peleg 199*). The known randomized election algorithms so far do not work on arbitrary graphs. There is a new algorithm that runs in arbitrary graphs (but requires knowledge of $n$). This algorithm is not yet officially published (due to Peleg et al. 2012).

I will list the references later.


Pseudocode for graph chase algorithm Input: undirected graph $G$, starting node $j$ for Justin Bieber (JB), and starting nodes for 4 fans $f_1, f_2, f_3, f_4$.

This problem has turns: for every turn, JB can either stay at his current node or move 1 node adjacent. Fans are working together and follow the same rules, but can share the same node. The fans are trying to occupy the same node as JB, and if any one of them achieves this, JB loses (Yes, you are on Justin's side for this problem!).

If both JB and his fans always have knowledge of the locations of everyone else, decide if it's possible for JB to avoid his fans indefinitely, no matter what his fans' strategies are. Your pseudo-code algorithm must be bound by a polynom in graph size $n+m = |V|+|E|$

This was a tricky, original problem from our algorithms class I'm really interested in. I was thinking that one way JB could avoid all the fans was if the graph was laid out in a way so that he and all his fans would go in a cycle forever, with JB at the front. But we weren't given the strategies for the fans though, so I'm just assuming they move in whatever direction that brings them closer to JB's location (but could there be a more complicated strategy they use, like box him in somehow?) I'm thinking for the pseudo code it should somehow decide whether JB and his fans can make such a cycle, but any help would be greatly appreciated.

Hint: What's the size of the state space?

The state of the world at any point is determined by _____.  Therefore, there are ____ many possible states.

Fill in the blanks, then think about how to use those facts to help you devise an algorithm.


Finding coprimes closest to a certain target Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$.

Where $m$ is odd, I have no problem producing an outcome close to the target, simply by squaring $2$ until close enough to the target.

When $m$ is even, I have a bit more trouble. I have tried a few different methods with no success. I have tried starting with $p = 3$, then multiplied $p\cdot\mathrm{gcd}(p-1, m)$ until $p$ and $m$ share all factors (in other words, until $\mathrm{gcd}(p-1, m) = 1$). This eventually finds a coprime, but there is no guarantee that it is close to the target, and I'm not sure how to operate on the number from here to get another coprime closer to the target.

The algorithm needs to be able to handle massive numbers with hundreds of digits, so it needs to be pretty efficient.

I'm not sure if I'm missing a necessary fact about coprime numbers, or if I'm just misinterpreting the info I have. Can anyone point me in the right direction? Maybe a fact about coprime numbers that I'm missing?

If you want the truely closest coprime to $\frac 4 7m$, you could start with $n = \mathrm{round}(\frac 4 7m)$. Then, while $\gcd(n,m) \neq 1$, try again with $n$ being the closest number to $\frac 4 7 m$ such that $n - q \not \equiv 0 \mod \gcd(q,m)$ for any previously checked number $q$ (keep track of previously checked numbers and gcds in a list)

Checking one candidate has complexity $\mathcal O(\log(m))$. The probability of any two numbers being coprime is $\frac 6 {\pi^2} \approx 60\%$ so the numbers of candidates to check should be $\mathcal O(1)$ on average.

Overall this should find you the closest coprime in $\mathcal O(\log(m))$ operations.


Problem with Understanding a Recursion Tree Consider the recursion tree:

$T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$.

I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p \rightarrow \frac{2p}{8} \rightarrow \frac{4p}{16} \rightarrow \frac{8p}{32} \rightarrow\ ...$.

This means that the time complexity is $O(p\ log\ p)$.

Now, I stopped all my leaves in the above recursion tree have $T(1)$, but say I have the condition $T(0) + O(1)$. Does this change my solution somehow?

Think of it this way, you have a mathematically formal description of a recursive function. Which every function maps an element (or more than one element) To 1 element in the codomain.

What would T(0) be in terms of this functions as an input? It wouldn't change the time complexity.


Understanding the bandwidth problem on graphs I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:

1 => 4
2 => 6
3 => 5, 6
4 => 7
5 => 3
6 => 2, 3, 7
7 => 4, 6

It is claimed an optimal ordering of the vertices is 1 4 5 7 3 6 2, but I don't see how.

When I draw the graph, 5 is 4 edges away from 4, and 3 edges away from 7... yet we jump back to 7 anyways? I don't understand how this problem works.

Wouldn't the ordering be 1, 4, 7, 6, 2, 3, 5 because everything is one node apart, with a maximum bandwidth of 2, because 2 is 2 edges away from 3? With 1 edge separating everything else.

Bandwidth problem explained in homework assignment:

  The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices).
  The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any
  edge. This is better understood through an example. Suppose G consists of 5 vertices and the edges (v1, v2),
  (v1, v3), (v1, v4), and (v1, v5). We must map each vertex to a distinct number between 1 and n. Under the
  mapping vi → i, the last edge spans a distance of four (ie. 5-1). However, the permutation {2, 3, 1, 4, 5} is
  better, for none of the edges spans a distance of more than two. In fact, it is a permutation which minimizes
  the maximum length of the edges in G, as is any permutation where 1 is in the center

I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:

  The bandwidth is the maximum distance in the graph between adjacent nodes in the ordering.

The correct definition is:

  The bandwidth is the maximum distance in the ordering between adjacent nodes in the graph.

Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.


Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable? I was reading the Sipser's book on the Theory of Computation, 3rd edition and came up with a question. "Does showing a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?" I believe that the answer is NO, however, the Theorem 5.30 states something different.

There are two problems concerned in this question. One is $A_{TM} = \{ <M,w>\ |\ M \text{ is a TM and accepts } w\}$ and the other is $EQ_{TM} = \{ <M_1,M_2>\ |\ M_1, M_2 \text{ are a TMs and } L(M_1) = L(M_2)\}$.

On Page 238, the Theorem 5.30 is stated as follows:

  Theorem 5.30 $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.

The proof is by mapping reduction of $A_{TM}$ to $\overline{EQ_{TM}}$, and at the same time, reduction from $A_{TM}$ to $EQ_{TM}$. This way, it has shown:

$\overline{EQ_{TM}}$ is Turing-undecidable.
$EQ_{TM}$ is Turing-undecidable.

Note that this reduction does not show that either of $\overline{EQ_{TM}}$ or $EQ_{TM}$ are not Turing-recognizable, since $A_{TM}$ is Turing-recognizable.

On the other hand, on Page 209, we have the following definition

  A language is co-Turing-recognizable if it is the complement of a Turing-recognizable language.

which is accompanied by Theorem 4.22:

  Theorem 4.22 A language is decidable iff it is Turing-recognizable and co-Turing Recognizable.

Therefore, we can obtain the following Corollary: If a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable.

Therefore, it is shown on Theorem 5.30 that $\overline{EQ_{TM}}$ and $EQ_{TM}$ are Turing-undecidable. This does not tell me anything more than the following proposition:

  Either $EQ_{TM}$ or $\overline{EQ_{TM}}$ or both are not Turing-recognizable.

However, the Theorem 5.30 states something stronger.

Am I missing something?

... a problem and its complement are not Turing-decidable means that the language & its complement are not Turing-recognizable?

This claim is false. In fact, at least one of them (or both are) is Turing-recognizable. Assume that both the set (problem) $A$ and its complement $\overline{A}$ are not decidable. Then if both $A$ and $\overline{A}$ were recognizable (recursively enumerable) then that would mean $A$ and hence $\overline{A}$ are decidable (Theorem 4.22), a contradiction.

  ... however, the Theorem 5.30 states something different.

This theorem states that $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable. In other words, both $EQ_{TM}$ and $\overline{EQ}_{TM}$ are not Turing-recognizable (recursively enumerable). This does not contradict to the above-stated claim.

Also, pay attention that the theorem 5.30 reduces $A_{TM}$ to $\overline{EQ}_{TM}$ (not to $EQ_{TM}$ as you claim in your post)  meaning that $EQ_{TM}$ cannot be Turing-recognizable (otherwise $\overline{A}_{TM}$ would be Turing-recognizable and hence decidable).

You are right, if a language is not decidable, then either the language itself, its complement or both of them are not Turing-recognizable, and since the theorem 5.30 proves that $EQ_{TM}$ is not decidable, it follows that either $EQ_{TM}$ either, $\overline{EQ}_{TM}$ or both of them are not Turing-recognizable. But this result is weaker and does not contradict to the theorem 5.30. In fact the latter (weaker) result is not necessary since the theorem already establishes the stronger result.


Machine Learning method maps from $\mathbb{R}$ to $\mathbb{R}^2$ I have worked with image classification and image segmentation etc.
While working with images we are either mapping from $\mathbb{R}^2\to\mathbb{R}$ or $\mathbb{R}^2\to\mathbb{R}^2$. Are there any machine leaning methods that can map from $\mathbb{R}\to\mathbb{R}^2$. For example, I have a feature vector of $3$-$5$ elements and I want to map it to $32\times32$ (approximately).
Is is possible? If it is, by which methods?

Sure.  You can use a neural network with fully connected layers; or a neural network with deconvolutional layers.  The latter is common in image segmentation tasks, so you may already be familiar with it.


Trick/insight to I implement given boolean function with minimum numbers of given gate I solved bunch of questions which give some function and then ask to implement it with minimum number of gates of specific type, each having specific number inputs. I was making mistakes in all those problems by not implementing given function with minimum number of gates.

Let me give those problems one by one and explain my point.

  Problem 1

  What is minimum number of two input NAND gates required to implement the function:
  $f=\overline A \overline C+\overline A\overline B+\overline B \overline C$

I translated the function directly to the circuit as follows:

Then I converted this to NAND-only implementation as follows:

But when I checked the answer, it was saying lesser NAND gates. So I tried something different. I solved equation as follows:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}$
$=\overline{\overline{\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}}}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

And realized that I will need seven NAND gates for following:

$\overline{A}$
$\overline{B}$
$\overline{C}$
$\overline{(\overline{A}.\overline{C})}$
$\overline{(\overline{A}.\overline{B})}$
$\overline{(\overline{B}.\overline{C})}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

But then I checked detailed solution and found that the solution has come up with following equation:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}\overline{C}$
$=\overline{A}.\overline{C}+\overline{B}(\overline{A}+\overline{C})$
$=\overline{A}.\overline{C}+\overline{B}\overline{(\overline{A}.\overline{C})}$
$=\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

This requires six NANDs:

$\overline{A}$
$\overline{B}$
$\overline{C}$
$\overline{(\overline{A}.\overline{C})}$ (used twice in the equation)
$\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}$
$\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

So I was wrong twice!!!

Problem 2
Another problem gave truth table of the function and asked to implement it with NOR gate. I prepared truth table for it and grouped zeroes as follows:

Knowing that I have to use NOR, I thought I should form product of sum equation of this and then take double negation to get NOR friendly equation. So, I formed equation for it as follows:

$f=(x+\overline y)(\overline x + y)$
$=\overline{\overline{(x+\overline y)(\overline x + y)}}$ (taking double complement)
$=\overline{\overline{(x+\overline y)}+\overline{(\overline x + y)}}$

Now this looks perfect NOR equation as thought and it requires five NORs. But when I checked the solution, I came to know that this is indeed ExNOR equation. The solution formed sum of product equation of K map:

$xy+\overline x \overline y$

and then implemented ExNOR with four NORs, something like this:

Doubt

I have solved many other problems. It almost always turned out that I have followed one approach and the solution followed another to further reduce the GATE count. I feel there should be some steps / methods to get idea how many minimum number of gated are required. I know this problem is NP complete. However I feel that there has to some definite patterns on k map which can lead us / give direction / provide hint to correct final answer.

Can there be any such method? trick?

There is no trick.  There is no efficient method.  The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-hard, too.  That should tell you that there is no systematic approach that always works and is reasonably efficient.  Instead, you will have to use heuristics and trial-and-error.  For instance, you might have to try multiple methods and take the best circuit you can find among all of them.


How to compute moving unique item Imaging I am running a forum and I continuously have log in of members. A member can log in simultaneously many times

So I have :

Tom Jerry Jack Tom Joe Kay Neo Tom ...

each log in comes with a time stamp

I want to have an algorithm that can count how many UNIQUE names have logged in the past 1 minute.

How to design an algorithm like this?

My design is to use a std::map then continuously update/trim the map

I am wondering if there is any smarter solution here.

Any insight?

Keep a hash table that stores a histogram of the items that have appeared in the past minute, as well as a counter for the number of unique items, initialized at zero. Also keep a circular queue with the actual timestamped list of items.

Every time you see a new item or query the number of unique items, go over the circular queue and delete all items which are older than one minute. For each one that you delete, update the histogram. If a cell in the histogram reaches zero, decrement the unique items counter, and delete the cell. If you are adding a new item, update the histogram, and if the item did not appear in the hash table, increase the unique items counter.


Creating a decision tree? So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink).

I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, Multi-Way 3, or Binary. For example:

5: (Blue, Green,Red,Orange,Pink)

4: (Blue, Green), (Red), (Orange), (Pink)
   (Green,Pink), (Blue),(Red),(Orange)

3: (Red,Orange), (Blue,Green), (Pink)
   (Red,Blue), (Green, Orange), (Pink)

2: (Blue,Green,Red), (Orange,Pink)
   (Pink), (Blue, Green, Red, Orange)

And so on. But how can I make a comprehensive list of all the possible splits? Is there a specific algorithm I could use? Or how would I even know how many max possible combinations there are with this?

Any help would be greatly appreciated, thanks!!!

The entropy of a given attribute is non increasing over  refinement of partitions. This means that the best possible partition is singletons (one value per set). This is the method used for discrete attributes in known algorithms such as ID3 or C4.5.

As a side note, the number of partitions is given by Bell's number.


"Greater than" condition in integer linear program with a binary variable How can one model the following condition in an integer linear program?

$$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$

where $A \in \{0,1\}$ and $B, C \in \mathbb N$. We have upper and lower bounds on both $B$ and $C$.

I think I found the answer here!
It is sufficient to use the big-M method by introducing the following constraints:

B >= C + 1 - M*(1-A);

C >= B + 1 - M*A


Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link failures.

Looking into the details of this algorithm (in Figure 2, page 133), I found that it implicitly assumes the "conditional write" primitives at the side of servers:

case received from w
    <W, label_w>: label_j = max{label_w, label_j};
                  send <ACK-W> to w;

Here, the statement label_j = max{label_w, label_j} is equivalent to if (label_j < label_w) then label_j = label_w, requiring the variable label_j maintained by each process $j$ to be monotonic. This in turn needs the if-then "conditional write" primitive.

My first question is:

  (1) Is this "conditional write" primitive necessary? Do you know any literature on emulations of atomic, SWMR registers without such primitives?

In the last section of the same paper, titled "Discussion and Further Research", the authors mentioned the emulations of stronger shared memory primitives in message-passing systems in presence of failures. One typical example is read-modify-write (RMW).

My second question is:

  (2) Do you know any literature on the emulations of RMW-like primitives?

Google search and a quick glance over the "cited by" papers do not bring me anything specific.

A partial answer to the second question:

In the book "Distributed Algorithms" by Nancy A. Lynch (1996) (Section 13.2  "Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables"), we have the following impossibility result:

  Theorem 13.11  There does not exist a shared memory system using read/write shared variables that implements a read-modify-write atomic object and guarantees 1-failure termination.


Efficient algorithm to filter off points from a point cloud I have a master point cloud, which essentially just a list of points with {x,y} coordinates.

The point cloud is HUGE ( like, it can contain more than 1 million points). The problem now is that I have another (sub)set of point clouds, and I need to check whether the points inside the second point clouds are the same with any of the points in the first point clouds, and then remove them from the list.

The characteristics of the second point cloud:

The second point cloud points are usually clustered in a corner of the first point cloud ( but not always).
None of the points from the second point cloud will lie outside of the first point cloud ( the first point cloud always contain every single point of the second point cloud)

The naive algorithm will be something like this:

   public static List<Point> FilterPoints(Lis<Point> master, List<Point> subset)
   {
    var FilteredPoints = new List<Point>();
    for(int i=0; i< subset.Count; i++)
    {
        var isContained = false;
        for(int j=0; j< master.Count; j++)
        {
          if(subset[i].X==master[j].X && subject[i].Y==master[j].Y)
          {
              isContained = true;
              break;
          }
        }
        if(!isContained)
        {
           FilteredPoints.Add( master[i]);
        }
      }
     return FilteredPoints;
}

But is there anyway to improve over the above naive algorithm in terms of speed, given the known characteristics of the both point clouds?

PS: I've also asked about how to make use of C# language characteristics( if any) in order to improve the speed for the above algorithm at SO.

You should use a set data structure for your subset-list. This would allow querying if it contains a given point in constant time.

Your function, as python-like pseudocode:

def FilterPoints(master, subset):
    # take the list and convert it to a set ( O(|subset|)
    subset_set = set(subset)
    # iterate through master and and the points that are not in subset O(|master|)
    filtered_list = [p for p in master if p not in subset_set]
    return filtered_list

Some points:

If master is larger than subset, the algorithm will be $\mathcal O(|master|)$
The equivalent of set in C# should be HashSet


What is hardware trap? Since it's called a trap I consider it caused by software, so why it's called a hardware trap? And how does it work?

https://en.wikipedia.org/wiki/Trap_(computing)

It is called a hardware trap because the mechanism of triggering it, and handling it, is embedded in the hardware itself and it cannot be [fully] controlled/disabled in software.


What's the difference between studying "Software Development", "Software Engineering", "Computer Science" and "Information Technology"? I really cannot understand the key-differences between those fields of study. Can please someone explain it in detail? If one graduates from a Master program of Computer Science, how does he differ from the one graduated from a Software Engineering program, or one from IT?

As D.W. wrote this is somewhat subjective since there is no standard definitions for those fields of study.
Regarding your last question, my experience in a couple of European universities is that "Computer Science" is a more theoretical program, often branched from a math faculty while "Software Engineering" is more practical, often part of the Engineering faculty.


Does location transparency imply access transparency? In distributed systems theory, I have found the definition that a distributed system requires, among others, location and access transparency.

I was wondering if location transparency does not already include access transparency.

Wikipedia defines the two as follows:

  Access transparency – Regardless of how resource access and representation has to be performed on each individual computing entity, the users of a distributed system should always access resources in a single, uniform way.

  Location transparency – Users of a distributed system should not have to be aware of where a resource is physically located.

If I am not to become aware of where a resource is physically located, doesn't that automatically imply that I have to be able to access all resources in a uniform way?

If yes, could you leave out access transparency from the definition without changing its meaning?

There is certainly a strong dependency between these two properties and many examples will point to this conclusion. Think about an API that needs to use the same operations to access both local and remote files. If you already have a list of files, you are unaware of their physical location (e.g., some URL) since you retrieved these files or how they were retrieved (e.g., ftp?). It should imply that you used the same means to retrieve that list of files. But this is not entirely true. Let's simplify Wikipedia's definition:

Access transparency - enables resources to be accessed using identical operations.

Location transparency - enables resources to be accessed without knowledge of their physical or network location.

This 2 forms of transparency are necessary since they refer to 2 different architectural layers. The access transparency refers to the application layer, whereas location transparency refers to the physical layer.
Returning to the initial example, you access the list of files using the API, but you are not entirely sure how that list was retrieved or where those files were located before they were retrieved.


BIT: What is the intuition behind a binary indexed tree and how was it thought about? A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand the intuition behind such a tree? How was it invented? What is the actual proof of its correctness?

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation.  This answer goes into one possible derivation.

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements.  You could start off by writing out seven buckets into which the numbers will be distributed:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Now, let's suppose that the cumulative frequencies look something like this:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards.  For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

One way that we can think about improving this operation would be to change what we store in the buckets.  Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket.  For example, in our case, we would rewrite the above buckets as follows:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket.  However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence?  If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes.  Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node.  For example, suppose we construct the following binary tree from these nodes:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree.  For example, given our values, we would store the following:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

Given this tree structure, it's easy to determine the cumulative sum up to a point.  The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question.  As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

For example, suppose we want to look up the sum for 3.  To do so, we do the following:

Start at the root (4).  Counter is 0.
Go left to node (2).  Counter is 0.
Go right to node (3).  Counter is 0 + 6 = 6.
Find node (3).  Counter is 6 + 15 = 21.

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root.  Any time you follow a right child link upward, add in the value at the node you arrive at.  For example, to find the frequency for 3, we could do the following:

Start at node (3).  Counter is 15.
Go upward to node (2).  Counter is 15 + 6 = 21.
Go upward to node (4).  Counter is 21.

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree.  To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree.  Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

For example, to increment the frequency of node 1 by five, we would do the following:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

Starting at node 1, increment its frequency by 5 to get

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

Now, go to its parent:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We followed a left child link upward, so we increment this node's frequency as well:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We now go to its parent:

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

That was a left child link, so we increment this node as well:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

And now we're done!

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers.  Let's rewrite each bucket index in this tree in binary:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Here, we can make a very, very cool observation.  Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it.  You are now left with the following:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number.  For example, node 5 has binary pattern 101.  The last 1 is the final bit, so we drop that to get 10.  Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links.  For example, during a lookup, we just care about the right links we follow.  During an update, we just care about the left links we follow.  This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key trick is the following property of this perfect binary tree:

  Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

For example, take a look at the access path for node 7, which is 111.  The nodes on the access path to the root that we take that involve following a right pointer upward is

Node 7: 111
Node 6: 110
Node 4: 100

All of these are right links.  If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

Node 3: 011
Node 2: 010
(Node 4: 100, which follows a left link)

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

Write out node n in binary.
Set the counter to 0.
Repeat the following while n ≠ 0:

Add in the value at node n.
Clear the rightmost 1 bit from n.

Similarly, let's think about how we would do an update step.  To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward.  We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore.  We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly.  In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

Hope this helps!


Is the SK2 calculus a complete basis, where K2 is the flipped K combinator? Specifically, if I defined a new $K_2$ as
$$K_2 = \lambda x. (\lambda y. y)$$
instead of
$$K = \lambda x. (\lambda  y. x)$$
would the $\{S, K_2,I\}$-calculus be a compete basis?

My guess is "no," just because I can't seem to be able to construct the regular K combinator from the $S$, $I$, and $K_2$ combinators, but I don't have an algorithm to follow, nor do I have good intuition about making things out of these combinators.

It seems like you can define
$$K_2 = K I$$
with the regular $\{S, K, (I)\}$-calculus, but I couldn't really work backwards from that to get a derivation of $K$ in terms of $K_2$ and the rest.

My attempt at a proof that it was not functionally complete essentially attempted to exhaustively construct every function attainable from these combinators in order to show that you reach a dead end (a function you've seen before) no matter what combinators you use. I realize that this isn't necessarily going to be true of functionally incomplete sets of combinators (e.g. the $K$ combinator on its own will never dead end when applied to itself), but this was my best thought. I was always able to use the $S$ combinator to sneak out of what I thought was finally a dead end, so I'm no longer so sure of the feasibility of this approach.

I asked this question on StackOverflow but was encouraged to post it here. I received a few comments on that post, but I'm not sure I understood them right.

Bonus: if it isn't a complete basis, is the resulting language nonetheless Turing-complete?

Consider the terms of the $S,K_2,I$ calculus as trees (with binary nodes representing applications, and $S, K_2$ leaves representing the combinators.

For example, the term $S(SS)K_2$ would be represented by the tree

        @
       / \
      /   \
     @    K2
    / \
   /   \
  S     @
       / \
      /   \
     S     S

To each tree $T$ associate its rightmost leaf, the one you get by taking the right branch at each @. For example, the rightmost leaf of the tree above is $K_2$.

As can be seen from the ASCII art below, all reduction rules in the $S, K_2, I$ calculus preserve the rightmost leaf.

         @                           @
        / \                         / \
       /   \                       /   \
      @     g    [reduces to]     @     @
     / \                         / \   / \
    /   \                       e   g f   g
   @     f
  / \
 /   \
S     e

      @
     / \
    /   \
   @     f    [reduces to]   f
  / \
 /   \
K2    e

From there on, it's easy to see that if some term $T$ reduces to $T'$, then $T$ and $T'$ have the same rightmost leaf. Hence, there is no term $T$ in the $S, K_2, I$ calculus such that $TK_2S$ reduces to $K_2$. However, $KK_2S$ reduces to $K_2$, hence $K$ cannot be expressed in the $S,K_2, I$ calculus.


How do you have a type typed "Type" when implementing a programming language? I am working on the base of a language model, and am wondering how to represent the base type, which is a type Type. I have heard of an "infinite chain of types", but (a) I can't seem to find it on the internet while searching anymore, and (b) I am not sure if that's what I need or what it really means in practice.
Basically, I have a system in the language like this:
type User
type String
type X
...

Internally these get compiled to something like this:
[
  {
    type: 'Type',
    name: 'User'
  },
  {
    type: 'Type',
    name: 'String'
  },
  ...
]

But actually, the type: 'Type' gets further compiled not pointing to the string 'Type', but to the actual Type object:
[
  {
    type: theTypeObject,
    name: 'User'
  },
  {
    type: theTypeObject,
    name: 'String'
  },
  ...
]

So then the problem is, I need to now define or specify the "type type" itself:
type Type

which I try represent in a similar way, so now we have:
[
  {
    type: 'Type',
    name: 'Type'
  },
  ...
]

which is:
let theTypeObject = { name: 'Type' }
typeTypeObject.type = theTypeObject

Is that correct? What is this really saying? It is a circular structure, does this even make sense conceptually?
What would be better to do in this situation? Or is this perfectly acceptable? Basically I would like to understand how to explain what this circular structure even means, because it just makes me confused.

The type "Type" is typed "Type". It is an element of itself...

That doesn't seem logically possible. So what should I do?

I think what you might have found in your previous researches might be a pure type system.
In a pure type system, to avoid having "Type" being a "Type" at the same level that "Int" is a "Type", you would define another layer of "Types" where you would define "Type" as the entire first layer (and you would define this layer in the next one, and so on)
In practice, you could define your base types as "types", and the next layer would be kinds. The type "type" would be a kind. You might also want to consider functions of types to types as another kind.


Show that if $SAT \in P/klog(n)$ then $SAT \in P$ Show that if $SAT \in P/klog(n)$ then $SAT \in P$
Assuming that there is a a constant $k \in \mathbb{N}$ such that $SAT \in P/klog(n)$, I need to prove that $SAT \in P$.
Since $SAT \in P/klog(n)$, then there is a sequence of advices $\{a_n\}_{n \in \mathbb{N}}$ of length $|a_n \le klog(n)$ and a turing machine $M$ that runs for at most $n^c$ steps (for some $c \in \mathbb{N}$ such that:
$$\phi  \in SAT \Leftrightarrow M(\phi, a_{|\phi|}) = 1 $$
I tried to show a Turing machine $U$ that runs in a polynomial time and solves $SAT$.
$U$ on an input $\phi$:

calculate the size $|\phi|$
write $a_{|\phi|}$ on start of the working tape
simulate $ M(\phi, a_{|\phi|})$ in a way that when $M$ tries to read $a_{|\phi|}$, it will read it from the start of the working tape, and the working tape of $M$ will start from offset $|a_{|\phi|}|$.
$U$ will return the same answer as $M$

Is my answer correct? It seems like I'm missing something
Help would be appreciated.

You need to combine two ideas here:

There are only polynomially many possible advice strings.
If you can solve the decision version of SAT, then you can solve the search version of SAT.

There is a slight annoyance that you need the search-to-decision reduction to involve only constantly many different input lengths. Assuming for simplicity that you can perform everything using a single input length $n$, here is what you do: you go over all possible advices for length $n$, and for each one, either determine that the SAT instance is unsatisfiable, or attempt to find a satisfying assignment. If you find a satisfying assignment, then the SAT instance is satisfiable, otherwise it isn't.
I'll let you fill in the details.


Constructing a deterministic one way infinite single tape Turing machine If I have an input string that is only composed of $a$'s and $b$'s, how can I construct a Turing machine that only accepts strings where the number of $b$'s divides the number of $a$'s?

For example:

$aaaabb$ is accepted

$baaab$ is rejected

Here is a rather reasonable way to implement this in Turing machines:

Sort the bs and the as so that the input tape is composed of bs followed by as.
Repeatedly perform the following operation: remove $B$ as from the end of the input tape, where $B$ is the number of bs.
Accept if you never got stuck perform an iteration of the previous step.

The second step can be implemented without explicitly counting $B$. For the first step, you can implement the simplest algorithm you can think of, say bubble sort.


Is a "tree" with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree? For the following $2$ cases:

(1) $V = \emptyset, E = \emptyset $ (i.e. nothing at all)

(2) $V = \{v_0\}, E = \emptyset $ (i.e. only 1 root node $v_0$)

Are they considered a valid tree? It seems like different literature have different definitions.

I recall that I have read a data structures and algorithms book that defines "A tree is a set of nodes that either: is empty or has a designated node, called the root ...". According to this definition, (1) and (2) are both valid trees. I don't have the book on hand, but I am sure if you search the quoted sentence above in Google, you can get lots of results, as quite a lot of lecture notes follow this definition.

However, another definition of trees often met is defined in terms of graphs:

A tree is "a connected graph without a cycle".

Using this definition, my question is transformed to another question: "Is an empty graph a connected graph?" But the answer to the latter question is debatable according to here:

Is the empty graph connected?

My question is, which one is the more accepted definition?

Here are a few properties of trees which can be relevant:

A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).
A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).
A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).

These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.

Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.


Why the given NFA is not possible I am trying to construct NFA for all languages ending in 00.

I got this

and this

First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the DFA by subset construction, but it is not the correct one since it couldn't accept strings like 100.

Is this beacuse, there is no non determinism in the second NFA? Or what is the general rule in drawing an NFA? We could always provide some form of non determinism?

The second NFA doesn't accept $100$. Make sure that you understand when an NFA accepts a given word. In this case, your NFA gets stuck at the very first character, since there is no transition labelled $1$ from the initial state.


Is constant a variable or subtype? I think of type as a range of values that the variable can take whereas the rest is known constant or does not matter. Variables (instances or objects), which share common properties, are considered to belong to the same type/kind/class. That is, the type properties are constant across the type. The type is actually a common property of a class of objects (variables). The variables have a variable part, which may change, making them flipping from one subtype to the other. However, the same applies to subtypes: subtypes also share a common constant property.

I may describe a class by a circle in Vienn Diagramm. Its subspheres would be types or variables. I think that the variable means that it has some fixed part, its type, and variable part, which make it variable and not constant. The constants or values would be an elementary point in the diagramm.

For instance, integer is a subtype of real. Integer variable means that it can take concrete values within the range of the integer area. Similarly, boolean variables, taking only values 0 and 1, are subtype of integer. But, what is a constant 1? Is it a real or integer or boolean variable or it is a specific type, instances of which have a common property: they have a value of 1? Is it a known treatment?

My interest stems from the practice: how can I save memory fixing the common part of variables in a language processing framework?

This seems very confused. Probably you should state which programming language you are referring to as some of these concepts may have different definitions depending on the language or formalism. Much is arbitrary (possibly not always too consistent).  For example, you do not necessarily have booleans as a subtype of integers.

One important issue is to distinguish syntax (what you write to talk about entities) from semantics (the actual entities you wish to talk about). In a simple world, a type may be understood as a set of values that the language can manipulate through specific representations. A constant is a representation of a specific value. In many languages, a constant is a name that is given to a specific value in a given context. A variable is a place holder for a value, that may change.  Now this is to be interpreted a bit differently depending on the type of programming langusge, notably imperative of functional (there are other kinds).

Things get more complicated when you start aggregating values in various ways, because some language will let you consider aggregates where some components may change.

You should probably go back to a textbook on programming languages.

P.S. I agree that considering types as sets of values is too simplistic. But I am trying here to make as simple an answer as I can. This is precisely why considering boolean as a subtype of integer may not always be a good idea, or may not be as simple as it may seem.


Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"? Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched literals in the clause. This prevents checking every clause for every newly assigned literal.

The correctness of the scheme comes from the fact that clauses are disjunctions and will only be false if all literals in it are false. So we know it is not false until at least the watched literal is false, and we only need to check when that happens.

I am wondering why the dual idea of a "watched clause" is not used as well. This is how it would work: the overall formula is a CNF, that is, a conjunction of clauses. The watched literal scheme already checks very fast whether the CNF has become false. However, it would also be useful to detect when it becomes true: no further search would be needed then. A conjunction is only true if all clauses in it are true. So we choose one "watched clause" $C$ and, if a literal in $C$ is assigned a value, we check to see if $C$ has turned true. If so, we mark that clause as now irrelevant, and pick another clause not yet satisfied. If we cannot find a not-yet-satisfied clause, all clauses are satisfied and the problem is satisfiable.

I realize this would require keeping track of more information; assigning to literals would now not only require checking if they are watched literals, but also if they are in the watched clause. More importantly, looking for a new watched clause requires checking if other clauses are not yet satisfied, which means checking all their literals. Depending on the structure of the problem instance, this could be much slower. However, for some instances (for example, problems with small clauses) this would be much faster because satisfaction would be detected much sooner.

So my question is whether this is not used simply for empirical reasons (say, it would be slower for most benchmarks), or if there is a deeper flaw about it that I am missing.

A secondary question is: if this is a merely empirical issue, then is there some simple argument predicting this from the description of the technique alone, or is it something that would need to be observed in practice? Or, in other words, if this is a bad idea, is it so in principle, or just empirically?

Addendum:

It has been suggested by an answer that the notion of watched literals implies the use of DPLL which implies tracking which clauses have been satisfied, and that therefore the question does not make sense. It is true that watched literals are used in the context of DPLL, but it is not true that this means tracking satisfied clauses.

The paper on Chaff, which defined watched literals, describes DPLL in pseudo-code as

while (true) {
    if (!decide()) // if no unassigned vars
        return(satisifiable);
    while (!bcp()) {
        if (!resolveConflict())
            return(not satisfiable);
    }
}

This shows that satisfiability is decided as positive only when all variables are assigned, not when all clauses are satisfied (which could happen much earlier). Chaff and zChaff have been the basis for many of modern SAT solvers, including the very prominent MiniSAT.

The same idea is described in detail in Filip Maric's paper "Formalization and Implementation of Modern SAT Solvers", which describes this approach as the basis for many of the most prominent SAT solvers today.

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign.  So the only time that a SAT solver would save by early notification is the time it would take to assign values to any remaining unassigned variables.  This is a one-time cost linear in the number of variables in the formula.  It's linear because there can be no backtracking once the formula is solved.

Meanwhile, to maintain your watched clause pointer you must do a search to find a new unsatisfied clause each time your watched clause is satisfied.  That search is linear in the number of clauses in the formula.  These searches will be triggered during the exponential part of the search and so you will probably do many of them on your way to finding a satisfying assignment.

The net result is that you will waste more time than you will save trying to immediately notice when all clauses are satisfied.

Note that if you're adapting a traditional SAT solver to count solutions, then your idea has more merit.  Noticing that all clauses are satisfied while there are still unassigned variables means you have found $2^n$ solutions to the formula, where $n$ is the number of unassigned variables.  This provides an exponential speedup over finding these solutions one by one, so the lazy clause tracking could potentially pay for itself.  However, an alternative would be to notice a satisfying assignment in the usual way and then undo assignments in reverse order until a clause is left unsatisfied.  You would have the same $2^n$ speedup without the clause tracking overhead.