Abstract machine that can recognize repetition Let $C$ be an infinite set of characters.  I'd like an abstract machine which can recognize sequences consisting of $k$ (constant) of repetitions of a char from $C$.

For example, if ${x,y,z} \subset C$, and $k = 3$, it should recognize $xxx$ but not $ddd$ or $xyz$.  (The same char must be repeated.)

Since $C$ is infinite, a finite state machine cannot recognize this.  A Turing machine trivially can.  But we don't anything like the power of a Turing machine; simply extending the FSM with a single register that points to a member of $C$ is enough.

My question is: What's the simplest formal abstract machine that is powerful enough to recognize this? Is there a standard extension to FSM's that enables them to recognize this? If I have more complicated versions of this machine (e.g. Move from state 2 to state 3 if you encounter a $k$ repetition of a $C$ char), what's the best way to express them?

There is a generalization of NFAs in which the transitions are labeled with regular expressions. (They are equivalent to NFAs and DFAs.) You can represent "twice the same letter" by $\sum_{\sigma \in \Sigma} \sigma^2$. Of course, such expressions are not standard, but if you want a succinct representation, this is one.


Cache effective access time calculation In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct one.

Assume a two-level cache and a main memory system with the following specs:

h1 = 80%       t1 = 10ns    L1 cache
h2 = 40%       t2 = 20ns    L2 cache
h3 = 100%      t3 = 100ns   Main memory

t1 means the time to access the L1 while t2 and t3 mean the penalty to access L2 and main memory, respectively.

I see two formulas as described below:

1-   Teff = t1 + (1-h1)[t2 + (1-h2)t3] which will be 32. The logic behind that is to access L1, first. So, t1 is always accounted. Then with the miss rate of L1, we access lower levels and that is repeated recursively. I agree with this one! You can see further details here.

2- As discussed here, we can calculate that using Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 which yields 24. However, that is is reasonable when we say that L1 is accessed sometimes. You can see another example here. Although that can be considered as an architecture, we know that L1 is the first place for searching data. So, the L1 time should be always accounted.

Is there any suggestion for that?

This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question about how we interpret the given conditions in the original problems.

(By the way, in general, it is the responsibility of the original problem/exercise to make it clear the exact meaning of each given condition. A notable exception is an interview question, where you are supposed to dig out various assumptions.)

Let us take the definitions given at Cache Performance by gshute at UMD as referenced in the question, which is consistent with the Wikipedia entry on average memory access time.

  Cache Access Time

  The fraction or percentage of accesses that result in a hit is called the hit rate.
  The fraction or percentage of accesses that result in a miss is called the miss rate.
  It follows that hit rate + miss rate = 1.0 (100%).
  The difference between lower level access time and cache access time is called the miss penalty.
  Effective access time is a standard effective average.

effective-access-time = hit-rate * cache-access-time
                      + miss-rate * lower-level-access-time

  Miss penalty is defined as the difference between lower level access time and cache access time. Then the above equation becomes

effective-access-time = cache-access-time + miss-rate * miss-penalty

Since "t1 means the time to access the L1 while t2 and t3 mean the (miss) penalty to access L2 and main memory, respectively", we should apply the second formula above, twice. That is,

Teff = t1 + (1-h1)[t2 + (1-h2)t3] = 32

For the sake of discussion, if we assume that t2 and t3 mean the time to access L2 and main memory including the time spent on checking and missing the faster caches, respectively, then we should apply the first formula above, twice. That is,

Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 = 24.

For the sake of discussion again, if we assume that t2 and t3 mean the time to access L2 and main memory directly assuming there is no caches at all, respectively, then we should claim there is not enough information to compute a reasonable answer. Or if we can assume it takes relatively ignorable time to find it is a miss in $L1$ and $L2$ (which may or may not true), then we might be able to apply the first formula above, twice.

You could say that there is nothing new in this answer besides what is given in the question. I would actually agree readily. All I have done is basically to clarify something you have known as well as showing how to select the right definition or formula to apply.

Now that the question have been answered, a deeper or "real" question arises. Are those two formulas correct/accurate/make sense?

The picture of memory access by CPU is much more complicated than what is embodied in those two formulas. The actual average access time are affected by other factors [1]. However, we could use those formulas to obtain a basic understanding of the situation.


How do I find the shortest representation for a subset of a powerset? I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness.

Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence $w\in \Sigma^*$ of least length such that for each $L\in A$, there is a $k\in\mathbb{N}$ such that $\{ w_{k+i} \mid 0\leq i < |L| \} = L$.

For example, for $A = \{\{a,b\},\{a,c\}\}$, the word $w = bac$ is a solution to the problem, since for $\{a,b\}$ there's $k=0$, for $\{a,c\}$ there's $k=1$.

As for my motivation, I'm trying to represent the set of edges of a finite automaton, where each edge can be labeled by a set of letters from the input alphabet. I'd like to store a single string and then keep a pair of pointers to that string in each edge. My goal is to minimize the length of that string.

I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard.

Call the word $w\in\Sigma^*$ a witness for $A$, if it satisfies the condition from the question (for each $L\in A$, there's $m\geq 1$ such that $\{w_{m+i}\mid 0\leq i<|L|\} = L$).

Consider the decision version of the original problem, i.e. decide whether for some $A$ and $k\geq 0$, there's a witness for $A$ of length at most $k$. This problem can be solved using the original problem as an oracle in polynomial time (find the shortest witness, then compare its length to $k$).

Now for the core of the reduction. Let $G=(V,E)$ be a simple, undirected, connected graph. For each $v\in V$, let $L_v=\{v\}\cup\{e\in E\mid v\in e\}$ be the set containing the vertex $v$ and all of its adjacent edges. Set $\Sigma=E$ and $A=\{L_v\mid v\in V\}$. Then $G$ has a Hamiltonian path if and only if there is a witness for $A$ of length at most $2|E|+1$.

Proof. Let $v_1e_1v_2\ldots e_{n-1}v_n$ be a Hamiltonian path in $G$ and $H=\{e_1, e_2, \ldots, e_{n-1}\}$ the set of all edges on the path. For each vertex $v$, define the set $U_v=L_v\setminus H$. Choose an arbitrary ordering $\alpha_v$ for each $U_v$. The word $w=\alpha_{v_1}e_1\alpha_{v_2}e_2\ldots e_{n-1}\alpha_{v_n}$ is a witness for $A$, since $L_{v_1}$ is represented by the substring $\alpha_1e_1$, $L_{v_n}$ by $e_{n-1}\alpha_n$, and for each $v_i$, $i\notin\{1, n\}$, $L_{v_i}$ is represented by $e_{i-1}u_{v_i}e_i$. Furthermore, each edge in $E$ occurs twice in $w$ with the exception of $|V|-1$ edges in $H$, which occur once, and each vertex in $V$ occurs once, giving $|w|=2|E|+1$.

For the other direction, let $w$ be an arbitrary witness for $A$ of length at most $2|E|+1$. Clearly, each $e\in E$ and $v\in V$ occurs in $w$ at least once. Without loss of generality, assume that each $e\in E$ occurs in $w$ at most twice and each $v\in V$ occurs exactly once; otherwise a shorter witness can be found by removing elements from $w$.
Let $H\subseteq E$ be the set of all edges occurring in $w$ exactly once. Given the assumptions above, it holds that $|w|=2|E|-|H|+|V|$.

Consider a contiguous substring of $w$ of the form $ue_1e_2\ldots e_kv$, where $u,v\in V$, $e_i\in E$. We say that $u,v$ are adjacent. Notice that if $e_i\in H$, then $e_i=\{u,v\}$, because $e_i$ occurs only once, yet it is adjacent to two vertices in $G$. Therefore, at most one of $e_i$ can be in $H$. Similarly, no edge in $H$ can occur in $w$ before the first vertex or after the last vertex.

Now, there are $|V|$ vertices, therefore $|H|\leq |V|-1$. From there, it follows that $|w|\geq 2|E|+1$. Since we assume $|w|\leq 2|E|+1$, we get equality. From there we get $|H|=|V|-1$. By pigeonhole principle, there is an edge from $H$ between each pair of vertices adjacent in $w$. Denote $h_1h_2\ldots h_{n-1}$ all elements from $H$ in the order they appear in $w$. It follows that $v_1h_1v_2h_2\ldots h_{n-1}v_n$ is a Hamiltonian path in $G$. $\square$

Since the problem of deciding the existence of Hamiltonian path is NP-hard and the above reduction is polynomial, the original problem is NP-hard too.


Why does this not prove $P\neq NP$? Fiorini, Massar, Pokutta, Tiwary and De Wolf (Exponential Lower Bounds for Polytopes in Combinatorial
Optimization, Journal of the ACM 62(2):article 17, 2015; PDF, ArXiv) show any linear program that solves travelling salesman needs super-polynomially many constraints.

Suppose $P=NP$ by 'some' method then we can solve the optimal tour explicitly and trivially setup a LP that 'solves' the TSP problem. So $P=NP$ implies that TSP has a poly-size LP formulation. The contrapositive is that TSP has no poly-size LP formulation implies $P\neq NP$. This paper shows TSP needs super-polynomially many constraints.

So why doesn't this show that $P\neq NP$?

What Fiorini et al. show is the following:

The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.)
Suppose that $X_n$ is a polytope whose projection over the first $\binom{n}{2}$ dimensions is $P_n$, and let $d_n$ be the number of constraints needed to define $X_n$ (i.e., the number of facets of codimension 1). Then $d_n \geq f(n)$ for some function $f(n) = 2^{\Omega(\sqrt{n})}$.

In other words, they show that TSP cannot be solved using LPs in one particular way. There could be some other way of using LPs to solve TSP which isn't ruled out by their result.
For example, perhaps you could use iterative rounding to solve TSP, at each step solving an LP. This is consistent with the result of Fiorini et al.
The method in your argument is likewise not ruled out by Fiorini et al.


What is a difference between cross-lingual IR and multi-lingual IR? In papers usually Cross-Lingual Information Retrieval (CLIR) and Multi-Lingual Information Retrieval (MLIR) use equivalently or distinctly. I want to know is there any difference between these two terms?

