Understanding NFA (nondeterministic finite automaton) with a null transition I'm reading Computer Science: An Interdisciplinary Approach. It mentioned an NFA (nondeterministic finite automaton) with a null transition, as shown above, recognizes all binary strings that do not contain bba as a substring.

I didn't quite understand why it says so. If the null transition happens before reading the bba, it stuck at state 2 and will report yes at the end?

If a run of an automaton reaches a state where it has no legal transitions for the next input character, that run rejects immediately.

So, in your example, if the automaton makes the null transition, it can read $bb$ while staying in state $2$.  But when it reads the $a$, it has no legal transition so that run rejects.  Any run that stays in states $0$ and $1$ must also reject, because those two states are rejecting states. Therefore, the automaton does indeed reject all strings containing $bba$.


Does the underlying computational calculus in type theories affect decidability? I'm looking for a high-level explanation although if that isn't possible or difficult, I'd prefer references to books/papers.

I understand that modern type theory is inspired by Curry-Howard correspondence. From the Wikipedia article on Curry-Howard correspondence:

  The correspondence has been the starting point of a large spectrum of
  new research after its discovery, leading in particular to a new class
  of formal systems designed to act both as a proof system and as a
  typed functional programming language. ... This field of research is usually referred to as modern type
  theory.

Looking at the various type theories proposed and under development, I have a few basic questions:

1. Most modern type theories marry a type system with lambda calculus. Are there examples where a type theory uses a computational calculus other than lambda calculus?

2. At a very high level, if every modern type theory is a bundle of a type system and a computational calculus and the computational calculus is turing-complete (like lambda calculus), does the computational calculus in any way affect the decidability of decision problems like type checking, type inference, etc.? (AFAIK modern type theories tweak the type system while keeping the associated turing-complete computational calculus intact and just tweaking the type system affects decidability of type checking, type inference, etc.)

EDIT

NB: The distinction between Type Theory 1 and Type Theory 2 is based on their application in formal verification of programs and not based on the philosophy of type theory research. Also, the Program/Computation/Dynamic blocks are bigger as I guess existing programming languages have higher computational complexity than the type theories used for formal verification of their programs.

W.R.T. to the illustration above:

1) In type theory 1 methods, are type theories used both consistent and complete (w.r.t. Godel’s incompleteness theorem)? If there are type theories in proof assistants that are incomplete; leading to undecidable decision problems, how does the undecidability manifest in practical applications (like proving the correctness of a complex distributed systems protocol)?

2) In type theory 2 methods, what are the limitations of type theories in static analysis (w.r.t. Rice’s theorem)? Here, is decidability in type theories also affected by the computational model of programming language (eg. imperative vs functional languages)?

I don't think that the term "modern" helps distinguish anything.  One way to explain is to draw a distinction between "behavioral", or "semantic", type theories and "formal", or "syntactic", type theories.

Behavioral type theories start with a notion of computation (say, an operational semantics of some kind), and define types as descriptions of program behavior, ie specifications.  For example, one might specify that a function takes primes to primes as a description of how it behaves.  Membership in a type is a matter of truth, not formal proof, and is never remotely axiomatizable, by Gödel's Theorem.

Formal, or syntactic, type theories are given by a collection of rules, including axioms as no-premise rules.  They are inherently recursively enumerable, and never come close to any notion of truth.  In particular such type theories, which often enjoy a (n empty) correspondence with a logical system (the poorly named C-H Correspondence), have no inherent meaning, computational or not.  They are mere formalisms.

The two concepts may be linked by stipulating a priori that programs must be "well-typed" in the formal sense, with specifications of behavior refining types (for example, isolating the primes among the naturals). There are good reasons to take this viewpoint, namely that the rules prevent you from writing the code that you didn't want to write (eg, enforcing abstraction boundaries).  But they also prevent you from writing the code that you do want to write (they define up-front what are the programs).  The benefit of such restrictions is something called "the fundamental theorem", which states that syntactically well-formed programs enjoy behavioral properties associated to their types, a generalization of "type safety".  In particular, the parametricity theorem is an example; it expresses that abstraction is properly enforced.


Product Sum of Special Arrays Can someone please explain why this is correct:
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+= productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return (depth)*sum;
}

But, following is wrong:
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+=(depth)* productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return sum;
}

I haven't been able wrap my head around it. Why is does it give wrong answer if I multiply the sum with depth before the for loop on an array ends?
It is clear from the sample output that if there are multiple array items at a depth, we are supposed to multiply the sum with the depth as many times.
Eg. depth 2 is multiplied by the sum twice in the example.
Could someone please break it down for me?

here, you are multiplying the depth of the "parent" array, instead of the nested array.
sum+=(depth)* productSum(array[i],depth+1)

try this
 sum+=(depth+1)* productSum(array[i],depth+1)

multiply it by depth+1


If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$? If $\overline{M}$ is recursively enumerable and $A$ is recursive, what could we say about $A \cap M$?
I think that as we know nothin about $M$, in general case we can't  determine wherther a random element $m$ belongs to $M$, so we coundn't say anything about $A \cap M$. Am I right?

If $\overline{M}$ is r.e., then we do know something about $M$: namely, that it's co-r.e. And the intersection of any two co-r.e. sets is co-r.e., so $A\cap M$ is co-r.e. (every recursive set is a fortiori co-r.e.). Beyond that, of course, we can't say anything: every co-r.e. set is of the form $A\cap M$ for some recursive $A$ and some co-r.e. $M$ (take $A=\mathbb{N}$ and $M=$ the co-r.e. set in question).

This may seem a bit silly, but being the complement of an r.e. set is a very strong property, even though we think of it less than r.e.-ness. Also, lots of natural sets are co-r.e. but not r.e., like the set of (indices for) Turing machines which never halt on any input. So the conclusion "$A\cap M$ is co-r.e." is actually quite meaningful.

This answers your specific question, but let me say a bit more.

We didn't really use that $A$ was recursive, merely that $A$ was co-r.e. But what if $A$ is merely r.e.? Then in general $A\cap M$ is neither r.e. nor co-r.e. This is the first step into the difference hierarchy: $A\cap M$ can be rewritten as $A\setminus \overline{M}$, that is, as the difference of two r.e. sets, and we can continue further and talk about more complicated Boolean combinations of r.e. sets. It turns out that this gives a proper hierarchy, even in the coarse terms of Turing degree: for each $n$ there is an $(n+1)$-r.e. set which is not of the same Turing degree as any $n$-r.e. set (I believe this was proved by Cooper but I don't have a reference on hand; it certainly followed his proof of the case $n=1$).

We can try to continue the difference hierarchy into the transfinite but one runs into some difficulties in doing so (namely, the issue of finding appropriate "names" for complicated infinite ordinals - this is where Kleene's $\mathcal{O}$ becomes unavoidably relevant). What we get winds up not being a true hierarchy: even though the ordinals are linearly ordered, we can't avoid having different "difference levels" which are incomparable. The resulting "pseudo-hierarchy" is however a quite interesting object, and is called the Ershov hierarchy.

For more information on this, I strongly recommend the first couple sections of the paper The Ershov hierarchy by Stephan, Yang, and Yu.


What is the complexity of the algorithm to calculate power set of a set? Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality n, there is a for loop iterating 2^(n-1) times. Hence the time complexity has to be O(2^n).

However, the time complexity as per the solution, is O(n*2^(n-1)). What mistake am I making?

Arraylist < Arraylist < Integer >> getSubsets(Arraylist < Integer > set, int index) {
    Arraylist < Arraylist < Integer >> allsubsets;
    if (set.size() == index) { //Base case - add empty set
        allsubsets = new Arraylist < Arraylist < Integer >> ();
        allsubsets.add(new Arraylist < Integer > ()); // Empty set
    } else {
        allsubsets = getSubsets(set, index + 1);
        int item = set.get(index);
        Arraylist < Arraylist < Integer >> moresubsets
        new Arraylist < Arraylist < Integer >> ();
        for (Arraylist < Integer > subset: allsubsets) {
            Arraylist < Integer > newsubset = new Arraylist < Integer > ();
            newsubset.addAll(subset); //
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    return allsubsets;
}

The pseudocode looks like:

// set: The set[0:n-1] which the power set has to be computed for
set getSubset(set):
    1. set_size = size(set)
    2. set_size == 1:
        2.1 return [{}, set]
    3. power_set_of_subset = getSubset(set[0:set_size-2])
    4. last_element = set[set_size-1]
    5. power_set_of_set = power_sets_of_subset
    6. for subset_of_subset in power_set_of_subset:
        6.1 subset_of_subset.add(last_element)
        6.2 power_set_of_set.add(subset_of_subset)
    7. return power_set_of_set

The running time of step 6 depends on the size of subset_of_subset.

The reason is that the final list needs to contain both the original subset and the subset with last_element added to it. This requires copying the subsets, which takes time linear in its size.

Consequently, the running time of the algorithm scales at least as the total size of all subsets, which is $n2^{n-1}$.


Determining how similar a given string is to a collection of strings I'm not sure if this question belongs here and I apologize if not.  What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" in a bag of strings.  For example, if I have bag of 10,000 US city names, and then I have the string "Philadelphia", I would like some quantitative measure of how likely 'Philadelphia' is a US city name based on the US city names I already know.  While I know I won't be able to separate real city names from fake city names in this context, I would at least expect to have strings such as "123.75" and "The quick red fox jumped over the lazy brown dogs" excluded given some threshold.

To get started, I've looked at Levenshtein Distance and poked around a bit on how that's been applied to problems at least somewhat similar to the one I'm trying to solve.  One interesting application I found was plagiarism detection, with one paper describing how Levenshtein distance was used with a modified Smith-Waterman algorithm to score papers based on how likely they were a plagarized version of a given base paper.  My question is if anyone could point me in the right direction with other established algorithms or methodologies that might help me.  I get the feeling that this may be a problem someone in the past has tried to solve but so far my Google-fu has failed me.

Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined.

Given the heuristics, you can use likelihood to get a score which would (hopefully) be higher for your sample data than for other text. In order to determine a reasonable threshold, you can perform cross-validation. Pick a set of sample phrases which are not city names. Divide the city names into two parts, a large (say 80%) part and a small (say 20%) part. Train your model on the large part (that is, collect statistics on the large part), and then evaluate your model on the small part and on the sample of bad phrases. Determine if there is a reasonable threshold that passes most city names, but only a small amount of bad phrases.


if P=NP, why is P a subset of NPC? Assuming P = NP, why should P be a subset of NPC?
Here is how I understand it:

P is a subset of NP
NPC is a subset of NP

if we solve an NP Complete problem on a deterministic machine in polynomial time then

NP is a subset of P
P=NP (from 1 and 3)
NPC is a subset of P (2 and 3)

But why is P a subset of NPC, if P = NP?
This question has been asked before and the answers just pointed to the definitions of NP, P and NP-C. I have gone through the definitions but still require a detailed picture.

To be in NPC a problem, C, has to be in NP, and every problem in NP has to be polynomial-time reducible to C.

If P=NP every problem in NP can be solved in polynomial time.

This means that if P=NP, we can for most problems in P define the following reduction to C; Solve the problem in polynomial time, if the instance you are looking at returns true then reduce it to an input to C for which we know that C returns true - Otherwise reduce it to an input for C that we know returns false.

So for an example; if we take C to the problem of determining if a number is even. And we want to reduce the hamiltonian path problem.  We solve the hamiltonian path problem; which we can do in polynomial time since we assume P=NP.  If we find that a hamiltonian path exists we select 2 as input to C.  If we find that no hamiltonian path exists then we select 1.

This of course fails if C always returns true, or always returns false, so those two problems, as noted by Tom, while part of P, can not be part of NPC.  However, all other problems in P will be in NPC if P=NP.


algorithm for predicting procces's memory/cpu usage based on other other prior/still running jobs In a 'pool' with a lot of  cpus ,jobs(processes) are running(lots of them) .

Given I have  time/resource usage 'samples' from many prior/still running jobs - how would you go about trying to predict the process resource usage ?

Very abstractly , what I think should be done is as follows :

1) New job is submitted and start running and I wait for some time to gather resource usage information/samples

2) find a subset of jobs that their  'behave' (up until that point in running time) 'similarly' - how would u do that ? maybe those who are always in a specific margin and also there average distance is closest ?

3) choose one job from the subset I found at stage 2, and give prediction of resource usage based upon that job..

