Find if there is matrix that satisfying the following conditions Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an efficient algorithm that will determine if there's a matrix $B_{n\times n} = \{b_{ij}\}$ , $b_{ij} \in \mathbb{Z}$ and

for every $1\leq i \leq n \sum b_{ij} = r_i$

for every $1\leq j \leq n \sum b_{ij} = c_j$

and

$0 \leq b_{ij} \leq a_{ij}$

Thought something with dynamic programming but didn't manage to solve it.

Hint #1:

   This can be solved with network flow.

Hint #2:

   Imagine $r_i$ units of flow entering the $i$th row, and $c_j$ units of flow leaving the $j$th column.  Does that give you any hints how to set up the graph for a network flow problem?


Show there exists a turing machine with the following properties I'm struggling to understand a question I've been given. The question asks:
Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning
values to the variables. Consider the problem of deciding whether (strictly) more than $2^{n−1}$
of these assignments satisfy the formula $\psi$. We will call the language that corresponds to this
decision problem, $L$.

From this I can tell that if $x_1, x_2, ..., x_n$ are the $n$ variables which can be either true or false. I understand why there would be $2^n$ different assignings for the formula, as each variable can be assigned 1 of 2 values. But then what is $\psi$ exactly, is it an assignment such as $\psi$=($x_1 \lor x_2 \lor ... x_n$). But then the later part of the question doesn't make any sense. Can someone please explain in more detail what it means by "deciding whether (strictly) more than $2^{n−1}$ of these assignments satisfy the formula $\psi$"?

The question is then to show that there exists a turing machine $M$ and polynomials $T$ and $p$, with the following properties:

• For every input $x$, $M$ terminates after at most $T(|x|)$ steps.

• If $x\in L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ accepts $<x, t>$] $>$ 1/2.

• If $x\notin L$, then $Pr_{t∈\small\{0,1\small\}^{p(|x|)}}$[$M$ rejects $<x, t>$] $≥$ 1/2

Where $Pr_{t∈\{0,1\}^{p(|x|)}}$[$M$ accepts $<x, t>$] means the probability, for a give $t$ from the set $\{0,1\}^{P(|x|)}$, that M accepts the input $<x,t>$ is greater than 1/2.
This is similar to the definition of bounded error probabilistic polynomial time(BPP), except that the definition for BPP have both equalities as $≥$, so I'm
guessing I need to show that the language L is in BPP. But how would I even start the proof to show that he language is indeed in BPP. Also the definition of a language in BPP is not identical to what is mentioned in the question, so maybe there's a different approach to answering the question. Also, I don't need to explicitly find the polynomials $p$ and $T$, but instead argue that they exist.

Any help to assist me with the question would be much appreciated

Look again at your definitions. $\psi$ is a formula of $n$ variables, eg.
$\psi_1 = x_1 \vee x_2$ or $\psi_2=x_1 \wedge x_2$, on 2 variables.

Now the question asks whether or not there are more than $2^{n-1}$ assignments to $x_1, x_2, ...$ that satisfy the formula. In other words, assignments that make $\psi$ evaluate to true.
For the above example, $\psi_1$ has 3 satisfying assignments (out of the $2^2=4$ possible assignments), while $\psi_2$ is satisfied only by a single assignment (namely, $x_1=x_2=\text{true}$). So $\psi_1 \in L$ and $\psi_2 \notin L$.

If you understand so far, then finding a probabilistic TM that accepts any formula with the above conditions with probability at least $1/2$ is trivial. I'll let you think about it some more.


Regularization term moving the hyperbolic plane When we train a network, we usually have an error function which usually looks like this:

$$Error = (output - target)^2$$

When we add a regularization term, it looks something like this:

$$Error = (output - target)^2 + reg term$$

I understand that there are many different ways of defining the reg term, but in this example, we can make it the sum of all weights.

When we do this, are we just not moving the hyperbolic plane up and down? The slope of it should stay the same everywhere and thus not really make a difference in finding a minimum of the error function.

The point of the regularization term is usually to keep the network from overfitting by keeping the weights vector with low absolute values or sparse. Therefore I would say a sum of all weights is not a good regularization term, because even extreme positive and negative weights can sum to zero. In the regularization term, the $L_2$, $L_1$, $L_0$ norms are commonly used (read about it here).

In a side note, if I understood you correctly, I would suggest to avoid imagining the target function (or loss function) as a hyperbolic plane, since usually DNNs contain non linear activation functions like ReLU.


MIT 6006 Quiz 2: The shortest path task I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.
The main idea of creating k-copies of a graph G is clear. What I'm really confused with is the final graph G':

Can you explain how the graph G' will look like?
How will the G' graph guarantee that all of the places {v0, v1, v2, vi} had been visited once we reached the destination vertex t?

I'm sorry if the community to post this question is wrong. Any suggestions are highly appreciated.
Input:

Solution:

Ok, I think here is how it should look like. You duplicate the graph G as many times as many v places you have to visit (e.g. v0, v1, v2). The order you must visit these vertices is the constraint which is expressed as zero weight edges (G1.v0 -> G2.v0, G2.v1 -> G3.v1).


What is the most efficient way to compute factorials modulo a prime? Do you know any algorithm that calculates the factorial after modulus efficiently?

For example, I want to program:

for(i=0; i<5; i++)
  sum += factorial(p-i) % p;

But, p is a big number (prime) for applying factorial directly $(p \leq 10^ 8)$.

In Python, this task is really easy, but i really want to know how to optimize.

(This answer was initially posted by the asker jonaprieto inside the question.)

I remember Wilson's theorem, and I noticed little things:

In the above program, it is better if I write:
$$\begin{align}
(p-1)! &\equiv -1 &\pmod p\\
(p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\
(p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)^{-1}} &\pmod p\\
(p-4)! &\equiv (p-3)! (p-3)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}} &\pmod p\\
\ (p-5)! &\equiv (p-4)! (p-4)^ {-1} \equiv \bf{(p-2)^{-1}} \bf{(p-3)^{-1}}\bf{(p-4)^{-1}}  &\pmod p\\
\end{align}$$

And you can find $(p-i)^{-1}$ because $\operatorname{gcd}(p, p-i) = 1$, so with the extended Euclidian algorithm you can find the value of $(p-i)^{-1}$, that is the inverse modulus.

You can view the same congruences too,  like to:
$$\begin{align*}
(p-5)! &\equiv (p-24)^{-1}&\pmod p\\
(p-4)! &\equiv (p+6)^{-1}&\pmod p\\
(p-3)! &\equiv (p-2)^{-1} &\pmod p\\
(p-2)! &\equiv 1&\pmod p\\
(p-1)! &\equiv -1&\pmod p\\
\end{align*}
$$
so, the sum is equal: $$ (-24)^{-1}+(6)^{-1} +(-2)^{-1}$$
and if you factorize in the beginning the factorials you get
$$ 8\cdot (-24)^{-1} \pmod p$$
And, voila, inverse modulus is more efficient than factorials.


If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T? In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.

There's no clear relationship, except that bigger inputs will tend to take longer.  What we call the "running time" in complexity theory is the number of basic operations but we just choose some set of basic operations and assume that they all have the same cost.  That's fine for asymptotic analysis but it doesn't correspond to the actual running time, as measured by a clock.