In this paper they differentiate between these two terms as follows:

  While CLIR is concerned with retrieval for given language pairs (i.e.
  all the documents are given in a specific language and need to be
  retrieved to queries in another language), MLIR is concerned with
  retrieval from a document collection where documents in multiple
  languages co-exist and need to be retrieved to a query in any
  language. MLIR is thus inherently more difficult than CLIR.


Time complexity of optimal algorithm for solving this problem Given an $N\times N$ matrix $M$ whose elements are integers, find the largest element that occurs in each row of the matrix.

I tried using hashtable as follow:

Idea is to use hash-table(let's call it $ht_1$) to keep track of count of occurrence of each element.
Now, To handle case where element repeats in same row we use another hash-table(call this $ht_2$). Now before performing increment in $ht_1$ we check whether this element is already occurred in this row itself or not. If not then and then we perform increment in $ht_1$.

Then once you finish processing whole array as just described make one more pass on array and this time keep track of max element which have exactly $N$ occurrence as noted by $ht_1$.

So overall this runs in $O(N^2)$ expected time.

But Because use of hash-table worst case time complexity is still $O(N^4)$.

Now, I wonder can I do better than this? Means is there any way to solve in $O(N^2)$ in worst case.

Note: There is no other constraint on this.

$O(n^2 log n)$ is easy: Create a sorted array of the items in the first row. Lookup the items in the second row in this array using binary search, and remove items that were not present. Same with the third row etc. The last remaining item is the largest one present in evert row. The main effort is $n^2$ lookups in an array of size n.

Using a hash table probably makes it $O (n^2)$.


Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair?

The naive approach is very straightforward, but has O(intervals) test performance:

list intervals (min, max)

func testVal(val){
  foreach (interval(min, max) in intervals)
    if (val > max) || (val < min) return false
  return true
}

In the problem I'm facing the list is not updated frequently, but it is tested against with very high frequency.

Thus, it's acceptable for updating the list to be expensive, but tests need to be sublinear, ideally constant time.

One option is to insert every value in the intervals into a hashtable, but this is memory-intensive and not practical when the intervals get large. Memory usage needs to be proportional to the number of intervals, not the sum of the sizes of the intervals (probably ok to have a log(n) memory usage term thrown in if it greatly aids performance).

I've started poking around with various tree-based options to make this better, but it feels like a general enough problem that I suspect there is preexisting work I should be referencing. Are there any existing solutions to get sublinear tests (ideally constant time) on a list of intervals by preprocessing them into some other datastructure(s)?

Here's my thought process on this problem:

If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order.

Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes.

For a given point and a given interval, you can determine whether the point is "outside to the left", "inside", or "outside to the right" in $O(1)$.

This assumption only works as long as you have a fixed word length, but that's generally true for all practical purposes.
Let's change the terms: "outside to the left" is "less than", "inside" is "equal to", and "outside to the right" is "greater than".

Now you can use standard binary search!

Since each comparison is $O(1)$, the total time is $O(\log n)$.

And voilà, each check takes only logarithmic time! Setting up the list in the first place takes $O(n \log n)$, and adding a new interval to the list later takes $O(n)$ in the worst case.


SVM with a priori information about class probabilities Given are two 2-d sets, each with its own bivariate normal distribution. I need to build an SVM classifier. The a priori probabilities of each class corresponds to the size of its set (20/50 for the first and 30/50 for the second one). I am quite confused about the way to implement the knowledge about set structure and a priori probability of classes. Any ideas appreciated.

(If your idea is supported by some R packages it would be very nice.)

SVM doesn't take into account that prior knowledge about the distribution of the classes, so if you want a classifier that takes advantage of that, you'll need a different classifier.

In particular, if you know the distribution of each class and the priors (class balance), you can use Bayes rule to classify each point directly, without needing any fancy classifier.  This is the optimal (most accurate) way to classify, is not hard to implement, and doesn't require any training set.

If you know that each class has a bivariate normal distribution but you don't know its parameters (mean and covariance matrix), you can use the training set to estimate these parameters, then use Bayes rule.


Stablishing termination of the construction of infinite stream with ranking functions I'm working with Turing's paradigm to prove termination of programs by annotating functions with ranking functions and I encounter the following example:

def zeros: Stream[Int] = 0 #:: zeros

This is Scala syntax for contructing a stream made of an infinite number of zeros. In this case, the evaluation terminates but there is no (evident) measure that would prove it so?

Does this mean that the ranking functions paradigm is limited? Or is there a function stablishing termination of zeros?

Turing, A. Checking a large routine. In Report of a Conference on High Speed Automatic Calculating Machines, 1949.

I think Turing's method is probably fine, but you are mistaken about why exactly the code you wrote, "terminates."

First, note that this is not really (written as) a function at all. It is a self-referential value. And the reason the program terminates even though it's defined in it is that the program does not attempt to evaluate it fully. In this case, perhaps it would be all right, because a sufficiently smart evaluator would notice that there is a loop in the pointer structure, but there are other examples where that would not be sufficient.

So, these infinite structures are not something that you prove 'terminate' by showing they can be labelled by some finite size. Instead, they are not evaluated at all until something else demands to see the structure, and then they are unfolded as needed. This sort of structure is sometimes called, "coinductive," whereas the Turing methodology you're talking about is related to induction.

However, there is a property related to termination for coinductive things. For termination of inductive definitions, we label inputs with natural numbers (say), and ensure that this number decreases for recursive calls, which ensures termination. For coinductive definitions, we consider things like #:: to increase size, and we want to ensure that the size of the result is bigger than the size of any recursive references. This ensures that we are incrementally producing more of the value after a finite amount of work, and this is referred to as the definition being, "productive."

The reason we care about this property is that we assume the parts of the program that cause the unfolding of the infinite values can only demand finite portions of them. If you can only look at a finite portion of a potentially infinite value, and the pieces each take a finite amount of time to produce, the overall computation terminates.

But, there is also a way to apply a more Turing-like methodology to this, and it is to recognize that streams could be implemented as functions. Stream[Int] is the same, in a way, as Natural => Int, where you ask for the value of the stream at a particular index, and it returns the value. And in this representation, productivity corresponds to the termination of the function for every natural number. In this case it's easy, because the function is x => 0, but other examples could require more sophisticated arguments.


Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f I am new to this topic, Linear Time Temporal Logic and I am trying to prove this equivalence --

$\Box\Diamond f \Leftrightarrow \Diamond\Box f$

This is my take --

Basic definitions:

$(\sigma, j) \models \Box f: \forall k \, [(k \ge j) \Rightarrow ((\sigma, k) \models f)]$

$(\sigma, j) \models \Diamond f: \exists k \, [(k \ge j) \Rightarrow ((\sigma, k) \models f)]$

Here, $(\sigma, j) \models f$ means $\sigma$ satisfies $f$ at $\sigma(j)$, for more details about this syntax, please see here.

Now the LHS:

$\begin{eqnarray}
(\sigma, j) \models \Box \Diamond f & : & \forall k \, [(k \ge j) \Rightarrow ((\sigma, k) \models \Diamond f)]\\
& \equiv & \forall k \, [(k \ge j) \Rightarrow [\exists p \, [(p \ge k) \Rightarrow ((\sigma, p) \models f)]]]\\
& \equiv & \forall k \, [(k<j) \vee [\exists p \, [(p<k) \vee ((\sigma,p) \models f)]]]\\
& \equiv & \forall k \, \exists p \, [(k<j) \vee (p<k) \vee ((\sigma,p) \models f)]\\
& \equiv & \forall k \, \exists p \, [(p<k<j) \vee ((\sigma,p) \models f)]\\
\end{eqnarray}
$

Again, the RHS:

$\begin{eqnarray}
(\sigma, j) \models \Diamond \Box f & : & \exists k \, [(k \ge j) \Rightarrow ((\sigma, k) \models \Box f)]\\
& \equiv & \exists k \, [(k \ge j) \Rightarrow [\forall p \, [(p \ge k) \Rightarrow ((\sigma, p) \models f)]]]\\
& \equiv & \exists k \, [(k<j) \vee [\forall p \, [(p<k) \vee ((\sigma,p) \models f)]]]\\
& \equiv & \exists k \, \forall p \, [(p<k<j) \vee ((\sigma,p) \models f)]\\
\end{eqnarray}
$

Now if we look at the last line of the both sides, the statement

$\forall k \, \exists p \, [(p<k<j) \vee ((\sigma,p) \models f)] \equiv \exists k \, \forall p \, [(p<k<j) \vee ((\sigma,p) \models f)]$

needs to be true to complete the proof, however intuitively, this is not true.

What I am missing? How do I proceed? Any idea?

You are not missing anything. These expressions are indeed not equivalent.
Assume $f$ in your case is an atomic proposition. Then the computation:
$f,\neg f,(f,\neg f)^\omega$ satisfies $□◊f$, but not $\Diamond \square f$.

Intuitively, $\Diamond \square f$ means "After a finite prefix, there is always $f$", while $\square \Diamond f$ means: "There are infinitely many $f$s".

By the way, you have some mistake in your semantics. It should be:
$(\sigma,j)\models \Diamond f$: $\exists k[k\ge j\wedge (\sigma,k)\models f]$.


Are there connections between the theory of computation and machine learning? I am wondering if studying the Theory of Computation/ Computational Complexity theory, specifically Sipser's 'Introduction to the Theory of Computation' will help me do machine learning/statistics/data science better. Are there any connections? I intend to study the book even if there aren't any connections.

Yes, check out Computational learning theory (Algorithmic learning theory) and conferences COLT and ALT although the connection with machine learning is arguably limited.


Need an algorithm to find the input factors that are most affecting the output I apologize if this question is already answered and appreciate any pointers to existing answers. I'm not familiar with statistical or data mining terms so my search was limited to basic words used in the title of this question. I did look at some algorithms but could not decide if they serve the purpose.

I'm looking for an algorithm that can give me % probability or % confidence that out of given set of input factors which inputs are affecting the output most. Let us take an example below and assume that input and output will be recorded 4 times a day for a month.

Output:

Phone's battery drainage
Phone heating up (temperature).

Input:

Ambient temperature
Which apps were used most when the output was measured (multiple input points)
Number of calls received and call length
Screen brightness
GPS connectivity enabled?
Bluetooth enabled?
Cellular signal strengh

If we measure this data for month, we will find that Cellular Signal Strength and screen brightness probably will be linked to Battery Drainage most. On the other hand 3D resource intensive games will be linked to Phones heating up the most. Can I deduce such relationship using any existing algorithm(s)?

Fundamental limitations on what you can achieve

The principled answer is: No, you can't reliably deduce such causal connections.  When you have only observations of the data, you can use statistical analysis to look for correlations, but you can't deduce causation.  Correlation does not imply causation.  You are looking for causality, but you cannot infer causality from field data (from external, uncontrolled observations of a system).  To test causality you need a controlled experiment.

This is a problem not just in principle, but often in practice as well.  In practice, we might have correlations among your "independent variables" or confounding factors you haven't accounted for, which causes correlations that aren't an indication of causality.

For instance, you might find that ambient temperature is correlated to display brightness (because at night it is cooler and darker, so phones turn down display brightness, whereas at day it is warmer and brighter, so phones turn up display brightness to compensate for the daytime light).  Now we'd expect that when the display brightness is higher, the battery will be drained faster.  Can you deduce this causal connection from statistical inference applied to some observations?  Well, you might observe a correlation between display brightness and battery drain rate, which sounds good.  But if display brightness is correlated to ambient temperature, then when you do a statistical analysis, you might also discover a correlation between ambient temperature and display brightness -- and that's a spurious correlation that doesn't indicate any causal connection.

Pragmatic, engineering answer

That said, the pragmatic answer is to use statistical analysis of your data to look for correlations, and then hope that at least some of the correlations will represent something real.  You have to go into it with eyes open knowing that some of the correlations will be spurious, for the reasons explained above, but maybe that's OK.  Maybe statistical analysis can still be useful to you.

So, how should you do the statistical analysis?  There are many possible ways.  It's best to say what is the best; that probably depends upon what relationships between the input and output you think are plausible.

But a very simple approach that I suspect will work well for you is to use linear regression.  Try to find a linear model that expresses an output variable (e.g., the battery drain rate) as a weighted linear combination of the input variables.  Linear regression can find the best weights for you that minimizes the prediction error.

Then, the size of those weights tells you exactly what you want to know.  Suppose you are predicting the battery drain rate, and in your linear model the weight for the screen brightness input variable is 0.7.  This means that if you increase the screen brightness by adding $\Delta$, then the battery drain rate is predicted to increase by adding $0.7 \Delta$.

Tricky details

There are a few things about your specific problem that might be a bit tricky.

One tricky aspect is the business about apps, and how to code that into a linear regression framework.  One way is to pick a few categories of apps, and then have a separate indicator input variable for each category (0 if that app is not present, 1 if it is present).  However, you don't want to have too many input variables, because that will require a lot more data to reliably form a linear model.  A few dozen app categories might be fine, but thousands of input variables for the thousands of different possible apps probably would not be.

Another tricky aspect arises if you expect there to be non-linear dependencies, and you want to find them.  For instance, you mention in a comment the possibility that low cellphone signal strength combined with running a 3D game might increase battery drain rate in a way that neither alone would.  If you expect those kinds of non-linearities, one standard way to deal with them is to introduce new input variables for "interaction effects": e.g., you introduce a new input variable which is the product of the signal strength times the indicator variable that indicates whether a 3D game is running.  (These new input variables are derived from the other input variables, but in a non-linear way.)  You can introduce one new "interaction" input variable for each pair of original input variables that you think might exhibit a combined effect of this sort (where the effect of their combination is greater than the sum of their individual effects).  This is a standard technique that you can find described in good tutorials on linear regression.

Ultimately, there's lots more to say on statistical data analysis, linear regression, and applying it to practice -- more than I can write in a single answer.  I recommend you read a good tutorial or two on linear regression and maybe the relevant chapters of some statistical textbooks.  If you still have more questions after all of that, it's also worth knowing about Cross Validated, a Stack Exchange site on statistics.


Complete Problems for $DSPACE(\log(n)^k)$ We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy?

To be precise: Does the class $DSPACE(\log(n)^k)$ have complete problems under $L$-reductions for each $k > 0$?

A standard proof of the space hierarchy theorem is based on the space-efficient simulation of Turing machines.  If I am not mistaken, this simulation implies that for every space-constructible function f: ℕ→ℕ, the following problem is in DSPACE(f(n)) (where n is the input length):

  Given an encoding of a deterministic Turing machine M with a read-only input tape and a read-write work tape with a fixed work alphabet (such as {0, 1, blank}), a string x, and a tally string 1t, decide whether M halts on input string x before using more than f(t) work space.

This problem is DSPACE(f(n))-hard under log-space many-one reducibility.  Here is a proof in the case of f(n) = lgkn.  For each language L∈DSPACE(logkn), there is a Turing machine M (of the form stated above) which accepts L in c lgkn space for some c∈ℕ.  Modify M to M′ so that when M rejects, M′ goes into an infinite loop instead.  Then given an input string x, let t = |x|c, and we generate the instance (M′, x, 1t) of the problem above.  (I think that the only slightly nontrivial part is that we cannot set t = |x|.)

Therefore this problem is DSPACE(f(n))-complete under log-space many-one reducibility.


Can this DFA be converted to a regular expression? I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?

Every DFA can be converted to a regular expression, so you must have made a mistake when you converted. The conversion is quite fiddly, so making a mistake with a nine-state automaton is easy to do, unfortunately.

It might help if you split the automaton in two: if the automaton accepts, it either reads an $a$ and then accepts using only states $2,4,6,\omega$ or it reads a $b$ and then accepts using only states $3,5,7,\omega$. So the regular expression must be something of the form $aR_{\{2,4,6,\omega\}}+bR_{\{3,5,7,\omega\}}$, where $R_S$ is the regular expression for the automaton that just has the states in $S$. Now, you just have to convert two nearly identical four-state automata, which should be easier to do correctly.


Bellman-Ford Termination when there is no change on vertex weights? We know the bellman-ford algorithms check all edges in each step, and for each edge if,

  d(v)>d(u)+w(u,v)

then d(v) being updated such that w(u,v) is the weight of edge (u, v) and d(u) is the length of best finding path for vertex u. if in one step we have no update for vertexes, the algorithms terminate. with supposing this algorithms, for finding all shortest path from vertex s in graph G with n vertex after k<n iterate is finished, can we conclude:

1) number of edges in all shortest paths from s is at most k-1