Are there known/standard way for my objective ? Would love to hear your ideas,direction etc ..

Here are the broad outlines of one general approach:

Determine what observable attributes of a job might help you predict the resource usage of the job.  You'll have to hypothesize what these might be based on your domain knowledge of the kinds of jobs you run, as well as your knowledge of what attributes of a job can be measured and observed, before the job finishes.
Treat that set of observable attributes as the "feature vector" for the job.  Each job gets assigned a "feature vector", based on the values of those attributes.
Gather training data: gather a data set, from past jobs, where you have measured the attributes of the jobs before they finished running and also measured the actual resource usage of those jobs.
Now use some suitable machine learning algorithm to predict the resource usage of new jobs, based on the training set and the attributes of the new job.  Select some appropriate supervised learning algorithm.  The choice of a specific algorithm will depend on how you expect the resource usage to vary depending on the attributes.  (Is it a linear relationship?  Smooth curve?  Something else?)  You might choose linear regression, or CART trees, or something else entirely.  There's lots of literature on this -- I'll leave you to study it on your own and get up to speed on standard materials on this subject.

You'll have to work out the details on your own and play with it a bit to see how well it works in your particular setting.  I can't tell you whether or not this will work well in the end; that will depend on your particular workload and the types of jobs you are dealing with.


Finding n farthest leaves in a tree Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function:
$$f(N)=\sum\limits_{x_1,x_2 \in N, x_1 \neq x_2}{dist(x_1,x_2)}$$
where $dist(x_1, x_2)$ is the number of edges in a path between two vertices/nodes $x_1$ and $x_2$.
What algorithm can I use?

If you have a binary tree, you should be able to solve this using dynamic programming.
Let $A[v,j,k]$ denote the maximum possible value of the objective function
$$f'(N) = \sum_{x_1,x_2 \in N} \text{dist}(x_1,x_2) + k \sum_{x \in N} \text{dist}(v,x)$$
where $N$ ranges over all subsets of exactly $j$ leaves from among those that are descendants of $v$ (i.e., leaves of the subtree rooted at $v$).
If $v$ is a leaf, it is easy to compute $A[v,j,k]$ for all $j,k$.
If $v$ has one child $v'$, it is easy to compute $A[v,j,k]$ for all $j,k$ from $A[v',\cdot,\cdot]$.
So now suppose $v$ has two children $v',v''$.  Then we can work out a recursive equation for $A[v,j,k]$ in terms of values $A[w,\cdot,\cdot]$ where the $w$'s are descendants of $v$:
$$A[v,j,k] = \max A[v',j',k+j''] + A[v'',j'',k+j'] + 2 j' j'' + jk$$
where $j',j''$ range over all values such that $j'+j'' = j$, $0 \le j',j'' \le j$.  The intended meaning is that $j'$ counts the number of leaves in $N$ that are descendants of $v'$ and $j''$ counts the number of leaves in $N$ that are descendants of $v''$.  In other words, we split $N=N' \cup N''$ where $N'$ contains $j'$ leaves from the descendants of $v'$, and $N''$ contains $j''$ leaves from the descendants of $v''$; then (loosely speaking) we compute the maximum value of $f'(N)$ in terms of the maximum values of $f'(N')$ and $f'(N'')$.  The $2jj'$ term counts distances of the form $\text{dist}(x_1,x_2)$ where $x_1 \in N'$ and $x_2 \in N''$.  The $jk$ term accounts for the fact that the $j$ root-to-leaf paths all need to be extended by one edge (thank you @j_random_hacker).

If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $v$ with $m$ children, create a little binary tree with $m$ leaves, then put $v$ at the root of that binary tree and paste the children of $v'$ in at its $m$ leaves.  Put a distance of 0 on all the edges of that new little binary tree except the top level.  Repeat recursively.
In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $v,w$ is the sum of the distances on the edges in the path between $v$ and $w$.  Now you should be able to generalize the above algorithm to that case.  I'll let you handle the details.


All problems about Turing machines that involve only the language that the TM accepts are undecidable I came across the below statement in the classic text "Introduction to Automata Theory, Languages, and Computation" by Hopcroft, Ullman, Motwani.

All problems about Turing machines that involve only the language that the TM accepts are undecidable

They say that the above theorem is per Rice theorem which states that:

"Every nontrivial property of the RE languages is undecidable."

How are these two statements equivalent? The former deals only problems while the later deals with non trivial property.

There are a few keywords in the excerpt from the said text book - non-trivial, problem, property.

Now what is a problem, assuming we are not dealing with combinatorial optimization problems,i.e. we are dealing with only questions which have an YES or NO answer to them.
When you ask a YES or NO question to an input string if the answer is YES you place it in a set $L$ and if the answer is NO you just discard it. Now this set $L$ is the language or the problem. It contains all those strings which which satisfy our YES or NO question.

  All non-trival problems about Turing machines that involve only the language that the TM accepts are undecidable

Here the author is talking about YES or NO questions (with respect to Turing machines) only involing the language that the Turing machine accepts,i.e. the Recursively Enumerable language(RE), which means that our "problem" set shall contain only RE languages. Now a trivial problem is one in which the our YES or NO question is either satisfied by all input or satisfied by none of the input. So a non-trivial problem is one which is neither empty nor it has all possible inputs.

  Rice Theorem: "Every nontrivial property of the RE languages is undecidable."

Property of RE languages is a set of RE languages having the said property.

Non-trivial property: The property is either satisfied by all concerned languages or by none.

So "nontrivial property of the RE languages" becomes the set of RE languages and it is neither empty nor it has all possible RE languages.

By the above argument we can say that the two statements are equivalent.

(In fact property and problem are the same thing, they both are set of strings after all. Now we might think that property is a set of languages, although while it is true, it is inconvenient to represent languages in a set(as languages can be infinitely long), rather what is done is instead of the language , we represent the corresponding Turing Machine with a suitable encoding)


Why do we try to maximize Lagrangian in SVMs? I was learning about support vector machines from MIT OpenCourseWare. I figured it out. I understand why we try to minimize $\frac{1}{2} w^2$. I just did not get why we try to maximize Lagrange expression like said at 35:56 in the YouTube video.

Margin (width) of the support vector is $2/\|w\|$. We want to maximize width it means that we also want to minimize $\|w\|$ from the equation $2/\|w\|$. It is true that we also want to minimize $\frac{1}{2}\|w\|^2$. Now we use Lagrange expression here, $$L = \frac{1}{2}\|w\|^2 + \sum_i α_i(y_i(w \bullet x+b)-1).$$ To find the minimum of $\frac{1}{2}\|w\|^2$, we apply gradient; $∇L = 0$. From the $∇L = 0$ equation, we get $Σ_iα_iy_i = 0$ and $w = Σ_iαi_iy_ix_i$. Then by using $Σ_iα_iy_i = 0$ and $w = Σ_iα_iy_ix_i$ equations and putting this in the Lagrange expression we end up with $$L(w,b,α) = \sum_iα_i-\frac{1}{2}\sum_{i,j}y_iy_jα_iα_j(x_i\bullet x_j).$$

I really understand up to here, but the professor said that we want to maximize $L$ here, why?
I really don't understand. Why are we trying to maximize the Lagrange expression? I thought we were trying to minimize it.

I think the answer to this deals with convex functions and duality.

$$L(w, b, \alpha) = \frac{1}{2}\|w\|^2 + \sum_i α_i(y_i(w \bullet x+b)-1).$$

When you minimize this, you are minimizing it over $w,b$. As you stated, this will produce the Lagrangian dual function:

$\Theta (\alpha) = inf L(w, b, \alpha) = \sum_iα_i-\frac{1}{2}\sum_{i,j}y_iy_jα_iα_j(x_i\bullet x_j)$

The maximization must be done here, but of the function $\Theta (\alpha)$ (the Lagrangian dual function).

Here is some background on why we are maximizing:

1) Let $p*$ be the optimal value of the problem of minimizing $\frac{1}{2}\|w\|^2$ (the primal). The Lagrangian dual function has the property that $L(w, b, \alpha) \leq p*$. It is a lower bound on the primal function. Instead of solving the primal problem, we are want to get the maximum lower bound on $p*$ by maximizing the Lagrangian dual function (the dual problem).

2) The primal problem is a convex function. The Lagrangian dual function is a concave function(can be verified). Maximizing a concave function is equivalent to minimizing a convex function. Therefore it is easy.

3) Why maximizing $\Theta (\alpha)$ is as good as minimizing $\frac{1}{2}\|w\|^2$: Let $d*$ be the value of $max \Theta (\alpha)$. This primal convex optimization problem satisfies Slater's constraint qualification which gives us strong duality ($d*=p*$). Therefore, $max \Theta (\alpha)$ is the same as $min \frac{1}{2}\|w\|^2$.


Definition of "idempotence" of a function? Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not idempotent. However, it seems controversial whether the return value is required to stay the same. For example, is the below function idempotent?

int foo = 1; // global
int bar() {
    int ret_val = foo;
    foo = 5;
    return ret_val; // 1, 5, 5, 5...
}

Or is there consensus over this?

There are two related concepts called "idempotence" in programming. One is the mathematical one that quicksort and Raphael talk about. Namely, given a mathematical function $f$, $f$ is idempotent if $f(f(x))=f(x)$. Or more algebraically, $f\circ f = f$.

The other notion that's common in practice and particularly for distributed computations is if an identical "request" is made multiple times, the system will behave as if it was made once. For example, an HTTP PUT is supposed to be an idempotent request so that it can be transparently repeated in case it's suspected that an earlier request was lost. This sense of idempotence is important in distributed computing because it turns at-least-once semantics into effectively exactly-once semantics.

The second notion cast into the context of an imperative language would correspond to the property of a procedure or method that calling it once is the same as calling it arbitrarily many times with the same arguments (assuming no intervening related procedures/methods are called).

The second notion can be related to the mathematical notion by viewing the request/procedure/method as performing a function on the state of the system (taken broadly). An idempotent request/procedure/method, corresponds to an idempotent function on the system state.

Arguably, the response to an idempotent request should be the same on every request. In practice, the responses tend to be informational and so potentially non-deterministic (often due to the concurrency inherent in distributed computing), that you have no real guarantee of any response. For example, the MDN page I linked discusses the case of HTTP DELETE. A HTTP DELETE may return a 200 status code after successfully deleting a resource and then a 404 for future HTTP DELETE requests. But the non-determinism of networking means that making two identical DELETE requests could produce any of two 200 responses, two 404 response, a 200 response followed by a 404, or a 404 followed by a 200 response. (And, of course, many other possibilities such as a 503 response or no response.) The upshot is that your DELETE request could get a 404 response even when you expected a 200 response for a variety of reasons and thus, since the 404 response means the resource wasn't there at the time the request was processed*, you should treat that as just as good as having gotten a 200 response.

If the semantics of your procedure/method are: "on these arguments, do this, then non-deterministically return one of this set of responses", then the procedure/method is free to return different responses (from that set of responses) even when called multiple times with the same arguments. I would consider such a procedure idempotent assuming the "do this" part was idempotent. On the other hand, if the semantics of your procedure/method are: "on these arguments, do this, then if it is the first time this procedure was called return X else return Y", then I would not consider the procedure/method idempotent.

* Of course, someone could have added it back between the time the 404 was generated and the time you received it.