For example, imagine your algorithm consists of an initialization phase that takes one second, regardless of the input, plus a quadratic time loop that takes $n^2$ milliseconds to process $n$ items.  Complexity theory just says that your algorithm has running time $\Theta(n^2)$, so doubling the size of the input multiplies the running time by four.  Asymptotically, this is true but, if you double the input size from $10$ to $20$, the running time only changes from $1.1\,\mathrm{s}$ to $1.4\,\mathrm{s}$, which is nothing like a factor of four (it's less less than $30\%$).

Another problem is that complexity theory doesn't model the sheer... well, complexity of modern computers.  A simple example: suppose your quadratic algorithm runs in half a second on an input of length $\ell$.  Great, it's going to run in just over half a second on a similar input of length $\ell+1$, right? Maybe.  Or maybe it takes ten seconds because your data doesn't fit in the cache any more.


Find number of awesome substring of a given binary string A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it.

For example :111 has 6 awesome substrings.01010 has 10 awesome substrings .In "01010" one such awesome substring is "1010" because  "1010" is substring of "01010" and 4(length of substring) is divisible by 2(number of 1's).

source : codeforces

My attempt : I was not able to come with solution better than O($n^2$) , however when i read the editorial they have did some optimization and solved it in O($n*n^{1/2}$) but i didn't understood it completely.

What and why i want to ask : I want some simpler explanation of same solution , maybe illustrating it by taking few example(s) . I love these type of questions and i really want to improve myself.

source of solution/editorial : solution (scroll down a little) .

I am open to any suggestions and comments .

Could you please explain exactly where you were stuck? Anyway, I'll choose some parts of the solution which were not described by author and shed light on them.

You can assume that $T=\sqrt{n}$ in the solution. The main idea can be formulated as follows:

For any positive integers $m, n$ such that $m \le n$ either $m \le \sqrt{n}$ or $\frac{n}{m} < \sqrt{n}$.

This is applied to all substrings where $m$ is the number of ones. It means that we can divide all substrings into two disjoint sets: where the length divided by number of ones is small (set $k= \frac{len}{m}$, then $k \leq \frac{n}{m} < \sqrt{n}$), or the number of ones is small ($m \leq \sqrt{n}$). Then we compute sizes of each set separately. When we apply such idea, we hope that each of these subtasks can be solved faster than a big one.

For the first set, I find the idea of computing $t[i]=i-k\cdot{}pref[i]$ well-explained.

For the second set, if we fix $l$, we can break segments of $r$'s into segments $[r_m, r_{m+1})$ for which the number of ones in substring $s_l \ldots{} s_r$ equals $m$. We consider only $m\leq \sqrt{n}$, and for each $m$ the number of suitable $r$'s can be found in $O(1)$. Note: the set of such $r$'s forms an arithmetic progression with a common difference $m$.

And, if we iterate over $l$ in descending order, we can also make a "structure" for recomputing these segments in $O(1)$.


Shortest path in a mutable graph I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to $V + E$, where $V$ is the number of vertices and $E$ the number of edges. I have $V= N^2$ vertices in my graph. Now suppose I remove $N$ vertices (for now lets assume at random, in reality there is a pattern). If I want to find shortest paths for my new graph, is there any information from the first computation that I can cache to speed things up?

A simple approach

Given that you have a DAG, and the only change you will make is to delete vertices, there is a crude but simple to implement algorithm you could use.  In addition to computing the distance from $s$ to every vertex, also compute the shortest paths tree.

Now, when you want to delete a vertex $v$, mark the entire subtree rooted at $v$ (in the shortest path tree).  Delete this from the shortest path tree, and process each of the nodes in that subtree to re-calculate their distance from $s$.  You can process those vertices in topological sorted order, and compute the updated distance for vertex $x$ by the standard formula $d(x) = \min \{1+d(w) : (w,x) \in E\}$.  The running time will be proportional to the size of the subtree you deleted.  Whether this is efficient in practice will depend on the structure of the graph and the nodes that you delete.

More sophisticated solutions

This kind of problem has been studied extensively in the literature.  The keyword you want to use is "dynamic shortest paths".  Here dynamic refers to the fact that the graph can change.  In your case, you want to support vertex deletions.  So, I suggest you spend some quality time with the research literature to review the known algorithms for dynamic shortest paths with vertex deletions.  Alternatively, look for algorithms for dynamic shortest paths with edge deletions (since when you delete a vertex you're probably going to delete all edges incident on that vertex as well).

See, e.g., Retrieving the shortest path of a dynamic graph and How to approach Dynamic graph related problems and https://cstheory.stackexchange.com/q/17135/5038 and https://cstheory.stackexchange.com/q/11855/5038 for some entry points into the literature.  Those algorithms apply to arbitrary graphs, but it might be possible to exploit the fact that your graph is actually a DAG to get even better performance.


Doubt regarding Maximum Bipartite Matching I was given this question by a friend:

"You are given 3 sets of size n, X,Y and Z. Devise an algorithm to find maximum number of different pairings (u,v,w,x) such that u,v,w,x belong to X,Y,Z and X respectively (u is not equal to x) and gcd(u,v,w,x)>1."

My approach is to create new sets S and T, such that S contains pair (u,v) (create a node A) with gcd(u,v)>1 and T contains (w,x) with gcd(w,x)>1 (node B). If gcd(u,v,w,x)>1 add an edge between A and B. Now find maximum matching in this bipartite graph.

But he isn't satisfied and says I didn't use the gcd property and the problem can be reduced significantly. Can this algorithm be improved?

Here's one possible hint:

$$\gcd(u,v,w,x) = \gcd(\gcd(u,v),\gcd(w,x)).$$

I expect your problem can also be solved using the techniques in the following paper:

Daniel J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1--30.

A maximal matching doesn't seem like the right approach.  The maximal matching algorithm you list will never choose two 4-tuples $(u,v,w,x),(u',v',w',x')$ such that $(u,v)=(u',v')$.  Thus, it won't produce the correct answer to the problem: it won't output the maximum number of different 4-tuples.


An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries Is there an incremental directed graph data structure that has the following properties:

Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper data-structures)
The accessible DAG is kept as a transitive reduction (notwithstanding other helper data-structures)
It should be optimized for a sparse graph (adjacency lists)
It should condense cycles as they are introduced, keeps a mapping between equivalent vertices that are all replaced with one "representative" vertex
Ability to quickly answer quickly ancestor/descendant/transitive/relationship queries (in $\mathcal{O}(1)$ or $\sim\mathcal{O}\left(\log \left|V\right|\right)$ time)
Should support vertex, edge insertion, deletion would be nice too
Mutable operations  (such as insertion) should be as output-sensitive as possible; in other words, the complexity should depend as much as possible on how much the operation must change the graph
Ability to record changes over an operation, if requested. Obviously this might necessarily increase the complexity, but the increase should be output-sensitive. Examples:

set of deleted vertices (due to condensation)
set of deleted edges (due to reduction)
set of new decendent relationships from $u$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(u,t)\in G'\wedge path(u,t)\not\in G\right\}$ )
set of new ancestor relationships from $v$ ( example: $insert(G,u,v) \rightarrow \left\{t ~|~ path(t,v)\in G'\wedge path(t,v)\not\in G\right\}$ )

The closest I can find is here, implementation. I think you can build on this to do have most of the properties I list, but I am wondering if there is anything better/well known, or perhaps if there is a name for this problem.

EDIT:
Related:

What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?
What is the fastest deterministic algorithm for incremental DAG reachability?
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Is there an online-algorithm to keep track of components in a changing undirected graph?
Dynamic shortest path data structure for DAG

Some keywords to help you search for related work: dynamic transitive closure, dynamic reachability problem, dynamic cycle detection.  Because you want to allow both insertions and deletions, this is known as fully dynamic transitive closure.

Alternatively, you might want to consider whether there could be some structure in the particular graphs that arise in your setting that might help you build schemes that are faster than the general case.


Hash table open addressing without dummy If a hash table is using open addressing as the collision resolution strategy, then  during deletion, we mark that slot as dummy.
I understand the reason behind that is because while probing, a dummy would indicate there are still used slots further down the chain to search for.

But my question is that is there any way to implement open addressing without need for a dummy, and without degrading the algorithmic complexity of the hash table operations?

I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element.

So is there any correct algorithm for this?

EDIT

There is a small article on Wikipedia regarding this.
I'll copy the relevant text (the whole article) here:

  In computer science, lazy deletion refers to a method of deleting
  elements from a hash table that uses open addressing. In this method,
  deletions are done by marking an element as deleted, rather than
  erasing it entirely. Deleted locations are treated as empty when
  inserting and as occupied during a search.

  The problem with this scheme is that as the number of delete/insert
  operations increases, the cost of a successful search increases. To
  improve this, when an element is searched and found in the table, the
  element is relocated to the first location marked for deletion that
  was probed during the search. Instead of finding an element to
  relocate when the deletion occurs, the relocation occurs lazily during
  the next search.

But I dont get it. If we move another element to the deleted place, it will again leave a hole in its probe sequence. How is it logically correct?

PS: This is another question somewhat related to the first one, so I dont know if I should make it a separate question or not.

I came up with and algorithm of moving the last non-Null element of the probe sequence to the place of the deleted element to make the probe sequence contiguous. But this would make it impossible to retrieve the moved element if its hash index value was greater than that of the removed element.
So is there any correct algorithm for this?

Yes. There is a "shift deletion" scheme, that is described, for example, in this answer.
BTW, in the state of the art open-addressing hash table implementations, SwissTable and F14 "dummy" elements rather than "shift deletion" are used, but insertion of "dummy" elements (or "tombstone" or "deleted", as they are also called) is avoided very often in practice.


Computability of Kolmogorov Complexity of Turing-Incomplete language I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows:
$A;B \text{ - executes instructions A and B one after the other.}$
$!x_i! \text{ - sets variable } x_i \text{ to the value }2.$
$\{x_i\} \text{ - doubles the value of the variable }x_i$
$[x_i] \text{ - halves the value of the variable } x_i \text{ and rounds it up.}$
$"w" \text{ - prints the string } w \in \{a,b,...,z,A,B...,Z\}$
$\lambda(x_i,A) \text{ - executes instruction } A \text{ exactly } x_i \text{ times, regardless of later changes to } x_i$
Specifically, I need to know whether the Kolmogorov Complexity relative to this language is generally computable. The program which computes this complexity may be written in a Turing-Complete language.
I understand that for any Turing-Complete language, the Kolmogorov complexity is not computable. This language here does lack the ability to create an infinte loop, though, and as such is less than Turing-complete. I am not feeling any intuition arising from this observation though. I'd assume that, this language being weaker, the Kolmogorov complexity may be computable now. Yet I can not find a proof for this. Giving an algorithm that fulfills this task appears overly complicated. The use of this language seems like a special case of the more general computability of the Kolmogorov complexity and as such, I can't derive from the attributes of the general case if the general case is not computable. This may still be.
I am not finding any ground to stand on with this problem and would welcome any tips and pointers towards a solution. Can we deduce anything else from this language than what I have mentioned so far? Does it's lower power relative to Turing-complete languages help us with this situation?

The important thing to notice is that your programs always halt. This makes computing the Kolmogorov complexity an easy task, since given a string $w$, you can go over all possible programs of length $\le|w|+2$ to find the shortest program whose output is $w$. The upper bound $|w|+2$ follows from the fact that for any string $w$, "w" is a program whose output is $w$.
In fact, you could probably compute the complexity of a string in polynomial time, since compression is only possible in the case of repetitions (you can not take advantage of a more general structure). Something along the following lines should work $KC(w_1...w_n)=\min\limits_i \big(KC\left(w_{i+1}...w_n|w_i\right) +KC(w_1...w_i)\big)$, where $KC\left(w|w'\right)$ is just $KC(w)$ if $w'$ is not a prefix of $w$, and $KC(w'')+O(\log j)$ otherwise where $w=w'^jw''$ and $j$ is the maximal number satisfying this. The point is that you only need to compute the complexity of substrings of $w$, of which there are $O(|w|^2)$.


What does the "0 ≤ K < N-1" expression means? Given the following statement:

  "A nonempty array A consisting of N integers is given. Any integer K,
  such that 0 ≤ K < N-1, splits array A into two non-empty parts"

What does the 0 ≤ K < N-1 expression mean in this context?

You have an array with indices from $0$ to $N-1$. $K$ is an in integer in this range, i.e. larger or equal to zero and smaller than $N-1$.

This integer splits the array into two parts as follows:

Part 1: From $0$ to $K$ (including K)

Part 2: From $K$ (excluding K, i.e. starting with $K+1$) to $N-1$.

$K$ has to be smaller than $N-1$ (and not smaller or equal) because else there would only be one Part (the whole array) for $K= N-1$.


Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL I am trying to prove that the language $L=${$0^n 1^m |m ≤n^2$} is not a context free language. To do so I selected a string $w=0^p 1^{p^2}$. However, I am new to the CFL pumping lemma, and I am not sure if my proof is correct. Specifically, does the value of $i$ need to be the same for all divisions?

My first division is: v and y both contain 0’s.

$u=0^h$

$v=0^j$

$x=0^k$

$y=0^q$

$z=0^{-h-j-k-q} 1^{p^2}$

When $i=0$, I get $uv^0 xy^0 z=0^h 0^0j 0^k 0^0q 0^{p-h-j-k-q} 1^{p^2}=0^{p-j-q} 1^{p^2}$. This means $w$ contains less than p 0’s, but p2 1’s. This means for any valid value of p, there are more than p2 0’s. So this is not in the language.

The second division is either v or y contain both 0’s and 1’s. When $i=2$ I have $v=0^j 1^k$ or $y=0^j 1^k$, when $i=2$, so 0’s and 1’s out of order as the sequence $0^j 1^k$ will be repeated.

Finally the case that both v and y contain 1’s.

$u=0^p$

$v=1^j$

$x=1^k$

$y=1^q$

$z=1^{p^2-j-k-q}$

When $i=3$, the string becomes $uv^3 xy^3 z=0^p 1^3j 1^k 1^3q 1^{p^2-j-k-q}=0^p 1^{p^2+2j+2q}$.
This means s contains more than $p^2$ 1’s, but only p 0’s, so the string is not in the language.

What you have done up to now is correct. The idea is that you should prove that the 'pumping' fails for all possible partitions of $w$. You have considered just two families of partitions, namely, the one for which
$vxy\in0^+$ and the one for which $vxy\in1^+$.

You are missing the cases in which the sliding window (ie. $vxy$) crosses
the boundary between $0$ and $1$.

Hence, next step is to consider the following cases (here $|w|$ is
the length of $w$):

1) $vxy=0^{|vx|}0^h1^k$ where $h,k\geq 1$ and $h+k+|vx|\leq p$

2) $vxy=0^{|vx|}1^{|y|}$ where $|y|>0$ and $|vxy|\leq p$

3) $vxy=0^{|v|}0^h1^k1^{|y|}$ where $h+k=|x|>0$ and $|vxy|\leq p$

4) $vxy=0^{|v|}1^{|xy|}$ where $|v|>0$, $|xy|>0$ and $|vxy|\leq p$

All of the above cases can be easily solved with the technique you used with the former ones.


Any problem solved by a finite automaton is in P After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P.

I think its true, since automata recognize very simple languages, therefore all these languages would have polynomial algorithms to solve them. Thus, is it true that any problem solved by a finite automaton is in P?

Yes, it is true. In terms of complexity classes,
$$
\text{REG} \subseteq \text{P},
$$
where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). More specifically,
$$
\text{REG} \subseteq \text{DTIME}(n), \tag{*}
$$
and $\text{DTIME}(n)$ is a strict subset of $\text{P}$ by the time hierarchy theorem.