2) weight of all shortest paths from s is at most k-1

I Think Neither the number of edges nor their total weight is limited by k-1 with the defining problem, but my TA says (1) is True. How can describe these conditions?

Part (1) is indeed true. The idea is that in $k$ steps the algorithm is only considering paths of length $k$. Indeed, you can prove by induction on $k$ that the path realizing the value of $d(v)$ after $k$ steps is at most $k$ edges long.

If the algorithm terminates after $k$ steps, then the results of the first $k-1$ steps are already optimal, hence (1).

Part (2) is indeed false, and I'm sure you can give a counterexample on your own.

The simultaneous version of the Bellman–Ford algorithm, referred to in part (1), has the following pseudo-code (where $d(x,y)$ is the weight of the edge connecting $x$ and $y$):

A[0,x,y] = ∞ for all x,y
t ← 0
do
  for all x,y:
    A[t+1,x,y] = min(A[t,x,y], { A[t,x,z] + d(z,y) : all z ≠ x,y })
  t ← t+1
while A[t,x,y] ≠ A[t-1,x,y] for some x,y
return A[t,x,y]

Take as an example the (undirected) graph $x - y - z - w$ (with unit weights). Here is a trace of the algorithm:

$$
\begin{array}{c|cccccc}
t & A[t,x,y] & A[t,x,z] & A[t,x,w] & A[t,y,z] & A[t,y,w] & A[t,z,w] \\\hline
0 & \infty & \infty & \infty & \infty & \infty & \infty \\
1 & 1 & \infty & \infty & 1 & \infty & 1 \\
2 & 1 & 2 & \infty & 1 & 2 & 1 \\
3 & 1 & 2 & 3 & 1 & 2 & 1 \\
4 & 1 & 2 & 3 & 1 & 2 & 1
\end{array}
$$


Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular I have looked up a question like this online and found this solution.
I couldn't understand what the new NFA A' looks like.
Could anyone give me an example of NFA A'?

Maybe the formal proof below will help you to understand the construction using a NFA.
Let $\mathcal{A} = (Q, A, \cdot, i, F)$ be a deterministic automaton recognising your language. For each pair of states $(p, q)$, let $L_{p,q}$ be the language recognised by the automaton $(Q, A, \cdot, p, \{q\})$. Thus $L_{p,q}$ is the set of labels of all paths from $p$ to $q$. By construction, each language $L_{p,q}$ is regular. Let $T$ be the set of transitions of $\mathcal{A}$, that is,
$T = \{ (p,a,q) \in Q \times A \times Q \mid p \cdot a = q \}.$
Let
$$
R = \bigcup_{(p,a,q) \in T}  \bigcup_{f \in F} L_{i,p}L_{q,f}
$$

Claim. $D(L) = R$.

Indeed, let $w \in D(L)$. By definition, there exist some words $u$ and $v$ and a letter $a$ such that $w = uv$ and $uav \in L$. Let $p = i\cdot u$, $q = p \cdot a$ and $f = q \cdot v$. By construction, $u \in L_{i,p}$, $v \in L_{q,f}$, $(p,a,q) \in T$ and $f \in F$. Thus $w \in R$.
Let now $w \in R$. Then there exist some states $p, q \in Q$ and $f \in F$  and some transition $(p,a,q) \in T$, such that $w \in L_{i,p}L_{q,f}$. It follows that $w = uv$ for some $u \in L_{i,p}$, and $v \in L_{q,f}$. Now $i \xrightarrow{u} p \xrightarrow{a} q \xrightarrow{v} f \in F$, which means that $uav \in L$. Consequently, $w \in D(L)$, which proves the claim.
Coming back to your question, the first copy of $\cal A$ in ${\cal A}'$ is used to accept $L_{i,p}$ and the second one to accept $L_{q,f}$. The $\epsilon$-transitions are used to pass from the first copy to the second one.


Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$ I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$.