Algorithms on random geometric graphs A random geometric graph (https://en.wikipedia.org/wiki/Random_geometric_graph) is constructed by choosing $n$ points in $\mathbb{R}^d$ at random according to some distribution, and setting $p_i \sim p_j$ if $\|p_i - p_j\|<r$, for some parameter $r$. Geometric graphs are of use in modelling real world networks.

For example, we can model a transportation map using the uniform distribution on $[0,1]^2$.

I am interested in whether there are good graph theoretic algorithms for dealing with these graphs. For example, is there an algorithm for finding the shortest path between two vertices that is better (in expectation) for these graphs than BFS? Obviously such an algorithm would be useful for GPS manufacturers.

Does research like this exist?

The graphs that you get are known as unit disk graphs. There is a vast literature about algorithms on unit disk graphs. Since you are asking about shortest paths, check out this article by Cabello and Jejcic. Of course all of this will not take into account that the graphs are generated by some random process.

For further references consult the wikipedia page or the Cabello and Jejcic paper.


Is this a correct decider? We are given the following language

B = {$<M,i>$ : M is a turing machine and $i \in \mathcal{N}$ and M accepts some string in atmost $i$ steps }

Is language B decidable ?

As per a hint from another fellow user, I decided to construct the following decider for B. Call it D.

D = On input

Enumerate all the strings in $\Sigma^*$ in lexicographical order (shortlex). Let the generated sequence be $s_1,s_2,...$ where each $s_k$ denotes all strings of lenght $k$
Simulate each string in $s_k$ on M for atmost i steps.
If any of them is accepted, ACCEPT.
When we have finished evaluating strings for length $s_i$, output REJECT.

Is this the correct decider for B ?

This language is decidable.

Hint: If you are allowed to run for only $i$ steps, what can you do with input of size $j>i$?


A programming language that can only implement computable bijective functions? Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?

There is no such language.

However, have a look at Boomerang. It is a language for writing bijections between strings. I do not know how wide a class of maps is expressible in it, but I am sure you can find out if you search a bit.

It is reasonable to require of a programming language that the set of valid programs be recognizable by an interpreter or a compiler, i.e., that it be a computably enumerable set. Suppose then we had a programming language whose set of valid programs were computably enumerable and which implemented precisely all computable bijections $\mathbb{N} \to \mathbb{N}$. That would imply that we can computably enumerate all computable bijections (simply enumerate all valid programs in this programming language), but this is impossible by the next theorem.

Theorem: Suppose $f_0, f_1, f_2, \ldots$ is a computable sequence of computable bijections. Then there is a computable bijection which is not in the sequence.

Proof. We construct a bijection $g : \mathbb{N} \to \mathbb{N}$ as follows. To define the values $g(2 k)$ and $g(2 k + 1)$, we look at $f_k(2 k)$:

if $f_k(2 k) = 2 k$ then set $g(2 k) = 2 k + 1$ and $g(2 k + 1) = 2 k$,
if $f_k(2 k) \neq 2 k$ then set $g(2 k) = 2 k$ and $g(2 k + 1) = 2 k + 1$.

Clearly, for every $k \in \mathbb{N}$, $g$ is different from $f_k$ because $g(2 k) \neq f_k(2 k)$. Furthermore, $g$ is computable and it is a bijection because it is its own inverse. QED.


Selling blocks of time slots Given $n$ time slots that $k$ people want to buy.  Person $i$ has a value $h(i,j)\geq 0$ for each time slot $j$.  Each person can only buy one consecutive block of time slots, which could be empty.

Is there a polynomial-time algorithm to compute the maximum value the seller can achieve?

Without the consecutiveness constraint, we can give each time slot to the person who values it most.  Also, if we fix the order of the time slots of the $k$ people, then dynamic programming can be used to solve for the maximum value of the first $0\le i \le k$ people buying the first $0\le j \le n$ time slots.

Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively.

We design a colored DAG $G$ whose vertices consists of three parts:

"Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
"Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing this literal.
"Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.

The edges include:

$s_{i-1}v_i(1)$, $v_i(j)v_i(j+1)$, $v_i(k_i)s_i$;
$s_{i-1}\bar{v}_i(1)$, $\bar{v}_i(j)\bar{v}_i(j+1)$, $\bar{v}_i(k_i)s_i$;
and $s_{n+i'-1}w_{i'}(j')$, $w_{i'}(j')s_{n+i'}$.

For instance, from the 3CNF
$(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$
the following graph is constructed (The edge directions are from left to right).

Now it is not hard to see that the original 3CNF is satisfiable if and only if there is a $s$-$t$ path with different vertex colors in $G$.

(By the way, it is a by-product that the existsence of $s$-$t$ path with different vertex colors in colored DAG is $\textsf{NP-hard}$. I didn't find many literatures about this problem in computational perspective. If you know, please comment!)

So what is the relation between $G$ and OP's problem? Intuitively what we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

Our matrix $h$ have $2n+1+\sum_i 2k_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K_i=2i+2\sum_{j=1}^i k_i$.

For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
All the other entries are 0.

For example, for the above example graph the corresponding matrix is

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered.
For the column $K_i+k_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s_i$. Since column $K_i$ must be assigned to $s_i$, by the consecutiveness we have to lose the columns $K_i+1$ to $K_i+k_i$. Same things happen if the scheduling assign the column $K_i+k_i+1$ to $s_{i+1}$.

Therefore, in order to have the value $\sum_i k_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

As a conclusion, deciding the maximum value of a legal scheduling is in $\textsf{NP-hard}$. Maybe that's why all our previous attempts to find an algorithm failed.


FM-index - print all patterns How is it possible to print all patterns of length $k$ contained in a string, using the FM-index and Burrows-Wheeler transform?

PROBLEM DETAIL:
The input I have is:

the text encoded with the Burrows-Wheeler Transform
the data structure of the FM-Index.

In particularly for the second element listed, I have:

$C(c)$ is a table that, for each character $c$ in the alphabet,
contains the number of occurrences of lexically smaller characters in
the text
$Occ(c, k)$  is the number of occurrences of character $c$ in
the prefix of the Burrows-Wheeler transform $1..k$

The only strategy that I've found at the moment is to reconstruct the text from the Burrows-Wheeler transform and, during that operation, for every char print the pattern that starts from it. In pseudocode,

---------------------------------------------
DATA
---------------------------------------------

bwt[n]  => burrow wheeler transform of the text
C, Occ => FM-index data structure
K => lenght of the patterns to be extracted (so extract all patterns of length k from text T)

---------------------------------------------
Algorithm
---------------------------------------------

n = |bwt|; //text length
T[0,n]; //array used to save the original text
T[--n] = bwt[0]; //first char of the original text

currentIndex = 0;

for i = 0 to |btw(T)| - 1 do
    //get original
    lastFirst = c(bwt[currentIndex]) + Occ(bwt[currentIndex], currentIndex);
    T[--n] = bwt[lastFirst];
    currentIndex = lastFirst;

    //print pattern only if we have reconstructed at least k char
    if((|btw(T)| - n) >= k) from original text
        print T[n, n+k]; //print last k char reconstructed
    endif;
endfor;

Is there a better technique or strategy to solve the problem? Is there a strategy that doesn't need to reconstruct the original text?

If I understand correctly, you want to print every substring of length $k$ from the original text. To do this you will need to invert the Burrows-Wheeler transform completely at some point, which is indeed what you do in your pseudocode. One improvement for your method would be to just store the $k$ latest characters instead of storing the whole string.

Your method is already as good as it gets, as it is equivalent to doing one pass over the string and directly printing the substrings, which is the minimum you have to do in any case.

--

Edit: so we want to print each substring only once. Now the problem becomes more interesting. An easy solution is to store the substrings in a hash map, for example, and thus avoid printing duplicates. If you can afford storing the original string and the inverse suffix array, then there is a sophisticated solution available which is good if $k$ is small.

A basic operation on the FM index is a left extension of a string. If we know the range of suffixes in the suffix array that start with the string $\alpha$, we can compute in constant time the range of $w\alpha$ for any character $w$. Here's how. Let $(i,j)$ be the range of the string $\alpha$. The range of $w \alpha$ is:

$$(C[w] + occ(w, i - 1) + 1,\;\; C[w] + occ(w,j)) \;.$$

We can start with the range of an empty string, which is $(1, n)$, and do a depth-first search of left-extensions down to a depth of $k$. At depth $k$ we will print the substring corresponding to the current range. For this we need to have the original string and the inverse suffix array $ISA$, which is defined by $ISA[SA[i]] = i$, where $SA$ is the suffix array. The substring corresponding to the range $(i,j)$ is the first $k$ characters of the suffix $ISA[i]$.

This method is very efficient in practice if $k$ is small, as it often is in bioinformatics applications. For a more thorough explanation on the backwards search I recommend e.g. this blog post: http://alexbowe.com/fm-index/


How exactly does a two stack pushdown automaton work? I have to explain how a 2-PDA works and then write a program (in Delphi) which simulates a 2-PDA step by step for the language $L = \{w\$w\ |\ w ∈ \{0,1\}^n\ with\ n>0\}$. So far, so good.

Now I know that a 2-PDA works with two stacks and is equivalent to a Turing Machine. It reads from an input tape and can save the current digit in either the first or the second stack. How can I decide in which stack the digit is read and/or saved? Especially since it's a computer program that should deal with that step.

Since it's equivalent to a Turing Machine, I get that one stack can deal with the left side and the other with the right side of the input. However, this is not really enough information for me to write a programm that simulates it. So how does the 2-PDA read the word, for instance, 01001$01001 from language $L$. Where does it begin? How does it accept the word?

I know, so many questions, I don't want to have them answered all in much detail but the most important thing is just how it works.

To write a program that simulates a 2-PDA (which will be able to process any transition function $\delta$, not just a particular language) what you need to do is to implement a stack class, with just the operations that it is allowed to have. The simulator is essentially a loop that keeps track of the current state of $\delta$, which has to be stored in a suitable way, and of the current input symbol. You will receive as input the encoding of a function, and the input string.

As for the specific language at hand: the $\$$ in the middle actually makes it quite easy to design a transition function for this language. Without it, you would have a more difficult (and more interesting) problem. Just push symbols into one of the stacks and wait for the $\$$ to come up. You can then start using the other stack for the second half of the input string. Pop them both together. If in the process all symbols match, and in the end both stacks are empty, accept.

As you can see, we won't necessarily use the two stacks as if they stood for the content of the tape at each side of the head of a Turing machine.


what does the author mean by directory structure in operating system? I'm reading Operating System Concepts by Avi Silberschatz(9thE), in section 11.4 File-System Mounting, the author explains the steps of filesystem mounting as follows:

  The operating system is given the
  name of the device and the mount point—the location within the file structure
  where the file system is to be attached.
  Next, the operating system verifies that the device contains a valid file
  system.
  Finally, the operating
  system notes in its directory structure that a file system is mounted at the
  specified mount point.

I'm confused with the final step, since to the best of my knowledge, the directory structure is stored somewhere on the disk, which records the files' information -- such as name, location, size, and type. Then what does the author mean by directory structure in operating system? Is it the same directory on disk?

Additionally, which part finishes the conversion from file name to physical address on disk? Is it the disk driver or the disk controller or done by processor with memory?

Step 3 of that description is indeed a bit confusing, and your comments are right.  The short answer is that the OS keeps track, in memory, of the set of mounted file systems and where they are mounted.


Complexity of Linear Diophantine equations My question is simply, can linear Diophantine equations be solved in polynomial time?  Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are all integers, and solving for $x_i$.  The algorithm I am using is based off of the following journal article:

http://www.jstor.org/stable/3620787 .

The algorithm I derived from the article is roughly as follow:

Find a minimum coefficient (there could be many, just pick the any of them).
Take every coefficient that is not the one you picked in the modulus of coefficient you picked.
Check if any coefficients are 1, if so, go to 5.
Go to 1.
Back-substitute to find solution.

Currently, I have an incomplete argument that the algorithm is indeed polynomial time.  My argument is as follows:

Suppose we choose the $a_j$ that such that it minimizes the number of bits all of the coefficients are reduced by, thereby maximizing the number of iterations.  Then, after we compute ${a^{'}_{{i} \neq {j}} = a_{{i} \neq {j}}} \mod {a_j}$ we know that $a^{'}_{{i} \neq {j}} < {{a_{{i} \neq {j}}} \over {2}}$, because if it were not, then $a_j$ could go into $a_{{i} \neq {j}}$ another time.  On the next iteration, the previous minimum $a_j$ cannot be the new minimum, since every other coefficient is less.  Thus, the previous minimum will necessarily be reduced by one bit.  Hence, all of the coefficients are reduced by at least 1 bit every 2 iterations.  Thus, the maximum number of iterations is twice the maximum number of bits for a coefficient $2\log_2(\max {a_i})$,  the back-substitution takes exactly the same number of steps, thus I estimate the algorithm is $O(\log(\max {a_i}))$, which is polynomial time with respect to the number of bits in the coefficient representation.

Am I missing something or is this correct?  Please let me know if there is anything I need to clarify.

Yes, this class of equations can be solved in polynomial time.  In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$.  That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd.  In addition, if a solution exists, one can be found using the extended Euclidean algorithm.


Why can't we flip the answer of a NDTM efficiently? I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it is unclear how another NDTM $T$ can determine in $O(n^{100})$ time how to flip $M$’s answer.

My Problem is as follows: A NDTM outputs $1$ iff there exists a sequence of non-deterministic choices that leads to the accepting state. Furthermore, there exists a universal NDTM $NU$ that can simulate every NDTM with only a small (logarithmic) overhead. So why can’t we construct T as follows: First, simulate M with the universal NDTM which should be possible in time $O(n\log n)$. Then output 1 – M’s answer. This would mean that we can flip the answer of any linear NDTM in time $O(n\log n)$.

A nondeterministic Turing machine accepts if at least one path accepts; it only rejects if all paths reject. This asymmetry makes it hard to "flip answers".

For example, suppose you have a nondeterministic Turing machine $M$ that has two paths for input $w$: one accepts, the other rejects. $M$ has at least one accepting path for $w$, so it accepts. Suppose we want to produce a machine that accepts exactly the inputs that $M$ rejects.  The obvious first attempt is to take $M$ and make its accepting states reject, and its rejecting states accept. $M$ has one accepting path for $w$ and one rejecting path; this new machine $M'$ has one rejecting path and one accepting path. So it still accepts $w$, which it was supposed to reject!

A nondeterministic machine can't look at all its paths simultaneously and take action based on what all of those paths do. If you like, you can think of it as a form of parallelism where the threads are forbidden to communicate with each other. When all of the threads have finished the program must ask itself the following question: "Did at least one of my threads accept?" If the answer is yes, it is legally obliged to accept; if the answer is no, it is legally obliged to reject. It cannot do anything else.

When you simulate a nondeterministic machine $M$ using another one, $M'$, each path of $M'$ simulates one path of $M$ and sees only that path. It can't say, "If all those other paths rejected, I'll accept" because it can't see the other paths; it can only see itself. So all it could possibly say is things like, "If the path I simulated accepted, I'll reject" or "If the path I simulated accepted, I'll accept too". Then, at the end of the computation, the machine has to say, "If any of my paths accepted, I'll accept too", leading to the problem I described above. To invert the behaviour of $M$, each path of $M'$ needs to say, "If the path I simulated accepted, I reject; else, I accept" and, at the end of the computation, the machine needs to say, "If all of my paths accepted, I accept; else, I reject."  This is because, if all of the simulator's paths accepted, that means all of $M$'s paths rejected, so $M$ rejected, so the simulator needs to accept. But the simulator isn't a valid nondeterministic Turing machine because it isn't using the legally mandated acceptance criterion. It can't do that.

The only way we know to figure out if a nondeterministic machine rejects its input is to try every possible path and verify that they all reject.  After all, if even one of them accepted, the machine would accept the input.  But trying every possible path is exponentially slower than trying just one.


Proof that regular languages are closed against taking the even-length subset This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.

Suppose $L$ is a regular language over $\Sigma = \{0, 1\}$. Show that the language

$\qquad L' = \{w \in L \mid |w| \in 2\mathbb{N}\}$

is also regular.

What I find surprising is that the booklet mentions that the language $\{w \in L \mid |w| = 2^k, k \in \mathbb{N}\}$ is not necessarily a regular language.

The language $Even = \{w\in\Sigma^{\ast}\mid \text{length of }w\text{ is even}\}$ is regular. user5507's answer demonstrates this with an NFA, and it's a basic exercise in most texts.

Then given that $L$ is regular, if we know that regular languages are closed under intersection for the purposes of the question, then the language $L'=L\cap Even$ is also regular.

If we're not allowed to use these closure properties, we can recapitulate the construction that gives the closure property (I'll just sketch it). Given a DFA $M_{L}$ for $L$ and a DFA $M_{Even}$ for $Even$, we can construct a DFA for $L' = L\cap Even$ that has a state space that is the product of the state spaces of $M_{L}$ and $M_{Even}$, with the follow transition rule: if $\delta_{L}(\sigma, q_{i}) = q_{j}$ and $\delta_{Even}(\sigma, p_{m})=p_{n}$ where $\sigma \in \Sigma$ and the $p$s and $q$s are states of the appropriate machines, then the product machine has a transition $\delta_{prod}(\sigma,(q_{i}, p_{m})) = (q_{j}, p_{n})$. Our accepting states are those states $(q_{i},p_{j})$ where $q_{i}$ and $p_{j}$ are accepting states in their respective machines.

That's the long an fiddly way around.

The second question depends on $L$, that is, if $L$ is not regular, then the intersection of $L$ and $Even$ may is not necessarily regular - the $w\in L$ in the definition is key.

EDIT: actually, reading vonbrand's answer, I misunderstood the second part. He is quite correct - the second language is the intersection of $L$ and $X=\{w\in\Sigma^{\ast}\mid \exists i \in \mathbb{N} \text{ such that } |w| = 2^{i}\}$ - not $Even$. So while what I said about $L \cap Even$ with $L$ not regular holds, $X$ isn't regular to begin with, so we get the same situation, but $L$ is regular and $X$ isn't.


Doubt regarding deletion from a B-tree After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for rearranging the tree after deleting an element.

Why is that ?

Because it keeps the B-tree balanced?

In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, people would have suggested that by now. I believe that the reason why this is the case is that the current algorithm is the simplest way possible to solve the B-tree problem. i.e. there's no useful further reduction of the problem to find.

That said, you have to be consistent but you are free to decide whether you want a tree that for example has either left or right bias but never both.

When deleting you also have a choice in whether to borrow from left or right first, or whether to merge with left or right first. You need to do both but you can attempt either left or right first.

The B-tree algorithm has some ambiguity or arbitrary things about it. Some aspects of it can be done in any number of ways, the end result will be the same. This can be confusing if you are not used to dealing with such arbitrary and/or ambiguous things.


Notation for operational semantics that can be used in code comments I'm defining an intermediate language for a multi-backend code generator that I'm writing.  I want to document the operational semantics for this intermediate language in a way that is readable both from within the source code and generated documentation (ocamldoc).  The notation introduced used in "Types and Programming" languages is great for a book, but I don't want to try to do the prerequisite over conclusion style notation via ASCII art.

Is there a widely recognized notation for operational semantics that doesn't require non-ASCII characters?  I looked through various RFCs but can't find any that use a non-natural language way of specifying semantics.

The input format for the tool OTT is based on ASCII and the rules look very much like type system/operational semantics rules. Maybe you could use that format. I'm sure that the parser for the input format is available as open source.


Reducing CLIQUE to Super Connector problem I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.
Regular CLIQUE problem:

Input: An undirected graph $G$ and a positive integer $K$.
Goal: Does $G$ have a clique of size at least $K$?

Our problem:

Input: An undirected graph $G$ and a positive integer $K$.
Goal: Is there a group of size $K$ of super connectors in $G$?

A super connector is a node with at least $C$ (i.e., a fixed number of) edges. A group $S$ of super connectors is a set of super connectors all connected to each other.
A group of super connectors is thereby a clique and a return value of TRUE from our problem will result in TRUE in the CLIQUE problem as well.
My idea to solve this is that I modify the graph by removing all nodes that aren't super connectors. We are then left with a graph where every node is super connectors and can then input the graph in the CLIQUE problem to see if there exists a clique and thereby get a solution for our problem. By modifying the graph like this both of the problems will give the same outputs with the same inputs. Am I on the right path or completely wrong?

The simplest NP-hardness reduction is as follows. Suppose we are given an instance $(G,k)$ of CLIQUE. If $k \leq c$ then we solve CLIQUE by brute force in time $O(n^c)$. Otherwise, $G$ has a $k$-clique iff it has a $k$-clique consisting of super-connectors. This is because any vertex in a $k$-clique must have degree at least $k-1 \geq c$, and so is a super-concentrator.


Structural parametrization for weighted vertex cover Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(2^\ell n^c)$ time, where $n$ is the number of vertices and $c$ is a constant.
I tried to approach this by finding a tree and find VWVC there with polynomial time and then brute forcing the rest $\ell$ edges in $O(2^{\ell})$, unfortunately i found a counterexample very quickly. Also I attempted to somehow assign all edges a weight (maybe for $uv\in E$ set $w(uv)=w(u)+w(v)$) and compute the minimal spanning tree and do something with that but I couldn't show that this would yield optimal vertex cover either. I'm kinda lost. Any hints appreciated.

Find the set $L$ containing the $\ell$ extra edges (actually, find any set $L$ of $\ell$ edges such that $G-L$ is a tree).
Let $C$ be an optimal solution.
For each edge $(u,v)$ in $L$, guess whether $u \in C$. If you guess "yes", add $u$ to a set $X$, otherwise add $v$ to $X$.
(Notice that it is possible for both $u$ and $v$ to be in $C$, but we do not need to explicitly consider this case).
Overall, there are at most $2^\ell$ distinct choices for the $\ell$ guesses.
At least one set $X^*$ among the guessed sets $X$ is a subset of $C$.
Given $X^*$ you can find the minimum weighted vertex cover in poylnomial-time by considering $F=G-X^*$. Since all the edges in $L$ have an endpoint in $X^*$, $F$ is a forest. Then you can find a minimum weighted vertex cover $C_i$ for each tree $T_i$ in $F$. The set $\cup_i C_i$ is a minimum  weighted vertex cover for $F$, and $X^* \cup (\cup_i C_i)$ is the sought solution.
You could also directly find a minimum  weighted vertex cover for $G-L$ with the constraints that the vertices in $X^*$ are forced to be in the cover. This can be done, e.g., with a straightforward modification of the dynamic programming algorithm for trees.
Another option is setting the weights of the vertices in $X^*$ to $0$ (or to $\sum_{v \in V}$) making them essentially "free" to select.
Since you don't actually know $X^*$ you can run the above procedure on each guess $X$ and then select the cover of minimum  weight.


Turing machine for unary encoded quadratic numbers I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go something like this: If we have $0^{1^2}$, we can just cross off that only $0$ and accept. If we have $0^{2^2}$, we can first scan and cross off two zeros and then scan again and cross off the last two zeros since there are four zeros total. And then for $0^{3^2}$, we have $9$ zeros, so in three scans we can just cross off three zeros.

So can anyone tell me if I have the right idea and how I can put this into an implementation description? What I can't think of is, how would it know though that it has just one zero, or 4, or 9, or 16 and so on?


The min number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is In a sliding window ARQ scheme, the transmitter's window size is N and the receiver's window size is M. The minimum number of distinct sequence numbers required to ensure correct operation of the ARQ scheme is

min(M,N)
max(M,N)
M+N
MN
Answer given is M+N but my understanding is

According to the given question the communication between sender and receiver is unidirectional or bi directional?

If it is unidirectional then answer should be max (N,M) , as sender will send N frames and each frame should have unique sequence number and if it is bidirectional then it should be M+N as both will have their Frames In transition with unique sequence number.

Is my interpretation is correct? Please correct me if I am wrong!!
If not why M+N is correct?

Your interpretation of bidirectional is correct.

First of all, it should be bi-directional. Here is the reason. The receiver window size M is not equal to sender window size N so it must be bidirectional. If it is unidirectional, then the receive window should be 1 for Go-Back-N protocol and N for Selective-Repeat protocol.

Then it is very straightforward: the minimum sequence number should be N+M. For example, the sender could choose [0, N-1] as sequence numbers while the receiver could choose [10000, 10000+M-1] as sequence numbers.

One thing to note, this problem is not strict. If you use Selective-Repeat protocol, then the minimum sequence number should be 2*(N+M) to handle both new packet and a retransmission.


Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1? I am wondering if there is a log time WBT (weight balanced binary search tree) data structure in which for any node, the sizes of its left and right subtrees diff at most by 1.

PS: I have read through Balancing weight-balanced trees but the weights of subtrees can differ up to a factor of $\Delta$.

Refer the following paper; https://www.researchgate.net/publication/2241064_A_New_Weight_Balanced_Binary_Search_Tree.
It has both bottom-up and top-down restructuring.


Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one? So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact.

Can we use some sort of techniques on regular expressions to make them more simpler?

For example what is the relation between concatenation and kleene star? If we have a concatenation with an union between two expressions that have kleene star can we draw a conclusion using some sort of property to distribute the concatenation somehow or do something else. I just started learning this subjects and I may not be very good at expressing what I think right now.

Minimizing regular expressions is very hard, see for example a paper of Gramlich and Schnitger, who show that no $o(n)$ approximation algorithm exists unless P=PSPACE. Another type of answer to your question is the formal systems mentioned in my answer to your related question.


Clarifying Practicality and Usage of a DFA's Accepted Language I was reading up on DFA's and their accepted languages when I stumbled across this:

Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}.

Since any $wy$ has to be an element of $L$ in order for $w$ to be an accepted string, and $L⊆Σ^∗$, then wouldn't all states be accepted by $M'$?

For example, for machine $M'$ with the alphabet $Σ=$ {$0,1$}, let $w=01$. Since all values of $y$ also have to be in the alphabet $Σ^∗$, $w$ would have to be accepted. Let $y=10$, $wy=0110$, which is in the alphabet $Σ^∗$. Similarly, let $y=110$, $wy=01110$, which is again in the alphabet $Σ^∗$.

The text mentioned some transition from $M$ to $M'$, but what would the use of $M'$ actually be? How is it any different than, say, $L=$ {$w∈Σ^∗$}? Would they share the same finite-state diagram?

Picture the DFA $M$ as a directed graph, as the usual graphical depiction. Then the final states of your $M'$ that accepts prefixes of the language accepted by $M$ will have all states from which a final state of $M$ can be reached as final states. It should be clear that not all states of $M$ qualify. In particular, any dead states of $M$ (non-final states that loop back on all symbols) won't be final in $M'$.


What type of formal notation is being used here to represent functional algorithms? Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design.  I have experience with a number of programming languages, but my only experience with functional programming is in Scala.  I understood that I would have to pick-up Standard ML and Haskell from the description of the book, but when I started reading the first section, I wasn't familiar with some of the operators being used.

Here are some examples of function definitions from the first chapter of the book (free to preview on Amazon):

I have seen "^" and "v" used to represent "and" and "or," but some of the other syntax (like False (0,n)) still throws me off.

In this one, I'm not sure what the accumArray(+)... is referring to.  I'm thinking it's like a fold method using addition, but I don't understand the rest of the line.

Here, the author has done a good job of describing that \\ is set difference and the two vertical lines crossed with a horizontal one is union.  However, I've never seen anything like that union symbol before.

I don't want to know what each of these examples means as much as I want to know what library of formal representation is Bird using to represent these algorithms, and also, if a specific programming language (Haskell/SML?) syntax is being used as well in conjunction with these special symbols.

The language is pretty-printed Haskell.

In regular source code, it would look like this:

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter (<= n) xs) (repeat True))
               where n = length xs

countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) -- Not actual code
as \\ (bs ++ cs) = (as \\ bs) \\ cs
(as \\ bs) \\ cs = (as \\ cs) \\ bs


What is the relationship between NP/NP-Complete/NP-Hard to time complexity? I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (minus the P problems of course), and NP-hard problems seem to be worse: $n^n$ or $n!$ (Chess, TSP). Is this a misleading interpretation?

See the definition of NP completeness. For a problem to be NP-complete, it

needs to be in NP and
all NP problems need to be reducible to it in polynomial time.

Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems.

NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^{O(p(n))}$, for some polynomial $p(n)$. But it is well know that if P $=$ NP, then NP problems can be solved in polynomial time.

NP hard problems are at least as hard as NP problems – you cite a few examples.


How to uniformly sample a sorted simplex I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should satisfy:

x + y + z = 1
0 <= x <= 1
0 <= y <= 1
0 <= z <= 1
x >= y >= z

My guess is all i have to do is uniformly sample a simplex (Uniform sampling from a simplex), and then sort the elements. But i'm not sure whether the result sampling algorithm is uniform.

Also, rejection sampling is not ideal for me, because i'll use this for high dimension.

Yes, all you have to do is to uniformly sample a simplex, and then sort the elements, under the assumption that the given distribution on the simplex is invariant under the permutation of the coordinates and the probability of a 0-measure set is 0.