The proof of (*) is as follows: for any problem in $\text{REG}$, there is a DFA which solves it. Convert that DFA to a Turing machine with the same states and transition function, which always moves to the right until it sees a blank, and then accepts or rejects. This Turing machine always halts in time exactly $n$.

It's also worth mentioning that $$
\text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$$
for any fixed constant $k$.


How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)? I'm trying to make a simpler version of CARDIAC for only performing addition. Now, I am encountering several problems in making something similar and looking for some ideas (I'm new to Computer Architecture).

Here's an excerpt of what CARDIAC is (Wikipedia):

  CARDIAC (CARDboard Illustrative Aid to Computation) was a learning aid
  developed by David Hagelbarger and Saul Fingerman for Bell Telephone
  Laboratories in 1968 to teach high school students how computers work.
  The kit consisted of an instruction manual and a die-cut cardboard
  "computer".
           The computer "operated" by means of pencil and sliding cards. Any arithmetic was done in the head of the person operating the
  computer. The computer operated in base 10 and had 100 memory cells
  which could hold signed numbers from 0 to ±999. It had an instruction
  set of 10 instructions which allowed CARDIAC to add, subtract, test,
  shift, input, output and jump.

Basically it's a simple illustration of how a computer works internally to do basic stuff(as explained in the excerpt). I'm only trying to do addition but I am trying to find a way to show what the output is.
Here's how I thought it would be:
I would use a 16-bit register with binary base and 10 memory cells. I  guess this should be more than enough for a basic addition illustration.

Now my problem is, I'm not very sure how to output the values. Let's say for example, I input 10(binary for 2) in register R1 and 1(binary for 1) in register R2. Now this goes to the ALU, which calculates the addition immediately and places it in register R3. This would be represented using arrows and sliding cards(values for R1, R3 and R3) in specific slots on the illustration.

My problem is, now that I have the value in R3, how do I output it using that cardboard illustration? Also, does the ALU work as logic gates to calculate the sum?

You want to make a binary adder. You can make one out of boolean logic gates. Your register will be based on your binary adder. It is not a more simple computer than the CARDIAC computer, because the CARDIAC works with base ten and the beginner does the arithmetic by hand. Boolean logic is taught much later in school than addition in base ten.


Print all subsets of a set ($a$) of $n$ positive integers, such that the product of their elements equals $p$ I have the following problem:

  Given a set a of n positive integers, write a backtracking C function that prints out all the subsets of a such that the product of their elements is p. Use an array for implementation of the set. What is the time complexity?

I have already solved the problem, both the idea and the C code is given below. My questions are:

How do I calculate the time complexity of my solution?
Is there a better way to solve this problem?

My idea:

The function f takes a, n, p, and furthermore a variable idx for the current index in the array, and a boolean array subset which marks which elements in a are in the subset considered by this iteration of f.

First we iterate through subset and for each element in a currently in the subset, we multiply it by the product variable (initialized to 1).

If at any point during this iteration the product equals p we print out the elements in subset.

However if at any point the product becomes larger than p we return immediately. No further multiplication by positive integers could possibly bring the product down.

If the product is less than or equal to p after the iteration is done, we iterate through each of the elements in a, after and including idx, for each making a copy of subset, adding the element to it and calling the function recursively for the next idx and the copy of subset.

We have to do this even if the product is equal to p because I cannot assume the set is sorted; there may be a 1 down the road which would also give a result of p if added to the current subset.

What this means is that the function, called initially with an empty subset and idx of 0, will evaluate the possible subsets in the following order:

{}
{ 0 }
{ 0, 1 }
{ 0, 1, 2 }
..
{ 0, 1, 2 .. n-1 }
{ 0, 1, 2 .. n-1, n }
{ 0, 1, 2 .. n-2, n }
{ 0, 1, 2 .. n-3, n-1 }
{ 0, 1, 2 .. n-3, n-1, n }
{ 0, 1, 2 .. n-3, n }
{ 0, 1, 2 .. n-4, n-2 }
{ 0, 1, 2 .. n-4, n-2, n-1 }
{ 0, 1, 2 .. n-4, n-2, n-1, n }
{ 0, 1, 2 .. n-4, n-2, n }
{ 0, 1, 2 .. n-4, n-1 }
{ 0, 1, 2 .. n-4, n-1, n }
{ 0, 1, 2 .. n-4, n }
..
{ 0, 2 }
{ 0, 2, 3 }
..
{ 1 }
{ 1, 2 }
..

And so on, you get the picture.

Time complexity?

I found both my idea and code too tough for trying to deduce the time complexity from, so I the first thought was that the time complexity must be $O(2^n)$ because it goes through all the $2^n$ subsets.

However, it doesn't go through all of them. If it detects a subset s the product of whose elements exceeds p, it immediately rejects both s and all other subsets of a that also have the offending s as a subset.

Does this impact the big O class, and if so, how? A rule of thumb I could apply to similar problems would be preferable to me instead of (or in addition to) any hard-to-digest theory.

The code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

void
f(
    unsigned *a,
    int n,
    int idx,
    unsigned p,
    bool *subset
)
{
    unsigned product = 1;
    bool empty_subset = true;

    for(int i=0; i<n; i++) {
        if(subset[i] == true) {
            product *= a[i];
            empty_subset = false;
        }

        if(product > p)
            return;
    }

    if(product == p && !empty_subset) {
        for(int i=0; i<n; i++)
            if(subset[i])
                printf("%u, ",a[i]);
        printf("\n");
    }

    if(idx >= n) return;

    for(int i=idx; i<n; i++) {
        bool *newsubset = (bool*)malloc(sizeof(bool) * n);
        for(int j=0; j<n; j++)
            newsubset[j] = subset[j];

        newsubset[idx] = true;

        f(a, n, ++idx, p, newsubset);

        free(newsubset);
    }
}

Suppose the set is

$$a = \{2,3,6\} \cup \{5,7,35\} \cup \{11,13,143\} \cup \{17,19,323\} \cup \cdots \cup \{p_{2k-1},p_{2k},p_{2k-1}p_{2k}\}.$$

(Do you see the pattern?  It has $3k$ elements, composed of $k$ groups of three.  The $i$th group contains $p_{2i-1}$, the $2i-1$th prime, and $p_{2i}$, the $2i$-th prime, and their product.)

Also, suppose the product you want to hit is $p=p_1p_2 \cdots p_{2k}$.

Then this set has at least $2^k$ subsets that multiply to this value.  In particular, in each group, you can either pick the first two terms, or you can pick the third term.

So you'll need to output at least $2^k$ sets.  This means the running time on an input of size $3k$ can be as large as $2^k$.  Or, in other words, the running time on an input of size $n$ can be as large as $2^{n/3}$.  This is exponential in the length of the input.  Therefore, the worst-case running time is exponential. When we ask about the complexity, we usually implicitly mean the worst-case running time. Therefore, the complexity is exponential. Even though sometimes you might do much less work than that, sometimes you do fully exponential work, so we call the complexity exponential.

Unfortunately, I'm not aware of any simple rule of thumb that suffices for this case.  Sometimes you have to figure out what's going on, and that might require a more deep analysis.