Legendre's theorem says $m$ has such a representation if $m \neq 4^a(8b+7)$ with $a,b \in \mathbb{N}$.  See on MathOverflow:

Legendre and sums of three squares
Efficient computation of integer representation as sum of three squares

If I just wanted to count  the number of representations as the sum of squares, we could find formulas in the Online Encyclopedia of Integer Sequences:

A005875 - Theta series of simple cubic lattice; also number of ways of writing a nonnegative integer n as a sum of 3 squares (zero being allowed).
A074590 - Number of primitive solutions to $n = x^2 + y^2 + z^2$ (i.e. with $\gcd(x,y,z) = 1$).

How do I list the sum of squares representations for each $m$?  I would take a slower algorithm if it were easy to implement.

I considered just writing: $\boxed{m -x^2 -y^2 = z^2 }$ and looping over $0 < x < y < \sqrt{m} $ and checking it is perfect square.

Another possibility is keeping an array square writing square[x*x+y*y*z*z] += [[x,y,z]] storing triples in the appropriate place as I find them.  That is something like $m^3$ time since I loop over $0 < x,y,z < m$.

Do any solutions jump out at you?

10/12/17 Here I take a naive approach:

N = int(M**0.5)

z = [ (a,b,c) for a in range(N) for b in range(N) for c in range(N)
      if a**2 + b**2 + c**2 == M]

This rather slow, but I could get solutions in the range N=10000 in about 20 seconds.  Here I run it 100 times within a half-hour.

Sometimes, there is no solution.  How can I improve this to work quickly at $N \approx 10^6$ ?

Your first approach is probably the simplest to implement.  Its running time will be $O(m)$.

Another approach: you could loop over all $x$ such that $0 < x < \sqrt{m}$, and for each $x$ enumerate all ways to express $m-x^2$ as a sum of two squares.  There's a lot of theory about how to express an integer as a sum of two squares (e.g., Lagrange's algorithm).  However, this will be more complex to implement.


Find a point shared by maximum segments Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$.

Example:

Segment 1: [-2,-1,0,1,2,3]
Segment 2: [1,2,3,4,5]
Segment 3: [-3,-2,-1,0,1]

You can represent them as [min, max]---it is equivalent:

Segment 1: [-2,3]
Segment 2: [1,5]
Segment 3: [-3,1]

How can I find an integer that belongs to the maximum amount of segments? For the given example, it is 1.

I look for the most efficient algorithm.

Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:

Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N \log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:

(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.

(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1

This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N \log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.


Assign undirected edges in a mixed graph to make graph cyclic/acyclic What is the complexity of the following problem?

Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle.

It doesn't "feel" like an NP-hard problem, but I can't think of an easy poly-time algorithm.

What about to make the graph acyclic?

As R B points out in the comments, to make the graph acyclic, you can just use a topological sort on the directed edges (ignoring the undirected edges temporarily) to get an ordering of the vertices, then use that ordering to direct the undirected edges.  Therefore, that problem is easy and can be solved in $O(|V|+|E|)$ time.

However, orienting the edges to create a cycle is more tricky.
Consider the graph:

    A
  /   \
 B --> C

In this case, simply sorting the graph to get A B C and then pointing the AC and AB edges backwards does not reveal the cycle.

As noted by R B, the acyclic variant of the problem is solvable iff the directed part of the graph is acyclic, in which case one can take a topological sort of the directed edges, and orient undirected edges consistently with the linear order obtained.

For the cyclic variant of the problem, we can use the following polynomial-time algorithm, where $G=(V,E)$ is the input graph:

for every directed edge $e=(a,b)\in E$, and for every orientation $(a,b)$ of an undirected edge $e=\{a,b\}\in E$:

if there is a path (directed where applicable) from $b$ to $a$ in $(V,E\smallsetminus\{e\})$:

find such a path $p$
make sure the path is simple by deleting subcycles
output any orientation of the undirected edges that agrees with the cycle $e,p$ and stop

if no edge worked, reject

Note that the simplicity of $p$ in particular ensures that no undirected edge appears twice in $e,p$, hence it gives a consistent orientation. Thus, if the algorithm accepts, it is correct. On the other hand, if there exists an orientation of $G$ that includes a (wlog simple) cycle $c$, and $e=(a,b)$ is any edge in $c$ (properly oriented), then $a$ is reachable from $b$ in $(V,E\smallsetminus\{e\})$ by means of the rest of the cycle. Thus the algorithm will accept sooner or later.

In terms of complexity, both problems are NL-complete as decision problems, and the search problem versions are in FNL.


What do the terms 'Sample' and 'Sampling' mean in the discussion of Pattern Recognition and Machine Learning? The tag sampling tells me that,

  Creating samples from a well-specified population using a
  probabilistic method and/or producing random numbers from a specified
  distribution.

Now, the question becomes: what is population then?

Suppose, I am implementing a classifier.

I have a set of training data in the file train.txt, and a set of test data in the file test.txt.

What element can be termed as 'Sample', and what activity can be termed as 'Sampling' in this case?

Suppose that you're a pollster. You're trying to understand who will win the elections in Mars. What do you do? You sample a few eligible voters from the voter population, ask them for their preferences, and tally their votes.
Sampling is not trivial, however, since your sample might not be representative, and so you might need to add in some weights when you tally the votes.

Here is another example. You're trying to understand the connection between lifestyle and longevity. You sample a few random people from the general population, and give them a questionnaire. Your goal is to create a formula that predicts life expectancy given some features of the person's lifestyle, such as whether they smoke or not.

The second example demonstrates the sort of problem that machine learning algorithms solve. Hopefully these examples give you enough hints to understand what sample and population mean in your context.


Maximizing sum of ranges of vertices edges Consider an arbitrary undirected graph $G = (V,E)$.  Suppose you have a collection of $|E|$ positive integers and each integer must be assigned to one edge.  Let us denote the collection of integers assigned to vertex $v$'s edges as $w(v)$. How would one assign the $|E|$ integers to the $|E|$ edges so as to maximize:

\begin{equation}
\sum_{v \in V}{max(w(v)) - min(w(v))}
\end{equation}

In other words, how would one maximize the sum of the range of each vertice's edge assignments?

As an example, consider the graph pictured below.  Same graph, same set of $|E|$ integers, but different assignments of integers to edges leads to the above equation evaluating to either 16 or 18.

I'll start by giving a negative example to @seteropere algorithm:

Let $G=(V,E)$, where $$V=\{x_1,x_2,x_3,y_1,y_2,y_3\}\ \ \ ,\ \ \ E=\{(x_i,y_i)\mid i\in [3]\}\cup\{(x_1,x_2),(x_1,x_3)\}$$
Let the weight collection be $\{3,3,2,1,1\}$.

The proposed algorithm starts by assigning weights $1,2$ and $3$ for $x_1$, and assume that $(x_1,y_1)$ was assigned 1.

This already means that the optimal solution profit (5, see figure) is not obtainable.

  That said, this problem is poly time solvable after all , greedily,
  but differently.

Hint: given a graph $G$ such that $\Delta(G)\geq 2$, prove that in the optimal solution there exists a vertex $v$ such that the maximal number and the minimal number are both in $w(v)$.

P.S.

The opposite problem, in which we aim to minimize $$\sum_{v \in V}{max(w(v)) - min(w(v))}$$

Is quite interesting by itself.


Longest path with limited edge traversals Given a graph where each edge has a capacity, is there an efficient algorithm to find the longest path in the graph which does not pass through an edge more times than its capacity? The exact problem I'm trying to solve is given a list of words, find the longest chain of words such that the last letter of the $n^{th}$ word in the chain is the same as the first letter of the $n+1^{th}$ word in the chain. So the number of vertices would be 26 (the length of the alphabet), and each edge would represent the words that start with the letter which its from vertex corresponds to and ends with the letter which its to vertex corresponds to. The list is about 60,000 words long, so something like $O(cV)$ or $O(cV^2)$ where $c$ is the total capacity would be nice.

In general, for a general graph with an arbitrary number of vertices, no.  The general problem is NP-hard (consider the case where all edge capacities are 1; this is the longest trail problem, which is NP-hard; my thanks to Willard Zhan for pointing out the connection to the longest trail problem),.  Therefore, there is unlikely to be an algorithm that is always correct and is efficient for all graphs.

In your case, it might be possible, as you can represent your problem as a graph with 26 vertices (one per letter) and 60,000 edges (one per word).  Moreover, you can condense it to a graph with 26 vertices (one per letter) and $26^2$ edges (one per pair of vertices).  Then, an exponential-time algorithm might suffice.  I don't know of any such algorithm, but I also can't rule out the possibility, either.

How to condense the graph?  Take all of the words (edges) that start with letter $i$ and end with letter $j$, sum up their corresponding capacities, and then add a new edge $(i,j)$ whose capacity is equal to that sum.  That leaves you with a single edge per pair of letters.  Any path through such a graph that respects the summed capacities can be transformed into a path in the original graph that respects the original capacities.

I realize this doesn't solve your problem, but maybe it is a small step towards that goal.


Partitioning NP-complete problems Let's suppose I have an NP-complete problem A.

Can there be $A_1$, $A_2$ such that $A_1$ and $A_2$ are disjoint, $A = A_1 \cup A_2$, and $A_1$ and $A_2$ are NP-complete?

My guess would be yes.  For example, just partition SAT into formulas with an even number of variables and formulas with an odd number.

Follow up:  Can I partition $A$ into infinitely many such $A_i$? (I suppose yes: take formulas with $2^n$ variables, $3^n$, $5^n$, $7^n$, $11^n$, or something like that)

There are many ways of accomplishing this. Consider SAT for example. Let SAT$_p$ denote a YES instance of SAT with $n$ clauses, where $p$ is the smallest prime factor of $n$. Clearly $\{ \mathrm{SAT}_p : p \text{ prime} \}$ is a partition of SAT. SAT$_p$ is clearly in NP. To show that it is NP-hard, we reduce from SAT. Given an instance of SAT having $n$ clauses, with add $m$ times the clause $x \lor y \lor z$ ($m$ to be chosen later so that $p$ is the smallest prime factor of $n+m$), where $x,y,z$ are new variables. The new instance is satisfiable iff the original one is, and by definition $p$ is the smallest prime factor of $n$. It remains to define $m$ and show that the reduction can be done in polynomial time (this depends only on the value of $m$ compared to the value of $n$).

Let $P$ be the product of all primes at most $p$. We will choose $m$ so that $n + m \equiv p \pmod{P}$. Clearly some $p < P$ fits the bill. I leave the reader to show that $p$ is the smallest prime factor of $n + m$.


Vehicle Routing Problem with multiple deliveries? I have a problem that can be reduced to the following:

  There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points" (eg. there are five places where you can pick up object A, and five places where you must deliver it). What is the optimal route?

It is similar to the "vehicle routing problem with pickups and deliveries", except that rather than delivering one item from one point to another there are multiple choices for pickup and delivery points.

Is there literature, or perhaps software, that treats this specific problem? Alternatively, can this problem be reduced to a more common variant?

It can be reduced to a TSP with an incomplete graph (i.e. with some missing edges). Each delivery "slot" is simply represented as a node in the graph, connected appropriately to the other nodes.


How hard is recovering a binary matrix from its check sums? I am interested in combinatorial (worst-case) one-way functions. I came across this problem which may be related to coding theory problems (I am not an expert in coding theory).

INPUT: Two vectors $R_{n*1}$ and $C_{1*n}$.

QUESTION: Is there a binary matrix $A_{n*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$.

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

  What is the time complexity of this problem? Is it NP-complete? Is it efficiently solvable? Is this a known problem in coding theory?

Also, it is interesting to know the time-complexity of a variant in which vectors $R$ and $C$ contains the integer sum of the one's in each row and column in $A$.

EDIT: It is interesting to note that the Sum problem becomes $NP$-complete if the directed graph is required to be acyclic (see the link in Yuval's answer).

Parity problem

It is clear that $\sum_i R_i \equiv \sum_j C_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that
$$
\begin{align*}
&(R_1,C_1) = \cdots = (R_{n-a},C_{n-a}) = (0,0) \\
&(R_{n-a+1},C_{n-a+1}) = \cdots = (R_{n-b},C_{n-b}) = (1,0) \\
&(R_{n-b+1},C_{n-b+1}) = \cdots = (R_n,C_n) = (1,1)
\end{align*}
$$
Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks:
$$
\begin{pmatrix}
0
\end{pmatrix}
 \times (n-a), \quad
\begin{pmatrix}
1 & 0 \\ 1 & 0
\end{pmatrix}
\times (a-b), \quad
\begin{pmatrix}
1
\end{pmatrix}
\times b
$$

Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.


Dijkstra without decrease key I was reading through this paper, "Priority Queues and Dijkstra's Algorithm" by Mo Chen et al., which suggests using Dijkstra's without edge relaxation, but to rather to just insert new nodes. Please see the pseudo code listed on the right-hand side below, which is taken from page 16 of that paper.

But to me the code looks wrong. I think the comparison should be
k <= d[u]

and also the update of the d[u] in the next line seems redundant to me. I think the delete-min operation can never return a vertex with distance label k which is strictly less than d[u] since whenever a vertex distance pair is inserted into the priority queue the distance array d is updated. Am I correct in assuming that this is a mistake in the paper?

You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.

The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] holds when (u,k) is picked up from the queue. Moreover, if d[u] is strictly smaller than k , the element should simply be ignored since it cannot be the shortest path to u.

You can change the condition to k == d[u] and remove following update to d[u].


Fast hash function for set equality I'm searching an hash function for integer set equality that must be fast.
It must support update (adding an element already in the set must not change the hash) and union.
MinHash has these 2 properties but it is too expensive and I do not need all the feature of MinHash, in fact I don't need set similarity but only equality.
Do you know something that can satisfy my needs?
Thanks :)

P.S. I have to implement it in C for an high performance software

MinHash already is super-fast.  I suggest you check whether you understand correctly how MinHash works.

Take any standard hash function $H$; then all you have to do is compute $H$ once on each element of the set.  You can implement $H$ with as fast a hash algorithm as you want.  The update operation requires one call to $H$ (namely, if your set's hash is currently $y$, and you add element $x$, the new hash is $\min(y, H(x))$), and the union operation is super fast (namely, the union of two sets with hashes $y_1,y_2$ is $\min(y_1,y_2)$).  Notice that these operation have the property you want (adding an element already in the set does not change the hash).

I have a hard time imagining how you could get much faster than that.

If you want this to be faster, a reasonable way is to choose a $H$ that is faster.

I've described a variant where the hash of a set is the smallest of the element-hashes.  The only downside is that the number of hash collisions might higher than you like.  Measure and see if that is actually a problem in practice.  If it is, you can consider variants that keep the $k$ distinct smallest element hashes.  If $k$ is large, you can store those $k$ hashes in a heap of size $k$ to make the update and union operations faster.


Recognizing a trajectory from a set Given a set of 2d trajectories/paths, where a trajectory is a list of [x,y,time] coordinates, and a new trajectory, how can I recognize which one in the set is most similar to it? The lists may not be of the same length, the time differences not the same.

I've tried using perceptual image hashes of the resulting lines, but this approach seems unreliable.

The measure of similarity should be scale and translation, but not rotation invariant.

I'm trying to recognize 2d gestures that are input with a mouse or touchpad in order to execute commands[0]. For this application, the velocity/acceleration of the movement will not matter.

I found this library that contains a few algorithms: https://github.com/bguillouet/traj-dist

[0] https://github.com/void4/termagic

The Fréchet distance is a similarity measure for trajectories that often works well for curves that we consider visually similar. However, it is not scale or translation invariant, because it compares the distances between the points of the trajectories.

You can try the Direction-Based Fréchet Distance, introduced in this paper by de Berg and Cook. This is a variant of the Fréchet distance that is based on the directions of movement instead of the points directly. This means that it is both scale invariant and translation invariant, but not rotation invariant.

Another possible approach that may be easier to implement if you have a library that can compute Fréchet distance and DTW1 distance between a pair of trajectories, is to first translate the pair of trajectories such that the first points have the same position, and then scale the trajectories such that the distance between the first and last point of the trajectories is the same in both trajectories. If you compute either the Fréchet distance or DTW-distance after these transformations, the total measure will be scale and translation invariant.

1: DTW (Dynamic time warping) is similar to the Fréchet distance, the main difference is that the Fréchet distance is a bottleneck measure, while DTW is not. In other words, only the 'most dissimilar parts' of the trajectories determine the Fréchet distance, while DTW takes the entire trajectory into account.


How to define a similarity between two graphs? Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$,  $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(Let's denote the set of all graphs over the vertices $V$ with $\mG$, so $G_1, G_2 \in \mG$).
Now I'd like to measure how similar (up to isomorphism) those graphs are, so ideally we'd have a metric
$$d: \mathbb G \times \mathbb G \to \mathbb R_{\geq 0}.$$
This should satisfy all the usual axioms of a metric

$d(G, H) = 0 \iff G \simeq H$ (Here we consider isomorphy as equality.)
$d(G, H) = d(H, G)$
$d(G, H) + d(H, I) \geq d(G, I)$

Is there a "useful" example of such a metric?
I know this is a little bit vague, but what I mean by that is that it should not be the trivial metric, and somehow relate to what we intuitively think would make sense: For example it would be nice if the distance if you remove one edge is smaller than if you remove two or more edges, or (I'm not sure if it actually makes sense, so it certainly is not necessary) that the distance between the empty graph and the complete graph is maximal.
For the sake of simplicty you can assume that $V$ is finite.

One such metric which is very useful is the graph edit distance. In a nutshell, you are allowed a certain number of operations, each with a cost, such as edge insertion or edge deletion (depending on the context you may also add, relabel, remove vertices) to transform one graph into another. The distance between any two graphs is then the minimum total cost of a transformation from one to the other (the costs need to be symmetrical for this to be a distance, e.g. the cost of deleting is equal to the cost of adding, and are usually taken to be unitary).
There are applications outside of pure graph theory such as pattern recognition or in bioinformatics (generalisations of string edit distance useful for DNA analysis).
Note that usually we don't consider "edit distance up to isomorphism" as your question seems to indicate you want, but it can of course be adapted in a straightforward way to fit that requirement.


short text categorization with spelling correction I am building a classifier for short texts in a chat system. My features are words and pairs of words.

Naturally, the sentences contain spelling mistakes. If a particular wrong spelling of a certain word hasn't appeared in the training corpus, the classifier has no chance to identify it.

I consider taking an existing spelling corrector, and integrate it with my current classifier, but I am not sure how to do it.

Do you know of a paper that integrates an automatic spelling correction tool with a short text classifier?

Could you not just pre-process the text? Simply pass over the corpus and correct errors via edit-distance or lookup tables. Once this has finished you can then run the classifier.

It you really want to incorporate the correction into your model, it would seem that you can re-define edit distance to compute the log-probability of some misspelled word matching another for some mismatch probability $\theta \sim \text{Beta}(\alpha, \beta)$.

The resulting probabilities can then be incorporated into the classifier directly, which would be parameterized by $\theta$. Depending on how complex your internal model is, you could find the ML or MAP estimate $\hat{\theta}$ by some EM algorithm, or if the model allows, analytically.


Find path from A to B which length ≈ L I have an undirected weighted graph.

I want to find the path from A to B which length (sum of the weights) is as close as possible to a specific value "L".

To do that, I have been doing a DFS to check all the possible paths... When L is relatively small, it's ok. But when I ask for a bigger L, it takes too much time to complete. I added some criteria to stop searching useless paths but that cannot solve the problem.

So I was wondering how to do what I am searching for. Is DFS the only solution ? I thought about genetic algorithms but I don't know if it would work.

Thank you !

There are no known efficient algorithms for your problem. Consider the case where every edge has weight $1$ and there are $n$ vertices in the graph. A path from $A$ to $B$ with weight (approximately) $n-1$ is (approximately) a Hamiltonian path from $A$ to $B$ and finding Hamiltonian paths is NP-hard.


Filling a string with wildcards with minimum cost You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.

You are allowed to write data to the string in blocks of fixed size: character-by-character, you can write contiguous blocks of identical characters of length 2, 3 ... N: X, XX, XXX, etc. For example:

  Block: XX, apply to the 2 position in X***Y*Z => X*XXY*Z

It is allowed to overwrite same characters:

  Block: XX, apply to the 0 position in X***Y*Z => XX**Y*Z

When you choose a size of block you would like to use, let's say S, "preparation" costs occurs: S*L, where L - some input constant. Let's say, you picked the size 2 (cost is 2*L), then you are allowed to write XX, YY, and ZZ to the given string. When you write a block of data to the given string, writing cost occurs - some input constant C that is independent of the block size. When you choose some block length, e.g. 2, you have to fill all blanks using block_size = 2, you are not allowed to decrease or increase it in the middle of writing. For example, if you write the first piece of data to the given string as XX, later you are allowed to use YY and ZZ only. The same with other sizes.

Your task is to identify the minimum possible cost to fill all blanks considering costs of writing data and preparing a block.

Let's consider the example above in details. We are given a string X***Y*Z, L = 20, C = 10. For each option, there are a plenty of variants how to fill blanks.

1) We can fill all blanks with a block of size 1 using any characters from {X, Y, Z}. Thus, total cost is 1*20 (prepare a block of size 1) + 4*10 (fill 4 wildcards) = 60. Possible results, there are plenty of them:

  XYXZYXZ, XXXYYZZ...

2) We can use block size = 2. For example, overwrite X* with XX, ** with XX, Y* with YY, the total cost is 2*20 (prepare the block of size 2) + 3*10 (perform 3 writing operations to fill all blanks), the total cost is 70.
Example:

  Solution 1

  Init: X***Y*Z

  step1: write XX at 0 => XX**Y*Z

  step2: write XX at 1 => XXX*Y*Z

  step3: write YY at 3 => XXXYY*Z

  step4: write ZZ at 4 => XXXXYYZ

My current approach is, basically, straightforward brute-force - start with block_size = 1, iterate it up to N, each time try to fill all the wildcards. If current block overwrites existing data, try changing symbol type accordingly (If a block consists of X, try using Y). If it's not possible, try another symbol type/block size.

Is there any better way?

I think I've found a solution (thanks, Yuval Filmus and D.W.!). It consists of 2 major steps:

1) Generate a valid string at minimal steps. You start traversing a string from left to right, moving by 1 character each time. I do this recursively. At each recursion level, you iterate a substring in a range [current_pos, block_size] and continue recursion from each character. By doing this you are exploring possibilities to print, let's say, 3 characters and to continue from any of them without any costs. During recursion, you explore all input characters: X, Y, Z, so each time you generate 3 branches. When you hit an end of a string, corresponding recursion depth equals to a number of used blocks.

2) Searching for an optimal block_size. Using binary search over a block's length to find the optimal block size could be tempting, but it does not work in general. The reason is that depending on costs of block's preparation/usage, cost function could be non-monotonic. Thus, it looks like you have to use linear search.


Training and testing image sizes for classification in computer vision When training a classifier for object detection using features extracted from images (eg HoG features), how important is it that the images used for training fed into the classifier in their natural aspect ratio?

For example, regardless of their aspect ratio, would a classifier work if all images were edited re-sized into squares of equal dimensions? (I know that OpenCV does this in its cascaded classifiers).

And if this is possible, then in the end, when we want to test the classifier, do we provide test images in their natural aspect ratio, or would the test images, too, have to be resized into squares?

It's important that all of the training and test images have the same aspect ratio but it doesn't necessarily have to be the natural one. If you think about it for a while you can see why that is. For example, if you're making a face detector and you have altered the aspect ratio to make all the faces look abnormally tall and skinny then you have a tall and skinny face detector. It won't work unless you do the same transform on the input images.

I'm not sure if I believe you about opencv making all the inputs to the cascade classifiers square. There is no reason it has to be square as long as all of the training images are the same size.


Intuition on O(number of leaves) for master theorem I am trying to develop the intuition of the master theorem for the case where $a > b^{d}$ [Case 3] in this video. In the video, they say that since most of the work is done at the leaves, we should expect $O(\text{number of leaves})$ but I don't see how that is similar to  $O(n^{\log_b a}$), which one would get from the proof.
I just need the connection to the intuition as in how to see  $O(n^{\log_b a}$) from $O(\text{number of leaves})$ even in the least rigorous way.  I don't need the actual proof. The presenter gets on to the proof where $n$ is a power of $b$ later on, which is easier to follow but I would like to know so that I don't have to look up the material every time I need to check my work. Given the order of the presentation, I suspect that the intuition can be obtained without the proof for now but I could also be wrong and would appreciate being corrected if that's the case.

The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\ell$ children at depth $\ell$ labelled $b^{k-\ell}$. In particular, taking $k = \ell$, we see that there are $a^k$ leaves. Since $n = b^k$, we get that the number of leaves is
$$
a^k = (b^{\log_b a})^k = (b^k)^{\log_b a} = n^{\log_b a}.
$$


Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy? Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, $\mathrm{L} \in \mathrm{NTIME}(n)$. Thus, $\mathrm{NTIME}(n^3)\subseteq \mathrm{NTIME}(n)$ which implies the non-deterministic time-hierarchy is false.

But we all know that time hierarchy is true. Where am I going wrong? The statement seems to be correct but I know it's wrong. How?

The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $L\in\mathrm{NTIME}(n^3)$.


Can't under stand change of variable T (n) = T(√n) + 1
The easy way to do this is with a change of variables. Let m = lg n and
S(m) = T (2^m).

T(2^m) = T (2^(m/2)) + 1

S(m) = S(m/2) + 1

Can any one explain why 1 and 2 are same and this works ??

Perhaps the concept will clear up if you try to solve the recurrence:

$T(n)=T(\sqrt{n})+1$.

Let $n\gt0$ which implies $\log_2n$ exists.

Let $m=\log_2n$ which implies $2^m=n$.

By the above statement and the first statement it is true that: $T(2^m)=T(2^{m/2})+1$. This is statement $A$

Define a new function $S$, such that $T(2^{\log_2n})=S(\log_2n)$.

$\implies T(2^m)=S(m)$ [By definition of $m$]

$\implies T(2^{m/2})=S(m/2)$.

By statement $A$ and above,

$S(m)=S(m/2)+1$.

Note that $m=\log_2 n$ and now we let $m$ be a perfect power of 2. Let $m=2^k$ where $k\ge0$. Also note that by imposing this restriction, we have also made $n=2^{2^{k}}$ thus $n$ is two raised a perfect power of 2.

Expanding the recurrence,

$S(m)=S(m/2)+1\implies S(m)=S(m/4)+2 \implies ....\implies S(m)=S(m/2^k)+k\implies S(m)=S(1)+k \implies S(m)=S(1)+\log_2 m.$

Now as $S(m)=T(n)$ [By definition of $S$ and $m$], we can write the last statement of the previous as follows:

$T(n)=\log_2\log_2 n+S(1)$

Again by definition of $S$, we get $S(1)=T(2)$ [Remember $S$ is a function in $m$ and $T$ is a function in $n$, but $m$ and $n$ are not independent. Infact $m$ has been defined as $\log_2 n$].

Hence we have a solution to your original recurrence,

$T(n)=\log_2\log_2 n + T(2).$

[Note that during the proof, we had restricted the values which $n$ could take up, but putting the solution back into the recurrence tells us that this solution works even when $dom(T)=\mathbb{R}^+$]


Counting strings with balanced substrings Consider a string of characters $a, b, c$ only. Such a string is called good if the number of $a$'s + number of $b$'s is equal to the number of $c$'s.

Given an integer $n$, find the number of strings of length $n$ consisting only of characters $ a,b,c$ such that all of its substrings of length $k$ are good.

Example:

$ n = 3 ,k = 2 $ is $6$,

$ n = 2,k = 1 $ is $0$

I could only solve when there are only two characters but can anyone help me how to solve when there are three characters.

For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence:
$$
\begin{align}
&M(k,s) = 1 \\
&M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\
&M(n+1,tc) = M(n,ct)
\end{align}
$$
Here $t$ is a string of length $k-1$. Summing over all good strings $s$, we can solve your problem.

Since $a$ and $b$ are really interchangeable, we can also consider a slightly different recurrence, in which $s$ only consists of $a$'s and $c$'s:
$$
\begin{align*}
&M'(k,s) = 2^{\#_a(s)} \\
&M'(n+1,ta) = 2M'(n,at) \\
&M'(n+1,tc) = M'(n,ct)
\end{align*}
$$
Here the second parameter is a "template" in which $a$ stands for either $a$ or $b$.

Using either recurrence, you can find explicit formulas for any given value of $k$.


How to efficiently sort and filter a large iterator Given an huge iterator (millions of random elements) and asked to obtain the top 10 elements in descending/ascending order.
What is an efficient way or algorithm to do this?

NOTE: The iterator size is to huge and cannot be all loaded into memory and in-place sorting done. (I need a different approach)

I have a simple implementation in Python (sorting an iterators containing hash maps), but it's not efficient

def sort(iterator, sort_key, count):
    result = []
    for idx, row in enumerate(iterator):
        if idx < count:
            result.append(row)
        elif idx == count:
            result.sort(key=lambda x: x[sort_key])
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]
        else:
            if row[sort_key] > result[-1][sort_key]:
                result.append(row)
                result.sort(key=lambda x: x[sort_key])
                result = result[:count]

    return result