That assumption holds often by default. Hopefully it holds in your situation. otherwise, a different sampling method or some preprocessing/postprocessing may be needed.

Here is a simple argument that should convince you that uniformly sampling and then sorting results in uniform sampling, given that assumption. Suppose we get a sample $x<y<z$ in the end. It may come from any one of the six kinds of original sampling, $(x,y,z)$, $(x,z,y)$, $(y,z,x)$, $(y,x,z)$, $(z,x,y)$ and $(z,y,x)$. The original sampling is uniform everywhere, and hence uniform on a neighborhood of these six points. Combining six identical (small) disjoint neighborhoods of them and dividing by 6, we see that sampling and sorting is also uniform on a neighborhood of $(x,y,z)$. Since $(x,y,z)$ can be any given point with distinct coordinates and the set of all points with at least two equal coordinates has measure 0, the sampling and sorting is uniform on the whole sorted simplex.

A rigorous proof along the same line of reasoning can be written if we want to be more formal.


Does the distributive property apply to regular expressions? Let $(Q,\Sigma,\delta, q_0, F)$ be a finite automaton, does
$$
(q_1a+q_2b)c=q_1ac+q_2bc
$$

hold for any $q_1,q_2\in Q$ and $a,b,c\in \Sigma$?

Here $Sa=\{\delta(q, a)\mid q\in S\}$ and $qa=\{q\}a$ for any $S\subseteq Q$, $q\in Q$ and $a\in\Sigma$. The operation "$+$" means set union.

since someone has edited the question, the question seems much more meaningful , and yes the above equality holds , here the equations

taking LHS of the equation

= ( $q_1$a  $+$ $q_2$b ) c

=$\delta$ ( (   $q_1$a  $+$ $q_2$b ) , c )  { as you defined Sa={ δ (q,a) ∣q ∈ S} }

=$\delta$ ( (   $q_1$a )  $\bigcup$   $q_2$b ) , c )

=$\delta$ ( ( $q_1$a),c ))    $\bigcup$   $\delta$ ( (    $q_2$b ) , c )

=$q_1$ ac $+$ $q_2$bc

which is equal to RHS.


Turing machine for which it is impossible to decide if it halts? Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the turing machine never halts) or $2$ (=the algorithm could not decide if the turing machine ever halts). If it returns $0$ or $1$ the answer must be correct.

Of course there are (countable) infinite many calculatable functions which could be used for this. All those functions could be called $f_n(t_i)$ where $t_i$ is a turing machine.

For every $f_n$ there must be some $t_i$ for which the function is not able to decide if the turing machine halts or not.
\begin{align}
\forall n\in\mathbb{N}:\exists i\in\mathbb{N}:f_n(t_i)=2
\end{align}

One could then define a new $f_m$ which tries all previous defined $f_n$ and if one of the previous $f_n$ was able to decide if a turing machine halts it has the final answer. But of course this also does not work perfect, beause there are still some turing machines for which it is not possible to decide if they halt (otherwise the halting problem would be solved).

Then it is possible to say that a turing machine (or infinite many...) $t_i$ must exist for which all halting problem solver approximations $f_n$ must return $2$.

In words: A turing machine must exist for which it is not possible to decide if it ever halts or not. Is such a turing machine known? If not: why not? Or isn't it possible to find such a turing machine?

Thank you very much

A turing machine must exist for which it is not possible to decide if it ever halts or not.

This is an incorrect conclusion. For some ordering of $f$ and $t$, it could be that $f_n$ correctly solves all $t_i$ for $i < n$, i.e. every $t_m$ is solved by $f_{m+1}$. This would still not give a complete solution to the halting problem, as long as the function $n \mapsto f_n$ is not computable.


How does one simulate continuous gravity using a discrete timestep? While gravity in real life is continuous, computers are limited to discrete calculations.

Therefore, a seemingly correct projectile simulation inevitably drifts off.

For example:

// Repeat once per frame
position += velocity * deltaTime;
velocity += gravity * deltaTime;

Graphed, compared to the actual projectile formula

This is an example of Euler's Method

Using differentiation, you can find a better formula. Since discrete calculations only "drift" if they are non-linear, you only need to alter the position/time calculation.

// Repeat once per frame
position += velocity * deltaTime + gravity * Math.pow(deltaTime, 2.0) / 2.0;
velocity += gravity * deltaTime;

Even large timesteps align perfectly with the continuous graph:


I want to design a context free grammar for the following This below language

$$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$
where $n \geq0$.

Since this seems very much like homework, i will give you a little Hint, taking as example a sub-case of your language:

The GFC for the string $a^3b^3$ is the following:

$S ⇒ aSb$

$aSb ⇒ aaSbb$

$aaSbb ⇒ aaaSbbb$

$aaaSbbb ⇒ aaabbb$

You can take the above as a starting point from which to adapt the grammar to your case.


How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar I am trying to define a non terminal symbol in a LALR(1) grammar (with CUP parser). It is requested that

the <code> token must appear exactly twice,
while the <hour> token must appear at least once.

In the end I came up with this definition:

section     ::= hour_l CODE SC hour_l CODE SC hour_l ;
hour_l      ::= /* epsilon */
            | hour_l HOUR SC ;

where SC is a separator (semicolon) between tokens and hour_l is the non terminal symbol for hour's list.
This solution has a problem: HOUR can be absent, because epsilon can be reduced from hour_l.
Is there a clever solution other than specifying all possibilities or using the semantic capabilities of CUP (ie. putting a counter of how many times HOUR is present in section)? I'd prefer not to use semantics in order to achieve this; in fact, it seems to me this is syntax related.

Thanks

My solution, suggested by a friend, is to use a Finite State Machine. I drew a Deterministic Finite Automata, and $C$ is the final state accepted by this machine:

I then transformed it into a right regular grammar:

section     ::= c ;
a           ::= CODE SC ;
b           ::= a CODE SC ;
c           ::= c HOUR SC | b HOUR SC | e CODE SC ;
d           ::= HOUR SC | d HOUR SC ;
e           ::= e HOUR SC | a HOUR SC | d CODE SC ;

Hope it helps.


How can I restructure matrices to have non-zero elements close to the diagonal? I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members of class $j$.

The order of elements does not matter, but $c_{ii}$ has to be the correct predction of class $i$. So for any given matrix $C$ you can swap columns if you swap the same rows.

How can I order the classes $1, \dots, n$ so that the biggest elements are close to the diagonal?

I thought one might pose this as an optimization problem, e.g. minimize
$$\sum_{i = 1}^n \sum_{j=1}^n C_{ij} \cdot {|i-j|}$$

How could I minimize this?

Code and example

I've already visualized a $369 \times 369$ matrix without any optimization. The confuscation matrix as JSON file and the code are here.

