Encoding 1-out-of-n constraint for SAT solvers I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x_1,x_2,\dots,x_n$ where it is intended that exactly one of these should be true and the rest should be false.    (I've sometimes seen this  described as a "one-hot" encoding.)

I want to encode the constraint "exactly one out of $x_1,\dots,x_n$ must be true" in SAT.  What is the best way to encode this constraint, to make the SAT solver run as efficiently as possible?

I can see many ways to encode this constraint:

Pairwise constraints. I could add pairwise constraints $\neg x_i \lor \neg x_j$ for all $i,j$ to ensure that at most one $x_i$ is true, and then add $x_1 \lor x_2 \lor \cdots \lor x_n$ to ensure that at least one is true.

This adds $\Theta(n^2)$ clauses and no extra boolean variables.
Binary encoding.  I could introduce $\lg n$ new boolean variables $i_1,i_2,\dots,i_{\lg n}$ to represent (in binary) an integer $i$ such that $1 \le i \le n$ (adding a few boolean constraints to ensure that $i$ is in the desired range).  Then, I can add constraints enforcing that $x_i$ is tree and that all other $x_j$'s are false.  In other words, for each $j$, we add clauses enforcing that $i=j \Leftrightarrow x_j$.

This adds $\Theta(n \lg n)$ clauses and I don't know how many extra boolean variables.
Count the number of true values.  I could implement a tree of boolean adder circuits and require that $x_1+x_2+\dots+x_n=1$, treating each $x_i$ as 0 or 1 instead of false or true, and use the Tseitin transform to convert the circuit to SAT clauses.  A tree of half-adders suffices: constrain the carry output of each half-adder to be 0, and constrain the final output of the final half-adder in the tree to be 1.  The tree can be chosen to be of any shape (balanced binary tree, or unbalanced, or whatever).

This can be done in $\Theta(n)$ gates and thus adds $\Theta(n)$ clauses and $\Theta(n)$ new boolean variables.

A special case of this approach is to introduce boolean variables $y_1,\dots,y_n$, with the idea that $y_i$ should contain the value of $x_1 \lor x_2 \lor \cdots \lor x_i$.  This intent can be enforced by adding the clauses $y_i \lor \neg x_i$, $y_i \lor \neg y_{i-1}$, and $\neg y_i \lor x_i \lor y_{i-1}$ (where we treat $y_0$ as a synonym for false) for $i=1,\dots,n$.  Next, we can add the restrictions $\neg y_i \lor \neg x_{i+1}$ for $i=1,2,\dots,n-1$.  This is basically equivalent to the Tseitin transform of a half-adder tree, where the tree has a maximally unbalanced shape.
Butterfly network. I could build a butterfly network on $n$ bits, constrain the $n$-bit input to be $000\cdots 01$, constrain the $n$-bit output to be $x_1 x_2 \cdots x_n$, and treat each 2-bit butterfly gate as an independent gate that either swaps or does not swap its input with the decision of which to do based upon a fresh new boolean variable that is left unconstrained.  Then, I can apply the Tseitin transform to convert the circuit to SAT clauses.

This requires $\Theta(n \lg n)$ gates and thus adds $\Theta(n \lg n)$ clauses and $\Theta(n \lg n)$ new boolean variables.

Are there any other methods I have overlooked?  Which one should I use?  Has anyone tested this or tried them experimentally, or does anyone have any experience with any of these?  Is the number of clauses and/or the number of new boolean variables a good stand-in metric for estimating the impact of this on SAT solver performance, or if not, what metric would you use?

I just noticed that this answer has some references on enforcing cardinality constraints for SAT, i.e., enforcing the constraint that exactly $k$ out of the $n$ variables are true.  So, my question comes down to a special case where $k=1$.  Maybe the literature on cardinality constraints will help shed light on my question.

For the special case of k out of n variables true where k = 1, there is commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects by Klieber and Kwon.  Simplified: Divide the variables into small groups and add clauses that cause a commander variable's state to imply that a group of variables is either all false or all-but-one false.  Then recursively apply the same algorithm to the commander variables.  At the end of the process demand that the exactly one of the handful of final commander variables be true.  The result is O(n) new clauses and O(n) new variables.

Given the ubiquity of two-watched-literals in DPLL based solvers, I think the O(n) clause growth is a decisive advantage over encoding schemes that would add more clauses.


Do linearly dependent features in feature vectors improve the feature vector? I was reading Wiki on feature vectors, and as far as I can see, it suggests creating new features from already existing features:

  Higher-level features can be obtained from already available features
  and added to the feature vector, for example for the study of diseases
  the feature 'Age' is useful and is defined as Age = 'Year of birth' -
  'Year of death'. This process is referred to as feature construction.

But assuming that you already have included 'Year of birth' and 'Year of Death' as features, will adding 'Age' (that is, 'Year of birth' - 'Year of death') as a feature in the feature vector improve it in any way? I'm thinking not, as the variables are linearly dependent.

If it depends on the machine learning algorithm used, I am mostly interested in SVMs.

Though edron's thought experiment is nice, it assumes that you do not already have both of those features. If you did, then adding the third feature cannot help, because, as you say, it is linearly dependent. Assume features x1 = Year of birth, x2 = Year of death and x3 = Age = x2-x1. Then any linear predictor gives:

x1*w1 + x2*w2 + x3*w3 = x1*(w1+w3) + x2*(w2-w3)

So, nothing has been gained and we could have learned the same thing with the original features.

A better way to augment the features is to add a nonlinear function of features, such as (x2-x1)^2.


Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $ I have to show that this language is not context free $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in  \{a,b\}^* \} $, where the $R$ corresponds to the reverse. For this I will use the pumping motto for free context languages. I know how it works, but I have problems choosing the correct $ \sigma $, because when looking at the alternatives for $ vwx $, knowing that $ uv^kwx^kz$ has to be met, I can't get to something concrete, the $a^{| \omega |}$ makes me sick. Is there any other way to show that it is not context free? or that $ \sigma $ could occupy.

The problem is not very hard if you break the proof of the pumped string not being in the language into cases. So let's work this out.
$$L = \{\omega \omega^Ra^{|\omega|}\;| \; \omega\in \{a,b\}^*\}$$
For every $n$, let us consider the string $\omega = a^nb^nb^na^na^{2n}$. You can check that this does belong to the language.
We are supposed to show that for any partition $\omega=uvwxy$, such that
$$|vwx|\leq n \;\mbox{and} \; |vx|\geq 1$$ there exists $k$ such that $uv^kwx^ky \notin L$.
Case1: $v,x$ lie inside the first $a^n$. Since, $|vx|\geq 1$, we can see that for $k=0$, the resulting string will not be in $L$.
Case2: $v,x$ lie in the starting $a^nb^n$. You should notice that if you again pump the substrings with $k=0$, then the substring cannot be broken into $\omega\omega^R a^{|\omega|}$, because the count of $a$'s at the end remains the same, and we cannot have an $\omega$ of length $2n$ in the resultant string for it to happen.
Case3: $v,x$ lie inside the first $b^n$. Here, again, you can see how $k=0$ will pump the string outside the language.
The further cases are similar to what described above. Work it out for better understanding. Please let me know if you aren't comfortable with any part of this solution.
PS: The $a^{|\omega|}$ which makes you sick was the sole reason this language is not a CFL, XD.


algorithm that removes extraneous connections from a graph For a nondirection graph $G=(V,E)$, I need to write an algorithm that finds connections that can be removed without destroying the graph (ex: a connection from a child of a child back to the root of the graph). I have created an algorithm with a runtime of $O(|V|+|E|)$ (utilizing BFS):

    smallerGraph(G,s):
    for all vertex u from V[G]do
      color[u]=WHITE
      p[u]=NIL
      n[u]=NIL
    end for
    for all vertex u from V[G]do
      if color[u]==WHITE then
        modifiedDFSVisit(G,u)
       end if
    end for
    return 0
    modifiedDFSVisit(G,u):
    color[u]GRAY
    for all vertex v from Adj[u]do
      if color==BLACK and p[v]!=u and p[n[v]]!=v then
        removeLink(u,v)
      end if
      if color[v]==WHITE then
        p[v]=u
        n[u]=v
        modifiedDFSVisit(G,v)
      end if
    end for
    color[u]=BLACK

Additionally, I am also looking algorithm that can solve the same problem, however this time with a runtime of $O(|V|)$. If this is possible, if someone could point me in the right direction, I would appreciate it. If it isn't possible, why? Would the answer change if I was given a list of the connections (as well as the number of connections)?

You describe the graph as

$V$ - a set of vertices
$E$ - a set of edges, where each edge is (presumably) an unordered pair.

To determine where you can go from each vertex $v \in V$, you need to scan the whole of $E$, so you are already $\Theta (|V| + |E|)$.

If the graph is in the form ...
$$ V \rightarrow 2^V$$
... then you can find a spanning tree in $\Theta(|V|)$. To enumerate the edges left out, you are up to $\Theta (|V| + |E|)$ again. But if you don't need to enumerate them, you can determine whether any given edge is spare in constant time.

Correction

  If the graph is in the form $ V \rightarrow 2^V$, then you can find a
  spanning tree in $\Theta(|V|)$.

I think this is wrong. Whatever your search order, at each vertex you have to look through the neighbours to find an undiscovered one, which might be the last. Depending on the structure of the graph, this might happen at every vertex. So the worst case at least is $\Theta (|V| + |E|)$.


Why does cpu benchmark increases faster than cpu frequency? Since duration of an instruction is just the number of cpu cycles needed times the time of a cycle, which is the inverse of the frequency, I do not get why the ratio of cpu benchmark of a two processors of a same trademark is not exactly the inerse of the ratio of the frequencies. Cpu is supposed not to loose time by being inefficient but only to obey and realize the processors instructions that we ask, which are the same in a test of benchmark of the two processors. Could you enlight me ?

Part of the benchmark might be limited by CPU time; other parts might be limited by IO or memory latency or other factors.  Speeding up the clock frequency will speed up the first parts but not the second parts.  As a result, doubling the clock frequency won't necessarily double the speed at which the benchmark is executed.  So, the two ratios aren't necessarily equal.


What is “Oracle Access”? I'm reading a paper for school and I have come across a passage that I don't understand. It says "If we allow the query to access the entries of the array through an oracle, it is possible to obtain a data structure of sublinear size".