You can use a max-heap or min-heap. If you want to find the top $k$ elements, use a min-heap. Start by inserting the first $k$ elements. For every subsequent element, compare it to the root of the min-heap. If the new element is smaller, continue to the next element. Otherwise, remove the root and insert instead the new element, operations which can be done in $O(\log k)$. In total, this is an $O(n\log k)$ algorithm.


What are the examples of trivial and non-trivial properties of language recognized by a Turing machine? Rice's theorem: Any nontrivial property about the language recognized by a Turing machine is undecidable.

I know the proof but I am not able to understand the theorem. I think trivial properties are like :language recognised by Turing machine contain at substring "aab". where as nontrivial property means is language accepted by Turing machine is finite etc.

My question : Give at least two example of trivial properties and two non-trivial property about the language  recognized by a Turing machine.

In the context of Rice's theorem, a trivial property has a very specific meaning.

Here, we define a property to be a set of Turing-recognizable languages. A property is non-trivial unless it contains no languages, or contains all Turing-recognizable languages.

We can clearly recognize these with a Turing Machine, since we can just make a machine that always says "YES" for the first case, or make a machine that always says "NO" for the second.

So both the properties you have identified are non-trivial properties, and are thus undecidable by Rice's theorem.


Compilation with a witness / certificate Sometimes, to install a program, you have a choice between compiling it yourself or downloading a precompiled binary. In theory (using a new programming language and a new compiler designed specifically for this), is it possible to generate a witness / certificate with the compiled binary such that checking the witness / certificate is very easy when compared to compiling things yourself, but ensures that the compilation indeed yields this binary ?