Without modification, you get a score of 303535 for:

This looks as if there could be some improvement. A quick first thought was to just randomly swap rows. Letting this run for $10^4$ steps (~5 minutes) leads to a score of 82552 and a visualization which looks a bit cleaner:

Doing this, I realized that my score might also need some improvement. I instead of moving elements to the diagonal, it would be nice if big blocks within the matrix would only contain zeros.

The total number of possibilities to arrange the items in $C$ is equal to the number of permutations of a list of length $n$ and hence it is $n!$. Hence for $369$ classes it is already $369! \approx 10^{788}$ - too much to brute force.

See also

My similar question on datascience.SE


Partitioning in time complexity of the sum We all know the partitioning problem: Given a super-set S of integers, can we partition S into 2 subsets with the same sum. And of course this problem is NP-complete.

My question is - let's denote M as the sum of all numbers in S. Is O(M) considered to be polynomial in this case?

I will clarify: I want to prove that a certain problem is NP-hard, and in order to do so I use a reduction from partitioning that uses O(M) nodes in a graph. Is this considered to be a polynomial build?

A Turing machine $T$ runs in polynomial time if there is a polynomial $p$ such that the running time of $T$ on an input of length $n$ bits is at most $p(n)$. The same definition works for other machine models such as the RAM machine.

Whether $O(M)$ is polynomial time or not depends on the way you encode the input. If the input is encoded in binary, then $O(M)$ isn't polynomial time, since the input could be of length as low as $O(\log M)$. If the input is encoded in unary (i.e., a number $x \geq 0$ is encoded as $1^x$) then $O(M)$ is polynomial time. It is part of the definition of the problem to specify the way the input is encoded.


NP-complete promise problems? Are there any good examples of promise problems that are NP complete?

There's two trivial answers:

No. For a problem to be NP-complete it must be in NP. To be in NP it must be a decision problem and promise problems aren't decision problems (they don't have to answer Yes or No on inputs outside the promise).
Yes. If you want to say informally that something is NP-complete (usually meaning "there's an obvious equivalent decision problem that is NP-complete"), then you can reformulate any decision problem as a promise problem just by taking the promise to be the set of sensible inputs. For example we can make a promise version of Dominating Set by taking the promise $L_{YES} \cup L_{NO}$ to be the set of all simple, undirected, unweighted graphs (so if you give it an input that's not a graph, it doesn't have to do anything in particular).

So there's no list of NP-complete promise problems because either none of them are (the strict answer), or you can just take any NP-complete problem and make a promise version.


Finding loop invariant I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are two nested loops. I am also really grateful if someone have any tips regarding finding a loop invariant.
My idea is that all $i$ which are primes are set on true and all $i$ which are not primes are set on false.. but I don't think that this is the loop invariant.

PRIME_FILTER(n)
1  P = INIT(n) // Initialize array P[1::n] with True
2  P[1] = False
3  i = 2
4  while i * i <_ n
5     if P[i] == True
6       j = i * i
7       while j <_ n
8          P[j] = False // Not prime
9          j = j + i
10    i = i + 1
11 return P

Let's see what the algorithm does in its first few iterations:

Mark all elements other than 1 as "potentially prime".
Mark all multiples of 2, starting at 4, as "not prime".
Mark all multiples of 3, starting at 9, as "not prime".
Skip 4, since it is known to be not prime.
Mark all multiples of 5, starting at 25, as "not prime".
Skip 6, since it is known to be not prime.
Mark all multiples of 7, starting at 49, as "not prime".

So it continues, until the next element is already larger than $\sqrt{n}$.
Here is how we can describe the contents of the array:

All elements other than 1 are "potentially prime".
All elements not divisible by 2 are "potentially prime", except for 2.
All elements not divisible by 2,3 are "potentially prime", except for 2,3.
All elements not divisible by 2,3,4 (equivalently, by 2,3) are "potentially prime", except for 2,3.

And so on.
Hopefully this gives you some ideas on the loop invariant.


Efficient algorithm to generate undirected graph edges from 3D distribution of nodes based on distance I have a set of nodes where each node $n_i$ is associated with a cartesian coordinate $\vec r_i$ and a radius $\sigma_i$. I want to generate a graph data structure where nodes $n_i$ and $n_j$ are connected by an undirected edge if $|r_{ij}| < \sigma_i + \sigma_j$. This is not my field and I am interested in efficient algorithm/workflow/software suggestions. I am working in C++.

This is the intersection graph of a set of spheres.  The case of 2D disks, all of the same size, is well-studied; its intersection graph is known as a unit disk graph, and it has been studied in some depth in the literature.  I don't know if your case has been studied in the literature, but those are some search terms you could use to try to find related work.


Does JPEG compression use a heuristic model similar to MP3? I know that MP3 uses a compression heuristic that allows it to exclude storing frequency data outside a certain range due to the limits of human hearing.

Does JPEG employ some sort of non-linear quantization heuristic that accounts for the limitations of humans to perceive small differences in specific color bands or ranges?

Thank you in advance for any responses.

There are several lossy aspects of the JPEG algorithm. The main one is quantization of high-order Fourier coefficients, and a more minor one is downsampling the color components.

JPEG compression of a black and white image (we deal with color images later on) is composed of four main steps:

Divide the image into $8 \times 8$ blocks.
Perform a two-dimensional Fourier transform on each block (specifically, apply the discrete cosine transform).
Quantize each of the Fourier coefficients.
Encode the Fourier coefficients using Huffman coding.

In addition, the DC component (the average of each block) is encoded differentially (with reference to the previous block). The lossy aspect here is the quantization, specified by a quantization matrix. Higher order coefficients are quantized more heavily, and the coefficients were originally chosen experimentally (though in principle they can be optimized for each image, since they are stored in the JPEG file). The quality parameter mainly affects the quantization matrix.