Searching for information on what Oracle Access is has given me nothing but stuff about Oracle Databases, which is obviously not what I'm looking for. I can't really wrap my head around what this means.

Can anyone point me in the right direction?

An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. How the oracle does this is abstracted away from (and sometimes an oracle might even do something impossible like solve the halting problem). It's just a way of saying "presume we had these computational abilities, then ...".


Over-fitting Always Occurs? i get stuck in one sentence in machine learning.

i read tom Mitchel book on ML, and some other materials.

if we have small training set, always over-fit can occurs?  or is likely to occurs?

i read lots of material but i'm not sure that which of my fact will be correct.

any solution or idea?

Roughly speaking, over-fitting typically occurs when the ratio $\frac{\text{complexity of the model}}{\text{training set size}} $ is too high. Think of over-fitting as a situation where your model learn the training data by heart instead of learning the big pictures which prevent it from being able to generalized to the test data: this happens when the model is too complex with respect to the size of the training data, that is to say when the size of the training data is to small in comparison with the model complexity.

Examples:

if your data is in two dimensions, you have 10000 points in the training set and the model is a line, you are likely to under-fit.
if your data is in two dimensions, you have 10 points in the training set and the model is 100-degree polynomial, you are likely to over-fit.

From a theoretical standpoint, the amount of data you need to properly train your model is a crucial yet far-to-be-answered question in machine learning. One such approach to answer this question is the VC dimension. Another is the bias-variance tradeoff.

From an empirical standpoint, people typically plot the training error and the test error on the same plot and make sure that they don't reduce the training error at the expense of the test error:

I would advise to watch Coursera' Machine Learning course, section "10: Advice for applying Machine Learning".


How to output all longest decreasing sequences Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for example $(3,2,1)$ is a decreasing subsequence of $(7,3,5,2,0,1)$.) I know how to calculate the length of longest decreasing sequences, but don't know how to report all longest decreasing sequences.

Pseudocode will be helpful.

Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a > b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.


How does the computational complexity of problems depend on the model specifics of a register machine? On wikipedia page of register machines it says that all register machines defined appropriately are equivalent to Turing machines but that

  Computational speed is very dependent on the model specifics.

Does this mean that when we say a problem has complexity $O(n^2)$ or is a polynomial time problem, or something like that, this is assuming some specific model of computation? If so, how general is the statement that a problem is in $P$ or in $NP$ or anything like that?

The basic definitions of computational complexity are normally phrased in terms of plain Turing Machines, so one has to be careful about transferring results to different models. Naturally, if you can perform look-ups faster, any program that requires that functionality will also be faster (at least for that part).

However if the other model is not to extreme, then the gap in the precise running times falls below our normal threshold of caring. That is, most models of fairly general interest are polynomially equivalent to Turing Machines, so even though a register machine is in some sense faster than a Turing Machine, it's not so much faster that it breaks the definitions - it only speeds things up by a polynomial factor (i.e. an $O(n^{a})$ algorithm will only go down to a $O(n^{b})$ algorithm with $b \leq a$).

You can of course define models that are significantly faster than a Turing Machine (for a trivial example, a Turing Machine that can solve $\mathsf{Clique}$ in a single step), at this point, you can't feasibly replace "Turing Machine" in the definition of $\mathsf{P}$ or $\mathsf{NP}$ with the new model without changing things significantly (but models like this do have other uses).


Y combinator, function composition I am trying to understand Y combinators. Could you please explain why the following are equivalent

(Y (f ∘ g))
(f (Y (g ∘ f)))

(Y is a fixed point combination)

It depends on the notion of equivalence you are using.

Suppose we compare these terms according to their denotational semantics,
on $\omega$-CPO domains. Denote with $F,G$ the semantics of the terms $f,g$. Thus, $F,G$ are Scott-continuous functions. Then, we have that the semantics of $Y(f \circ g)$ is, according to the Kleene's fixed point theorem

$$
(1) = [\![ Y(f\circ g) ]\!] = \bigsqcup\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\}
$$
where $\bigsqcup$ denotes the supremum / least upper bound.

Similarly, we get

$$
(2) = [\![ f(Y(g\circ f) ]\!] = F(\bigsqcup\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\})
$$

By continuity, we get
$$
(2) = \bigsqcup\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\}
$$

One can then prove that $(1)=(2)$ by observing that any element of any one chain is bounded above by some element of the other chain. Indeed, we have
$$
\bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots
$$
estabilishing that $(1)\sqsubseteq(2)$. Further,
$$
F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots
$$
estabilishing that $(2)\sqsubseteq(1)$, concluding the proof.

Much less formally, the term $Y(f \circ g)$ expresses the infinite application
$$
f(g(f(g(\ldots))))
$$
and, similarly, $Y(g \circ f)$ expresses
$$
g(f(g(f(\ldots))))
$$
It is fairly natural, then, that applying a single $f$ on top of the second one results in the first one. The above domain-theoretic proof provides a formal justification of that.


Minimum distance of nodes from a set of two nodes In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, which gives us $\mathcal{O}(V + E)$ running time.

Is there any better way to do this? possibly with one BFS?

EDIT: We can start two BFS from $w$ and $v$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $w$ then the nodes in distance 1 of $v$ and then nodes at distance 2 of $w$ and so on. by the time there is no node in the queue of BFS of node $v$, we can end the search. any node which is first visited with $v$ BFS is closer to $v$ than $w$.

But again I suppose there is a more efficient way to do this.

You can do this with only one BFS and the solution is very simple.

I will assume that you have as input a graph $G = (V, E)$. Let $dist$ be a vector which stores the distance of all nodes of your graph to node $v \in V$.

You must run a BFS algorithm starting on node $v$ and store the distance from each node to $v$ in $dist$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $i$ such that $dist[i]$ < $dist[w]$.

The overall complexity of this algorithm is $\mathcal{O}(V + E + V)$. In a tree, we have that $|E| = |V|-1$. Thus, the complexity is $\mathcal{O}(3 V) = \mathcal{O}(V)$.


Trying to understand this Quicksort Correctness proof This proof is a proof by induction, and goes as follows:

P(n) is the assertion that "Quicksort correctly sorts every input array of length n."

Base case: every input array of length 1 is already sorted (P(1) holds)

Inductive step: fix n => 2. Fix some input array of length n.

Need to show: if P(k) holds for all k < n, then P(n) holds as well

He then draws an array A partitioned around some pivot p. So he draws p, and calls the part of the array that is < p as the 1st part, and the part that is > p is the second part. The length of part 1 = k1, and the length of part 2 is k2. By the correctness proof of the Partition subroutine (proved earlier), the pivot p winds up in the correct position.

By inductive hypothesis: 1st, 2nd parts get sorted correctly by recursive calls. (Using P(K1),P(k2))

So: after recursive calls, entire array is correctly sorted.

QED

My confusion: I have a lot of problem seeing exactly how this proves the correctness of it. So we assume that P(k) does indeed hold for all natural numbers k < n.

Most of the induction proofs I had seen so far go something like: Prove base case, and show that P(n) => P(n+1). They usually also involved some sort of algebraic manipulation. This proof seems very different, and I don't understand how to apply the concept of Induction to it. I can somewhat reason that the correctness of the Partition subroutine is the key. So is the reasoning for its correctness as follows: We know that each recursive call, it will partition the array around a pivot. This pivot will then be in its rightful position.  Then each subarray will be further partitioned around a pivot, and that pivot will then be in its rightful position. This goes on and on until you get an subarray of length 1, which is trivially sorted.

But then we're not assuming that P(k) holds for all k < n....we are actually SHOWING it does (since the Partition subroutine will always place one element in its rightful position.) Are we not assuming that P(k) holds for all k

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with.

The proof you describe is known as the principle of strong mathematical induction and has the form

  Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that

  $P(1)$ is true, and
  $(\forall k < n \;[P(k)])\Longrightarrow P(n)$

  Then $P(n)$ is true for all integers $n\ge 1$.

In the proof to which you refer, that's exactly what's going on. To use quicksort to sort an array of size $n$, we partition it into three pieces: the first $k$ subarray, the pivot (which will be in its correct place), and the remaining subarray of size $n-k-1$. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.

We show this is correct by strong induction: since the first subarray has $k<n$ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has $n-k-1<n$ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.


How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves? Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves.
I think I can do this by induction.

For $h(t)=0$, the tree is empty. So there are no leaves and the claim holds for an empty tree.

For $h(t)=1$, the tree has 1 node, that also is a leaf, so the claim holds.
Here I'm stuck, I don't know what to choose as induction hypothesis and how to do the induction step.

If the statement you're trying to prove by induction is

  For all positive integers $n$, a complete binary tree with $n$ nodes has $\lceil{n/2}\rceil$ leaves.

then the induction hypothesis must be

  For all positive integers $k<n$, a complete binary tree with $k$ nodes has $\lceil{k/2}\rceil$ leaves.

Similarly, if the statement you're trying to prove by induction is

  For all positive integers $n$, a hoosegow with $n$ whatsits has $2^{\lfloor\sqrt{n}\rceil!}\cdot n^\pi$ nubbleframets.

then the induction hypothesis must be

  For all positive integers $k<n$, a hoosegow with $k$ whatsits has $2^{\lfloor\sqrt{k}\rceil!}\cdot k^\pi$ nubbleframets.


Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time This question is taken from an exam of a Computer Theory Course.

  Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that have the form: $L=\{ww^R\mid w\in\{a,b\}^+\}$.

Tape 1: Read-Only & monodirectional
Tape 2: Read and Write, bidirectional

$w^R$ is the reverse of $w$.

My guess:

With determinism and  $L = \{{wcw^R | w \in \{a,b\}^+ \}}$ I copy the input from tape 1 onto tape 2, then I check if the first part of the tape is equals to second part using two markers, $X$ for $a$ and $Y$ for $b$ to keep track of the current iteration.

In every iteration of the algorithm I check if there is a corresponding $a$ (or $b$) in the second part of the tape, reading the tape backwards.

In the last iteration, if i read only $X$ or $Y$ i accept, otherwise reject.

With non-determinism: i need to guess where is the center of the tape. One of the configuration in the computation tree would be $wq_cw^R$ where $q_c$ identify the state representing the string's center. Here i can do the same verification for the deterministic version of the problem.

Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize

$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$

How would you do that on a deterministic version of the machine you're trying to use?  Now, in the real problem, nobody's telling you where the middle of the string is.  How would you use nondeterminism to get around that problem?


Time complexity of pairs in array double loop I know, that the following is: O(n^2),
int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

But, should something like count = count + 1; be taken into account?
For predicting or making up a complex time equation, or using sum notation,
n + n-1 + n-2 + n-3 + (…) + 1

The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input.
In your case, the size of the input is at least $n$ (defined to be the length of array), and so count fits in a single machine word. Each of the basic operations in the algorithm cost $O(1)$, and so the overall time complexity is $\Theta(n^2)$, since the algorithm executes this many basic operations.


Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset My problem. Given $n$, I want to count the number of valid multisets $S$.  A multiset $S$ is valid if

The sum of the elements of $S$ is $n$, and
Every number from $1$ to $n$ can be expressed uniquely as a sum of some of the elements of $S$.

Example.
For example if $n=5$ then $\{1,1,1,1,1\}, \{1,2,2\}, \{1,1,3\}$ are valid.

However, $S=\{1,1,1,2\}$ is invalid because 2 can be formed by both $\{1,1\}$ and $\{2\}$ (i.e., 2 can be expressed as both $2=1+1$ and $2=2$), so the second condition doesn't hold. Similarly 3 can be formed by $\{2,1\}$ and $\{1,1,1\}$.

$S=\{1,2,4$} is also invalid because all numbers from $1$ to $5$ can be uniquely made, but the sum of the elements of $S$ is not $5$.

I've tried to find a good algorithm for this problem for quite some time but cannot solve it. It is from codechef.  I've seen some of the submitted solutions but I still couldn't get the logic for solving the problem. NOTE: The time limit for the question is 10 seconds and $n<10^9$

For a multiset I will use the notation $S = \{(a_1, c_1), (a_2, c_2) ... \}$ $a_i<a_j$ if $i<j$, which means $a_i$ occurs $c_i$ times in multiset S.

Till now I have drawn some conclusions

First element of the required sorted multiset should be $1$
Let $S=\{1,a_2 \cdots a_k\} | a_1 \leq a_2\cdots \leq a_k $ be a set following the two properties then $\forall r<k \ \ a_{r+1} = a_r \text{ or } (\sum_{i=0}^ra_i) + 1$
Let $S=\{(1,c_1),(a_2,c_2) \cdots (a_k,c_k)\} | a_1 \leq a_2\cdots \leq a_k$, where $a_i$ is occurring $c_i$ times, follows the required properties then from the above conclusion we can say that $\forall i \ a_i|n+1$ and $a_i | a_j$ if $j > i$ .
Proof: $a_{i+1} = (a_ic_i + a_i -1 )  + 1 \Rightarrow a_i | a_{i+1}$
Now consider $S=\{ \underbrace{1,1 \cdots 1}_{d-1},d,d \cdots d,dm_1, dm_1 \cdots dm_1,dm_2, dm_2 \cdots dm_2, \cdots \}$ i.e. all the subsequent numbers after 1 will be a multiple of $d$. So let $f(n)$ be the count of such multiset possible then $f(n) = \sum_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$ where I am summing over all possible number of $1's$($=d-1$). In other terms $f(n-1)=g(n)=\sum_{d|n,d \neq n}g(d)$

Finally my problem is reduced to this - find $g(n)$ in an efficient way so that it doesnt exceed the time limit.

Here is what the fastest solution is doing. It is indeed computing your function
$$ g(n) = \sum_{\substack{d \mid n \\ d < n}} g(d), \quad g(1) = 1. $$
Given $n$, we factor it (see below) and then compute all factors (see below) $f_1,\ldots,f_m$ in some order such that $f_i|f_j$ implies $i \leq j$ (property P). We now compute $g$ according to the formula by going over the factors in the given order. Property P ensures that when we compute $g(d)$, we have already computed $g(e)$ for all non-trivial factors $e$ of $d$. There is also an optimization (see below).

In more detail, we go over the factors in order, and for each factor $f_i$, we find all of its non-trivial factors by checking which of $f_1,\ldots,f_{i-1}$ divides $f_i$.

Factoring: Preprocessing: we make a list of all primes below $10^9$ using the Eratosthenes sieve. Given $n$, we simply use trial division.

Generating all factors: This is done recursively. Suppose $n = p_1^{k_1} \cdots p_t^{k_t}$. We run $t$ nested loops $l_1 \in \{0,\ldots,k_1\},\ldots,l_t \in \{0,\ldots,k_t\}$, and output $p_1^{l_1}\cdots p_t^{l_t}$. You can prove property P by induction.

Optimization: Since the program is run on several inputs, we can use memoization to save time across different inputs. We only memoize small values (up to $10^5$), and this allows us to store all memoized values in an array. The array is initialized with zeroes, and so we can tell which values are already known (since all computed values are positive).

If the prime factorization of $n+1$ is $p_1^{k_1},\ldots,p_t^{k_t}$, then $f(n)$ depends only on $(k_1,\ldots,k_t)$, and in fact only on the sorted version of this vector. Every number below $10^9$ has at most $29$ prime factors (with repetition), and since $p(29)=4565$, it seems feasible to compute $f$ (or rather $g$) for all of them, recursively. This solution could be faster if there were many different inputs; as it is, there are at most $10$.

It is also possible that this function, mapping partitions to the corresponding $g$, has an explicit analytic form. For example, $g(p^k) = 2^{k-1}$, $g(p_1\ldots p_t)$ is given by A000670, and $g(p_1^2 p_2\ldots p_t)$ is given by A005649 or A172109.


Converting Mathematical Statements to SAT Formulas Is it possible to write a mathematical statement (like Goldbach's conjecture, for example) as a nontrivial 3-SAT formula that is satisfiable iff that statement is true? iff it is false? iff it is independent of the axioms of ZFC? So, for any statement, you would have (at most) 3 formulas, for which only one can be satisfiable. Is there any work in this field (you can use the Pythagorean Theorem as a more simpler example)?

If you want to know whether there exists a general method/algorithm which can convert any given mathematical statement (by which you mean statements written in logic (say first-order logic, second-order logic ... etc)) to a SAT formula which is True iff that statement is True, then the answer is No.

The reason being that evaluating whether an SAT formula  is true or false is decidable (in exponential time if not faster), whereas these logics are usually undecidable. So, no such algorithm can exist.

Of course, there are logics which are decidable, and the statement of those logic can be converted to SAT formula (maybe trivial ones like True or False as mentioned by @D.W) by a specific algorithm. See: http://www.lsv.fr/~haase/documents/h18.pdf


Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X I am stuck on a problem in which I have to print sum of 2Pi mod 1000000007 for all i where Pi  is sum of numbers in ith subset of a set X.

Length of set can be upto 100000.

Value of element in the range [0,1012].

Here's the link of the Problem.
Problem Statement

I could not find any approach other than Brute-Force which gives verdict TLE.

@Moderators,admins etc.
Before putting this question on hold or marking off-Topic or closed....
Please comment the reason so that I can know the reason and if possible reword it or ask on any other StackExchange Site.
I first posted it on codegolf.stackexchange.com and people(moderators) there have suggested me to post it here as it comes under algorithm category.

You can read about it here.

Programming Puzzles and Code golf

Thank You

If the set you're using is $X=\{x_1,x_2, \dotsc,x_n\}$, then the expression you want to evaluate is equivalent to
$$
(2^{x_1}+1)(2^{x_2}+1)\dotsm(2^{x_n}+1)\bmod{1000000007}
$$
This isn't too hard to prove; here's an example to help you see what's going on:

Suppose $X=\{a,b,c\}$. Then the subsets of $X$ are, obviously,
$$
\{\},\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}
$$
and the corresponding sums of elements in those subsets will be
$$
0,a,b,c,a+b,a+c,b+c,a+b+c
$$
leading to the sum
$$
2^0+2^a+2^b+2^c+2^{a+b}+2^{a+c}+2^{b+c}+2^{a+b+c}=(2^a+1)(2^b+1)(2^c+1)
$$
The general result can be established by a fairly simple induction proof.


Register images from a camera which has undergone pure forward translation Images are taken by a DSLR camera, always set at a particular Focal length.  The scene contains objects with varying distance to the cameras.  Since the camera has undergone translation, homography no longer applies.  Thus looked into Epipolar Geometry for pure translation.  I know a very close estimate of the displacement of the camera (in between images, say Image 1 taken at x and Image 2 taken at x+d).  Is there anyway to find the transformation that maps Img1 to 2 or vice versa to accomplish image registration (need to do image differencing after) ? Can the fundamental matrix and the displacement be used to transform an image to another ?  I am using OpenCV for my implementation.

Without knowing a decomposition of the scene into objects and the depth of each object (distance to each object), it's not possible to achieve what you want.  A very-close object will be affected much more by the translation than a very-distant object.


How to find percentage of CPU time consumed during DMA operation? Q) Consider 1MBps hard-disk is interfaced to the processor in a cycle stealing mode of DMA whenever $64$ bytes of data is available in the buffer,then it is transferred to main memory (1 word = 64 bits) and machine cycle time is 2 micro sec. Then,

1.) Percentage of CPU time consumed for DMA operation is ?
2.) Percentage of CPU time consumed for DMA Operation if burst mode is used?

Given Solution :
1.) For Cycle Stealing Mode
1 word = 64 bits = 8 bytes is transferred in one  cycle.
Since total 64 bytes is to be transferred So total number of cycles $= 64/8 =8 $,
1 cycle time = 2µs , So time for 8 cycles is = 16µs
Now time taken by disc to transfer 64 B is  $(64)/10^{6}=64µs$
Hence % of CPU Time consumed = Data Preparation Time / Data Transfer time $= (16 / 64)*100\% = 25\%$
My Doubt : How does the above formulae give the % time consumed by CPU  or basically where CPU spends time during a DMA transfer and why are we dividing by the disk transfer time.

2.) For Burst Mode : Since all data is transferred at once so only 1 cycle is needed for data transfer i.e. 2 µs
So % CPU time consumed = Data Preparation Time / Data transfer Time
=$(2/(2+64))*100\%$ =~ $3\%$
My Doubt : Why are we adding the 2 in burst mode.