To avoid trivial answers, I'll specify things a bit more: The source language should contain ML, and the target language should be some realistic assembly language. The compiler should do many optimizations so that speed of the compiled program is comparable to that of OCaml, and in particular the compilation can not be just concatenating an interpreter and the source.

From what I've read, the longest thing in compilation is the optimizations. So my question is more or less: Can optimizations run much faster on a non-deterministic machine (in which case, we can use the witness to know which path to take on the real machine).

In theory, what you are asking about has been studied, under the name "translation validation".  See, e.g., the following classic paper:

George C. Necula. "Translation validation for an optimizing compiler." PLDI 2000.

In practice, compilation is such a complicated messy process that I doubt there will be any easy-to-verify certificate that proves the entire compilation process was done correctly (including lexing, parsing, front-end, optimization, back-end, assembly, linking, etc.).  Academic work typically focuses on just one or two phases of the process (e.g., some of the stages of optimization).

One should separate two separate issues: can the verifier be simpler than the compiler?  can the verifier be faster than the compiler?

Simpler is interesting, because it means the verifier can potentially be more trustworthy (e.g., less likely to have bugs).  Classic work on translation validation focuses on that case.

Faster is a different question.  Some optimizations are deterministic and won't benefit, but there are certainly plenty of optimizations that involve a search over some space of possibilities.  An extreme version of that is the concept of "superoptimization", which optimizes a short code sequence by searching over all possible optimized versions and finding the one that is the fastest while remaining semantically equivalent to the original.  See, e.g., the following papers:

R. Sausnauskas, Y. Chen, P. Collingbourne, J. Ketema, G. Lup, J. Taneja, J. Regehr.  "A Synthesizing Superoptimizer."

Sorav Bansal, Alex Aiken. "Automatic Generation of Peephole Superoptimizers."  ASPLOS 2006.


What does the exact $\mu$-recursive program for minimization look like? The minimization of a given primitive recursive function $f$ is computed by the following expression:

$
\newcommand{\pr}[2]{\text{pr}^{#1}_{#2}}
\newcommand{\gpr}{\text{Pr}}
\newcommand{\sig}{\text{sgn}}
\text{Mn}[f] = \gpr[g, h] \circ (\pr{1}{1}, \pr{1}{1})
$

$g = \sig \circ f \circ (\pr{1}{1}, c^1_0)$

$h = \text{Cond}[\text{t}_\leqslant \circ (\pr{3}{3}, \pr{3}{2}), \pr{3}{3}, \text{Cond}[ \text{add} \circ (\text{t}_= \circ (\pr{3}{3}, \text{ suc} \circ \pr{3}{2}), f \circ (\pr{3}{1}, \text{suc} \circ \pr{3}{2})), \text{suc}  \circ \pr{3}{2}, \text{suc}  \circ \text{suc}  \circ \pr{3}{2} ]]$

The first call to the function ($\text{Mn}[f] \circ (\pr{1}{1}, \pr{1}{1}) (n, k)$) will return at most k+1 and terminate for all inputs, if $f$ is total recursive.

A $\mu$-recursive search would not necessarily terminate, if no $z \leqslant k$ such that $f(n, z) = 0$. But I fail to see how that $\mu$-recursive expression would look in contrast to the above one, meaning $-$ what would the part of the expression look like, that makes the function not terminate.

I think you're confused about definitions. What you represented above is bounded minimization where we look for the least number $z$ below a given bound $k$ such that $f(n,z) = 0$. Such bounded minimization can be defined without any extra gadgets, using only primitive recursion.

The so-called $\mu$ operation performs unbounded search. It is not something we can define using primitive recursion. It is a new primitive operation which we add to primitive recursive functions to obtain recursive functions.

That is, if $f$ is a function of several arguments then $\mu(f)$ is a partial function which satisfies
$$
\mu(f)(\vec{n}) = k \iff f(\vec{n},k) = 0 \land \forall j < k, f(n,k) \neq 0.
$$
If there is no such $k$ then $\mu(f)(\vec{n})$ is undefined.

Every primitive recursive function is total. However, $\mu$ allows us to create non-total functions, for instance $\mu(f)(1)$, where $f(n,k) = 1$, is everywhere undefined. Therefore, $\mu$ is not something that can be defined using primitive recursion.

There are various mechanisms that exceed the power of primitive recursion which allow us to define $\mu$. One such is a general recursion, and another is a fixed-point operator.


Prove the following claim on Hamilton Path? I am trying to prove the following claim:

Given DAG graph, there is Hamilton path iff the following algorithm
returns true:

Do topologic sorting.
Move on the graph's vertices one by one (from low to high). In case there is no edge connecting 2 vertices with adjacent values from the topologic sorting then return false.
if no false was returned after we check all vertices, return true.

I am stuck of proving one side which is: if there is Hamilton path then the algorithm returns true.
I tried using induction on number of vertices in the graph n:

Base case is simple for n==0.

Assuming claim is correct for n I want to prove for n+1

So I said, let's exclude the last vertex in the given Hamilton path (let's call it a), and assume by contradiction that the algorithm returned false.
This means one of the 2:

Two vertices with adjacent values had no edge connecting them and both aren't a.
this contradictc the assumtion that the claim hold for graph with n vertices.

One of the two vertices is a and the other isn't a.

I am stuck on proving that case (2) will give us a contradiction, How may I continue?

Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.
Hint: there must be two parallel nodes. Can we reach one from the other?


Normal colorings of cubic graphs (part 1) Edit 2019 June 27 Question 3 is new

...

  Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or with three.

There is also the following

  Conjecture Every bridgeless cubic graph (that is, a cubic graph without a cut edge) can be normally 5-colored.

We are looking for algorithms to normally color cubic graphs

  Questions

  Could you suggest an algorithm to find normal $k$-colorings of cubic graphs, with $k$ at most 9, that is efficient and simple.  The coloring should include at least one edge $e$ such that the $e$ and its adjacent edges are colored with 3 colors, if this is possible.  It is known that 9 colors should suffice. It is my understanding that a linear time algorithm is known, but I've not been able to find it in the literature.

  More importantly:

  Could you suggest an algorithm to find normal 5-colorings of cubic graphs if they exist?
  Can you find a way to color the graph using a vertex coloring algorithm ... to illustrate what I mean, to do edge coloring of a graph $G$, you perform vertex coloring on the line graph of $G$.  To do strong edge coloring of $G$, you perform vertex coloring on the square graph of the line graph of $G$.  In that same spirit, is there a reasonable auxiliary graph on which to do standard vertex coloring to achieve a normal coloring of $G$?

If there is a better site where this question could be posted, please indicate this.  If this site is not for questions requesting information about algorithms, please notify and it will be removed immediately.  I have never posted in this site.

Some old results by Vladimir Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165-176, imply that Question 3 has an affirmative answer. Although the auxiliary graph is not assured to be in some way as elegant or natural as in the case of line graphs or their squares. The easiest example that I can come up with has 13 times the order of the line graph.
This construction also gives an affirmative answer to Question 2.


Given a set of irregular polygons finding a set of vertices (one on each polygon) such that distance between points is maximized Given a set of irregular polygons with the same number of points, where $polygon_i$ is completely contained within the boundary of $polygon_{(i+1)} $.

I need to find a set of vertices (one vertex from each polygon) such that the pairwise distances between all of the points selected are maximized.

What kind of algorithm should I be looking at to solve this problem? The practical use case of this would be a case with 4-8 polygons with roughly 1000-3000 vertices each, I am looking for an approach that could work under these parameters, but am also interested in the classification of this problem from a theoretical perspective.

It seems like this is case of treating each point as the center of circle that is a member of an independent set in a geometric intersection graph, and then moving the points along the polygon boundary that they lie on such that the radius is maximized while keeping the set independant.

Potential Simplifications here are:

Each polygon has the same number of vertices.
All vertices of $polygon_i$ are contained entirely within the area of $polygon_{(i+1)} $
All polygons lie on the same 2D plane.

I don't know whether this problem is in P.  Given the similarity to facility location problems, it smells like it might be NP-hard.  However, I can suggest some candidate algorithms.  They break down into two categories: algorithms to get the exact optimal solution, and heuristics to get a pretty-good solution that hopefully will be an approximation to the optimal (but no guarantees).

Exact algorithms

One approach is to convert to a decision problem, and then an algorithm for independent set.  The decision problem is:

Given sets $S_1,\dots,S_k$ of points and a distance $d$, is there a way to choose one point from each set so that no two points are at distance $\le d$ from each other?

(Each $S_i$ represents the set of points in a single polygon.)
Binary search over $d$ lets you convert any algorithm for the decision problem into an algorithm for your optimization problem.

Now form a graph $G=(V,E)$ where $V=S_1 \cup \dots \cup S_k$, and where you have an edge between every pair of points that are at distance $\le d$ from each other.  You are looking for an independent set $v_1,\dots,v_k$ such that $v_i \in S_i$ for all $i$.  There are many approaches for solving such a problem.

For instance, you can express it as a SAT instance, and feed the result into a SAT solver.  You'll have one boolean variable $v$ for each $v \in V$; if $v$ is set to true, then that means you've included $v$ in your set.  Now you have a bunch of clauses of the form $(\neg v \lor \neg w)$ for each pair $(v,w) \in E$, asserting that you don't pick any pair of vertices at distance $\le d$, as well as a clause for each set $S_i$ asserting that you pick exactly one element of $S_i$.

Or, you could express it as an integer linear programming instance, and feed the result into an ILP solver.  You'll have one zero-one variable $v$ for each $v \in V$; add an inequality $v+w \le 1$ for each pair $(v,w) \in E$, along with an equality $x_1+x_2+\dots + x_j = 1$ where $S_1=\{x_1,\dots,x_j\}$ (and similarly for each $S_i$).

Or you could apply an approximation algorithm for independent set, such as the greedy algorithm based on selecting the minimum degree vertex at each step.

The graph $G$ is a geometric intersection graph, so you might be able to use algorithmic ideas customized for that kind of graph.  You'd have to investigate them  for yourself and see if they can be applied to your problem.

Heuristics

One heuristic is to use the Farthest Point First heuristic from clustering.  You pick a point arbitrarily, then pick the point that is furthest from it, then pick a third point that is furthest from these two (maximizes the minimum-pairwise-distance), and repeat.

You'll need to adjust it to your setting, to make sure you don't pick two points from the same polygon.  There are multiple ways to do that, but one simple one is: if you've already picked some subset of points, then discard any remaining ones that are from the same polygon as one of those, and only consider what's left as a candidate for your next point.


Keywords for classification of 2D time series data? Trying to find the right search terms for literature on classifying 2D time series data.

I am looking at data from positional tracking of a swarm of insects over time. I have example datasets for specific insect behaviors, and I would like to play around with training a classifier on these.

The one-nearest neighbor classifier is very competitive for time series.
http://www.cs.ucr.edu/~eamonn/ICML2006.pdf
If you want code or data, I have lots of both.
eamonn


Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular.

My suggestion is as follows:

Assuming $L\in{}REG$, let $p$ be the number that exists for $L$ according to the pumping lemma.

Let $w=ab^{p}ba^{p}$ with $|w|=2p+2>p$.

Since $w\in{}L$, $w$ can be written as $w=xyz=ab^{p}ba^{p}$, so that:

$|xy|\leq{}p$, in this case $xy=ab^{q}$ with $q\leq{}n-1\leq{}p$
$|y|\geq{}1$, in this case $y=b^{n}$
$\forall{}i\geq{}0,xy^{i}z\in{}L$

But for $i=0$ we have $xy^{0}z=xz=aba^{n}\in{}L$ which violates the definition of $L$, so that $L\notin{}REG$.

Does this constitute a sufficient proof with the pumping lemma or am I at least on the right track? I would appreciate any feedback.

It's not sufficient proof because you only proved that if you choose the decomposition $x=ab^q$ and $z$ the rest does not meet the three points of the pumping lemma but remember that the lemma says:

If $L$ is regular then there is a constant $N>0$ associated to $L$ such that  $\forall \sigma \in L$ with $|\sigma|\geq N$ $\textbf{exist}$ a decomposition $\sigma = xyz$ ...

Summarizing. you proved that your decomposition doesn't work. Now you have to try all other possible decompositions.


I'll give a hint by breaking down the problem into nice looking components. I'll leave it to you to implement the components and use them yourself.

1) A function from id to the ring number it is in.
For example,