Color images are encoded by first moving into the YCbCr color space (similar to television's YPbPr), in which Y is the saturation components, and Cb and Cr are the color components. The latter two components are downsampled by a factor of 2 in the horizontal dimension (this is the most common choice, though others are possible), since the human visual system is less sensitive to this kind of data. Each of the color components is then encoded as a black and white image, using two different quantization matrix, one for the Y component, the other for the Cb and Cr components. The latter matrix quantizes more heavily.


Show that a function belongs to grade of incline This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$

I need to show and proof to which of these function grades does the function: $n^7$ belong to.
I didn't get a chance to ask my professor on this topic so I'm not sure how to solve this problem.

The term of $O(...)$ means representation of the performance of a solution. It is not entirely clear what you see under the expression n ^ 7. And because it is a representation of the complexity of the algorithm is needed to know how this power will count. There can be several calculation algorithms, each of which will have a different expression of the complexity. If you used the algorithm to multiply numbers, then you can, for example, the multiplication using konvolučního algorithm for the discrete Fourier transform. Performance of such algorithm is the maximum $O(7\cdot n \cdot log\space n)$, where n is the number of components of the vector needed for representation of numbers using the discrete Fourier transform.
Otherwise, if this is just a number, then I can also provide your own custom algorithm that takes advantage of the symmetry of the multiplication, exponentiation, and in case there is no need to perform a transformation for the convolution and there would be performance requirements could be smaller.


Integer Programming Traveling Salesman - Checking if Tour is Complete I'm reading a Wikipedia article on the Traveling Salesman problem as an Integer Programming formulation (http://en.wikipedia.org/wiki/Travelling_salesman_problem). The authors have all their constraints and I don't understand the final one. The following statement is in there.

  To prove that every feasible solution contains only one closed sequence of cities, it
      suffices to show that every subtour in a feasible solution passes through city 0 (noting that
      the equalities ensure there can only be one such tour). For if we sum all the   inequalities
      corresponding to x[ij]=1 for any subtour of k steps not passing through city 0, we obtain:
      n * k <= (n-1) * k

I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalites?

A little further the author states the following.

  Without loss of generality, define the tour as originating (and ending) at city 0.
      Choose u[i]=t if city i is visited in step t (i, t = 1, 2, ..., n). Then
      u[i]-u[j] <= n-1,
      since u_i can be no greater than n and u_j can be no less than 1; hence the
      constraints are satisfied whenever x_{ij}=0. For x_{ij}=1, we have:

  u[i] - u[j] + nx[ij] = (t) - (t+1) + n = n-1,

  satisfying the constraint.

I guess I don't understand how this detects that we pass through all the nodes.

Okay, looking at this some more, I think I've discovered a bit more. This equation is the MTZ formulation (Miller-Tucker-Zemlin) and it's geared at finding subtours.

Having digested some snippets from papers like Gabor Pataki's Teaching Integer Programming Formulations using the Traveling Salesman Problem, there's a statement in there that if a subtour did not contain node 1, then along this subtour the u[i] value would have to increase to infinity. I'm not 100% sure, but what I think this means is that if you had nodes 3 and 4 linked together (edge from 3 to 4 and another from 4 to 3), you would have the following constraints...

$u_3 - u_4 + 1 \le (n-1)*(1-x_{34}) \le 0$

$u_4 - u_3 + 1 \le (n-1)*(1-x_{43}) \le 0$

The contradiction here is that $u_4$ is one step greater than $u_3$ which is one step greater than $u_4$.

First, an overview is as follows:

  The last constraints enforce that there is only a single tour covering all cities, and not two or more disjointed tours that only collectively cover all cities.
  To prove this, it is shown below (1) that every feasible solution contains only one closed sequence of cities, and (2) that for every single tour covering all cities, there are values for the dummy variables $u_i$ that satisfy the constraints.

Interpreting the last constraints as a theorem:
$$u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n \Leftrightarrow \text{there is only a single tour covering all cities.}$$
then part (1) is the necessary condition ("$\Rightarrow$"): every feasible solution in ILP implies a unique tour; and part (2) is the sufficient condition ("$\Leftarrow$"): every single tour corresponds to (at least) one feasible solution.

For your questions:

  I specifically don't understand the "For if we sum all the inequalities..." part. Sum which inequalities?

We aim to prove the part (1): every feasible solution contains only one closed sequence of cities. To this end, we should exclude the case that two or more disjointed subtours that only collectively cover all cities: For instance, subtours $0 \to 1 \to 2 \to 0 \bigcup 3 \to 4 \to 3 \bigcup 5 \to 6 \to 5$ covering all cities $0, \cdots, 6$ is not a legal tour, but it does satisfy the first and the second set of equalities.

Consider any subtour which does not pass through the city $0$ and sum the inequalities of $u_i - u_j + n x_{ij} \le n - 1 \quad 1 \le i \neq j \le n$ for the subtour (taking $3 \to 4 \to 3$ as an example):

Summing up $$(u_3 - u_4 + n \cdot 1 [x_{34} = 1] \le n-1) \text{ and } (u_4 - u_3 + n \cdot 1 [x_{43} = 1] \le n-1),$$ we have $$2n \le 2 (n-1).$$

Generally, for a subtour (which does not pass through the city $0$) with length $k$, we will get $nk \le (n-1) k$. Contradiction.

Therefore, every subtour must pass through the city $0$. Further, the first and the second equalities enforce that all subtours must be disjoint. As a consequence, there can only be a single tour covering all cities.

  I guess I don't understand how this detects that we pass through all the nodes.

As I mentioned in the "overview", part (2) is the sufficient condition: We are given a single tour covering all cities, we aim to show that this tour corresponds to some feasible solution in this ILP. Because such a given tour trivially satisfies other constraints which do not involve these $u_i$ variables, it suffices to show that there are values for $u_i$ that satisfy the last constraints. This is proved by construction: Choose $u_{i}=t$ if city $i$ is visited in step $t$.


Width of a String/Line in an Image I have been looking for a method to find the width of a line.

I found the solution(link: http://www.mathworks.com/matlabcentral/answers/88645-average-width-of-lines),

"sum up the image to get the area, then skeletonize the image and sum up that image to get the total length.Then divide the area by the length."

Can anyone please explain the following?
1. what is summing up to get image area?
2. what is summing up skeletoniized image to get length?
I did not get this.

I have to find the thickness of a string from a given image. I can take the image of any dimension and quality I want. How do i measure the thickness of a string? That is what I was trying to resemble as width of a line. Essentially, thickness of a string can be thought as width of a line, I think.

Moreover, I can not assign any unit to my measurement i.e., m/cm/mm. So I have to measure some sort of ratio to represent the thickness and reach a decision.

My outcome should be Yes or No based on the thickness. For example, if the thickness is greater that a certain value I would not take the string to process.

The string can be made of anything.

"sum up the image to get the area, then skeletonize the image and sum
  up that image to get the total length.Then divide the area by the
  length."

Input images is a binary image, thus either the pixel value will be zero(black pixel) or 255(while pixel).

Summing up the image gives the sum of all while pixels(black pixel are zero).

i.e., the area of whole white line

$Area = Sum/255$

After skeletonizing the image, the thick white lines become almost one pixel thick.

Summing it up will give the approximate length of the line.

Now, as we know the area occupied by the white line and length of the line.

Dividing them will result the thickness of the line.


Database normalization impractical After third form normalization, extra tables shall be created. And the functional determinant are used as primary key in the new table, as foreign key in the modified old table. My question is that following this strategy, the referential integrity enforces that when attributes have to be added to the new table before attributes can be added to the "old" table. one can't add attributes to the "Old" table first. However, in my application, it is more intuitive to add attributes in the old table first. It appears to me the normalization rule is not very applicable in such situation.

Database tables are not just files. In a way, they are also abstract entities. During the process of normalization of an existing dataset, a foreign key must coexist with the table to which it refers, so that referential integrity is never relaxed. In practice, this is not possible, but any intermediate steps should be considered only as implementation level issues.

That said, I can't see why creating the secondary table before updating the "old" table would be counterintuitive.

For the sake of intuitiveness, you can say that the "old" table will disappear, after the normalization process has been finished. Only new tables will be there, including a new version of the old table, with the foreign key already in place, and filled with data.


In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated? The sheet of equivalences given to us in class provides the the equivalences

\begin{array}{|c|c|c|}
\hline
\text{Resolution} & A \vee B, \neg B \vee C \models A \vee C &
\neg A \implies B, B \implies C \models \neg A \implies C \\
\hline
\end{array}

I noticed that the $A$ is negated. Is this necessary for proper Resolution? Or is this just an example that $A$ can be negated?

To me it makes logical sense that $A \implies B, B \implies C \models A \implies C$, but being somewhat new to the subject matter I would like to ensure that $\neg A$ is not necessary for Resolution.

The answer is yes. But the departure point is slightly different.
Here it is:

\begin{array}{|c|c|c|}
\hline
\neg A \vee B, \neg B \vee C \models \neg A \vee C &
A \implies B, B \implies C \models A \implies C \\
\hline
\end{array}

The former statement is just the fact that if you start with $A\vee B$
and turn it into an implication you find $\neg A\implies B$.


Function Maximization in Java I have a bivariate function like

$
f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y}
$

and I want to find its global maximum over a range of
$
x \in [0, 200] \text{, and } y \in [300,50000]
$

What kind of algorithms I can use to find the global maximum. I want to have keywords for searching and finding materials.

Are there any java library which I can use to solve these kind of problems?

The most basic algorithm is probably gradient gescent which can also be used for maximization. It uses the gradient of the function to optimize and (starting from an initial point) "goes" into the most promising direction. For maximization this is the direction of the gradient. Look at the examples on Wikipedia. That should give you an idea how it works. Note that in is pure variant, it always gets stuck in local optima. I don't know if there is a Java library for this. I programmed it myself some time ago, but this code is very specific to the task.

Another thing to look at is the Nelder-Mead method. It is also susceptible to local minima and requires a smooth function. It is implemented in Flanagan's Java Scientific Library. Basically you have to extend MaximizationFunction and implement the function

public double function(double[] param)

which contains your function above. This method evaluates your function given the parameters param (in your case two values: x and y) and returns the function value.

Then you can use the whole program like this:

//Create instance of Maximisation
Maximization max = new Maximization();

// Create instace of class holding function to be maximised
YourFunction funct = new YourFunction();

// initial estimates (your initial x and y)
double[] start = {100.0, 3000.0};

// initial step sizes (take a good guess)
double[] step = new double[start.length];
Arrays.fill(step, 100);

// convergence tolerance
double ftol = 0.0001;

// maximal number of iterations
int maxIter = 5000;

// Nelder and Mead maximisation procedure
max.nelderMead(funct, start, step, ftol, maxIter);

// result of maximization
double result = max.getMaximum()

Since your variables have restrictions, you should add some constraints via the addConstraint method of Maximization.


How do I do a subtraction question on turing machine For example, 111-11

I want to have the output as 111-11=1

I am a beginner at TM and am having a hard time trying to solve this question.

It seems that you have unary numbers, so there are three cases to consider: number you subtract from is greater, uqual or smaller, this gives you hint what to handle.

In unary when you subtract 11 from 111 (111 - 11 = 1) you have to delete ones in minuend until subtrahend is 0.
In case these are equal, you have to denote 0 (empty tape might denote this). In the third case, result is negative.

Case 1) 111 - 11 = 11 - 1 = 1 - 0 = 1
Case 2) 111 - 111 = 11 - 11 = 1 - 1 = 0 - 0 = 0
Case 3) 11 - 111 = 1 - 11 = 0 - 1 = - 1

So let us start with first phase: start with scratching from both sides, call it say qS:
'B111-11B' where B is blank, on qS put B at leftmost 1, switch state to qS1, which goes right until it finds B. Moves one to the left, if it is 1, put B and return to the leftmost 1 (say state qSr). After execution:
'BB11-1BB' repeat
'BBB1-BBB' if in state qS1 there is no 1 but -, put B on - and accept.

Case 2 would yield something like 'BB-BB', if you are happy with Blank tape as 0, case 1 solves it already, otherwise put 0 on the tape if there are no 1 left.

Case 3 leaves you with situation like 'B1-11B'. Here only modification is to accept when after - there is Blank. So one step later, there is 'BB-1BB', this is result already.

What could go wrong?
There might be input like 'B11-1-1B', if you are not promised it won't happen. In such case split going right in qS1 into find '-' and then find Blank. If after first '-' there occurs another one, reject on it.

To practice more you could write your code in simulator online, check addition first as Apass.Jack suggested. When you finish, try multiplication, the sooner the better.

To see a working version look at my subtraction code at simulator.

This code has format:
state read_symbol write_symbol direction new_state, everything after semicolon is a comment, halt-accept is accepting state, halt-reject is rejecting state * in direction is not move instruction (you may be familiar with S notation or do not really care how it moves, since machine halts now).

qS 1 _ R qS1 ; state to start scratching left to -
qS - - R q2 ; check if there is 1 after 1
qS1 1 1 R qS1 ; pass through 1
qS1 - - R qS2 ; minus found
qS2 1 1 R qS2 ; going for rightmost 1
qS2 _ _ L qSr ; blank found after all 1
qS2 - - * halt-reject ; second minus found, reject bad formatted input
qSr 1 _ L qSr2 ; scratch last 1
qSr - 1 * halt-accept ; scratched 1 at the beginning appears here.
qSr2 1 1 L qSr2 ; leave 1 as is
qSr2 - - L qSr2 ; leave - as is
qSr2 _ _ R qS ; start another pass

q2 1 1 R q2c ; there is a - but still input may be malformed, check it

q2c 1 1 R q2c;
q2c - - * halt-reject ; found second -, reject
q2c _ _ * halt-accept ; there is negative number on tape, accept

q2 _ _ L q2m ; there is only minus left, clean it up
q2 - - * halt-reject ; malformed
q2m - 0 * halt-accept ; accept after cleanup

; tested on accepting -, 1-, -1, 1-1, 11-1, 111-1, 1-11
; testet on rejecting 1--1, 11-11-, --, -1
; to explore it more, maybe -11-11 should give -1111? Not handled now