1 word=64 bit=8 B

64 B=8 word

machine cycle time=2 microseconds => 1 word is transferred from io buffer to memory by cpu in 2 microseconds =>  data preparation time by cpu
64 B data and io bandwidth is 1MBps

so 64/10^6 seconds = 64 microseconds = transfer time by io device = time to dump data from io device to io buffer

now in cycle stealing mode generally data is transferred byte wise..but here word size is given so we assume data is transferred word wise..

64B data in 64 microseconds

=> 8 word data in 64 microseconds

=> 1 word data in 8 microseconds = this is word transfer time by io to buffer

so % cpu blocked= % cpu time consumed = % time CPU is actually transferring data from io buffer to main memory= (2/8)*100%=25%

in burst mode its ( 2 / (2+8) )*100%=20%>>>>>>>

in burst mode all data is transferred once as a block...so we wait for io to dump all of 64 B data in its buffer which is 64 microseconds

now cpu will fully transfer this data from io buffer to main memory..64 B data meaning 8 word data meaning 8*2 microseconds meaning 16 microseconds..

so  16*100/(16+64) % = 2*100/(2+8) = 20%


How to compute quotient subgroup efficiently? Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group.

Model of computation is RAM

For all pair of $a$ and $b$ in $G$ just check $a.b - b.a = 0$ , but it is going to take much time $O(n^2)$. Is there a faster algorithm to solve this problem?

Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group:

  In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.

It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ that has not yet been assigned to any coset, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\{gh : h \in H\}$, and assign all such elements $gh$ (not just the $g$ we started with) to this coset.  Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.


Cyclic deterministic finite automata, exponential advantage over DFA Let's define Cyclic deterministic finite automata (CDFA) as a DFA that treats its input a bit differently -- namely, CDFA when given input $w$, firstly transforms its input into $w@$, where $@$ is a special character outside the alphabet that acts as a loop, gluing end of $w$ to the beginning of $w$. So, when CDFA reads $@$ and is currently in state $q$, it then reads whole input (i.e. $w@$) again (so CDFA acts as if it was reading infinite word $w@w@w@w@\ldots$), starting this time from the state $q$. CDFA accepts iff during reading symbol $@$ it is in accepting state.

How to show the following:

  For every $n$ natural, there is language $L_n$ and CDFA $C_n$ such that $C_n$ has less than $3n$ states, but every DFA recognizing $L_n$ has at least $2^n$ states.

?

I tried firstly to find some regular language that I know requires approximately $2^n$ states, but the only candidate that springs to my mind is

  $L = \{w \in \{0,1\}^{\star} : \text{n-th symbol counting from the end is 0}\}$

However, I'm not sure whether there exists CDFA having less than $3n$ states. To be honest, I have no idea why it is $3n$ and not other $kn$.

Let $\Sigma$ be an alphabet of size $n$, and consider the language $L_n$ of all words over $\Sigma$ which contain all letters of the alphabet. It is well-known that the minimal DFA for $L_n$ contains $2^n$ states. On the other hand, $L_n$ is accepted by a CDFA with $n+1$ states.


what does this phrase mean: "train a policy network" I am familiar with the basics (and perhaps a substantial amount of basics) of imitation learning and reinforcement learning. In IL (imitation), we take demonstrations from an assumed expert, which we also assume has the most efficient policy.

What does this statement mean: This will train a policy network using the expert dataset and store the results.

Question: Why do I need to TRAIN a policy network? What is it for?
Are there any algorithms that come with this training a policy?

Thanks

A policy is just a response or action given a state (situation).  Training a neural network with samples from an expert is just searching for a function F that efficiently maps states to actions.

For example for chess, a neural network can be trained with the action to be taken in a given state of the board.  This can be trained using a database of existing (human) expert games.
The resulting network is a policy network that maps a given board setup (state) to the chess move to be executed in that state that more likely leads to a win (action).


How do I apply patch sized features to larger images? I've been trying to teach myself some machine learning, and I wanted to ask what seems a simple question, but I've not been able to find any resources that explain the next step.

Let's say I am doing semi-supervised learning, and have a few hundred sparsely distributed feature extractors, trained on random 32x32 regions (the unsupervised part of the process).

I now want to take the larger images in my training set, and do some supervised learning based on the feature extractors I now have. In this case, multi-label classification.

The bit I'm not clear on is what I do with the full sized image from my training set:

Take random samples from it? -- seems like it would be pot luck if it picks an area needed to identify appropriate labels
Take overlapping tiles with a sliding window? -- seems like I'd end up with absurd dimensionality, since for each tile, I get a whole vector of features
Take adjacent tiles? -- dimensionality still nonsensical, and probably translation sensitive as well

It's a hypothetical example, but let's say my inputs are 800x600 photographs, i.e. the input is about 100-1000 times bigger than the samples I used in the unsupervised learning stage.

The options are various.

If you want a naive and easy workaround simply resize your image (shrink it) and trust that the interpolation would preserve information.

If not, you might want to use Gaussian Pyramids or Spatial Pyramid Match Kernels:

http://www.ifp.illinois.edu/~jyang29/papers/CVPR09-ScSPM.pdf
http://www.vision.caltech.edu/Image_Datasets/Caltech101/cvpr06b_lana.pdf