How do you prove the Natarajan's Lemma intuitively? Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$.

Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive proof of the following lemma .

$|H|\le |X|^{Ndim(H)}\cdot k^{2Ndim(H)}$

The lemma is in the book "Understanding Machine Learning: from theory to algorithms". You just search keywords "Lemma 29.4".

You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.


difference between predictive modeling and clustering? What are the fundamental differences between predictive modeling and clustering? according to literature, predictive modeling is a supervised learning with aim to construct models to predict the value of target attribute. On the other hand, clustering is a unsupervised method to split a data set to a couple of groups.
In my idea, both of them are the same. when you are finding out the target attribute, you are actually trying to categorize it which is similar to clustering.
I know that in clustering, we make subgroups of available data while in predictive modeling we try to find a model to predict value of attribute of unseen data based on current available data.
Could anyone explain the differences between these two concept clearly?
Thanks

Predictive models are sometimes called learning with a teacher, whereas in clustering you're left completely alone.

Predictive models split data into training and testing subsample which is used for verifying computed model. Predictive (or regression) model typically assign weights to each attribute. From clustering you can compute some internal evaluation metric, but that doesn't necessarily correlate with (desired) human judgment. Unsupervised learning (clustering) mostly treats all attributes as equal as without external information, as one can't say which attribute is more important than the other.


How to find minimum number of k-input LUTs needed to express a n variable boolean function? An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to express a n variable boolean function.

For example : - n=8 and k=4 8 input variables are a0,a1...a7

1) f1(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6*a8 Requires 3 LUTs : LUT1 :a0*a1 + a3*a4 =x1 LUT2 :a5*a7 + a6*a8 =x2 LUT3 : x1+x2

2) f2(a0,a1,..a7)= a0*a1 +a3*a4 + a5*a7 + a6 Requires 2 LUTs : LUT1: a0*a1 +a3*a4 =x1 LUT2: x1+a5*a7+a6

NOTE: I want to solve this for the particular case of n=8 and k=4. Though, I would like to extend it to other cases like (n,k)= (8,2).

The following decision version of your problem is NP-complete:

  Given a formula $f$, an integer $k$, and an integer $s$ (encoded in unary), determine whether $f$ can be represented using at most $s$ many $k$-input LUT's.

Indeed, you can easily solve SAT by asking whether the instance of SAT can be represented using at most one 0-input LUT. If you disallow $k=0$, you need to work a bit harder: a formula $\phi$ is satisfiable iff $\phi \oplus x$ (where $x$ is a fresh variable) can be represented using at most one 1-input LUT.


Improve worst case time of depth first search on Euler graphs How to improve the worst case scenario for a depth first search on an Euler graph, starting at some point and ending at that same point?

I need to do the whole search but it is not fast enough for large amounts of data. I have tried bidirectional search but I can not keep the result numerically ordered. Therefore I wonder if there is any other good method to smooth the worst case scenario for the depth first search.

If I understand correctly, the only way to have a numerically ordered eulerian path would be having a path looking like 1,2,3..,n,1. All nodes in the path must have degree 2 (since you can only get into the once), except perhaps for nodes with degree 0, that you can instead skip.

If this is the case, the algorithm would just be a matter of testing if the 1,2,3..n path is eulerian, with no need to find eulerian paths with a traditional algorithm.


Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher? This post and this post indicate that when the dimensionality gets higher, KDTree gets slower.

Per scikit-learn doc, the KDTree becomes inefficient as D(dimensions) grows very large (say, $D>20$): this is one manifestation of the so-called “curse of dimensionality”.

Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?

The problem arises due to  curse of dimensionality.  If the dimensionality is $k$ , the number of points in the data, $N$ should be $N ≫ 2^k$. Otherwise, when $k-d$ trees are used with high-dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than brute force search. So for high value of $k$, approximate nearest-neighbour methods should be used instead.

  most of the points in the tree will be evaluated

When the dimensionality increases to high value, the volume of the space increases so fast that the available data become sparse.Organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. Hence $k-d$ trees become ineffiecient for high dimensions.


Issue with Multithreading spin locks a spin lock solution to the critical path problem is shown below . my question is will this or will this not  result in starvation ?

    Thread A                Thread B
leave note A;           leave note B;
while (note B) {\\X     if (noNote A) {\\Y
    do nothing;             if (noMilk) {
}                               buy milk;

if (noMilk) {                  }
    buy milk;           }
}                       remove note B;
remove note A;

let me illustrate my point ,if thread A and B are scheduled as shown wont that result in starvation ?

note : those arrows are meant to indicate a cycle .

note: I'm following the online operating system course from Berkeley (http://www.youtube.com/playlist?list=PL-XXv-cvA_iCrnl0625nXp4GimjT-cv_1) .

In lecture 4 ,they talk about this as a correct solution to the critical path problem