id 0 is in the 0th ring.
id 1,2,3,4,5,6,7,8 is in the 1st ring.

2) A function from ring number to the last id of the ring.
For example,

0th ring's last id is 0
1st ring's last id is 8
2nd ring's last id is 24

3) A function from ring number to the last pos of the ring. For example,

0th ring's last pos is (0,0)
1st ring's last pos is (-1,1)
2nd ring's last pos is (-2,2)

4) A function from id to the increment of pos to reach the next id. Let's call this function $g$. For example,

$g(10) = (1,0)$
$g(20) = (0,-1)$

It has to do with what part of the ring the id is in.

Hopefully, this has structured the problem in a way you can see the solution easier by yourself.


If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular? If $L_1,\,L_1L_2$ are regular languages with $L_1\neq \emptyset,\,\lambda\notin L_1,\,\lambda\notin L_2,$ is $L_2$ regular?

I think I found a correct proof for this question but my professor says it cannot work. Her issue is with the right quotient step but I cannot see why it is incorrect. Can anyone shed some light on this?

$$
L_1L_2 = \{ w_1w_2 : w_1 \in L_1,\, w_2 \in L_2 \} \qquad \vert w_1 \vert \ge 1,\, \vert w_2 \vert \ge1
$$

$$
\left( L_1L_2 \right)^R = \{ w_2^Rw_1^R : w_1 \in L_1,\, w_2 \in L_2 \}
$$

$$
\left( L_1L_2 \right)^R / L_1^R = \{ w_2^R : w_2 \in L_2 \} \qquad (w_1^R \in L_1^R)(\forall w_2^Rw_1^R) \implies w_2^R \in \left( L_1L_2 \right)^R / L_1^R
$$

$$
\left( \left( L_1L_2 \right)^R / L_1^R \right)^R = \{ w_2 : w_2 \in L_2 \} = L_2
$$

$$
L_2 \, \text{is regular by closure of reversal and right quotient on regular languages.}
$$

How about this? $L_1=\{a^n\mid n>0\}$, $L_2 = \{a^{m^2}\mid m>0\}$. Certainly $L_1$ and $L_1L_2$ are regular, but $L_2$ certainly isn't.


Why does the splay tree rotation algorithm take into account both the parent and grandparent node? I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why would the following not work:

As we insert, for instance, a new node to the tree, we check whether we insert into the left or right subtree. If we insert into the left, we rotate the result RIGHT, and vice versa for right subtree. Recursively it would be sth like this

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

That should avoid the whole "splay" procedure, don't you think?

The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case.  Suppose the tree is just a totally unbalanced path of right children; no node has a left child.  The only leaf in this tree is the tree with the maximum key.  If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting tree is still totally unbalanced.

Now suppose we repeatedly promote every node in the tree, one at a time, in decreasing key order, using the simpler algorithm.  After all the promotions are done, the tree has returned to its original state, and we have used roughly $n^2/2$ rotations.  Thus, on average, each promotion in this sequence requires $\Omega(n)$ rotations; moreover, I can repeat this pattern forever.  So the amortized cost for this promotion algorithm is $\Omega(n)$.

This bad example appears in Sleator and Tarjan's original splay tree paper.

The splay algorithm considers not just one node at a time, but two nodes at a time.  In particular, if the node $x$ being splayed is the right child of a right child, the splay algorithm first rotates $x$'s parent, and only then rotates $x$.

The advantage of this more complex algorithm is that it not only brings the accessed node to the root, but also moves every ancestor of the accessed node roughly halfway to the root, but never moves any node more than a constant number of levels away from the root.

Sleator and Tarjan prove that the amortized time per splay is only $O(\log n)$.  (The proof uses a tedious case analysis using a magic potential function; honestly, if you're curious, just read the original paper.)  Of course a single splay can take $\Omega(n)$ time, but starting with an empty tree, you have to perform a lot of insertions and splays to set up such a bad example.

More briefly: Splaying moves nodes upward quickly and downward slowly.


Deciding Recursive/Recursively Enumerable when given Turning machine encoding as a language Let $L_{1}$ and $L_{2}$ be two languages defined as follows :
   $L_1 = \{ \langle M\rangle \mid L(M) \neq \emptyset \}$
   $L_2 = \{ \langle M\rangle \mid L(M) = \emptyset \}$
   where $\langle M\rangle$ denotes the encoding of a Turing Machine $M$.
$L_{1}$ is the set of encodings of TMs that accept at least one string (i.e. the with non-empty languages), and $L_{2}$ is the set of encodings of TMs that do not accept any string (i.e. with empty lanugages). By making a language out of such encodings, I am essentially asking a Turing Machine to decide on another Turing machine as to whether the second TM has an empty language or not. This is essentially the halting problem, and so both languages are undecidable.

Now, I am not able to characterize $L_{1}$ and $L_{2}$ from among

not recursively enumerable
recursively enumerable but not recursive
recursive

As you note, both languages are undecidable, so neither are recursive. Then the remaining possiblities are recursively enumerable or not.

Note that $L_{1} = \overline{L_{2}}$, so if they were both recursively enumerable, then they would both be recursive, so we know at least one is not even recursively enumerable.

It turns out that $L_{1}$ is recursively enumerable, given an input $\langle M\rangle$ we can simulate $M$ on all strings over the alphabet by interleaving the execution of $M$ on each string. It may take a long time, but if $M$ accepts something, we eventually (in finite time) find it, so we can recognise that $\langle M\rangle \in L_{1}$.

Then simply by logical deduction, $L_{2}$ can't be recursively enumerable, as it is already co-r.e., but not recursive.


What is the appropriate means of bias field in image processing? I want to do image segmentation. In (Li, C. et al, 2011) article about A Level Set Method for Image Segmentation I saw that the authors use bias field estimation. I searched a lot but I couldn't understand the meaning of bias field...What is the appropriate mean of bias field?

Bias field is magnetic based inhomogenity in results of MRI, which comes from magnetic settings, patient position etc.
This term has no standard definition in terms of image processing.
Essentialy this is smooth, low frequency, gradiented signal, which covers valuable data.
In terms of MRI this is just artifact and very often when somebody says that image will be preprocessed or will get rid of artifacts, bias field is included (naming it simply - noise from equipement).


Path in directed, weighted, cyclic graph with total distance closest to D? Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d.

Output: A path between A and B with distance closest to d. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.

Bonus question: are there any algorithms to compute a path from A to B that visits every node at least once, while finding the distance closest to d?

The problem is NP-hard, by reduction from subset sum (given weights $w_1,\dots,w_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative).  This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$  Of course, the algorithm takes exponential time, but it is an algorithm.