Other options are a bit untidy. For example, you might take overlapping samples from it, apply some sort of feature extraction and if those features are still big for you, apply a PCA or LDA for dimensionality reduction. (There are more clever sampling strategies such as farthest point sampling : http://webee.technion.ac.il/people/zeevi/papers/17-00623193.pdf

Also taking a look at the covariance matrices might provide you relevant information. Why don't you also check:

http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/36416.pdf

Cheers,


Intuitive description for training of LSTM (with forget gate/peephole)? I am a CS undergraduate (but I don't know much about AI though, did not take any courses on it, and definitely nothing about NN until recently) who is about to do a school project in AI, so I pick a topics regarding grammar induction (of context-free language and perhaps some subset of context-sensitive language) using reinforcement learning on a neural network. I started to study previous successful approach first to see if they can be tweaked, and now I am trying to understand the approach using supervised learning with Long Short Term Memory.
I am reading "Learning to Forget: Continual Prediction with LSTM". I am also reading the paper on peephole too, but it seems even more complicated and I'm just trying something simpler first. I think I get correctly how the memory cell and the network topology work. What I do not get right now is the training algorithm. So I have some questions to ask:

How exactly does different input get distinguished? Apparently the network is not reset after each input, and there is no special symbol to delimit different input. Does the network just receive a continuous stream of strings without any clues on where the input end and the next one begin?
What is the time lag between the input and the corresponding target output? Certainly some amount of time lag are required, and thus the network can never be trained to get a target output from an input that it have not have enough time to process. If it was not Reber grammar that was used, but something more complicated that could potentially required a lot more information to be stored and retrieved, the amount of time need to access the information might varied depending on the input, something that probably cannot be predicted while we decide on the time lag to do training.
Is there a more intuitive explanation of the training algorithm? I find it difficult to figure out what is going on behind all the complicated formulas, and I would need to understand it because I need to tweak it into a reinforced learning algorithm later.
Also, the paper did not mention anything regarding noisy training data. I have read somewhere else that the network can handle very well noisy testing data. Do you know if LSTM can handle situation where the training data have some chances of being corrupted/ridden with superfluous information?

LSTM is designed to process a stream of data chunks (each chunk being the set of inputs for the network at this point in time) that arrive over time and observe features occurring in the data and yield output accordingly.  The time lag (delay) between the occurrence of features to recognize may vary and may be prolonged.

One would then train the network by streaming training examples in randomized ordering which should also have some timeshift noise added in the form of idle passes (have the network activate when inputs are at default idle values eg: when no audio in the case of a speech processor) [exception: if any training data should obey periodic timeshift patterns such as music then the timeshift noise should keep the timeshifting synchronized eg: in music making sure a start-of-measure training example isn't shifted to mid-measure and so forth]

It is possible also to have a semi supervised setup where the network is always in a training configuration and it's trained with examples that expect output of an idle value when no feauture is present or the appropriate expected value when a feature is presented to train).

If feedback format training is desired it can be emulated by:

saving the internal state (time t)
activating the network on current inputs (now at t+1)
supervisory process evaluates the output obtained at t

3a if correction is needed first rewind to the saved state (rewinds network back to t)
3b generate a training example with the correction
3c run a train (backprop) pass for this slice rather than an activation

thus one implements a feedback style system since training examples are basically only created while the network is "getting it wrong."  The feedback format is useful if one wants the network to attempt improvisation (like Schmidhuber's music example).

it should be pointed out that part of the correction feedback (and thus training examples) necessarily includes those that enforce idle valued output when features are not present at the current time

It was mentioned by the OP that [there is no separation of inputs] except that actually there is.  If one thinks of a voice recognition scenario one has periods of utterances (features the LSTM should detect) interspersed with long periods of silence.  So to address the concern it would be fair to say those periods of silence are in fact separating the sequenced groups of inputs (those silences too are actually a feature the network needs to detect and learn to respond with idle valued outputs ie: learn to do nothing when silence).

A note about resetting of the network

Any reset or recalling of a saved network state in the LSTM sense has a meaning of "go back in time" thus undoing any learning the LSTM performed prior to the reset.

Thus you were correct in stating LSTMs are not reset prior to each training sample nor tranining epoch.  LSTMs want their data streamed, or provided in an 'online' manner, so-to-speak.


exact matching between two strings - linear edit distance? This is the problem, given a string with characters from: a-z, ., *, and another string with characters from a-z. where * can delete the character before it, otherwise * is skipped and . can match any single character. the question is whether the first string can match the second one.

Note: That is the statement of the problem as I found, but in this case the character * performs the same function that ? in a regular expression.

Example:

isMatch("a*", "") = true; //"a*" could be "a" or an empty string ""
isMatch(".", "") = false;
isMatch("ab*", "a") = true;
isMatch("a.", "ab") = true;
isMatch("a", "a") = true;

I've already solved this problem using a slightly modified edit distance, which I only know a 2D dynamic programming approach. I wonder whether exists a linear solution for this problem, maybe it is solvable without a dp approach?

As far as I understand you cannot solve the problem in linear time. If in the first string every character a-z is followed by *, the problem coincides with substring matching. So, isMatch("a?a?b?b?b?a?b?a?b?a?","abba") asks whether abba is a subsequence of aabbbababa.


Finding maximal cardinal independent set given oracle The problem is given an oracle $O(G, k)$ that would say if graph G contains IS of size k devise an algorithm for finding independent set of max cardinality that makes poly number of calls to the oracle. My attempt has been that first finding the maximal possible size and then try to find the set of that size by removing vertices one at a time. I understand for a given node it either has to be in or not in the set, then I noticed that that there are multiple overlaps between chain of removals and I could devise a DP algorithm of sorts. But I'm just really stuck after that and was wondering if any hint could be given.

Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.

Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try more vertices until we find a vertex that does. If $O(G') = O(G) - 1$, then we put $v$ aside, and continue in the same way with $G'$.

Taking all vertices put aside, we obtain a maximum cardinality independent set of $G$.


How do I explain that a polynomial time reduction is in fact polynomial time? I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete.

My solution is as follows, which is pretty much copied almost 100% from a textbook example with only an extra requirement for satisfiablity at the end...

  $$QuadSat\leq_{p} Clique$$
  Let $\phi$ be a formula with k clauses such as
  $$\phi=\bigwedge_{1}^{k}(a_k\vee b_k\vee c_k)$$
  The reduction $f$ generates the strong $\langle G,k\rangle$, where $G$ is an undirected graph defined as follows:

  The nodes in $G$ are organized into $k$ groups of three nodes each called the \textbf{triples}, $t_1, \dots, t_k$. Each triple corresponds to one of the clauses in $\phi$, and each node in a triple corresponds to a literal in the associated clause. Label each node of $G$ with its corresponding literal in $\phi$.

  The edges of $G$ connect all but two types of pairs of nodes in $G$: No edge is present between nodes in the same triple, and no edge is present between two nodes with contradictory labels. $QuadSat$ is satisfiable if and only if the resulting graph $G$ contains four or more $k$-$cliques$. Each unique $k$-$clique$ in $G$ represents a set of satisfying assignments to $QuadSat$.

  The reduction runs in polynomial time, because the construction of the graph is a polynomial function; one pass through all the triples to create all the vertices for $V$, and one pass through the same triples to create the edges.

I feel like my explanation as to why my reduction is polynomial in time is severely weak, possibly bordering on wrong. How can I explain this better?

And something else: I think this only proves that QuadSat is in NP, but not necessarily NP Complete. How can I prove this?

Your reduction indeed shows that $QuadSAT\in NP$, since you showed a reduction to a problem in NP.
Perhaps an easier way to have done this, is to simply show that there is a "short witness" for the membership of a formula in $QuadSAT$.
In order to show NP-hardness, you must show a reduction from an NP-hard problem. A good candidate for that is $SAT$ (or $3SAT$).


Minimizing transportation cost through a network, multiple source/sinks I have the following problem:

Inputs:

A finite collection $V$ of vertices
A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$)
An amount of resource $s:V\to\Bbb R$ on each vertex, satisfying $\sum_{u\in V}s(u)=0$

The problem is to determine a transfer function $f:V^2\to\Bbb R^{\ge0}$ such that $\sum_{v\in V}(f(v,u)-f(u,v))=s(u)$ for all $u$, which minimizes $\sum_{u,v}f(u,v)c(u,v)$.

The story to tell is that the points represent places with some amount of resource (if $s(u)$ is positive) or with some need of the resource (if $s(u)$ is negative), and $c(u,v)$ is the cost of sending a unit of resource from $u$ to $v$. We assume that every vertex can send resource to any other vertex, and the direct path is usually better than passing through an intermediate point. How do we minimize the cost of sending everything from where it is to where it is needed?
What is the name of this problem, and do there exist efficient algorithms to solve it? It seems similar to the minimum cost flow problem, but this only has one source and one sink, has maximum capacities for all the edges, and often needs multiple node paths for the resource, while here the direct path is always at least as good as a longer path (because the cost function is a metric).

This is an instance of the minimum-cost circulation problem.  Replace each vertex $v$ by two vertices $v_\text{in}$,$v_\text{out}$.  Each edge $(u,v)$ is replaced by $(u_\text{out},v_\text{in})$, with capacity (upper bound) given by $c(u,v)$ and lower bound 0.  Then, add an edge $(v_\text{in},v_\text{out})$ with both the lower bound and upper bound set to $s(v)$.

There are polynomial-time algorithms for this problem.


Finding a maximal set of nonintersecting line segments in a unit circle Let P be a set of n points that divides the unit circle into equal pieces. Let S be a set of m line segments such that their end points are points in P. The points aren't unique per line, meaning several lines can share points.
I need to find the biggest subset of S of non intersecting lines. Lines that share an end point are treated as intersecting.

In the great piece of art above, n = 3 and m = 2, connecting all dots will form an equilateral triangle, and the two lines are intersecting.

What I tried doing is to apply dynamic programming, but I can't formulate a recursive relation. I tried enumerating the point P = {1,2,...,n} and claiming something like "Let C[k] be the largest subset using only point from 1 to k etc..." but couldn't relate it to k - 1, plus I didn't take advantage of the fact the the points divide the circle into equal pieces.

Any clues\help will be vastly appreciated. :)

For intervals we have got a similar problem.

In the case of interval two intervals $(x_i,y_i)$ and $(x_j,y_j)$ are intersecting if $x_i  \leq y_i \leq x_j \leq y_j $ or $x_j \leq y_j \leq x_i \leq y_i$ is not true.
The problem for intervals is discussed in Maximum non-overlapping intervals in a interval tree.

In your case however lines are intersecting only if you have $x_i \leq x_j \leq y_i \leq y_j \leq x_i$ in circular order. Here $x_i$ and $y_i$ are the circumference distance from a fixed point say the top point.

As suggested in the solution  for intervals you can either apply dynamic programming or the greedy algorithm.


Prove REGULAR_TM is undecidable I am studying the proof of the following theorem:

Given the language

$\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M $ is a turing machine and $\mathit{Accept}(M)$ is regular$\}$

$\mathit{REGULAR}_\mathit{TM}$ is undecidable.

The proof given in Sipser shows that if we already have a machine $R$ that decides $\mathit{REGULAR}_\mathit{TM}$ then we can make a machine $S$ that decides the halting problem:

$$\mathit{Accept}_\mathit{TM} = \{\langle M, w \rangle | M \mbox{ is a turing machine and }w \in \mathit{Accept}(M) \}$$

I am having trouble understanding the proof. Here's how I understand it:

When $M$ (any turing machine) and $w$ (any string) is fed to the machine $S$, we construct a machine $M_2$ that takes a string $x$ as input, but first runs machine $M$ on $w$. First case, if $w$ $\in $$\mathit{Accept}(M)$, then $M_2$ simply accepts x. That is $\mathit{Accept}(M_2) = \sum^*$ in this case - i.e a regular language. Otherwise, second case, $M$ rejects $w$, then $M_2$ checks if the input $x$ is of the form $0^n1^n$, and accepts if it is so - i.e $ \mathit{Accept}(M_2) $ is not a regular language. Inside $S$, for both these cases if we run $R$ on $M_2$ returns the appropriate result which $S$ can directly return.

The case I am confused about, the third case, is when $M$ does not halt on $w$. Then $\mathit{Accept}(M_2) = \{\}$, which is a regular language, and $R$ will therefore return ACCEPT, which $S$ cannot directly return as $w \notin \mathit{Accept}(M)$. But the description of the solution sounds to me like $S$ returns ACCEPT even in this case(pseudocode below). So what am I doing wrong? There's probably a very basic idea I am missing. Here's the pseudo-code for the machine $S$, and inside $S$, as you can see, there's the machine $M_2$ that $S$ creates.

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)  // Might hang here
        if r == ACCEPT:
            return ACCEPT
        else:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

Look up Rice's teorem. Its proof is quite short and sweet. It says that any non-trivial property of a TM language (i.e., one that not all TM languages share) is undecidable, in the sense that it can't be decided by looking at the TM if the language it accepts has the property.

The property of being regular (or a context free language, or the empty language, or the language of all strings, or...) is non-trivial, so if a particular TM accepts a language with the property is undecidable, by Rice's theorem.


Fixed Points of Factorial Function (This is taken from the book Semantics with Applications)

I'm trying to determine the fixed points for the following block:

while (x!=1)  { y = y *x; x = x -1; }

As I understand, a fixed point g has to satisfy the following:

F g s = g s

where s is a state, F is a functional.

The functional F, in this context, would be defined like so:

if (s x = 1): F g s = s[x ->1]
otherwise: F g s = g s[y -> y*x, x -> x -1]

So now I'm trying to come up with a valid fixpoint g.

My attempt is this:

if (s x >=1): g s = s[x -> 1]
otherwise: g s = undefined

I think it's valid since it satisifes  F g s = g s

Am I on the right track and thinking correctly?

(I'm reading the books Semantic with Applications and the lack of solutions has made it very difficult to verify my thinking)

First, let's simplify your F a bit. Instead of

if (s x = 1): F g s = s[x ->1]
otherwise:    F g s = g s[y -> y*x, x -> x -1]

we can equivalently write

if (s x = 1): F g s = s
otherwise:    F g s = g s[y -> y*x, x -> x -1]

since s is the same as s[x->1] in the case s x = 1.

Second, we need to be more precise. We can't write s[y -> y*x, ...] since at the left of -> we need a value, and y*x is not a value but an expression. More in detail, y is a variable name whose value (in the current state) is s y. So, we should write instead s[y -> s y * s x, ...]. We get:

if (s x = 1): F g s = s
otherwise:    F g s = g s[y -> s y * s x, x -> s x - 1]

Now, let's check your fixed point claim. Let g be defined as follows:

if (s x >=1): g s = s[x -> 1]
otherwise:    g s = undefined

and let's compute F g s, aiming to check whether F g s = g s for all s.

F g s
= { definition of F }
if (s x = 1): s
otherwise:    g s[y -> s y * s x, x -> s x - 1]
= { let's call s' the last state }
if (s x = 1): s
otherwise:    g s'
      where s' = s[y -> s y * s x, x -> s x - 1]
= { definition of g }
if (s x = 1): s
otherwise:    if (s' x >= 1): s'[x -> 1]
              otherwise:      undefined
      where s' = s[y -> s y * s x, x -> s x - 1]
= { definition of s' }
if (s x = 1): s
otherwise:    if (s x - 1 >= 1): s[y -> s y * s x, x -> 1]
              otherwise:      undefined
= { arithmetics }
if (s x = 1): s
otherwise:    if (s x >= 2): s[y -> s y * s x, x -> 1]
              otherwise:      undefined

This looks quite different to g s! Indeed, your g is not a fixed point.

Intuitively, that code computes the factorial of x (times the original value of y) inside y,
and loops forever on nonpositive x,
so I would expect a fixed point to be

g s = if (s x >= 1):  s[y -> (s y) * (s x)!, x -> 1]
      otherwise:      undefined


Data structure and structural relationships “Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values, they involve important structural relationship between the data elements.”

  Knuth, Art of Computer Programming, vol. 1 (Fundamental algorithms), 3rd edition, p. 252.

My question is what does “structural relationship between the elements” mean. How are these structures different from any mathematical structure?

Your citation is incorrect--this is on page 232 in 3rd edition, not 252 (first paragraph of "Information Structures", chapter 2.1.
Based on having the chapter available, Knuth is talking about data structures in general. I agree the with suggestions above--just ignore this paragraph if it doesn't make sense or seems obvious. I personally agree that it does not seem to define anything or communicate anything clear to me.


Forward Error Correction for streaming data I am very familiar with error correcting codes. However, it is not obvious how to apply them to adaptive streaming data. There also doesn't seem to be much literature on the problem.

The naive approach might be to take small codewords of data and use forward error correction until there is a statistically significant chance that the client has received them. Then, move to the next codeword.

My question is whether there are known pitfalls with the naive approach and whether there exists a more comprehensive or performant solution (let's ignore the use of locally decodeable codes for now).

tl;dr: This solution is quite good for random noise, but fails for bursty noise, or if you wish to get extremely low failure probability.

Random Noise

Assume the average noise (across the entire stream) is 10%, that is, each symbol is flipped with probability 0.1.
The naive approach you suggest can be summarized as taking small chunks of data ("small" with respect to the size of the stream), and encoding each chunk individually via some ECC.
For instance, a single chunk may be of length $\log N$, while the stream is of length $N$. Then, if you use ECC on that chunk (and expand it into length $C\log N$, for some large constant$~C$), there is a probability of $\approx 2^{-C\log N}$ that it will be decoded incorrectly. Taking a union bound over the entire stream, there is only a polynomially small probability that some chunk of data will fail.

If polynomially-small failure probability is good for you - you are golden. Otherwise, you will have to take ECC with larger redundancy, and this may be impractical. There's also an issue of delay, but that is secondary here.

Bursty noise

A different problem arises when the noise is not random, but adversarial, or even simpler, just bursty. Here again we can assume that 10% of the transmissions are noise, however they can come as a single burst of noise, corrupting  $N'/10$ consecutive transmissions. Clearly, the above naive solution will fail, since there are many codewords that will be completely noisy. Note that even if you increase the redundancy of each encoding, this will not help. The only solution is to increase the chunk size (that is, to send at most 10 encoded chunks), but this is terrible in terms of delay.

One solution to the bursty noise is send the information in a random order. If the transmission is long enough and the information is spread across this transmission quite evenly, then even a burst of noise "behaves" like a random noise with high probability (i.e., it will corrupt the codewords in balanced manner, and will have low probability to completely corrupt a single codeword). This might not be enough.

Using stronger codes (that have an "online" property) can help resisting more noise, improve the delay and reduce the failure property to be exponentially small. See Franklin et al., "Optimal Coding for Streaming Authentication and Interactive Communication" (IEEE Trans. Info. Theory. 61:133-145, 2015). There is also a similar encoding scheme that works for sliding windows rather than unbounded streams, see "Efficient Error-Correcting Codes for Sliding Windows".


Explicit algorithms and algorithms involving unknowns Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.

The first algorithm, by means of some textual reformatting and filling in the usual gaps in high-level reasoning, can be easily (say, within several days of coding) turned into a (relatively large) computer program in some imperative programming language, including that of Turing machines (provided appropriate tooling support, of course).
The second algorithm can almost be turned into code in some imperative programming language, except there are some unknown constants (e.g., the algorithm contains an assignment "$x := c^2$", where $c$ is nonconstructively defined by Theorem 5.19.38, which says $\exists\,c\in \mathbb{N}\colon\dots$). In the best case, this algorithm has some merits such as creating a connection to some other area of mathematics, and in the worst case, this algorithm is simply "'print $r$;', where $r$ is the constant $R(5,5)$". We know that the second algorithm solves our task, i.e., that a Turing machine corresponding to our high-level description exists, but we don't know some part of this algorithm exactly.

In mathematical writing, how do you call these algorithms when you provide the reader with them? I mean, how do you distinguish between them? Do you say explicit/nonexplicit? Effective/noneffective? Any other pair of terms?

Personally, I would call the first one an algorithm, and I would call the second a non-constructive proof of the existence of an algorithm.  But it probably doesn't matter all that much what you call it, exactly, as long as you are explicit and clear about what you mean.

Related: https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs, https://cstheory.stackexchange.com/q/12162/5038.


Big theta notation in substitution proofs for recurrences Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.
For example, on page 91, the recurrence
$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$
is written like so in the proof
$$ T(n) \le 3T(⌊n/4⌋) + cn^2. $$
But can't $\Theta(n^2)$ stand for, let's say, $cn^2 + n$? Would that not make such a proof invalid?
Further in the proof, the statement
\begin{align}
T(n) &\le (3/16)dn^2 + cn^2 \\
     &\le dn^2
\end{align}
is reached. But if $cn^2 + n$ was used instead of $cn^2$, that step would instead be the following
$$ T(n) \le (3/16)dn^2 + cn^2 + n $$
Can it still be proven that $T(n) \le dn^2$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?

By definition, a function $f(n)$ is $\Theta(n^2)$ if there exist constant $b,c,N$ such that for all $n \geq N$,
$$ bn^2 \leq f(n) \leq cn^2.$$
In particular, as long as $n \geq N$, we can always replace $f(n)$ by $cn^2$ when upper-bounding an expression.
In your example of $cn^2 + n$, when $n \geq 1$ we have $n \leq n^2$ and so $cn^2 \leq (c+1)n^2$.


Proving that no two state DFA accept the language L = {$0^i : \forall i \ge 0$} $\lor$ {$^i : \forall i \ge 0$} how do i prove that no DFA with two states can accept the language

$$ L = \{0^i : i \ge 0\} \cup \{ 1^i : i \ge 0\}. $$

I had a lot of troubles coming up with anything that made sense.

Use Myhill–Nerode theory. Here are four words which are pairwise incomparable:
$$ \epsilon,0,1,01. $$

The following table gives words separating them:
$$
\begin{array}{c|c|c|c|c}
& \epsilon & 0 & 1 & 01 \\\hline
\epsilon & & 1 & 0 & \epsilon\\\hline
0 & 1 & & 0 & \epsilon\\\hline
1 & 0 & 0 & & \epsilon\\\hline
01 & \epsilon & \epsilon & \epsilon &
\end{array}
$$

According to Myhill–Nerode theory, every DFA for $L$ must contain at least four states. It is not too hard to construct a DFA containing four states, so four is the minimal number of states.


What is the the relation between the amount of data transmitted and line distance? I am wondering what is the relation between line distance and the amount of data transmitted on that line. I know only the basic of computer science. Let's say I want to calculate the time it takes for 100 GB to transfer over a line with the speed of 100MBps. If I just divide them, I will get 1000 seconds but in my online class, the lecturer said the time depends on the line distance. Since it is an introductory course, he doesn't explain anymore. So my question is, how is it relevant and why? I know the simple answer should be the resistance of the line increase as it got longer but does the resistance affect on the needed time significantly? How could I calculate the needed time with distance?

Distance sets lower bounds on latency, the effect on throughput as opposed to data rate depends on protocol.
Raw error rate increases with distance.


Are problems in NP $\cap$ coNP less difficult than those in NP-complete? I am taking a complexity class now, and I struggle to understand the concept of "hardness":
Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \textsf{coNP}$, $L$ cannot be $\textsf{NP}$-complete. The formal meaning is that not all languages in $\textsf{NP}$ can be reduced to $L$, but does it mean that $L$ is easier to solve than $\textsf{NP}$-complete language (in the sense that it is more likely to have non-exponential algorithm which decides it)?

Is it plausible that the optimal algorithm for $L$ is exponential? (For 3-SAT there is a known assumption, ETH, which as far as I understand states that the optimal algorithm for it has to be exponential).

You had several questions in there, let's just look at a couple of them, the way I understood you.

  Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard?

Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the statement is not entirely correct).  ("Hardness" means that it is at least as hard as all the problems in the class.  "Completeness" means that it is "hard" and is contained in the class in question., see the reference question [1].)

We do believe that $\textsf{NP} \cap \textsf{coNP}$ is strictly contained in $\textsf{NP}$, and that therefore $L$ cannot be $\textsf{NP}$-hard.

  Could it be that the optimal algorithm for $L$ is exponential?

That could very well be.  Factoring is in $\textsf{NP} \cap \textsf{coNP}$ [2], and we don't believe there exists a polynomial time algorithm for Factoring.

What is the definition of P, NP, NP-complete and NP-hard?
https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp


Asymptotic time complexity of a two-loop program I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for:

for (int x = 0; x < y; x++) {
    total  +=  total;
    total  +=  x;
}

and:

while (y > 0) {
    total  -=  y;
    y  =  y/2;
}

Combining those two pieces of code, what is the run time of that function and how do I calculate it?

The first loop has $y$ iterations, each iteration takes constant time ($O(1)$), so all together we have $O(y)$. The second loop has $\log_2(y)$ iterations of constant time, giving a complexity of $O(\log_2(y))$. Both loops together we have: $O(y + \log_2(y)) = O(y)$ because $y$ dominates $\log_2(y)$.


Computer Science Book for Young Adults What is a good beginner computer science book for a young adult, say, a 15 year old? I want to get started in CS, but have no idea where to start. I have limited experience in programming.

Even this might be too basic for teenager, I nicely shows how to abstract problems, and is applicable for kids :

I highly recommend all CS people to take a look at: Computer Science Unplugged , just to see how CS can look different :).

For young CS minded people I recommend to develop intuition by solving programming tasks from problem solving contests, like programming contests: ACM ICPC, Olympiads in Informatics etc.

It's nice way to go into "Practical Algorithmic" , which gives you best from both worlds: programming and algorithms. Thanks to that you will be prepared to go in future in both directions: CS oriented industry (Google, Yahoo etc), and University CS.

Nice places to start:

Sphere On-line Judge - you can sort problems from easiest to hardest and try to solve them
http://www.topcoder.com/ - There are many contests for HS, you can find there similarly minded people to you.


Deterministic context-free languages are closed under regular right-product I am looking for a proof for the following problem:

  For languages $L$ and $R$, if $L$ is deterministic context-free
  and $R$ is regular, then $LR$ is a deterministic context-free
  language.

Note: $RL$ may not satisfy this condition, e.g. if $L=\{wcw^R\mid w\in (a|b)^*\}$, and $R=\{a\}^*$.

Here is an idea. You have to work out the details by your own.

Let $Q_R$ be the states of a DEA accepting $R$, and let $Q_L$ be the states of a deterministic PDA accepting $L$. You build now a new deterministic PDA $P$ that accepts $LR$ as follows:

The state space of $P$ is $Q'=Q_L\times \mathcal{P}(Q_R)$. If you have read $w$ and you are with $P$ in state $(s,T)$, this tells you the following: $L$ would be in state $s$ after reading $w$, and for every $t\in T$ there was a possibility that a prefix of $w$ was in $L$, and the remaining suffix of $w$ would have send the DEA for $R$ to state $t$. You accept if you are in a state $(s,T)$, that contains an accepting DEA-state in $T$. The transitions can be worked out straight-forward. Notice that it might be helpful to modify the PDA for $L$ first, such that it has a total transition function. You can achieve this easily by adding a non-accepting dummy states, that collects all missing transitions.


Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ I have found an exercise where it tasks to provide a grammar and a pushdown automata for
$L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
While finding a pushdown automata for it is quite easy (four states and two stack symbols $p$ and $t$, where $0^x$'s push $p$, $1^t$'s and $0^z$'s pop $p$ or push $t$ if there are no $p$'s, and $1^w$'s pop $t$), I am unable to find an equivalent grammar for it. Perhaps there is some trick for this?

Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form
$$
0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w.
$$
If $y \geq x$, let $y=x+b$. Then we are interested in words of the form
$$
0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b 0^z 1^z 1^b.
$$
We can generate words of the first form using the grammar
\begin{align}
&T_1 \to AW \\
&A \to 0A0 \mid Y \\
&Y \to 0Y1 \mid \epsilon \\
&W \to 0W1 \mid \epsilon
\end{align}
We can generate words of the second form using the grammar
\begin{align}
&T_2 \to XB \\
&X \to 0X1 \mid \epsilon \\
&B \to 1B1 \mid Z \\
&Z \to 0Z1 \mid \epsilon
\end{align}
Taking these two grammars together and adding a new rule $S \to T_1 \mid T_2$, we get a grammar for your language. Note that you can merge $X,Y,Z,W$. The resulting grammar is
\begin{align}
&S \to AX \mid XB \\
&A \to 0A0 \mid X \\
&B \to 1B1 \mid X \\
&X \to 0X1 \mid \epsilon
\end{align}


Building Simple Parse Trees I am trying to learn how to build parse trees.

I have watched videos and tried to do some on my own, but am a little lost.

In this example, I am given the following:

$$
\begin{align*}
&S\to(L) \\ &S\to a \\ &L\to L,S \\ &L\to S
\end{align*}
$$

and then I am told to draw a parse tree for the expression $(a,(a,a))$.

I know that the first $S$ is the start symbol, I know that since I am trying to draw it for a specific string, I should use the bottom up approach, but I am very confused.

Can the lines above also be written as
$$
\begin{align*}
&S\to(L)|a \\
&L\to L,S|S
\end{align*}
$$
or can they not be combined that way?

How would you write this tree?  What confuses me the most is how to write the tree using the $L$ and $L,S$ but resulting in $(a,(a,a))$.

I would appreciate any explanation or demonstration offered.

The notation $S\to(L)|a$ is shorthand to $S\to(L)$ and $S\to a$, so you can rewrite the grammar in your equivalent form; I don't see how this makes things any different, since the two grammars are exactly the same.

The first step in writing a parse tree is coming up with a derivation. In the derivation below, I use boldface to indicate the non-terminal being expanded.
$$
\begin{align*}
\mathbf{S}&\to(\mathbf{L}) \\ &\to(\mathbf{L},S) \\ &\to (\mathbf{S},S) \\ &\to (a,\mathbf{S}) \\ &\to (a,(\mathbf{L})) \\ &\to (a,(\mathbf{L},S)) \\ &\to (a,(\mathbf{S},S)) \\ &\to (a,(a,\mathbf{S})) \\ &\to (a,(a,a))
\end{align*}
$$
There are several different derivations which "feel" the same. For example, in this derivation I always expanded the left-most non-terminal, but you could just as well expand any other non-terminal. When you draw the derivation tree, all these derivations give rise to the same tree.

Here is the actual derivation tree, drawn by Rick Decker:


Is every regular/context free langauge decidable in LogSpace? I know all the regular languages are decidable but not sure whether it can be done in LogSpace.

For regular languages, we have
    $$ \text{REG = DSPACE}(O(1)) = \text{NSPACE}(O(1))$$
where REG is the class of regular languages. This can be easily seen from the equivalent formalisms of regular languages. A language is a regular language iff it is the language accepted by a deterministic finite automaton. A language is a regular language iff it is the language accepted by a nondeterministic finite automaton.

In fact, $\text{REG = DSPACE}(o(\log \log n))$. That is, $Ω(\log\log n)$ space is required to recognize any non-regular language [1].

For context-free languages, please see the answer by Yuval Filmus.


Cost in time of constructing and running an NFA vs DFA for a given regex Repost from Stack Overflow:

I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.

The question I'm having problems with at the moment is as follows:

  Given a regular expression (a|bb)*, derive an estimate of the cost in time for
  converting it to a corresponding NFA and a DFA. Your answer should refer to
  the size of the regular expression.

A similar question from another year is:

  Given that, for the above example, you know the size of the original regular
  expression, |r| and the size of the input string |x|, explain how you would calculate the cost in time for constructing and running the NFA versus constructing
  and running an equivalent DFA.

The resulting NFA for (a|bb)* has 9 states, while the DFA has 4. Even knowing this, I have no idea how to approach the question.

Kiliki's answer has some things wrong.

They say:

  The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)

This doesn't even really make sense. If you are constructing a NFA from a regular expression there are no well defined "nodes" to speak of. A sufficient algorithm is the Thompson's construction.

Amortized time for constructing an NFA from a regular expression

A regular expression is composed literal characters stuck together in various ways

concatenation
alteration and
Kleene star.

Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where Os are states.

       x
    O ---> O

There are other rules for concatenation, etc. that join together NFA's like the one above, but the important part is that any operation adds a small finite number of states and transitions (never more than two states or four transitions actually. If you want the details have a look at the super helpful wiki link above).

The number of literals and operations (concatenation, etc.) is easily determined from the length of the string of the regular expression. The amount of one or the other is different only by a constant factor. Thus we can safely say that constructing an NFA from a regular expression using Thompson's construction is O(n) where n is the length of the string of the regular expression.


Classification accuracy based on top 3 most likely classifications My goal is to recommend jobs to job seekers based on their skill set.

Currently I'm using an SVM for this, which is outputting one prediction, e.g. "software engineer at Microsoft". However, consider this: how significantly different are the skill sets of a software engineer at Microsoft and a software engineer at IBM? Probably not significantly different. Indeed, by inspection of my data set I can confirm this. Hence, the SVM struggles to discriminate in situations like this, of which there are many in my data set, and my classification accuracy is about 50%.

So I had an idea.

In SK Learn, once you've trained some model, you can compute the probability a particular input X belongs to each class.

So for each input X in my test set, I took the the top 3 most likely classifications. Then I tested whether or not the correct label was in the top 3 predictions. If it was, then I considered the prediction to be correct. In doing so, the classification accuracy increased to over 80%.

So my question is: is this a valid approach to measuring classification accuracy? If it is, then does it have a name?

In my mind, it is valid given my intended application, which is to recommend a selection of jobs to a job seeker, which are relevant to their skill set.

This is called top-3 accuracy.  See https://stats.stackexchange.com/q/95391/2921, https://stackoverflow.com/q/37668902/781723, https://stats.stackexchange.com/q/156471/2921.  Sure, you can use it.  Whether top-1 accuracy or top-3 accuracy is better correlated with user satisfaction will depend on your particular application and on your users.


Which NP-Complete problem has the fastest known algorithm? In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?

Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$.  You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size.

Also, the question Are there subexponential-time algorithms for NP-complete problems? addresses similar questions.


Non-primitive recursiveness in real world nonmathematical software? Is there a real world nonmathematical example of computer software that isn't primitive recursive?

I'm not interested in examples that are somehow closely related to theory of computation or logic (like automated theorem proving, model checking, compiler design etc.), or examples that aren't primitive recursive in a trivial way (i.e. having unbounded loops that could have been bounded).

The example doesn't have to be an actually existing piece of code (although it would be great if it is).

Many useful pieces of software have "unbounded" loops that can't be trivially bounded. Any program with a user interface that waits for input, for example. You'd probably also be surprised by the number of software that contains an interpreter of some sorts: your browser, your PDF reader, the software on your printer...


Reducing states of a GTG I used this generalized transition graph with 3 states and got an equivalent generalized
transition graph with 2 states:

GTG:

Equivalent with 2 states:

I'm not sure about the regular expressions linking the nodes $q0$ and $q2$, if someone can clarify where I may have gone wrong here.

Actually the regular expressions from $q_0$ to $q_2$ and from $q_2$ to $q_0$ seem to be correct, but the loops around $q_0$ and $q_2$ are more questionable. Although they will lead to a correct answer, they could be simpler and I am not sure you applied the algorithm correctly.

If you want to be sure of your answer, I would recommend to use linear equations. This is exactly the same method, but it might be safer. In your case, you have the system
\begin{align}
X_0 &= (a+b)X_0 + (aa + b)X_1 + ab^*X_2 \\
X_1 &= X_0 + ba X_1 + bX_2 \\
X_2 &= (bb + a) X_0 + aX_1 + 1
\end{align}
where $1$ denotes the empty word. You want to eleminate $X_1$. To do this, rewrite the second equation as $X_1 = baX_1 + (X_0 + bX_2)$ and apply the general result that if $1 \notin K$, the unique solution to the equation $X = KX + L$ is $K^*L$. In your case, you get $X_1 = (ba)^*(X_0 + bX_2)$. You now copy-paste this value of $X_1$ in the two other equations (and I really did it this way!) to get
\begin{align}
X_0 &= (a+b)X_0 + (aa + b)(ba)^*(X_0 + bX_2) + ab^*X_2 \\
X_2 &= (bb + a) X_0 + a(ba)^*(X_0 + bX_2) + 1
\end{align}
which leads to
\begin{align}
X_0 &= (a+b+ (aa + b)(ba)^*)X_0 + ((aa + b)(ba)^*b + ab^*)X_2 \\
X_2 &= (bb + a + a(ba)^*)X_0 + a(ba)^*bX_2 + 1
\end{align}
You can now recover the regular expressions if you wish: $q_0 \xrightarrow{a+b+ (aa + b)(ba)^*} q_0$, $q_0 \xrightarrow{(aa + b)(ba)^*b + ab^*} q_2$, $q_2 \xrightarrow{bb + a + a(ba)^*} q_0$, and $q_2 \xrightarrow{a(ba)^*b} q_2$.

A further simplification. You may observe that in your original automaton, you have $q_0 \xrightarrow{a+b} q_0$. This implies that for any word $u$, there is a path $q_0 \xrightarrow{u} q_0$. It means that the transition $q_0 \xrightarrow{a+b+ (aa + b)(ba)^*} q_0$ in the second automaton is redundant and could have been replaced by $q_0 \xrightarrow{a+b} q_0$.


Is the complement of a Max Prefix Sum a Min Suffix Sum? Given an array A of n real numbers, are the maximum prefix sum and minimum suffix sum (and vice-versa) of A complements?

I.e. Given A[1..n] and its maximum prefix subarray P[1..i], is its minimum suffix subarray S[j..n] where i+1 = j?

Or stated another way, is sum(A) = maxPrefixSum(A) + minSuffixSum(A) true?

For an array of only negative numbers, let's assume that P is empty and maxPrefixSum(A) = 0.  Similar logic applies in the opposite case.

It depends on whether the maximum prefix and minimum suffix are unique. Consider for example the array $0$ — you can easily find a counterexample to your claim. Suppose therefore that $\sum_{i \leq j \leq k} A[j] \neq 0$ for all $i \leq k$. Let now $j$ maximize $\sum_{i=1}^j A[i]$, and let $k$ minimize $\sum_{i=k+1}^n A[i]$. We want to show that $j=k$. Otherwise, there are two cases:

If $j < k$, let $S = \sum_{i=j}^{k-1} A[i]$. By assumption $S \neq 0$. If $S > 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i]$, and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.
If $j > k$, let $S = \sum_{i=k}^{j-1} A[i]$. By assumption $S \neq 0$. If $S < 0$ then $\sum_{i=1}^{k-1} A[i] > \sum_{i=1}^j A[i]$, and otherwise $\sum_{i=j+1}^n A[i] < \sum_{i=k+1}^n A[i]$.


Checking my understanding of right quotient So I am trying to fully understand the concept of quotient languages.

I will give some examples, let me know if this is correct:
Say that

L1={} and L2 is {ot}, then L1/L2 is {carr}
Or if L1=ab*c and L2 is b*c then L1/L2 is a.

If this is it, I will then try to approach more complex concepts :)
Thank you!

If $L_1=ab^*c$ and $L_2$ is $b^*c$ then $L_1/L_2$ is $ab^*$.

Note that the $b$'s are not forced to disappear.
For instance (as part of these languages) $\{ab^{10}c\}/\{b^3c\} = \{ab^7\}$.


Intersection/Union of recursively enumerable languages that aren't decidable? For $L_1,L_2 \in RE - R $ , I want to prove or disprove if the following can occur:

$L_1 \cap L_2 \in R$
$L_1 \cup L_2 \in R$
$L_1 \cap L_2 \in R$ and $L_1 \cup L_2 \in R$

What I did:

I think any two disjoint languages suffice, since the empty set is decidable.
I think something along the lines of a language and its complement but I'm struggling to think of an example.
It seems impossible but I have no idea how to prove it.

Any help/further insight would be welcomed!

Correct. We can have $L_1\cap L_2=\emptyset\in R$. A good answer would give an example of such a pair $L_1$, $L_2$ so you should figure that out on your own.
Correct but for the wrong reason. If $L_1$ and its complement are both $RE$, then both are recursive and the question says that neither is recursive.  You should prove this yourself, as you'll need it for the next part.

Hint for this proof: show how to use machines that accept $L_1$ and $\overline{L_1}$ to give a machine that decides $L_1$.)
Hint for the question: take a recursives language $K_1$ and $K_2$ and set $L_1=K_1 \cup \text{something}$ and $L_2=K_2\cup\text{something else}$ in a way that gives $L_1\cup L_2=K_1\cup K_2$.

Correct. We know that $L_1\in RE$. Use $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ to show that $\overline{L_1}\in RE$. By the extra proof I suggested you do in the previous part, that means that $L_1\in R$, contradicting the requirement that $L_1\in RE\setminus R$.


How to determine(with some confidence) if two extremely long lists of numbers (terabytes) are similar? I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers.

The main rule if if two distributions are the same, also the order of data does matter for example:
A = {1 2 4 5 6}
B = {6 5 4 2 1}
C = {0.5 0.5 1 2 3 4 5 6}

in above case A and C are still similar but A and B are totally different

To be more clear lets split the question into 3 main tasks

Given large lists A,B find if lets say 50% of A is contained in B (Most efficient technique without comparing all numbers from list)
Given A,B match above condition check that the overlapping numbers have similar order as mentioned above i.e. if 2 in A is followed by 1 same should happen in B. The positions of 1,2 can be different in B.
Select two independent batches from A and B and test if those are from Poission distribution, binomial distribution.

Check out Jaccard Similarity, as it gives a measure of set similarity.  See MinHash, locality sensitive hashing.


generating mazes using Eller's algorithm - why do I get loops? I'm making a maze generator that uses Eller's algorithm. There's not much information about this particlar algorithm on the Internet. So I have some things misunderstood about it. I've made a picture to show you the proccess of generating an incorrect maze.

I didn't found any information about this in article1 and article2.

What should I do to avoid generating loops?

here I get two blocks of the same set, but they don't go one after the other. So I join the second one go it's own unique set

Don't do that; this is not a step mentioned in your first reference! Two cells are in the same set when there is already a path between them (by going up though the already generated portion). By arbitrarily placing the second block into a new set, you are ignoring the fact that it is connected to other cells.

When you leave the 3 blocks alone, you will get

(03 17)03
 03(03 03)

You are required to place a wall between two blocks of the same set, because they already have a path between them. Thus you produce

 03 03|03

And don't had a loop.


2D interval scheduling problem Suppose I give you $n$ axis-aligned rectangles with a specified width, height, and x-position (of the left edge) $\{(w_i, h_i, x_i) \mid i \in \{0, \ldots, n - 1\}\}$, as well as a bound $(y_\mathrm{min}, y_\mathrm{max})$ on the valid y-positions. These rectangles must have integer-valued coordinates for their vertices. Is there an efficient (e.g.: $O(n^3)$) approximation algorithm that gives a sequence $\{y_0, \ldots, y_{n - 1}\}$ of y-positions such that the number of overlaps between any two rectangles (i.e.: edges in the overlap graph) is minimized (and hopefully zero)?

Note that if $y_\mathrm{max} = 10$ and $h_k = 3$, then $y_k = 9$ would be invalid, since the top edge would be at $12$ which is more than $10$.

This is called the offline dynamic storage allocation problem. Check out the papers cited by https://epubs.siam.org/doi/abs/10.1137/S0097539703423941 for a good review of the literature.


NP Class Definition of a Certificate Given the definition for all x ∈ Σ∗

  x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1

Lets say the input x = ababab

Then the certificate u shouldn't be longer than p(|x|).

But what would be p(|x|)? In my example?

In this case, $p(|x|)$ denotes any function polynomial in the length of $x$.

Asking what $p$ is when $x=ababab$ is like asking "What is the running time on input ababab?" without specifying the algorithm you want to know the running time of (or specifying the problem the algorithm is supposed to solve, for that matter). It's a meaningless question. $p$ should be specified as part of proving that a particular language $L$ is in NP. You can't talk about what $p$ is without first defining a language.

If, for instance, you wanted to prove that Vertex Cover is in NP, then for a given graph $G$ and integer $k$, the certificate $u$ could be a vertex cover of $G$ of size at most $k$. Such a certificate would have size equal to the number of vertices of the graph (one bit per vertex) and thus $p$ could simply be the identity function. $M$ would be a machine that verifies that a given certificate $u$ is indeed a valid vertex cover.


What are Predictive Clustering Trees in machine learning? Anybody could let me know what exactly the PDT is and where does it come from? it comes from predictive modeling or decision tress?

I read some articles and websites like: this and this
but both of them are about predictive modeling. I think PDT comes from decision tree rather than predictive modeling.

Clus might get you started. It uses predictive clustering trees and is described in this article, although you'll probably need a student account to get access to that article.

They have a list of publications that you should also find instructive.


How does one implement Dijkstra while skipping an edge Like let’s say you find the shortest path, but you want to find an alternate path as well. In order to do that, you have to ignore each edge in the shortest path one at a time, and then find the shortest path without using that respective edge. At that point you have a set of alternate paths, of which you want to select the one that is the shortest yet also different enough.

But I don’t know how to find the alternate paths while skipping edges. Could anyone please clear this up

Check out Yen's Algorithm for finding the K-shortest paths using any shortest path algorithm. The link provided uses Dijkstra's algorithm as an example