Process B isn't looping; it runs and then quits. In other words, there won't be a second "leave note B" in your picture. There is a loop in process A (a busy wait, as it's called) and when process B removes its note, then execution will return to A's loop: A will check and see that there is milk so will remove its note and quit.


Featurizing images of different dimensions I'm building a non linear svm for images to solve a classification problem with domain {0, 1} and I'm currently doing featurization. What I want to do is create 3 features for each pixel representing the rgb value. However, my input images have different dimensions meaning that they are of different widths and heights. So doing just this would result in images having a different number of featurizations.

For example: If i have one image of (10, 2) dimension {(width, height)} then it has 10 * 2 pixels, each with a rgb value. So there would be 10 * 2 * 3 features for this image. If i have a (11, 2) image, then it has 11 * 2 * 3 features.

I am ordering the pixels by first moving horizontally and then verticall. So if I have a (2, 2) dimension image then F1, F2, F3 would be the first three features of pixel (0, 0) wheras F10, F11, F12 would be the features of pixel (1, 1)

One way I thought about solving this is by just extending each image to the maxwidth and maxheight over all images, filling values with -1's for rgb pixels where the image has been extended. For example if i have and image of dimension (2, 2) and the max width and height is (3, 3), then the new image would be of dimension (3, 3) and the with new pixels (2, 2), (0, 2) (1, 2) (2, 0) (2, 1). All of these new pixels would have -1 for all rgb values.

However, will this affect my classifiers ability to recognize patterns? I'm planning on using a svm with radial kernal to start. Is there a better way to fix this?

Option 1: You can crop the images to the smallest sizes in all dimensions. However, blindly cropping images will cause you to lose important information, if you don't have a region of interest. For example, if you are focusing on faces, it is fine to define a ROI and crop around the face. On the other hand, for example if you are doing pure color-wise comparison of images, you will not know if you are cropping all red pixels from an image, that actually contain valuable information.

Option 2: You can scale them to the largest sizes in all dimensions. However, blindly resizing images might cause you to lose important structural information. For example, if you are doing color-wise comparison, you can upsample the images and the mean of the pixels will not change much. On the other hand, for example  if you are looking for faces in an image, your faces will not be circular but elliptical.

Option 3: You can extend the images to the largest sizes in all dimensions. This introduces additional information if you don't filter it in the following steps. For example, for color comparison, you can fill with value nan and later neglect features which has value nan. You can fill with nan, or -1, or mean, etc.

Option 4: You can define a window to process the images. Imagine that you have an n*n window (say 3*3), and you slide that window on the image and extract features from each window (F1 is from [1:3,1:3] of the image, F2 is from [2:4,1:3] of the image, ...). Thus, the features are independent of the image size. However in this case you need to have a clever way to combine those features, because you will have different number of features from each image.


Term-rewriting software recommendation Is there an easy to use software that implements term-rewriting? Or do I need to write my own parser for it?
I am looking for something that will take in a fixed set of user-specified rules and will be able to reduce arbitrary terms under those rules. Is there a standard tool for doing such rewrites?

PLT Redex has support for term rewriting. You'll find that most of the examples are focused on small-step operational semantics for programming languages, but in general the system allows for arbitrary rewriting, including non-determinism. It also has a bunch of nice features, like randomized testing of properties, alpha-equivalence, steppers for visualising/debugging, and excellent graphical output.
If you want higher-order syntax, you might be interested in something like ELPI.
For a super-lightweight prolog-style programming, you might be interested in miniKanren.


Is this a Context Free Language? I got this question on my final exam: Is the following language context-free?

$$ L = \{w\bar w^R \mid  w\in \{0,1\}^*   \}$$

Notation:
The string $\bar w$  is obtained from $w$ by replacing all 0s with 1's and all 1's with 0's.  The string $\bar w^R$ is $\bar w$ in reverse order.

  I've thought about it being a context-free language, but I notice that
  when you pump the string in the middle, the string will still be in the
  language. (using pumping lemma)

I think it's context free.
This is the context free grammar:

$$
S \to 0S1 \mid  1S0 \mid \varepsilon $$
(It's basically a palindrome, but both sides are exact opposites.)

A Context free grammer is one in which LHS of atleast one of the productions is free from any terminal symbols (context).
According to your production rule,it is clearly CFG.


Does Provable P equal Provable NP? My question is a very basic one. It seems feasible to believe that $\mathsf{P = NP}$, because there is some "pathological" good algorithm for SAT, yet it is impossible to prove that the algorithm is actually correct and/or that it runs in polynomial time, in a standard axiomatic system like ZFC.

Let's fix a logic $L$ that is strong enough to encode statements about Turing machines. (Edit: I should have clarified that by this I mean the same requirements as Godel's second incompleteness theorem. For the purposes of this question, assume that $L$ proves the peano axioms PA.)

Then define
\begin{align*}
\mathsf{ProvableP} &:= \{A \mid L \text{ proves } [A \in P]\} \\
\mathsf{ProvableNP} &:= \{A \mid L \text{ proves } [A \in NP] \}
\end{align*}

Now we have that $\mathsf{ProvableP} \subseteq \mathsf{ProvableNP} \subseteq \mathsf{NP}$. But does $\mathsf{ProvableP} = \mathsf{ProvableNP}$? How does this relate to the original P vs NP question?

Partial answer: The SAT problem is $\mathsf{ProvableNP}$-complete, but $\mathsf{ProvableNP}$ is closed only under provably polynomial-time reductions, not necessarily all polynomial-time reductions. However, this does seem to show that if $\mathsf{ProvableP} = \mathsf{ProvableNP}$, then since SAT is in $\mathsf{ProvableNP}$, $\mathsf{P} = \mathsf{NP}$.

So what is remaining is the converse: if $\mathsf{P} = \mathsf{NP}$, does $\mathsf{ProvableP} = \mathsf{ProvableNP}$?

I picked the P vs. NP question because it's the "canonical" unsolved problem in complexity. But, a similar question could be asked about any two complexity classes.

You need to define $L$ carefully. Currently, you seem to require only these properties:

"$L$ proves $[A \in \mathsf{P}]$" implies $A \in \mathsf{P}$
"$L$ proves $[A \in \mathsf{NP}]$" implies $A \in \mathsf{NP}$
"$L$ proves $[\mathrm{SAT} \in \mathsf{NP}]$"

Let $L$ be such that it ever proves only these two statements:

$[\mathrm{ONE} \in \mathsf{P}]$, where $\mathrm{ONE}$ is a dummy problem like "always accept", which is clearly in $\mathsf{P}$.
$[\mathrm{SAT} \in \mathsf{NP}]$

Then $\mathsf{ProvableP} = \{\mathrm{ONE}\}$ and $\mathsf{ProvableNP} = \{\mathrm{SAT}\}$, which are different even if $\mathsf{P}=\mathsf{NP}$. Note also that $\mathsf{ProvableP} \nsubseteq \mathsf{ProvableNP}$.


Why isn't the Generalized Super Mario Bros. obviously in NP? It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) video game is NP-hard.

  Theorem 3.1. It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros.

(When generalizing the original Super Mario Bros., we assume that the screen size covers the entire level, because the game forbids Mario from going left of the screen.)

However, it does not claim that SMB is in NP.

My problem: Why isn't SMB obviously in NP?

I came up with two reasons.

First, the solution/certificate to SMB may be not of polynomial size, due to e.g., timing. Is this valid? If so, how to argue this point more formally?
Second, the computer can be treated as a second player. Thus, SMB is a two-player game, which may be reasonably harder. However, are the actions of the computer player determined from the beginning of the game so that we can still regard SMB as a single-player game?

Related posts:

What is the whole picture of the NP-hardness proof of Super Mario Bros?
Why are Chess, Mario, and Go not NP-complete?

Added: A follow-up paper also by Erik Demaine (et al.) which shows that a generalized level of SMB is PSPACE-complete.

One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify the portion of the video game that is nessecary for their reduction framework.

Another aspect is that a priori I would see no reason that e.g. Donkey Country would be PSPACE-hard (which the paper shows), but SMB not. Sure, likely the framework from the paper cannot be used directly to show SMB is PSPACE-hard, but that doesn't mean it isn't possible. So, it doesn't seem obvious to me why SMB is not PSPACE-hard, from which it follows that it isn't obvious that it lies in NP. (as long as you don't think it is obvious that PSPACE$\neq$NP, at least)

As for your specific reasons why SMB might not be in NP, the fact that other games are PSPACE-hard seems a good argument why a polynomial certificate may not exist. However, proving that there indeed cannot be a polynomial size certificate would be the same as proving PSPACE$\neq$NP, so there are no known techniques to do that.

The second reason is related to the reason why the other games are PSPACE-hard. In general, solving two-player games can be done by reasoning "If P1 makes this move in turn 1, then for all moves P2 can do, pick a move for P2 s.t. $\ldots\ldots$ at the final move, P1 wins". This is the same as determining whether there is a satisfying assignment to a boolean formula with alternating universal and existential quantifiers: the true Quantified Boolean Formula problem (QBF). QBF is a PSPACE-complete problem.

This means that a 2-player game is PSPACE-hard if the above strategy of essentially going over all the moves is the only strategy to be guaranteed to win. The strategy of the 'computer' is of course limited in being only a simple function of the current state, but such a limited strategy can apparently be enough, as in the other games that are shown to be PSPACE-hard.

One question that may rise is why it is obvious that the problems lie in PSPACE. The authors cover this on page 2, but I will rephrase their argument here for the sake of completeness. Their main assumption is that the size required to describe the internal game state is polynomial in the input size. Their (somewhat informal) argument for this is that state changes of the game must controlled by a 'simple' and deterministic function of the player input. From the assumption it follows that we can solve a game reachability problem by making moves nondeterministically while maintaining the current game state. This means that the problem is in NPSPACE, and therefore in PSPACE as PSPACE=NPSPACE.


Output cycle found by DFS We can use DFS to find a cycle in a given graph. The idea is that a cycle exists if we can find back edge in the graph. First I just want to detect if a cycle exists, if so return true else false. Here is what I have got so far:

DFS(G,s)
  for all v in V do
    color[v] <- white; parent[v] <- nil
  end for
  DFS-Visit(s)

G is the given graph and s is the starting node.

DFS-Visit(u)
  color[u] <- gray
  for all v in Ajd[u] do
    if color[v] = gray then
       return true // found cycle
    if color[v] = white AND DFS-Visit(v) then
       return true // found cycle rooted in v
  end for
  color[u] <- black
  return false // no cycle found

Ajd[u] is the list of u's neighbours. So by processing the children of u we might discover a node that is marked gray. If so u and v are connected with a back edge and we found a cycle.

Now I want to extend this algorithm to output the found cycle. Any ideas on how to do that? I thought about using a stack and simply push all u's in DFS-Visit onto the stack. When true is returned I can output the cycle by taking the nodes from the stack. What do you think?

Using a stack won't solve my problem, because the stack will contain nodes that are not part of the cycle.

I have another idea. When we found a cycle we know v=u. To print the cycle we have to go back using the parent list until we reach u:

DFS-Visit(u)

  color[u] <- gray
  foundCycle <- false
  vv <- nil

  for all v in Ajd[u] do
    if color[v] = gray then
       vv <- v
       foundCycle <- true // found cycle
       break
    if color[v] = white then
       parent[v] <- u
       DFS-Visit(v)
  end for
  color[u] <- black

  if foundCylce then
      printCycle(vv, u)

printCycle(v,u)
  if v=u then
     print v
  else
     print v
     printCycle(parent[v], u)

When true is returned I can output the cycle by taking the nodes from the stack.

The stack contains the nodes you still have to visit, so they can not be part of the cycle.

There are at least two options to actually obtain data from a DFS.

Create the DFS tree explicitly; this gives you full information.
If you only want one cycle, you can store a pointer to the visited node's parent (the tree edge) instead of labelling it gray.


How to find 5 repeated values in O(n) time? Suppose you have an array of size $n \geq 6$ containing integers from $1$ to $n − 5$, inclusive, with exactly five repeated. I need to propose an algorithm that can find the repeated numbers in $O(n)$ time. I cannot, for the life of me, think of anything. I think sorting, at best, would be $O(n\log n)$? Then traversing the array would be $O(n)$, resulting in $O(n^2\log n)$. However, I'm not really sure if sorting would be necessary as I've seen some tricky stuff with linked list, queues, stacks, etc.

The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:

Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\sigma_d = \sum_{i=1}^n A[i]^d$.
Compute $\tau_d = \sigma_d - \sum_{i=1}^{n-5} i^d$ (you can use the well-known formulas to compute the latter sum in $O(1)$). Note that $\tau_d = m_1^d + \cdots + m_5^d$, where $m_1,\ldots,m_5$ are the repeated numbers.
Compute the polynomial $P(t) = (t-m_1)\cdots(t-m_5)$. The coefficients of this polynomial are symmetric functions of $m_1,\ldots,m_5$ which can be computed from $\tau_1,\ldots,\tau_5$ in $O(1)$.
Find all roots of the polynomial $P(t)$ by trying all $n-5$ possibilities.

This algorithm assumes the RAM machine model, in which basic arithmetic operations on $O(\log n)$-bit words take $O(1)$ time.

Another way to formulate this solution is along the following lines:

Calculate $x_1 = \sum_{i=1}^n A[i]$, and deduce $y_1 = m_1 + \cdots + m_5$ using the formula $y_1 = x_1 - \sum_{i=1}^{n-5} i$.
Calculate $x_2 = \sum_{1 \leq i < j \leq} A[i] A[j]$ in $O(n)$ using the formula
$$
x_2 = (A[1]) A[2] + (A[1] + A[2]) A[3] + (A[1] + A[2] + A[3]) A[4] + \cdots + (A[1] + \cdots + A[n-1]) A[n].
$$
Deduce $y_2 = \sum_{1 \leq i < j \leq 5} m_i m_j$ using the formula
$$
y_2 = x_2 - \sum_{1 \leq i < j \leq n-5} ij - \left(\sum_{i=1}^{n-5} i\right) y_1.
$$
Calculate $x_3,x_4,x_5$ and deduce $y_3,y_4,y_5$ along similar lines.
The values of $y_1,\ldots,y_5$ are (up to sign) the coefficients of the polynomial $P(t)$ from the preceding solution.

This solution shows that if we replace 5 by $d$, then we get (I believe) a $O(d^2n)$ algorithm using $O(d^2)$ space, which performs $O(dn)$ arithmetic operations on integers of bit-length $O(d\log n)$, keeping at most $O(d)$ of these at any given time. (This requires careful analysis of the multiplications we perform, most of which involve one operand of length only $O(\log n)$.) It is conceivable that this can be improved to $O(dn)$ time and $O(d)$ space using modular arithmetic.


Length of an Edit Script and the Number of Deletions I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller.  The algorithm sounds like a good fit for a project I'm doing at work.  I have found some implementations in my target language that I could reuse, but I want to make sure that I understand the algorithm (and the code) because it is so crucial to my project.

I am a ways into the paper, and seem to be understanding it, but there's something important in the abstract that still doesn't make sense to me.  This is the relevant portion:

  Let $A$ and $B$ be two sequences of length $M$ and $N$ respectively, where without loss of generality $N \ge M$, and let $D$ be the length of a shortest edit script between them.  A parameter related to $D$ is the number of deletions in such a script, $P = D/2 - (N - M)/2$. We present an algorithm...

This relationship between $P$, $D$, $N$, and $M$ is not proven in the paper.  And when a try using it with a simple example (turning "xy" into "x", for instance), I get a nonsensical answer.  Can someone please explain the relationship?

This is a straightforward consequence of the fact that the edit script only contains insert and delete operations.  It follows from a little bit of basic arithmetic -- it's nothing especially deep.

Consider a script that contains $I$ insert operations and $P$ delete operations.  Then the total number of operations in the edit script is $I+P$.  If we're given that the total number of operations is $D$, we know $D=I+P$.  Also we know $M+I-P=N$ (since each insert operation increases the length of the document, and each delete decreases it).  Solving these two simultaneous equations yields the relationship you list.


Coordinates of the center and the radius of the circle on the image What is the simplest possible way to calculate the coordinates of the center and the radius of the circle on the image (for example BMP and I'm interested in image of the Sun included below)?

If you want to automate the process I would use Hough Circle Transform.  It is an algorithm used to detect circles in an image. This Wiki article will describe Hough Transform better than I can.

You can manually find the center of a circle using these methods.


A heap based problem I have been struggling with this question from my problem set. I do not want a solution but some hints on how to proceed.

  You are given a file of numbers which represent the values of associated with
  certain chemical reactions for the past year from a large scale industrial laboratory (reactions
   can happen on the millisecond scale, so this file is very large). Let $n$
  represent the number of values in the file. For some fixed $k$, devise
  a $\mathcal{O}(n \log k)$ time algorithm for finding the highest $k$
  reactions that occur in the file.

$\textbf{My approach:}$ I reasoned that I should build a max-heap and exploit the get-max() queries and save the $k$ highest values to an array. The time complexity to build a heap is $\mathcal{O}(n)$ and here mentions the extract-max query is $\mathcal{O}(\log n)$ so this operation would run in $\mathcal{O}(n\log n)$ time and not $\mathcal{O}(n\log k)$? Also, I'm not sure why extract-max runs in $\mathcal{O}(\log n)$ time?

You don't need to put all numbers encountered in the heap. Never let your heap grow in size more than $k$. Keep a min heap. Now, if at some point of time heap has size $ < k$, then push the number encountered ( say $i$ ) into the heap. If heap is full and the number $i$ is greater than top element of heap ( say $top$ ) , pop the $top$ and insert $i$ into heap. At the end all the numbers in the heap are your desired $k$ numbers. Each operation takes $O(logk)$ steps ( as heap size is always $ \le k$ ). And there are $n$ steps so $O(nlogk)$.


Applying a 1-qubit gate to entangled qubits Given two entangled qubits in the state ${|00⟩+|11⟩\over \root \of 2}$, I have trouble getting the way of applying a 1-qubit gate (let's say a Hadamard) to 1 of the entangled qubits (let's say the first one). Actually I have several questions:

Following this link, Ran G. says that "You can apply a quantum gate on any subset of the qubits."
On the other, hand Agent Gotse says here that "You can not compute the Hadamard gate on only one qubit, as the state is entangled and cannot be factored into two independent qubits."
Do the answers contradict themself?
I understand part of the principle of the entangled pair, it a superposition of bipartite system. But given for example an entangled pair $|00⟩+|11⟩ = |0⟩ \otimes |0⟩ + |1⟩ \otimes |1⟩$, and two unitary operators $A\ B$ to appy to the system.
Why can't we juste do $A|0⟩ \otimes B|0⟩ + A|1⟩ \otimes B|1⟩$?
I mean what is the mathematical meaning of that?
Finally, the superdense coding use an entangled pair, and in the procedure given in the link, Alice apply some operator to her qubit without changing Bob's one (because it's probably far far away...). Quantum Computing textbooks say that in the case of an entangled pair, Alice has to apply $U \otimes I$, with $U$ the chosing operator.
But Alice has only 1 qubit, and clearly $U \otimes\ I$ acts on 2 qubits (it's a $4*4$ matrix), how it's works physically?

I think you're confusing people talking about what must be done theoretically (to compute operations on qubits on paper) with people talking about what must be done experimentally (to operate on qubits in the real world).

  Do the answers contradict themself?

No. The person who appeared to be saying "you can't apply the operation" just meant that the algebra you do to apply the operation won't start by factoring the state. When doing algebra you can't apply the operation in the simple way that you'd use when the qubits factor.

  Why can't we just do $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$?

You can! $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$ is equivalent to $(A \otimes B) (|00\rangle + |11\rangle)$. To apply a Hadamard operation to one qubit while leaving the other alone, set $A=H$ and $B=I$.

  Alice has only 1 qubit, but U⊗I acts on 2 qubits. How does it work physically?

Alice just does whatever she would do to apply $U$ to her single qubit. That applies the operation $U \otimes I$ to the system of two qubits.


Is huffman-encoding with distinct frequencies of symbols unique? Say I have following text: "abbcccddddeeeee".
As you can see, each letter has a different frequency of occurence.
When making a Huffman-Trie to encode this String, will this trie be unique?

I thought a bit on the problem and I can't come to a definite conclusion, but I think the trie will NOT be unique. Say the begin-situation:

a(1) b(2) c(3) d(4) e(5)

To make a trie, we take the lowest frequencies together and make a node above it with the sum of those frequencies. Because the frequencies are all ascending, there is only 1 way to take the lowest nodes. In this case, a and b. If we keep going on further, it wel never occur that we need to choose 2 subtries out of a larger collection, there will always be just 2. When seeing this, you could conclude the trie will be unique BUT. I see never stated in which order the two subtries need to be added. For example, to make the first new subtrie, we can put node a left OR right of node B. We can do this at each level and eventually, this will flip some bits in the end-result.

Am I correct?

2 3 4 5 is a counterexample:

4 5 5 (combine 2 and 3 to make 5, and reorder)

Now there are 2 choices for 4 to partner with: either the original 5, or the one formed by 2+3.


Prove that $L^r$ is context free without alphabet I'm stuck with this problem:

Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$  is context free or not.

Since I don't have the alphabet I cannot think of a grammar that generates this language, so I decided to prove that it's not context free by applying the pumping lemma for CFL. So I started with the hypothesis that $L^r$ is context free, thus if $x\in L^r$ that $x^r\in L$.

Then I tried to find different possible strings that once pumped didn't belong anymore to $L^r$, but I'm not able to find such string.

Is this a bad aproach? Where am I wrong?

Informally, by construction $L^r$ consists of the strings in $L$ reversed. Since $L$ is context-free, it has a Grammar in Chomsky normal form. All production rules in this grammar will fall in one of three classes:

$A \rightarrow BC$
$A \rightarrow a$
$S \rightarrow ε$

Thus by reversing the order of non-terminals in the RHS of all rules of category 1., a new grammar can be derived that produces $L^r$.

This new grammar is also in Chomsky normal form, thus $L^r$ is context-free.


How to calculate least common multiple (LCM) for two numbers with constants (shifts)? What's the most effective algorithm to calculate LCM for 2 numbers where each of them has their own "shift"?

Example:

We want to find LCM for 25 + 5 as c and 30 + 10 as c
Then for the first case, the sequence will look like this:

25*1+5, 25*2+5, 25*3+5, 25*4+5...

And the second one:

30*1+10, 30*2+10, 30*3+10, 30*4+10...

In this case, the result should be 130 - 5th member of the first sequence and 4th of the second one.

Given integers $a,b \geq 1$ and $c,d \geq 0$, you are looking for the set of solutions of $ax + c = by + d$ over integers $x,y \geq 0$. We can assume without loss of generality that $d = 0$ (replace $c,d$ with $c-d,0$ or $0,d-c$) and that $(a,b,c) = 1$ (otherwise, divide everything by the GCD).

I claim that if there is any solution then necessarily $(a,b) = 1$. Indeed, suppose that $(a,b) = g > 1$. If $ax + c = by$ then $g \mid ax,by$ implies $g \mid c$, and so $(a,b,c) = g > 1$, contrary to assumption. Therefore $(a,b) = 1$.

If $ax + c = by$ then $ax + c \equiv 0 \pmod{b}$ and so $x \equiv -c/a \pmod{b}$ (note that we can divide by $a$ since $(a,b)=1$). Similarly, $y \equiv c/b \pmod{a}$. These equations essentially give us both the minimal solution and all solutions.

As a demonstration, consider your example: $30x+10 = 25y+5$. This is equivalent to $6x+1 = 5y$, so $(a,b,c) = (6,5,1)$. Any solution must satisfy $x \equiv -1/6 \equiv 4 \pmod{5}$ and $y \equiv 1/5 \equiv 5 \pmod{6}$. Indeed, $6 \cdot 4 + 1 = 5 \cdot 5$. The general solution is $(x,y) = (4+5N,5+6N)$.


What are the known ambiguities in C language grammar? I have found this reference for the C syntax Backus-Naur Form (BNF). I was wondering if there are any other ambiguities in this grammar other than the infamous "dangling else"? Also how we can modify the BNF grammar to avoid those ambiguities, including the known one mentioned above?

Not sure if this answers your question, but I will contribute two details regarding lexing/parsing ambiguities in C in general. I hope these are still helpful.
Consider the expression T ** c;. Since C supports type declarations via typedef, the parser itself cannot decide whether this is multiplication with variables T and *c or a variable declaration of a pointer to pointer c of type T**. We'll need information fed into the parser by the lexer to decide which situation we're parsing (the lexer will resolve each valid type name to a type).
Another situation similar to the situation above gives rise to an ambiguity in the C syntax: In general, statements like a +++ b are ambiguous, since both (a++) + b and a + (++b) are valid. In this kind of situation, the C compiler follows the "longest match" rule: the compiler will match against the longest sequence of characters it can match.


Difference between multimethods and overloading Context

I've been programming in java for a few years now. And atm i'm learning something totally different: Clojure.
There the expression problem can be solved by using multimethods whereas in java you will need something like the visitor pattern or something alike.

The question

I've been reading about multimethods and got quite confused with the actual difference with method overloading.

The only difference I spotted so far that a multimethod doesn't depend on the runtime type of the object on which the method is called.

Overloading is when two or more methods have the same name but different signature (different argument types, different number of arguments). Overloading is resolved statically, depending only on the static types of the arguments. (The interaction of overloading and overriding, in Java, for example, makes the story a little more complicated). Overloading resolves statically to a particular method signature. Then at runtime, dynamic dispatch will select the most appropriate method with that signature.

Multimethods are a collection of methods that have the same name, the same number of arguments, and overlapping type signatures. Whenever a call is made to a multimethod (using the name of the multimethod), all of the methods in the collection is considered as a possible candidate for dispatch. The precise candidate is chosen depending on the runtime types of the arguments – the most specific method is selected. The actual runtime types of all arguments are used to determine which one to run, which differs from traditional single dispatch in Java, where only the first argument (the target) of the method is used to determine which method body is run.


Showing the following language is decidable Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.

Generally such questions seem to be solved by constructing a DFA that accepts all strings that have equal number of 0's and 1's and then constructing a DFA that accepts the intersection of the one we constructed and M. Then we can run $E_{DFA}$ to check. Here we can't construct a DFA that accepts $0^n1^n$ as it is not regular, but we could construct a PDA. I think Sipser's book gives a way. But intersection of two PDA's need not necessarily be a PDA. Also we don;t have anything like $E_{PDA}$ which is decidable. I am not aware. How could we solve this. I know this is a solved excercise in Sipser, but I want to understand how one could approach such questions.

You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.

So. We have some DFA $M$, and we can build a PDA $N$ which recognizes the language $\{w : \#_0(w) = \#_1(w)\}$, where $\#_a(w)$ denotes the number of occurrences of the symbol $a$ in the string $w$ (note this is not the same as $\{0^n 1^n : n \geq 0\}$). Then $L(M) \cap L(N)$ is context-free. Checking if $M$ accepts a balanced string amounts to checking if $L(M) \cap L(N)$ is the empty language. But it's known that emptiness of context-free languages is decidable. Given $M$, we can easily construct the machine which recognizes $L(M) \cap L(N)$ and check if $L(M) \cap L(N)$ is empty. So your problem is decidable!


Random uniform sampling of position restricted permutations Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions?

Consider $N \times N$ restriction matrices $R$, that is matrices over $\{0,1\}$. Each such $R$ defines a set of permutations $\Pi_R$ according to

$\qquad\displaystyle \pi \in \Pi_R \iff \forall i \in [1..n].\ \pi(i) = j \implies R_{i,j} = 1$.

Note that $R$ is not permutation matrix but a general restriction matrix.
I want to sample uniformly from $\Pi_R$ given $R$.

So far I am using Hungarian's assignment algorithm to produce random permutations consistent with restriction matrix $R$, but these permutations are significantly non-uniformly sampled.

Examples:

Every $R$ that has one one per row and column admits only a single permutation.
For

$\qquad\displaystyle R = \left( \begin{array}{ccc}
0 & 1 & 0 \\
1 & 1 & 1 \\
1 & 1 & 1 \end{array} \right) $

there are only two permutations:
$\pi_1 = (2 1 3)$ and $\pi_2 = (2 3 1)$.
If $R$ contains only ones, $\Pi_R$ is the set of all permutations.

I'll answer both the question as it currently stands, and the original version of the question.

The current question

Your question is basically asking for a way to sample uniformly at random from the set of perfect matchings of a given bipartite graph.  In particular, we have $N$ nodes on the left side corresponding to the $N$ rows of $R$, and $N$ nodes on the right side corresponding to the $N$ columns of $R$.  Draw an edge between node $i$ (on the left) and node $j$ (on the right) when $R_{i,j}=1$.  This gives a bipartite graph $G$.  Now there's a bijection between the perfect matchings of $G$ and the permutations in $\Pi_R$, so we want to sample uniformly at random from the perfect matchings of $G$.

The following question refers to algorithm for exactly that problem: Sampling perfect matching uniformly at random.  In particular, there are existing algorithms that approximate sampling from the uniform distribution (i.e., their distribution is almost uniform).

The original question

Originally, the question imposed the stronger restriction that $\pi(i)=j \Longleftrightarrow R_{i,j}=1$.  Here's the solution to that version of the problem.

Theorem. If $R$ is a permutation matrix, there is a single permutation $\pi$ that is compatible with $R$.  If $R$ is not a permutation matrix, there is no permutation $\pi$ that is compatible with $R$.

Recall that a permutation matrix is a matrix that has exactly one 1 in every row and every column.

Proof of theorem. Consider any row, say row $i$.  If it is all zeros (has no $1$), then there's no matching permutation ($\pi(i)$ has to equal something).  If it has two or more $1$'s, there is no matching permutation (you can't have $\pi(i)=j$ and $\pi(i)=k$ where $j\ne k$).  So for there to be a matching permutation, the row must have exactly one $1$.  Since the row $i$ was arbitrary, this must be true of all rows.  By symmetric, the same is true for all columns.  QED.

You can easily recognize whether a matrix is a permutation matrix or not.  Given a permutation matrix you can easily recover the corresponding permutation.  Therefore, an algorithm to do what you want is trivial.  The algorithm either outputs nothing (if $R$ is not a permutation matrix) or always deterministically outputs a single permutation (if $R$ is a permutation matrix).

For the example $3 \times 3$ matrix you gave in your question, there is no permutation that is consistent with that matrix.  Your matrix has $R_{2,1}=1$ and $R_{2,2}=1$.  By your conditions, this implies the requirements that $\pi(2)=1$ and $\pi(2)=2$.  However, $1\ne 2$, so it is impossible to have a permutation $\pi$ that satisfies both of these requirements.


Rank operation in search tree, number of nodes between 2 values What kind of search tree should I use in which I will have operation Rank[x, y] which will return number of existing nodes/values between x and y in time O(depth of tree) so the operations find, insert and delete will have also time complexity O(depth of tree)?
I was thinking about a-b tree, which has find, insert and delete in O(log n), but I do not know how should I implement the rank operation. I was thinking to add each value in node information about number of its children but it wont be in O(log n) time.

Use an AVL tree $T$ that is augmented so that each vertex $v$ also stores the number of vertices in the subtree of $T$ rooted at $v$.
Given two vertices $u$ and $v$ of the tree you can find the number of values between $u$'s and $v$'s key by summing the sizes of at most $O(\log n)$ subtrees of $T$ dangling from the (unique) path from $u$ to $v$ in $T$.
These are exactly the highlighted trees/vertices in this answer, which also gives you a $O(\log n)$-time algorithm to find them.
The time complexities of insertions, deletions, and searches are asymptotically unaffected (i.e., they are in $O(\log n)$).


On a semiconductor chip, what state (on/off or read/write) corresponds to conducting or insulating behavior? My textbook has a brief explanation of how semiconductors are used in modern computer chips because they can be made to conduct (by applying enough voltage to excite electrons across the band gap) or to insulate (by dropping the voltage to a lower level or shutting it off entirely) and this conditional, binary state can be used as an 'on/off' logic gate.

In modern computer systems, which state is "on" and which is "off"? In other words, is it the case that when we increase the voltage to cause conductance in the semiconductor that we have a "1" value and that when we drop the voltage down, we have a "0" value, or is it the other way around?

Or is it more appropriate to say "read" vs "write"?

Does the on/off or read/write state vary from one manufacturer to another? Or from one type of memory to another? I.e. does DDR SDRAM use conducting as "on" and insulating as "off" while other forms do it the other way around?

P.S. If comp sci isn't the right SE, please could you advise a better SE for this question?

In order to understand how physical background of the computers works, you should consider higher-level abstractions of the semiconductors. Otherwise, you will get stuck in a mess of semiconductors. Without basic knowledge of transistors and how these transistors form a logic gate, it will not be easy to comprehend the memory structures and read/write cycles.

To visualize, in CMOS technology, there are two complementary logic structures where one of them is connected to the ground and the other one is connnected to the high voltage source. In rest, these structures are "on" and "off" complementarily. When your output changes, on-off states of them are inverted, thus there are both 'on' and 'off' logic in every case. The scheme is completely different in another technology, let's say PTL.

In the memory case, 'HIGH' and 'LOW' voltages represent immediate memory state rather than individual 'conducting' and 'insulating' states of transistors. If a transistor between low voltage source and your memory output is 'conducting' while a transistor between high voltage source and your memory node is 'insulating', then you have a 'logic 0'. Still, all of them are technology dependent.


Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2? I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether
$$AB = C$$
and be correct with high probability.

The algorithm  choose a random $r$ n-bit vector and if
$$A(Br) = Cr$$
then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr[error] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)_{i} = d_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v_i = \tilde r + v_i \;\; (\operatorname{mod} \; 2) \implies r = \tilde r  \;\; (\operatorname{mod} \; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr[A(Br) \neq C] = Pr[Dr \neq 0] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely,
$$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$
The last inequality is a bit of algebra I leave to you.


What is the relation between arithmetic circuits and straight line programs? One definition of arithmetic circuits is as follows:

  An arithmetic circuit $\Phi$ over the field $\mathbb F$ and the set of variables $X$  usually, $X = \{x_1, \dots , x_n\}$) is a directed acyclic graph as follows. The vertices of $\Phi$ are called gates. Every gate in $\Phi$ of in-degree $0$ is labeled by either a variable from $X$ or a field element from $\mathbb F$. Every other gate in $\Phi$ is labeled by either $\times$ or $+$ and has in-degree $2$.

A straight-line program seems to be a succession of basic operations without any if or while statement. So it seems to be a term from the associated free algebra expressed suitably "compressed" as an acyclic graph. But a (reference to a) nice definition of straight-line programs would already help me a bit with respect to this question.

What I really want to know is whether an arithmetic circuit is a special case of a straight-line program? If yes, then why is arithmetic circuit complexity considered so important, while even finding a reference for a proper definition of straight-line programs seems to be quite challenging? (I found a definition in The Extraordinary Power of Division in Straight Line Programs, but this is a paper from 2012, and the notion itself seems to be much older.)

Straight-line programs and arithmetic circuits are two equivalent ways of describing the same computational model. A straight-line program typically has the following instructions:

Reading the input: $t_i \gets x_j$.
Initialization by constants: $t_i \gets r$ for all $r$ in the ambient field.
Addition, subtraction, multiplication, division: $t_t \gets t_j \pm t_k$ and so on.
Output: $o_i \gets t_j$.

The input and output instructions aren't really necessary. The inputs are $x_1,\ldots,x_n$ and the outputs are $o_1,\ldots,o_m$.

Exercise: show that (multiple-output) arithmetic circuits and straight-line programs are equivalent: they compute the same functions with the same size complexity (if you define size in the correct way, and allow the same sets of gates and lines).


Whats exact definition of 'atomicity' in programming? the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also mean that a program should not run concurrent when it is supposed to be atomic?
let's say we have 2 program as an example:
example_program1:

counts int i = 1 to 100 every second
every number is printed in new line

example_program2:

just prints "hi"

and a parent program that includes both of these program and run them once receiving a signal to start a specific program (e.g via sigaction in linux) with 2 version:
version 1:

runs the program (even concurrent) anytime once receiving the signal
which means program2 can print "hi" while program1 is still printing out the numbers

version 2:

only run one program at a time
signal for other program is blocked until program in progress has terminated

in this example, can only version 2 be considered atomic or both? Would this program be non-atomic only if e.g program2 would increment i by 1 during its process?

If an operation X is atomic, that means that anyone observing the operation will see it either as not yet started, or as completed, and not in any state that is partially completed. That's it.

Obviously if you write code to perform an operation X, and other code can see it half performed, or interfere with it, then your implementation of the operation X is not atomic.

In some contexts, an”atomic” operation can succeed or fail; if such an atomic operation fails then the effect must be exactly the same as if the operation had never been started.


On-line simulation of a two-head tape Turing machine using single-head tape(s) I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles for the fact that one single-head tape doesn't suffice for this problem and the simulation should be done using two single-head tapes, but I haven't been able to present an accurate simulation of two-head TM using these single-head tapes. Are there any thoughts on how to do so? Thanks,

Two heads on a single tape are more powerful (in real time) than two single heads on two distinct tapes.

See T. Jiang, J.I. Seiferas and P.M.B. Vitanyi, 1994, "Two Heads Are Better than Two Tapes"

EDIT: I just read the proof and it is not trivial (and I didn't read/understand the details :-):

The language $L = \{ x2x' | x \in \{ 0,1 \}^* $ and $x'$ is a prefix of $x$ $\}$ can be easily recognized by a two-head single tape TM in real time: one of the two heads stays on the beginning of the input, the second moves right and as soon as it reads the 2 both move right and check whether $x'$ is a prefix of $x$.

But $L$ cannot be recognized by a two single-head tapes TM in real time. In a TM with two single-head tapes one of the two tapes is empty and trivially if the first head scans the input while the other copies it, when the 2 is read, the prefix of $x$ is far from both heads.

Hence the prefix(es) of $x$ should be made "quickly" available at every time using a so called "holographic" representation (see fig. 1 of the paper). But if $x$ is incompressible this cannot be achieved and when it is time to check the prefix one of the two heads must move too far from its current position (the number of moves cannot be bound by a constant).


Demonstration that EXP is closed under union complementation and concatenation How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?

By definition $EXP = \bigcup_{k\in N}{DTIME\big(2^{n^k}\big)}$.

Let $L_1, L_2 \in EXP$. Then $L_1 \in DTIME\big(2^{n^m}\big)$ and $L_2 \in DTIME\big(2^{n^k}\big)$ for some $k,m \in N$.

So for a string $w$ checking $w \in L_1 \cup L_2$ takes $2^{n^m} + 2^{n^k}$ time which is $O(2^{n^l})$ where $l = max(m,k)$. So $L_1 \cup L_2 \in DTIME\big(2^{n^l}\big)$ and hence in $EXP$.

Let $w$ be a string of length $t$. Then checking $w \in L_1L_2$ takes $t(2^{n^m} + 2^{n^k})$ since for strings $u$ and $v$ such that $w=uv$ we check $w \in L_1$ and $v \in L_2$ $t+1$ times since there are $t$ different prefixes and suffixes of $w$. Assuming $l = max(m,k)$ we have $t2^{n^l}$ running time which is less than $2^t2^{n^l} = 2^{t + n^l}$ which belongs to $EXP$.

Finally, checking $w \in L_1$ takes $O(2^{n^m})$ times so the Turing machine halts with "no" if $w \in L_1$, with "yes" otherwise. Thus $\overline{L}_1^{} \in EXP$.


Is there a known method for constructing a grammar given a finite set of finite strings? From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?

If given n strings of m length, it should be possible to make a grammar that will generate those strings, and just those strings.

Is there a known method for doing this? Ideally a technique name I can research. Alternatively, how would I go about doing a literature search to find such a method?

This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature.  See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, https://cstheory.stackexchange.com/q/27347/5038.

For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, Smallest DFA that accepts given strings and rejects other given strings, Are there improvements on Dana Angluin's algorithm for learning regular sets, and https://cstheory.stackexchange.com/q/1854/5038.


Find the shortest OPEN path connecting a set of 2D points (special case) I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.

The precondition is very simple: For each point there's always a set of nearby points within a narrow arc, and another (possibly empty) set of nearby points within a narrow arc at a nearly opposite direction. There are no other nearby points.

For each set of three contiguous points within the path, namely A, B and C, the angle ∠ABC always has a measure between 90° and 270° (most of the time it's close to 180°, though there are a couple cases of points forming a nearly right angle), and the angles ∠BAC and ∠BCA have a measure of less than 90° (or possibly a smaller threshold).

My naïve idea is: for each point, evaluate the vectors toward the nearest n points to find whether there are two nearest opposite pairs and make the path piecewise (if all the other points are at nearly the same direction, then we're at the beginning or end of the path).

However, I want to know about a better way to trace the shortest path between the set of points, given the constraints above.

Edit: I forgot to say. No, I don't want a cycle. Though minimum Hamiltonian paths are still NP-hard, I...

You know what? I'll build a sparse graph that only contains the set of edges whose weight (Euclidean distance) is less than a threshold, then run Dijkstra's algorithm through the resulting adjacency list. This will work well with my data.

Your paths are varieties of what are often called angle-restricted paths in the literature, and exploring the literature may help with your
particular situation:

Fekete, Woeginger, 1997, "Angle-Restricted Tours in the plane."
Dumitrescu, Pach, Tóth, 2009, "Drawing Hamiltonian cycles with no large angles."
Bárány, Pór, and Valtr, 2009, "Paths with No Small Angles"

The general angle-restricted TSP (Traveling Salesman Path) problem is NP-hard, as
established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."


A language that is not context free I working through some textbook exercises, and came across a problem that I'm struggling with.
Give a CFL $L$ such that $\{x|\forall y \in \Sigma^* \space xy \in L\}$ is not a CFL.
I've got the idea that we can let $L$ be formed by taking a language that is not CFL, and following each element by every string, and also add in the prefixes of elements of the non CFL language. But I'm not sure how to find a language such as this that is a CFL.
However, I'm struggling to think of an example with such a property.
Any help would be appreciated.

For simplicity, let us define that if $L$ is some language, $pref(L)$ to be the described language generated from $L$ (do not not to be confused with the language prefix operator)
Let us also define $\Sigma = \{a,b,c,e\}$.
We know that the language $L=\{a^nb^nc^n|n\in\mathbb N\}$ is not CFL, so we may want to use it.
Lets think in terms of your idea: we will want some other language $\hat L$ where $pref(\hat L)$ is similar to $L$ itself.
First, notice that simply applying your idea is not very useful: we may start with a word $aaabbbccc\in L$ and after we add to its the $y$ at the end, we can find ourselves with the word $aaabbbccccccccccccc\in \hat L$. This will make everything much harder to do, as this word could as well end up in $pref(\hat L)$ (think why!) and therefore in this case $pref(\hat L)$ is not very similar to $L$.
So how do we fix it? We can just add a new letter that will seperate our words in $L$ from the rest. This letter will be $e$ (short for "end") - so our new definition for $L$ would be as follows: $L=\{a^nb^nc^ne|n\in\mathbb N\}$. Now, if we would have taken a look at $\hat L = L\Sigma^*$ (concatenation of those two languages) we would have $pref(\hat L)=\hat L$  but also $\hat L$ is very similar to $L$ in its core structure (and also is not a CFL for the same reason $L$ isn't).
Now we have a different problem, since $pref(\hat L)=\hat L$ we obviously can't have $\hat L$ being a CFL with $pref(\hat L)$ not a CFL. To fix this, we need a key observation: if we add some arbitrary word to $\hat L$, for example the word $ababa$ - then since it wasn't in $L$ already, it won't be in $pref(\hat L)$ too! (find a $y\in \Sigma^*$ where this word concatenation with $y$ is not in $\hat L$)
This means, we may somehow be able to add things to $\hat L$ while keeping $pref(\hat L)$ the same (and not a CFL). Adding all words of the form $we$ where $w\in\Sigma^*\setminus\{e\}$ with $|w|=3n$ for some $n\in\mathbb N$ should do the trick, but I will leave proving that $pref(\hat L)$ didnt change with those additions. Notice now that this language not is CFL, but its also regular! the automata that solves this language is simple: it checks whether the first occurrence of the letter $e$ is in a position that is a multiple of 3.
So finally, the language $\hat L=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*\bigcup \{we|w\in\Sigma^*\setminus\{e\}\land \exists n\in\mathbb N .|w|=3n\}$ is regular (and hence a CFL) while $pref(\hat L)=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*$ is not a CFL.

Sorry if this post was too long! I hope it helped you understand the problem and its solution on all of their steps and thinking methods.