Estimating the number of distinct elements Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation.

We have a stream $\sigma = \{a_1, ..., a_n\}$, with each $n \in [n]$, and this implicitly defines a frequency vector $F = {f_1, ..., f_n}$. Let $d = |\{j : f_j > 0$}| be the number of distinct elements that appear in $\sigma$.
For an integer $p > 0$, let $zeros(p)$ denote the number of zeros that the binary representation of $p$ ends with. Formally,
$zeros(p) = max\{i : 2^{i}$ divides $p\}$
Algorithm:
Initialize:

Choose a random hash function $h$: $[n] \mapsto [n]$ from a 2-universal family;

z $\leftarrow $ 0;

Process $j$:
3. if $zeros(h(j)) > z$ then $z \leftarrow zeros(h(j))$
Output: $2^{z+\frac{1}{2}}$
The basic intuition here is that we expect $1$ out of $d$ distinct tokens to hit $zeros(h(j)) \geq log(d)$, and we don't expect any tokens to hit $zeros(h(j)) >> log(d)$. Thus the max value of $zeros(h(j))$ over the stream - which is what we maintain in $z$ - should give us a good approximation to $log(d)$.

The idea is that the hash function $h$ maps elements to random elements. Now think about the likelihood that the last $k$ digits of a random number are $0$. There's a 50/50 chance that the number ends with $0$, but it becomes more and more unlikely as you increase the number of zeroes at the end. For $000$, the probability is already down to $\frac{1}{8}$, and for ten zeroes it's around one in one thousand. So it's very unlikely that any one random number has a lot of zeroes at the end.

So what's the maximum number of zeroes can you expect when you take $d$ random numbers? It's unlikely that one of the $d$ numbers ends in loads of zeroes, but the probabilities are so that it's likely that at least one has $\log{d}$ zeroes.

If you do this with one hash function, that's a pretty rough estimator, but due to the so-called median trick you can do it a couple of times with different hash functions, use the median of the outputs, and the certainty of the result increases exponentially in the number of different hash functions (they have to be independent).


How can I treat a problem like a search problem in AI? I'm a CS student and I'm trying to understand the searching algorithms used in AI.

My problem is that I don't really understand how to treat a problem like a search problem. I don't know which would be the first steps for solving it and how shall I choose the right algorithm for that.

For example, I have a problem like that:

n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of
an n×n n grid. The vehicles must be moved to the top row but in reverse
order; so the vehicle i that starts in (i, 1) must end up in (n−i+ 1, n). On
each time step, every one of the n vehicles can move one square up, down,
left, or right, or stay put; but if a vehicle stays put, one other adjacent
vehicle (but not more than one) can hop over it. Two vehicles cannot
occupy the same square.

I understood that the start state of each car is the bottom row,
each car has at most five possible moves from any position and if each car has
a 3x3 grid of empty space around it, then all five moves are possible.

My idea is that I should treat the car route like a tree where each node is a position of the car at a time, but I don't know how correct is it.

Which would be my first steps regarding this problem to solve it like a search problem?

I would be very thankful for any advice!

To treat it as a search problem, you should have a decision tree in mind. In your example, the each node's degree would be the total combination of possible movements for each car (except for the combination in which all cars stay put). Then, each edge of the decision tree would represent a transition from one timestep to the next and each node would represent the positions of all the vehicles at that timestep. One can use the current depth of the tree during the search process to track the current timestep. Using this setup, there are many possible tree search algorithms that may suffice for your problem.


NP-Hardness of Hamiltonian cycle with $|V|$ divisible by 3 Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph $G=(V,E)$  with $|V|$  divisible by 3 and DHAM3  be the problem of determining if a Hamiltonian cycle exists in such graphs. Are DHAM3 and SHAM3 $\mathcal{NP}$-hard?

What I tried is I proved that the problem of finding Hamiltonian cycle is in $\mathcal{NP}$ and that 3-SAT problem, which is $\mathcal{NP}$-Complete, is reducible to Hamiltonian cycle problem which makes it $\mathcal{NP}$-hard, but I am not sure what's the purpose of $|V|$ divisible by 3, does that change anything?

There is no "purpose" for the condition that the number of vertices be divisible by 3 – it is part of the problem statement. DHAM3 is the special case of DHAM in which the number of vertices is divisible by 3. In principle this might make the problem easier (a special case can only be easier), but in this case DHAM3 is also NP-hard (and so NP-complete), as you can show by reduction from DHAM.

The problem SHAM3 is not a decision problem and so not eligible to be NP-complete or NP-hard.

How do you show that DHAM3 is NP-hard by reduction from DHAM? You have to come up with an efficiently computable function $f$ that takes an instance $x$ of DHAM and outputs an instance $f(x)$ of DHAM3 in such a way that $x \in DHAM$ iff $f(x) \in DHAM3$. In other words, $f$ takes a graph $G$ and outputs a graph $f(G)$ whose number of vertices is divisible by 3, and moreover $G$ is Hamiltonian iff $f(G)$ is Hamiltonian.

The difficulty here is that the original graph $G$ might have a number of vertices which is not divisible by 3 (otherwise you can take $f(G) = G$). I'll let you figure out how to overcome this difficulty.


Does domination rule apply for inadmissible heuristics? Let's say $h_1(n) \geq h_2(n)$ so that dominance is established even if $h_1$ and $h_2$ are both inadmissible/non-optimal heuristics -in whichever given search space.

Is $h_1$ still faster/better than $h_2$ or does the dominance rule only apply to admissible heuristics?

Also, if I could ask for a bit of extra help, can you provide a link/reference to an academic material that establish this relationship between dominanation and inadmissibility? Thank you!

First things first. In your question you put together two different concepts, namely admissibility and optimality of heuristic functions:

Optimality: A heuristic function $h(n)$ is optimal if and only if $h(n)=h^*(n)$ for every state $n$ of your state space, i.e., it returns the cost of an optimal path from $n$ to the goal.
Admissibility: A heuristic function $h(n)$ is said to be admissible if and only if $h(n)\leq h^*(n)$, i.e., it never overestimates the effort to reach the goal.

Clearly, optimality is a stronger property than admissibility. Also their impoortance comes from different factors:

Optimality: It can be proven (under a rather restricted model) that a specific class of search algorithms (such A$^*$, IDA$^*$, RBFS, DFBnB, etc.) only expand nodes along an optimal path when a perfect heuristic is used.
Admissibility: It can be proven (under a very general model) that a specific class of search algorithms (as those aforementioned) will return optimal solutions when using an admissible heuristic functions.

This said, dominance is an orthogonal property to these as it does refer neither to the accuracy of heuristic functions nor their ability to return optimal solutions. Your definition is correct:

Dominance: $h_1(n)$ is said to dominate $h_2(n)$ if and only if $h_1(n) \geq h_2(n)$ for all states $n$ in your state space. Note that this is a strong definition as it should be fulfilled for all states. In general it is said that $h_1(n)$ is more informed than $h_2(n)$.

And its importance is relative to the performance of the search algorithm when using one heuristic function or another:

Dominance: It can be proven (again under a rather restricted model) that a search algorithm (from the class of search algorithms mentioned above which are known as admissible search algorithms) expands less nodes when using a more informed heuristic function $h_1(n)$.

There is a lot to say here. First, that this property refers only to the must-expand nodes, that tie-breaking is assumed to be applied in the same way when using one heuristic or another, etc. There is no need to go in much deep detail to note however that this property makes a lot of sense when $h_1(n)$ and $h_2(n)$ are both admissible -optimality, as you say is disregarded here. If you put all conditions together you'll note that: $h_2(n) \leq h_1(n) \leq h^*(n)$ so that $h_1(n)$ provides better estimates for all nodes $n$ in the state space, i.e., the values returned by $h_1(n)$ are closer to the cost of the optimal path. This argument lies at the core of the proof of the effectiveness of $h_1(n)$ when being compared to $h_2(n)$.

Now, if neither $h_1(n)$ nor $h_2(n)$ are admisible, then:

Weak inadmissibility: $h_1(n)$ and $h_2(n)$ are inadmissible but they might return admissible estimates for some nodes. In this case, nothing can be said about the relative performance of these heuristics. It can be proven, however, that there is no guarantee about the optimality of the solutions returned by any of the search algorithms mentioned above.
Strong inadmissibility $h_1(n)$ and $h_2(n)$ always return inadmissible estimates, i.e., $h_1(n), h_2(n) \geq h^*(n)$ for all states $n$. If $h_1(n)\geq h_2(n)$ then $h_1(n) \geq h_2(n)\geq h^*(n)$ so that the opposite observation applies now and $h_2(n)$ returns estimates which are closer to the cost of the optimal solution. This does not imply that $h_2(n)$ will serve to expand less nodes but in general one should expect better solutions to be obtained with $h_2(n)$.

Concluding, domination is an orthogonal property to admissibility. They, when being put together serve to make observations about the optimality of the solutions returned and the expected number of necessary expansions to find them, but they can be used in different contexts as well.

As for extra material, I do highly recommend you a couple of books:

Judeal Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesly, 1984.
Stefan Edelkamp, Stefan Schr\"odl, Heuristic Search: Theory and Applications, Morgan Kaufmann, 2012.


Grammar for $\{ a^i b^j: j < 2i \text{ and } j \ne i \} $ For the following language, write grammar independent of the text.
$$\{a^i b^j: j < 2i \text{ and } j \ne i \} $$
I want a hint to start solving this problem. Where should I start?

If $j \neq i$ then either $j < i$ or $j > i$. Hence you can write your language as
$$
\{ a^i b^j : j < i \} \cup \{ a^i b^j : i < j < 2i \}.
$$
It suffices to find a grammar for each of these two languages. Such questions have been asked and answered on this site.


What is the relationship between the complexity class $L^n$ and $NL^m$? The space hierarchy theorem shows that
$$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{PSPACE}}$$
and
$$\mathrm{\mathbf{NL}}^{1} \subsetneq \mathrm{\mathbf{NL}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NL}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NPSPACE}} = \mathrm{\mathbf{PSPACE}}$$
where
$$\mathrm{\mathbf{L}}^{m} = \mathrm{\mathbf{DSPACE}}\left( \log^{m}(n) \right)$$
and
$$\mathrm{\mathbf{NL}}^{m} = \mathrm{\mathbf{NSPACE}}\left( \log^{m}(n) \right)$$

Thus, there exists a function $\varphi \colon \mathbb{N}^{+} \mapsto \mathbb{N}^{+}$ such that for every $m \in \mathbb{N}^{+}$,

$$\mathrm{\mathbf{L}}^{\varphi(m)-1} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{\varphi(m)} \subsetneq \mathrm{\mathbf{PSPACE}}$$

The Savitch's theorem shows that for every $m \in \mathbb{N}^{+}$,
$$\mathrm{\mathbf{L}}^{m} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{2m}$$

Now, we know that $m+1 \leq \varphi(m) \leq 2m$ and $\varphi(1) = 2$.

Can we find $\varphi$ ? Is it an open problem or not?

It is not known whether $\mathsf{L} = \mathsf{NL}$, and this is a famous open question. More generally, I believe that no better bound than $\phi(m) \leq 2m$ is known for any value of $m$, nor is this bound known to be optimal for any value of $m$.


Is the set of real numbers a language? Is the set of real numbers a language?

My idea is that the set of real numbers can't be a language because it is uncountable. Every language must be  countable.

Is there any other way to solve this problem?

The definition of a language, from Hopcroft-Ullman Introduction to Automata and Language Theory, is :

  A set of strings all of which are chosen from some $\Sigma^*$, where $\Sigma$ is a particular alphabet, is called a language.

And from the same book, the definition of a string is :

  A string (or sometimes word) is a finite sequence of symbols chosen from some alphabet.

So strings must be finite. If we represent real numbers by sequences of digits, those sequences would be infinite in length, so that representation won't give us the language of real numbers.

But can we use another representation ? For example, even though we have rationnal numbers with an infinite sequence of digits, we can consider them as a language thanks to fractional representation.

Suppose that the set of real numbers were a language. Let's call that language $L$, and $\Sigma$ its alphabet. $L$ is a subset of $\Sigma^*$, thus $L$ is countable because $\Sigma^*$ is countable. We conclude that the set of real numbers can't be a language because it's an uncountable set.

NOTE : We can explicitly define an injection from $\Sigma^*$ to natural numbers. First, associate for every letter of $\Sigma$ a unique integer, call it $int(a)$. Let $\sigma$ be that bijection, here is its definition :

$$\left \{ \begin{array}{r c l} \sigma(\epsilon) &=& 0 \\ \sigma(\omega) &=& \prod_{i=1}^{|\omega|} \pi(i)^{int(\omega_i)} &;& \omega \neq \epsilon \end{array} \right .$$

Where $\pi(i)$ is the $i^{th}$ prime number and $\omega_i$ the $i^{th}$ letter of $\omega$.


Tight asymptotic bound for recursive algorithm I have this algorithm where:

$$
T(n) =
\begin{cases}
  1 & \text{if}\; n \le 1 \\
  T(n/2) + 1 & \text{otherwise} \\
\end{cases}
$$

So, evaluating for $T(0), T(1), T(2), T(3), \ldots, T(n)$, I'm getting values like:
$$ 1, 1, 2, 2, 3, 3, \ldots, n, n $$

I assume this is twice the sum of $1$ to $n$, that would be the same as $n (n+1)$ or $n^2+2$.

Is my assumption ok?

Suppose that $n = 2^k$. Then
$$ T(n) = T(2^k) = T(2^{k-1}) + 1 = T(2^{k-2}) + 2 = \cdots = T(2^0) + k = k + 1. $$
So $T(n) = \log_2 n + 1$ in that case. In the general case you would get something similar, $T(n) = \lfloor \log_2 n + 1\rfloor$.


Finding the longest path of sum $0$ in a weighted tree How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)?

In other words, I want to find a path so that the sum (sum of numbers on edges) is equal to zero, and the amount of edges along which I went is the maximum.

If the (simple) path needs to go from the root to a descendant:

Perform BFS or a preorder DFS visit of your tree and, for each vertex $v$, record:

the length $\ell(v)$ of the unique path from the root of the tree to $v$; and
the depth $d(v)$ of $v$ in $t$.

This can be done in constant time per vertex since, if $v$ is the root $\ell(v)=d(v)=0$, otherwise $\ell(v) = \ell(u) + w(u,v)$ and $d(v) = d(u) + 1$, where $u$ is the parent of $v$.

Return the vertex $v$ for which $\ell(v)=0$ and $h(v)$ is maximized. The total time spent is linear.

If the (simple)  path needs to go from an ancestor to a descendant:

Perform a preorder DFS visit and maintain a dictionary $D$ that stores the ancestors $u$ of the current vertex $v$. The key of a vertex $u$ in $D$ is the length $\ell(u)$.

When an edge $(u,v)$ is traversed moving away from the root, add $\ell(u)$ to $D$. When an edge $(u,v)$ is traversed (moving towards the root) remove $\ell(u)$ from $D$. In case of ties in $D$ break them in favor of the lowest vertex.

When a vertex $v$ is visited, we want to search $D$ for an ancestor $u$ of $v$ with key $\ell(u) = \ell(v)$, meaning that the path from $u$ to $v$ has length $\ell(v) - \ell(u) = 0$. This can be done in $O(\log H) = O(\log n)$ time, where $H$ is the height of the tree.

The overall time complexity is then $O(n \log H) = O(n \log n)$.

If the (simple) path can be arbitrary:

For each vertex $v$ compute its depth $d(v)$ in any standard way.

Perform a postorder DFS visit and, for each vertex $v$, maintain a dictionary $D_v$ that stores all descendants $z$ of $v$. The key of $z$ is the distance from $v$ to $z$. Break ties in favor of vertices $z$ with larger $d(z)$. In addition to the standard operations, you can also assume that $D$ is able to increase all its keys by a constant amount in $O(1)$ time.

When $v$ is visited and $v$ is a leaf, $D_v$ contains only $v$ itself with key $0$. Otherwise, let $u_1, \dots, u_k$ be $v$'s children and assume w.l.o.g. that  $u_1$ maximizes $|D_{u_1}|$. Construct $D_v$ as follows:

Initially $D_v = D_{u_1}$.  Notice that $D_{u_1}$ will not be used anymore. This operation amounts to renaming $D_{u_1}$ to $D_v$.
Increase all the keys in $D_v$ by $w(v, {u_1})$.
Add $v$ with key $0$ to $D_v$.
The vertex $z$ with key $0$ in $D_v$ is such that the path from $v$ to $z$ has length $0$ and the number of edges from $v$ to $z$ is maximized (remember our tie-breaking rule). This is a candidate path.
For each $u = u_2, \dots, u_k$:

For each vertex $a$ with key $\ell_a \in D_u$:

Check whether there is a vertex $b$ in $D_v$ with key $\ell_b = -\ell_a - w(v,u)$. If this is the case then there is a candidate path from $a$ to $b$ of length $0$ and hop-length $d(a) + d(b) - 2d(v)$.

For each vertex $z$ with key $\ell_z \in D_u$:

Move vertex $z$ from $D_u$ to $D_v$. Its new key in $D_v$ is $\ell_z + w(v,u)$.

Return the best candidate path seen during the visit.

To bound the time complexity notice that, apart from a $O(n \log n)$ term needed to add the vertices $v$ into $D_v$, it is dominated by the complexity needed to move vertices $z$. When a vertex $v$ is moved from $D_u$ to $D_v$, the size of $D_v$ will be at least twice the size of $D_u$. This means that each vertex can be moved at most $O(\log n)$ times.

The overall time complexity is therefore $O(n \log^2 n)$.


Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier? The question came to my mind while studying the NP definition. Do we know any such languages?

For any instance of a problem, take the instance itself as the certificate. Linear size, verifiable in polynomial time for problems in P, not known for problems in NP.


Why can we drop the superscripts in the Floyd Warshall algorithm? In the lecture notes, our professor mentioned that we can take down the space taken by the FW algorithm from $O(n^3)$ to $O(n^2)$ by dropping all the superscripts in the matrices (i.e. use one $n\times n$ array $D$).

I just want to check my understanding, is it because by default $D^k=D^{k-1}$ except for the values $i,j$ where $d_{ik}^{k-1}+d_{kj}^{k-1}<d_{ij}^{k-1}$ where we set $d_{ij}^k=d_{ik}^{k-1}+d_{kj}^{k-1}$ but in essence we are using the values in the $D^{k-1}$ matrix to update itself?

However, what if we change one value, say $d_{i_1j_1}^k$ in the $kth$ iteration but then we need to reuse the value $d_{i_1j_1}^{k-1}$ later on in the same $kth$ iteration, wouldn't it be lost?

Basically in iteration k no entry $d_{ij}$ can change if $i=k$ or $j=k$. Since you update the entries in $D$ by considering $d_{ik}$ and $d_{kj}$ you can do all these updates in-place.

However there is an even simpler argument if you only want to show that the algorithm requires $O(n^2)$ space. At every iteration $k$ the values in $D^k$ only depend on the previous matrix $D^{k-1}$. Therefore it is enough to store the matrix $D^{k-1}$ of the previous iteration, use it to fill the next matrix $D^k$ and then you can safely discard $D^{k-1}$. So you only ever need to keep two matrices in memory and arrive at $O(n^2)$ space. Of course no sensible implementation would actually do this but it is enough to show the space bounds.


Is there a faster than O(n^2) solution for Box stacking problem? The Box Stacking problem is as follows:

  You are given a set of $n$ types of rectangular 3-D boxes, where the
  $i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real
  numbers). You want to create a stack of boxes which is as tall as
  possible, but you can only stack a box on top of another box if the
  dimensions of the 2-D base of the lower box are each strictly larger
  than those of the 2-D base of the higher box. Of course, you can
  rotate a box so that any side functions as its base. It is also
  allowable to use multiple instances of the same type of box.

Is there a solution faster than the $O(n^2)$ solution given here?

This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question:

As in the link, for a box in the input with dimensions $(w_i, d_i, h_i)$, consider all rotations of the box, but maintain the property that the first dimension is always $\ge$ the second dimension. So each input box corresponds to three boxes, and consider all these $3n$ boxes, and sort them in decreasing area of the base (ie. the product of the first two dimensions).

Let this sorted sequence be $(a_1, b_1, c_1), (a_2, b_2, c_2), \ldots, (a_{3n}, b_{3n}, c_{3n})$.

Let $DP[i]$ be the maximum height that you can achieve using the first $i$ boxes in this sequence, such that the topmost box is the $i^{th}$ box. Initially $DP[i] = 0$ for all $i$. The recurrence is

$DP[i] = c_i + \max_{\substack{j < i \\ a_j > a_i \\ b_j > b_i}} DP[j]$

Now, instead of spending $\mathcal{O}(n)$ time to find this optimal $j$, we will do it faster using some data structures. Think of each box $(a_j, b_j, c_j)$ as a point $(a_j, b_j)$ in a 2D plane, which has a value $DP[j]$. Now what we want to find is the point in the rectangle $[a_i + 1, INF] \times [b_i + 1, INF]$ which has the maximum value. Note that we can ignore the constraint $j < i$ because it will be implicitly satisfied from the dimensional constraints.

For this, construct a 2D Segment Tree aka Fenwick Tree (look at the section 'Compression of 2D Segment Tree'), using $a_i$ as the values in the outer Segment Tree, and $b_i$ as the values in the inner Segment Trees. You can also use most other 2D Range Query data structures for this.

You can query for the maximum value in that rectangle in $\mathcal{O}(\log^2{}n)$ time, and once you have computed $DP[i]$, you will have to update that value in all the $\mathcal{O}(\log{}n)$ inner Segment Trees, which would take a total of $\mathcal{O}(\log^2{}n)$ time.

Hence, the problem can be solved in $\mathcal{O}(n\log^2{}n)$ time, and $\mathcal{O}(n\log{}n)$ space.


Insertions in Red-Black Trees I studied methods for inserting new nodes into Red-black trees for the first time this month.

In doing so, I read a lot of pages on the internet and found that ( if I'm not mistaken ) there are many, many, many accepted algorithms for inserting nodes into red-black trees.

Furthermore, I noticed that it is possible to have two insertion algorithms that don't break red-black tree invariants, but also can start with the same initial tree, insert the same node, and end up with different resulting trees.

I think.

For example, take this website's algorithm for insertion:
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

And then there's this famous example from 'Purely Functional Data Structures' by Chris Okasaki:

And then there's this algorithm from Ohio State:
https://www.pdf-archive.com/2017/03/28/08-red-black-tree/08-red-black-tree.pdf

Is it true that there are many red-black tree insertion algorithms that, given the same domain, will map the elements in that domain differently?

Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time.  That is, there exists more than one valid red-black tree insertion algorithm, whose outputs are not always equal.

The easiest way of seeing this is to focus on the correspondence between red-black trees and $(2, 4)$-B-trees.  A black node with its red children correspond to a B-tree node.

In particular, if you have two sibling B-tree nodes with four elements in total, they can be distributed 1/3 or 2/2.  In red-black terms, if two black nodes are cousins, it's possible for each to have one red child, or for one of them to have two red children and the other to have none.  More than that, you can shuffle the elements around between the nodes locally to transform one such pattern into the other.

As wikipedia says, "The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time"; the imperfection of balancing gives room for multiple tree representations of the same set.


How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence? Theorem 15.1 (Optimal Substructure of an LCS)

Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS.

If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y_{n-1}$.

If $x_m \neq y_n$, then $z_k \neq x_m$  implies that Z is an LCS of $X_{m-1}$ and Y.

If $x_m \neq y_n$, then $z_k \neq y_n$ implies that Z is an LCS of X and $Y_{n-1}$.

format copied from related post
The above cases are intuitive and easily provable.
I do not understand additional cases not explicitly mentioned in the theorem:
What happens here:
$x_m \neq y_n$ and $z_k \neq x_m \neq y_n$
The above statement combines cases 2 and 3. Does that mean Z is an LCS of both LCS of $X_{m-1}$ and Y AND X and $Y_{n-1}$? That doesn't make sense to me.

If $x_m = y_n$ then any longest common sequence must end with $x_m = y_n$. This is what the first item covers.
If $x_m \neq y_n$, then there are three types of longest common sequences:

Longest common sequences ending in $x_m$.
Longest common sequences ending in $y_n$.
Longest common sequences ending in neither.

These are all the cases. There is no other case.


Random permutations by probability matrix I have the following problem:

I need to generate $\ell$ random permutations each of length $n$ from a list of $m$ elements ($m \ge n$) by a predefined probability matrix $P$ of size $n$ x $m$.

Distribution probability matrix $P$ = {$p_{i,j}$} describes the probability that i-th position is occupied by $j$-th element ($i\in \{1,\dots,n\}$ and $j \in \{1,\dots,m\}$).

Of course
 $1 \ge p_{i,j} \ge 0$ and $\sum\limits_{j=1}^m(p_{i,j}) = 1$ (rows of matrix P are normalized, to be equal 1)

$\sum\limits_{i=1}^n(p_{i,j}) > 0$ (each element has nonzero probability to be at least on one position)

If $p_{i,j} = 0$, then $i$th position of permutation can not be occupied by $j$th element.
 If $p_{i,j} = 1$, then $i$th position is occupied only by $j$th element

Example:
 For $$P = \begin{bmatrix} 0.5 & 0.5 & 0 \\
 0 & 0.5 & 0.5 \\
 0.5 & 0 & 0.5\\
 \end{bmatrix},$$
 I get only two permutations [1 2 3] and [2 3 1] with the same frequency.
 But for $$P = \begin{bmatrix} 0.01 & 0.99 & 0 \\ 0 & 0.01 & 0.99 \\ 0.99 & 0 & 0.01\\ \end{bmatrix},$$ I significantly prefer permutation [2 3 1]

Realistic values $\ell = 1\,000$–$10\,000$, $n = 30$, $m = 50$

Is there any suitable and effective (fast) algorithm?

Edit: The problem is motivated by permutation sampling for stochastic combinatorial optimization. Permutations are parametrized via probability matrix P. The probability matrix P is generated by black-box objective function responses.

Edit2: This is typical algorithm for permutation sampling at stochastic optimization problem:

Generation of partial permutations $x$ by probability matrix $P$

Generate a random permutation $(\pi_1, ... ;\pi_{n})$ of the set of positions $(1,...,m)$.
Define $P(1) = P$ and set $a = 1$.
Generate $x_{\pi_{a}}$ according to the distribution formed by the $a$-th row of $P(a)$ , that is $(p_{(\pi_{a},1)},... ,p_{(\pi_{a},m)})$. Thus, element $x_a$ is placed into position $a$.
Obtain $P(a+1)$ from $P(a)$ by first setting the $x_{a}$-th column of $P(a)$ to 0, and then renormalizing the rows to sum up to 1.
If $a = n$ then stop and return $x$; otherwise set $a = a + 1$ and return to step 3.

Matrix $P$ is during optimization cycle obtained by update algorithm, which produce stochastic (not bistochastic) matrix. I want to be sure, that this algorithm is mathematically correct.

Your problem is not well-defined. As David Eisenstat notes in his comment, your matrix actually has to be bistochastic rather than just stochastic, since every convex combination of permutation matrices is bistochastic. Also, there could be many ways of representing a given bistochastic matrix as a convex combination of permutation matrices. As a simple example, the matrix $$\begin{bmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{bmatrix}$$ can be obtained by taking all permutations or just $123,231,312$.

The Birkhoff–von Neumann theorem states that every bistochastic matrix is a convex combination of permutation matrices. Its algorithmic proof gives a polynomial time algorithm that gives such a combination with at most $n^2$ matrices, which is probably optimal or close to optimal. In the literature you might be able to find faster algorithms; if you do, please let us know.


Checking Feasibility of Linear Program in Polynomial Time Given a linear system of the form:

$$\begin{array}{c}
x_r = a \quad x_j = b \\
c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\
x_1+x_2 + x_3 + \ldots + x_n = k\\
0 \le a,b,x_1,x_2,x_3...x_n \le 1\\
k \ge 0
\end{array}$$

How quickly can the feasibility of the system be checked? To clarify: $x_r,x_j$ are members of $x_1,x_2...x_n$. Would it be $O(n^{3.5})$ since I believe that is the general complexity for running a linear program or would it be less? Can one use gaussian elimination to quickly reduce the first 4 equations in $O(n^3)$ and after that systematically move through the equations starting from the terms with largest coefficient and moving to terms with smallest coefficient assigning values that bring the equations as close to satisfactory as possible?

Additional info:

I am assuming that the number of variables scales linearly. $n \ne N$ (I think that was clear though).

Restating the problem.  As far as I can tell, your system is equivalent to the following:

$$c_1 x_1 + \dots + c_n x_n = N$$

subject to the constraints

$$0 \le x_1, \dots, x_n \le 1.$$

Solving this problem. This is a linear program, so certainly we can tell in polynomial time whether it has any feasible solution, as a result of the fact that there are polynomial-time algorithms for linear programming.

However, there's a better solution.  We can directly solve this problem by inspection, without needing a linear programming solver.

Suppose without loss of generality that $c_1,\dots,c_j$ are positive and $c_{j+1},\dots,c_n$ are zero or negative.  (You can re-order the variables to put things into this standard form.)

Then it follows that $c_1 x_1 + \dots + c_n x_n \le c_1 + \dots + c_j$.  So, if $c_1 + \dots + c_j < N$, then this problem has no feasible solution.  On the other hand, if $N \le c_1 + \dots + c_j$, then it is easy to demonstrate that this problem does have a solution: simply let $x_1 = \cdots = x_j = N/(c_1 + \dots + c_j)$ and let $x_{j+1} = \cdots = x_n = 0$.  These $x_i$'s will all fall in the desired range.

Thus, feasibility can be checked in $O(n)$ time (in the RAM model, where basic operations take $O(1)$ time).

Details.  Why is it fair game to reduce the problem to the form given above?  How did I get the simpler form above?

Well, first off, I removed the variables $a,b$ from the linear program.  No matter what values you assign to the $x$'s, you'll always be able to assign a value to $a,b$ derived from the $x$'s that satisfies the equations that mention $a,b$.

Similarly, I removed the equation $k=\dots$ and the variable, since no matter what value we assign to the other variables, we can simply set $k=x_1+\dots+x_n$ and get a value that will satisfy this equation; it will also satisfy $k\ge 0$, since all the $x_i$'s are required to be $\ge 0$.  That leaves me with the problem shown at the top of my answer.


Proving a language is not regular I need to prove that the following language is not regular

  $\{c^mb^na^n \mid n>0,m\geq0\}$

But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but every example I see is in the form

  $\{a^nb^n \mid n>0\}$

Or something similiar.  This does not help me with my problem, because I dont fully understand pumping lemma and am not sure how to do it for two variables that have no dependency on each other.  I know to take a length P from L, and I also need a string s>=P.
Which then becomes P=xyz, but it is this step that confuses me.

There are many ways to solve this. Here are some:

If $L = \{c^m b^n a^n : n>0, m\geq 0\}$ were regular then so would $L \cap b^*a^*$ be.
The words $\{ b^n : n > 0 \}$ are pairwise inequivalent modulo $L$, so $L$ is irregular according to Myhill-Nerode.
The pumping lemma works if you ignore the $c$ part.


Is there a known way to convert any $QBF_2$-formula into an equisatisfiable $QBF_2$-formula in CNF in polynomial time? It is easy to turn any boolean formula and any quantified boolean formula into an equisatisfiable formula in CNF using Tseitin transformation:

$$
Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \Phi \Rightarrow Q_1 z_1 Q_2 z_2 \ldots Q_n z_n \exists x ((\neg{x} \vee \Psi) \wedge \Phi[x/\Psi] ),\ Q_i \in \{ \exists, \forall \}
$$

(For details, see for example here). My two questions are:

Can any formula of the form $\forall z_1 \ldots \forall z_n \exists
    z_{n+1} \ldots \exists z_m \Phi$ be turned into an equisatisfiable
formula of the same form (so beginning with $\forall$ and with just
one alternation of quantifiers) in CNF using Tseitin transformation?
I'm assuming Yes, since Tseitin transformation only adds
existential quantifiers ($\exists$) right before $\Phi$.
Can any formula of the form $\exists z_1 \ldots \exists z_n \forall
    z_{n+1} \ldots \forall z_m \Phi$ also be converted into an equisatisfiable formula of the same form (so beginning with $\exists$ and with just
one alternation of quantifiers) in CNF in polynomial time? I'm assuming No since Tseitin transformation would give us the form $\exists z_1 \ldots \exists z_n \forall
    z_{n+1} \ldots \forall z_m \exists x_1 \ldots \exists x_l \Phi'$ and I'm not aware of any other polynomial time transformation useful in this case.

Yes, for exactly the reasons you listed.
I don't know of any way to do what you want.  However, it is possible to convert it to a formula of the form $\neg \forall x \exists y \Psi$ (negate it, then convert $\neg \Phi$ to CNF via the Tseitin transform and let $\Psi$ be the result), so if you have an oracle that will solve QBF2-CNF queries, it can be used to solve QBF2 queries.


How can one come up with reasonable IP subnet allocations? An ISP has following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20
The ISP wants to give half of this chunk addresses to Organization A,
and a quarter to Organization B, while retaining the remaining with itself.
Which of the following is a valid allocation of addresses to A and B?

  A) 245.248.136.0/21 and 245.248.128.0/22
  B) 245.248.128.0/21 and 245.248.128.0/22
  C) 245.248.132.0/21 and 245.248.132.0/21
  D) 245.248.136.0/24 and 245.248.132.0/21

It is easy to make out that option 'C' and 'D' are wrong. Option 'B' is not possible due to address overlapping. The answer is 'A' for sure, but I'm unable to understand how. How is 245.248.136.0/21 and 245.248.128.0/22 calculated? I've been trying to solve this the
whole day but found no solution to it, any help on how to solve this problem would be appreciated.

Also, how can I determine the range of addresses that can be allocated to organizations A and B?

Hints:

Try working out the binary representation of 245.248.136.0 (it's 32 bits) and of 245.248.128.0.
Re-read what the /21 and /22 notation means and how CIDR works.
What is the range of IP addresses included in 245.248.128.0/22?  in 245.248.136.0/21?

I think once you understand the concepts you'll find that this question is straightforward.

Advice: Rather than asking a question about this specific exercise, you might do better to ask a question about some concept you don't understand: e.g., what /N notation means, how CIDR works, etc.  But make sure to do your research first.  There's lots written on CIDR, /N notation, etc.  You can probably clear up your confusion on your own by doing proper reading on those concepts.


Would a sparse NP-Complete language imply L = NP? Would a sparse NP-Complete language imply L = NP?

Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-complete to L-complete for NP=L. [4] below does not directly address this.

Here is my proof attempt:

[1] Assume there exists a (sparse NP-Complete language).

  Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP.

https://en.wikipedia.org/wiki/Mahaney%27s_theorem

[2] In other words, (sparse NP-Complete language) implies (P = NP).

[3] From [1] and [2] (P = NP).

[4] (P = NP) implies (P-complete = NP-complete).

[5] From [3] and [4] (P-complete = NP-complete).

[6] From [1] and [5] there exists a (sparse P-Complete language)

  In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse P-complete problem, then L = P."

https://en.wikipedia.org/wiki/Sparse_language

[7] In other words, (sparse P-complete problem) implies (L = P).

[8] From [6] and [7] (L = P).

[9] From [3] and [8] (L = NP).

Your claim [4] is wrong - the issue is with the term "$X$-complete" for a complexity class $X$.

Stricly speaking, barring specific convention the phrase "$X$-completeness" doesn't pin down a single notion: we also need to specify the reducibility notion involved. For example, Cai/Sivakumar look at P-completeness with respect to logspace and NC many-one reductions, while "NP-complete" refers to polynomial-time many-one reductions. Changing the reducibility notion changes the completeness (and hardness) notion - for a silly example, everything in P is NP-complete with respect to exponential-time Turing reductions.

So the implication "P=NP implies P-complete=NP-complete" is a non-sequitur, since the implicit reducibility notions are different. P=NP does imply (say) "P-complete w/r/t logspace reductions = NP-complete w/r/t logspace reductions," but that's a completely different thing.


Converting regular (Type-3) grammar to a deterministic finite state automaton I would like to create a deterministic finite state automaton (DFA) M=(Q, Σ, δ, q0, F) that is accepting the language generated by the following regular grammar (RG) G=(N, Σ, P, S). In short I want to convert RG to DFA.

G = ({S,A,B},{a,b},P,S)
P = {
S -> aA | bB,
A -> aS | a,
B -> bS | b
}

I have found these rules that convert RG to a finite automaton (which might not be deterministic if I think correctly).

1. δ(B, a) = C if B → aC ∈ P
2. δ(B, a) = K if B → a ∈ P
   K ∈ F
3. δ(K, *) = emptySet
   i.e. q0 ∈ F, if S → ε ∈ P
   I dont understand rule 3

Now I am using these rules on G this way.

A -> aS
becomes
δ(A, a)=S
according to
1st rule

A -> aS
becomes
δ(A, a)=K
according to
2nd rule

Now I already have

δ(A, a)=S
δ(A, a)=K

which means the automaton is not deterministic because

δ(A, a)={S,K}

Am I doing something wrong?

As Rick Decker said, the algorithm doesnt guarantee that the conversion from G will yieald a DFA. Therefore I should convert to a NFA and than to the DFA. The howto is here.


How does value decompression work for Facebook's Gorilla in the case where count of leading zeroes is not stored I am referring to this paper: http://www.vldb.org/pvldb/vol8/p1816-teller.pdf

My question is regarding section 4.1.2 where it says:

  When XOR is non-zero, calculate the number of leading and trailing zeros in the XOR, store bit ‘1’ followed
  by either a) or b):

  (a) (Control bit ‘0’) If the block of meaningful bits
  falls within the block of previous meaningful bits,
  i.e., there are at least as many leading zeros and
  as many trailing zeros as with the previous value, use that information for the block position and just store the meaningful XORed value.

When decompressing, how do we know if we should add leading zeroes or tailing zeroes? For example lets say we have following 48 bits numbers:

A = 0xfff ffff fffff
B = 0xfff 0000 fffff
C = 0xfff 0ff0 fffff

and

A xor B = 0x000 ffff 00000

B xor C = 0x000 0ff0 00000

If we follow the compression algorithm for A xor B we will store the number of leading zeroes , which is 12, as well as the meaningful bits ffff.

Now, for B xor C because "there are at least as many leading zeros and as many trailing zeros as with the previous value", so we only store the meaningful bits ff. When I want to decode ff, base on previous compressed bits, I know that I have at at least 12 leading zeroes and 20 tailing zeroes, but I still need to fill in 8 zeros; should I do ff00 or 00ff or other combination?

I found my answer after reading the reference implementation: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

The use of the term "meaningful bits" in the paper is ambiguous. I thought the sentence "use that information for the block position and just store the meaningful XORed value." means to store the bits with all the trailing and leading zeroes stripped because "meaningful XORed value" is a value with no leading and trailing zero. But, according to reference implementation you just strip off same amount of leading and trailing zeroes as previous value delta; the meaningful bits in this case may still contain some leading and trailing zeroes.

So, for the example in the question, we should store 0ff0 as meaningful bits instead of just ff.


Is this method really uniformly random? I have a list and want to select a random item from the list.
An algorithm which is said to be random:

When you see the first item in the list, you set it as the selected item.
When you see the second item, you pick a random integer in the range [1,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.
For each item you see, you increase the count, and with probability 1/count, you select it. So at the 101st item, you pick a random integer in the range [1,101]. If it's 100, that item is the new selected node.

Is it really uniformly random?
My thoughts are:
As the number of nodes increases, the probability for them being selected
decreases, so the best chance of selection is for items 1, 2, 3, ..., not for 20, 21, ..., 101.
Each node will not have equal probability of being selected.
Please clarify, as I have trouble understanding this.

The algorithm works, but to understand why, you need to know basic probability theory. The idea is to prove by induction that at step $t$, the currently selected algorithm is uniform among the first $t$ elements. This is clearly the case when $t=1$. Assume now the induction hypothesis for time $t$, and consider what happens at time $t+1$. With probability $1/(t+1)$, the element at position $t+1$ is selected. With probability $t/(t+1)$, the previously selected element is retained. By assumption, this is a uniformly random element among the first $t$ ones, and so the probability that any given element out of the first $t$ is selected is $t/(t+1) \cdot 1/t = 1/(t+1)$. In total, we see that each of the first $t+1$ elements is selected with the uniform probability $1/(t+1)$.

If you don't like induction, you can also do it all at once. For item $i$ to be selected as the output of the algorithm, it needs to have been selected at time $i$, and to not have been dropped at any further time. If there's a total of $n$ elements then this happens with probability
$$ \frac{1}{i} \cdot \frac{i}{i+1} \cdot \frac{i+1}{i+2} \cdots \frac{n-2}{n-1} \cdot \frac{n-1}{n} = \frac{1}{n}. $$


$L$ APX-hard thus PTAS for $L$ implies $\mathsf{P} = \mathsf{NP}$ If $L$ is an APX-hard language, doesn't the existence of a PTAS for $L$ trivially imply $\mathsf{P} = \mathsf{NP}$?

Since for example metric-TSP is in APX, but it is not approximable within 220/219 of OPT [1] unless $\mathsf{P} = \mathsf{NP}$. Thus if there was a PTAS for $L$ we could reduce metric-TSP using a PTAS reduction to $L$ and thus can approximate OPT within arbitrary precision.

Is my argument correct?

[1] Christos H. Papadimitriou and Santosh Vempala. On the approximability Of the traveling salesman problem. Combinatorica, 26(1):101–120, Feb. 2006.

Some people (including more than one moderators) complained to me for posting an answer based on a comment, and I am tired of defending me from them.  I asked them to delete this answer.


Is HORN-SAT in LIN, if so why is that not an indication that P=LIN? The Complexity Zoo defines $LIN$ to be the class of decision problems solvable by a deterministic Turing machine in linear time.

$$LIN \subseteq P$$

Since HORN-SAT is solvable in $O(n)$ (as indicated in Linear-time algorithms for testing the satisfiability of propositional horn formulae (1984))

  New algorithms for deciding whether a (propositional) Horn formula is satisfiable are presented. If the Horn formula $A$ contains $K$ distinct propositional letters and if it is assumed that they are exactly $P_1,…, P_K$, the two algorithms presented in this paper run in time $O(N)$, where $N$ is the total number of occurrences of literals in $A$.

I am wondering why we can't conclude that

$$LIN = P$$

given that HORN-SAT has also been proven to be $P$-complete under log-space reduction? I must be missing something. Or is that a well-known fact?

(I have yet thoroughly gone through the 1984 paper so I don't quite understand the algorithms for solving HORN-SAT in linear time, and thus I may have misunderstood the implication.)

The deterministic time hierarchy theorem precludes all problems in P being decided in linear time.  If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll find that the reduction itself requires more than linear time.


jump to MMIO address In the ARM architecture, what happens on executing a jump instruction whose jump target address is an MMIO address (or in paging mode, a virtual address that is mapped to an MMIO address)?
Would this such an instruction abort?
If it succeeds and sets the EIP accordingly, what happens next: Will the CPU actually fetch the next instruction by reading MMIO address (which may be connected to a peripheral device)?

If it succeeds, reasoning about such a CPU seems problematic because reads and writes to IO addresses are potentially visible to the outside world, unlike DRAM. For example, the effect of out-of-order instruction prefetching will be visible to the outside world via IO.

The MMIO is read into instruction cache, and the code executes as normal. The instruction cache assumes that the contents of memory underneath it do not change unless the cache is explicitly flushed.

Not only does this work, it's common practice to execute code directly from flash devices in very small embedded applications.


Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?
If it is true how to prove it?

Update

It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then $A$ is recursive. but by $A \leq_m\bar{A}$ I can't deduce that $\bar{A}$ is r.e.

Hint: If $A$ reduces to $\overline{A}$ then $\overline{A}$ reduces to $A$ (using the same reduction).


Interpolation Optimization Problem I will try to give the motivation behind this problem and later the math formality.
Given a grayscale image (1 Channel - M by N Matrix).
Someone marks some pixels as anchors.
Now, you need to interpolate the other pixels (Which are not anchors) by minimizing a given cost function s.t. the end result is an image which has the original image values at the anchors and interpolated values else were s.t. it minimizes the cost function.

Given an $M$ by $N$ matrix (A 1 channel image for that matter) $ I $.

Subset of the elements (Pixels) in the matrix are marked as reference and their location is a group marked as $ S $.

The optimization cost function is given by:

$$ \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2, \text{ s.t. }  \forall p \in S \; E(\mathbf{p}) = I(\mathbf{p})\,, $$

where a bold letter $ \mathbf{p}, \mathbf{r}, \mathbf{s} $ means an element (Pixel) location.

The group $ N(r) $ is the neighborhood of $ \mathbf{r} $, which is size $ k $ namely, a $ k  $ by $ k $ rectangle where $ \mathbf{r} $ is in the middle.

The weights $ {w}_{\mathbf{rs}} $ are defined as following:

$$ {w}_{\mathbf{rs}} \propto \exp\left(-\frac{(I(\mathbf{r}) - I(\mathbf{s}))^2}{2\sigma^2_r} \right )\ \ \text{ s.t. } \sum_{\mathbf{s} \in N(\mathbf{r})} w_{\mathbf{rs}} = 1\,. $$

Namely, the weights are normalized to 1 within the neighborhood. The variance is calculated on the matrix $ I $ in the neighborhood (You can assume it is given).

So the problem is to find a matrix $ E $ which is equal to $ I $ on all reference points and interpolates other places by bringing the cost function to minimum.

It looks like a weighted least squares per neighborhood (The inner brackets).

I couldn't formalize it (For the whole matrix) a way that can be easily calculated and solved in e.g. MATLAB.
Is there a way to formalize it as classic Weighted LS problem?
Or any other form which using the classic tools will bring solution (Get the interpolated matrix)?

Could any one help with that?

P.S.
I tried using the Weighted LS per neighborhood disregarding the rest didn't yield the expected results (Obviously).
Tried it just to see how far the real solution is from this naive solution.

Using few tricks the equation can be transformed into classic Quadratic Programming problem:

$ E = \arg \max_{E} \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2 $

Defining $ \mathbf{e} = vec \left ( E \right ) $, Namely vectorizing the matrix, and defining a matrix $ A $ defined the proper usage of the weights $ {w}_{\mathbf{rs}} $, Namely put them in the correct entry at each row per pixel the above could be rewritten as:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left ( \mathbf{e} - A\mathbf{e} \right ) }^{T} \left ( \mathbf{e} - A\mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) $$

Defining $ B = I - A $ yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} {B}^{T} B \mathbf{e} $$

Defining $ L = {B}^{T} B $ , namely $ L , is a Symmetric Positive Definite Matrix yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}  $$

Adding the equality constraints using $ C \mathbf{e} = \mathbf{t} $ where $ \mathbf{t} $ is vectorization of all "Reference Pixels"

All in all this yields a Classic Quadratic Programming problem given by:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}, \; s.t. \; C \mathbf{e} = \mathbf{t} $$

Few notes:

The matrix $ L $ is Symmetric and Positive Definite matrix and usually sparse (Assuming "Small Neighborhood").
The matrix $ L $ wast built by the Matrix $ I - A $ which each row of it was normalized to be zero (Each row of $ A $ is normalized to 1 ).

Now two things are needed:

Optimized fast algorithm to solve this problem utilizing its properties.
Assuming the image is large, are the methods to solve this problem by blocks to avoid memory limits?


Running time for Breadth-First-Search vs Depth-First-Search Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$.
I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.

Is it because DFS is guarenteed to visit all vertices and hence has the lower bound $\Omega(V+E)$?

Note: I am studying the CLRS book, which is where the running times is coming from

The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study).

It is not surprising that the CLRS book presents the running time of BFS as $O(V+E)$ even though $\Theta(V+E)$ is the optimal asymptotic bound for its running time. It is actually a general practice that the running time of an algorithm is described in term of big $O$ even though it might be possible to describe in term of big $\Theta$. The reason is that how tight we can bound the  running time of an algorithm from above is the major concern for many situations.


Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings I'm trying to understand this dynamic programming related problem, adapted from Kleinberg's Algorithm Design book.

You’re consulting for a group of people (who would prefer not to be
mentioned here by name) whose jobs consist of monitoring and analyzing
electronic signals coming from ships in coastal Atlantic waters. They want
a fast algorithm for a basic primitive that arises frequently: “untangling” a superposition of two known signals. Specifically, they’re picturing a situation in which each of two ships is emitting a short sequence of $0s$ and $1s$ over and over, and they want to make sure that the signal they’re hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows.

Given a string $x$ consisting of $0s$ and $1s$, we write $x^k$ to denote $k$ copies of $x$ concatenated together. We say that a string $x$ is a repetition of $x$ if it is a prefix of $x^k$ for some number $k$. So $x = 10110110110$ is a repetition of $x = 101$. We say that a string $s$ is an interleaving of $x$ and $y$ if its symbols can be partitioned into two (not necessarily contiguous) subsequences $s'$ and $s''$, so that $s'$ is a repetition of $x$, and $s''$ is a repetition of $y$. (So each digit in $s$ must belong to exactly one of $s'$ or $s''$.) For example, if $x = 101$ and $y = 00$, then $s = 100010101$ is an interleaving of $x$ and $y$, since characters at position $1,2,5,7,8,9$ form $101101$—a repetition of $x$—and the remaining characters form $000$—a repetition of $y$.

In terms of our application, $x$ and $y$ are the repeating sequences from the two ships, and $s$ is the signal we’re listening to: We want to make sure $s$ “unravels” into simple repetitions of $x$ and $y$. Give an efficient algorithm that takes strings $s, x,$ and $y$ and decides if $s$ is an interleaving of $x$ and $y$.

Let's use caps, S for input string, A for x and B for y. Furthermore, let |S| = lenS, |A| = lenA, |B| = lenB.

With any Dynamic Programming problem, it is useful to append to the problem:

  "... demonstrate one such solution." or, equivalently
  "... provide one such proof certificate."

This is because a Dynamic Programming solution is equivalent to searching over proof certificates. For this problem, what's a proof certificate? There are many possibilities. One of them is: Strings over {a, b} of length lenS.

  Certificate aabbaa encodes: S[1] = A[1], S[2] = A[2], S[3] = B[1], S[4] = B[2], S[5] = A[3],... where array indices in A & B wrap around i.e. A[r + lenA] = A[r].

Clearly, S is an interleaving of A & B if and only if such a proof certificate exists. The task now boils down to finding one such certificate, if it exists.

Source code in C++ (Repl: https://repl.it/@vemana/csstackexchange#interleaving/main.cpp)

#include <bits/stdc++.h>

using namespace std;

const int MAX_LENS = 100, MAX_LENA=100, MAX_LENB=100;

// Memoization array
// Initialize: to -1.
int memo[MAX_LENS][MAX_LENA][MAX_LENB];

// Initialize: to 0
// Encodes the Proof Certificate, C
// SELECT[r] = 1 implies C[r] = a
// SELECT[r] = 2 implies C[r] = b
int SELECT[MAX_LENS][MAX_LENA][MAX_LENB];

// The input strings
string S, A, B;

// Initialize: lenS = S.size(), lenA = A.size(), lenB = B.size()
// Expected: lenS > 0, lenA > 0, lenB > 0
int lenS, lenA, lenB;

vector<string> getCertificate() {
  if (SELECT[0][0][0] == 0)
    return vector<string>(); // No solution

  vector<string> ret(2);

  int s = 0, a = 0, b = 0;
  while(s < lenS) {
    if (SELECT[s][a][b] == 1) {
      ret[0] += A[a];
      ret[1] += '_';
      a = (a+1)%lenA;
      s = s + 1;
    } else {
      ret[0] += '_';
      ret[1] += B[b];
      b = (b+1)%lenB;
      s = s + 1;
    }
  }
  return ret;
}

// Finds certificate for S[s...lenS] where
// next index in A is a (0 based)
// next index in B is b (0 based)
//
// Returns 0 if not found
// Returns 1 if found
int findCertificate(int s, int a, int b) {
  if (s == lenS)
    return 1; // Found the "empty" certificate.

  int& ret = memo[s][a][b];
  if (ret != -1)  // already computed
    return ret;

  // Try to match S with A
  bool takeA = (S[s] == A[a]) && findCertificate(s+1, (a+1)%lenA, b) == 1;

  // Try to match S with B
  bool takeB = (S[s] == B[b]) && findCertificate(s+1, a, (b+1)%lenB) == 1;

  if (takeA) {
    SELECT[s][a][b] = 1; // SELECT A to extend the certificate
    return ret = 1;
  }

  if (takeB) {
    SELECT[s][a][b] = 2; // SELECT B to extend the certificate
    return ret = 1;
  }

  return ret = 0; // Neither matched. So, no certificate found
}

// Just run with ./a.out < in
// File 'in' has three strings, one per line, representing A, B & C.
int main() {
  // initialize S, A, B, lenA, lenB, lenS, SELECT, memo

  cin >> A;
  cin >> B;
  cin >> S;
  lenA = A.size();
  lenB = B.size();
  lenS = S.size();
  memset(memo,-1,sizeof(memo));
  memset(SELECT, 0, sizeof(SELECT));

  int out = findCertificate(0, 0, 0);
  vector<string> cert = getCertificate();
  string output = cert.empty() ? "NOT INTERLEAVED" : ("INTERLEAVED\n" + cert[0] + "\n" + cert[1]);
  cout << output << endl;
  return 0;
}


complexity - Non Polynomial reduction I have a question, does non-polynomial reduction exists for all problems?
the issue is only regarding polynomial reductions?

You can show that it is not the case that every two languages are reducible to each other using a counting argument. Consider the class of all  languages $ 2^{\Sigma^*}$. If by contradiction every two languages are reducible to each other, then every language is an $2^{\Sigma^*}$-hard language (in particular, there is a language that all languages reduce to). One can show that there are more languages than reductions. Thus, an $2^{\Sigma^*}$-hard language
must have two different languages that reduce to it using the same reduction, but this is impossible.
More formally, assume by contradiction that there is an $2^{\Sigma^*}$-hard language $L$. We know that there are $2^{\aleph_0}$ languages, yet, as there are only $\aleph_0$ TMs, there are also only $\aleph_0$ reductions. Then, it follows that there are distinct languages $A$ and $B$ such that
$A \leq_m L$ and $B \leq_m L$, but the reductions from $A$ and $B$ to $L$ coincide. Denote this reduction
by $f$. Since $A\neq B$, there exists w.l.o.g a word $x\in A\setminus B$. Since $f$ is a reduction from $A$ to
$L$, we get that $f(x) ∈ L$. But $f$ is also a reduction from $B$ to $L$, and thus we get that $f(x) \notin L$, and we
reached a contradiction.


Find the number of words in a language of given length I was asked the following question:

  Consider the language $S^*$, where $S = \{ab, ba\}$, write out all the words that have seven or fewer letters?

How do I go about calculating the number of words? Are there any resources that break this down to the most basic level?

You can solve the general problem using linear algebra. First, construct a DFA for the language $S^*$. Then, describe its transition function in matrix form: if the state space is $Q$, construct a $Q \times Q$ matrix $A$ in which $A(s_1,s_2)$ is the number of letters that would cause a transition from $s_1$ to $s_2$. If $s$ is the starting state, let $1_s$ be the corresponding vector, and let $j$ be the all-one vector. The number of words of length exactly $n$ is $1_s A^n j$ (or perhaps $j A^n 1_s$ if I mixed things up). You can use the spectral decomposition of $A$ to get a formula, or you can calculate it quickly using repeated squaring.

That is the general theory. In your case, it's not too hard to enumerate all words of length up to $7$ by hand. I challenge you to do that.


Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two strings that have a hamming distance of 1.
For example, if I generate the string 0123456789 then I never want to generate any of these strings: {1123456789, 2123456789, 3123456789, ...}
What is the largest set of unique strings in the universe of possible strings that satisfy the constraint where no two strings have a hamming distance of 1? If this set can be identified, is there any reasonable way to enumerate it?

There is a simple solution: use exactly the strings with sums of digits being divisible by $10$. There are $10^9$ such strings and it is easy to enumerate them, find $i$-th of them in the lexicographic order, generate random such string, et cetera.
Indeed, if two strings differ in exactly one position, then their sums of digits are also different modulo $10$. For example, the sums of digits for strings $0123456789$, $1123456789$, $\ldots$, $9123456789$ are $45$, $46$, $\ldots$, $54$ respectively.
Moreover, this solution is largest possible. Indeed, there are $10^9$ such strings: for every way to choose first $9$ digits, there is an exactly one way to choose the last digit to make the sum divisible by $10$. Hence, there are $10^9$ strings in our set.
On the other hand, any set of strings with minimal Hamming distance $2$ has at most $10^9$ elements. Indeed, consider $10$ strings with a given prefix of length $9$. They all are within Hamming distance $1$ of each other (because they differ only in the last position). Hence, at most one of them can belong to any "good" set. Therefore, any "good" set contains at most $10^9$ elements.


Real RAM computational mode Given a real value $M>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number sufficiently close to $M$?

In Real RAM precision is infinite, this comes straight from definition: it uses exact real numbers. As you have noticed this is purely theoretical model. It is also worth notting that real-RAM model gives enormous computational boost from standard RAM model where each cell uses only fixed length, called machine word.

For hardware (practical one), using something like IEEE754, these are not real numbers, but fixed-precision representation, with sign, significand and exponent. Common float has about seven digits of precision. There are types using 24, 32, 64, 80, 128... bits.

If you want to model something with practical indication in mind, do not use real-RAM as it is too powerful.


Why are Chess, Mario, and Go not NP-complete? I have a hole in my understanding of what makes a problem NP.

I understand that Mario, for example, is NP-hard - it can be reduced to the NP-complete problem of 3SAT (see https://www.youtube.com/watch?v=mr1FMrwi6Ew)

Therefore if these games were also in NP, they would be NP-complete (by definition).

My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly. Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?

It's a common misconception that chess is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces. The question is, given a certain position on an nxn board, will white win if both players play perfectly? There may be a "yes" answer and the certificate for NP might be a list of perfect moves for both players, but it's intractable to check if those moves by black are actually perfect. Maybe black has better moves so that white doesn't win. You can't check such a certificate in polynomial time.

Also, it may even be the case that a game takes an exponential number of moves, so that such a certificate is of exponential length.


Is there an Algorithm that can code itself? Suppose there is algorithm that has a strong NLP module. Could it use the NLP module to read text books such as http://www.amazon.in/Artificial-Intelligence-Modern-Approach-Prentice/dp/0136042597 in text form, parse it, understand the semantics and then use the knowledge to improve the very code it's written in ?
Like a virtual computer scientist? Is any research group working on it or even thought of that idea?

While there are no program synthesizers that can synthesize themselves in their entirety, plenty of synthesizers can synthesize pieces of themselves. Rohit Singh, for instance, has a project using the Sketch synthesizer to optimize many logical solvers, including that of Sketch itself.


NSA Recommended Cryptography Algorithms changes from a single paper I know that the NSA has recommended cryptography algorithms, such as their A/B suite algorithms and their Commercial National Security Algorithms Suite. I also know that they change their recommendations for key size, an example being in 2019 when they changed the key size recommended for RSA and Diffie Hellman from 2048 to 3072.
Are there any examples of changes like this that have been directly prompted by the publication of a mathematical paper or the creation of an algorithm? When people ask me about the applications of prime numbers to cryptography I want to be able to cite a specific time where math has changed real word cryptography recommendations.

There are many examples in cryptography.  Much of progress in cryptography is driven by academic research.
The Advanced Encryption Standard (AES) was a result of a request for research from the National Institute of Standards and Technology.  Two cryptographers proposed a new algorithm, which was eventually adopted as the standard.  A bit over a year ago NIST released a report estimating that there was $250 billion in economic benefit from the AES standard.  This can be directly traced back to academic research.  This doesn't involve prime numbers or number theory, though.
Key sizes and algorithm design typically comes out of academia.  The RSA algorithm was created by academics who published a research paper proposing the algorithm (which in turn built on prior research from others, such as Hellman and Diffie), and has been extremely widely used to protect digital infrastructure -- including secure browsing and other uses.
Research has played a major role in setting parameters and key sizes for cryptographic algorithm; see, e.g., https://en.wikipedia.org/wiki/Key_size for a number of examples.
Caveat: many of the researchers doing this work might self-identify as computer scientists more than mathematicians.  But the lines between theoretical computer science and applied mathematics in this area are blurry.


Difference between Parallel and Concurrent programming? When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel.

And some programming languages specifically claim support for parallel programming, such as Java.

Does this means parallel and concurrent programming are actually different?

Distinguish parallelism (using extra computational units to do more work per unit time) from concurrency (managing access to shared resources). Teach parallelism ﬁrst because it is easier and helps establish a non- sequential mindset.

From " A Sophomoric∗ Introduction to Shared-Memory Parallelism and Concurrency" by
Dan Grossman (version of November 16, 2013)


Simple majority classifier question one of my training questions for my exam is the following one:

  Suppose you are testing a new algorithm on a data set consisting of
  100 positive and 100 negative examples. You plan to use leave-one-out
  cross-validation (i.e. 200-fold cross-validation) and compare your
  algorithm to a baseline function, a simple majority classifier. Given
  a set of training data, the majority classifier always outputs the
  class that is in the majority in the training set, regardless of the
  input. You expect the majority classifier to achieve about 50%
  classification accuracy, but to your surprise, it scores zero every
  time. Why?

My only solution about it is that the training data is inverse to the real data.
But I'm not sure about my answer. May anybody help me?

Regards,

Patrick

You have 100 examples of the positive class and 100 examples of the negative class.

Now you do:

examples = "List of all 200 examples"
accuracies = Empty list
for(i=0; i<|examples|; i++) {
    one = examples[i]
    training = examples \ {one}

    # !!!!!!!!!!!!!!!!!!!!!!!!!
    majority_clf = get majority in training. This is the other class than the class of "one"
    # !!!!!!!!!!!!!!!!!!!!!!

    accuracies.append(majority_clf.predict(one) == class(one))
}
overall_accuracy = sum(accuracies) / |accuracies|


Augmenting AVL tree to calculate sum of subtree Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function
calculateSum(key), which receives a key of a node and returns the sum of its subtree.
I implemented it this way:
sumSubtree(node):
    if node != null:
        return sumSubtree(node.left) + sumSubtree(node.right) + node.key
    return 0

calculateSum(key):
    node = Search(key) // assuming I have a search function
    return sumSubtree(node)

which solves it in $O(\log n)$.
But I read it is possible to maintain the sum during insertion and deletion. And augment an AVL tree this way.
Which solution would be better? Mine, or the other method? Does it matter?

Your solution is traversing the whole subtree on each call to subSubtree so it is actually $O(|T|) \neq O(\log n)$ where $|T|$ is the length of the subtree. If I query the root of the tree it will go over every node, so complexity is $O(n)$.
If you keep the sum of the subtree while modifying it (insertions/deletions) then the pseudo-code will look like:
calculateSum(key):
    node = Search(key) // assuming I have a search function in O(log n)
    return node->size

Search can be implemented in $O(\log n)$ and getting the size is $O(1)$ since it is stored on the node itself, hence the overall complexity will be $O(\log n)$.


What is this type of consistency called in DataRetrieval? I am trying to find the name of this feature that is implemented with SQL Databases:

Given a Record $R^1$ in table having two values for two different fields, e.g.
Let value of field 1 $F_1$ be $V_1$, Let value of field 2 $F_2$ be $V_2$
A any query requiring records s.t. $F_1 = V_1$ should contain $R^1$.
Also any query requiring records s.t. $F_2 = V_2$ should also contain $R^1$.

If a database does not have the above property then it definitely considered broken.

My question is what is the name for this kind of consistency?

I would call it expected consistency.

Unless you are just defining the $=$ operator.

When you get into transactions can have uncommitted or dirty value. By default $=$ will only match committed values but you can search on the uncommitted value. Look up ACID around data consistency.

Also careful with any as with an AND condition it needs to satisfy both so you may not get $R^1$ for $F_2 = V_2$ if another AND condition is not satisfied.


NP languages definition Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not?
Because I need to have an informal definition of that, in order to give just an idea of it, without using formalism.
Otherwise how could I define it roughly speaking?

Is it good to define a language $\mathcal{L}$ in NP as a language for
  which, given an element $x$, it is possible in polynomial-time to
  check whether $x \in \mathcal{L}$ or not?

No. If you could do that you could "check" that this language would be in P, because you can check (or more formally decide) all possible words for membership in polynomial time this way.

A correct formulation would be:

  A language $\mathcal L$ is in NP if for every word $x$ in the language there exists a witness $w$ which is of length polynomial in the length of $x$ and given the witness and the word you
  can verify language-membership in polynomial time.

Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.


Languages accepted by modified versions of finite automata A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide some transition for all elements of the input alphabet; in other words, the transition function $\delta : Q \times \Sigma \rightarrow Q$ should be a (total) function.

Imagine what we will call a doubly deterministic finite automaton (DDFA). It is defined similarly to a DFA, with two exceptions: first, instead of the transition leading from one state to one other state for every possible input symbol, it must lead to two distinct states; second, in order to accept a string, all potential paths must satisfy either one or the other of the following conditions:

All potential paths through the DDFA lead to an accepting state (we will call this a type-1 DDFA).
All potential paths through the DDFA lead to the same accepting state (we will call this a type-2 DDFA).

Now for my question:

  What languages do type-1 and type-2 DDFAs accept? Specifically, is it the case that $L(DFA) \subsetneq L(DDFA)$, $L(DDFA) = L(DFA)$, or $L(DDFA) \subsetneq L(DFA)$? In the case that $L(DDFA) \neq L(DFA)$, is there an easy description of $L(DDFA)$?

Proofs (or at least moderately fleshed-out sketches) are appreciated, if they aren't too complicated.

This combined with Alex's answer give the complete picture.

$L(DDFA)\subseteq L(DFA)$ can be proven by adapting the usual powerset construction with a modified final state condition. In the power set construction, states are sets of states from the original automaton. Usually after performing the powerset construction, a state is final if one of the states in the set is final in the original automaton.

In type-1 DDFA, final states in the constructed automaton are the sets where all elements are final in the original automaton.
In type-2 DDFA, final states are the singleton sets of the final states from the original automaton.

In both cases, the resulting automata are DFAs.

Now type-2DDFA's can express only the languages $\{\epsilon\}$ and $\emptyset$, depending on whether the starting state is accepting or not. This is because the two transitions from a state need to go to distinct states, but acceptance is only possible if they end up on the same state.


Is there a metric for the similarity of two image filters? Definitions

An image filter is a matrix $m \in \mathbb{R}^{k_1 \times k_2 \times k_3}$ which gets applied to an image $I \in \mathbb{R}^{l_1 \times l_2 \times l_3}$ as a discrete convolution

$$I'(n_1, n_2, n_3) = \sum_{i=0}^{k_1} \sum_{j=0}^{k_2} \sum_{k=0}^{k_3} I[n_1-i - \lfloor \frac{k_1}{2} \rfloor, n_2 - j - \lfloor \frac{k_2}{2} \rfloor, n_3 - k - \lfloor \frac{k_3}{2} \rfloor] \cdot m[i, j, k]$$

There are some well-known filters like Laplace filters, Prewitt filters, ... (see my interactive example)

For example, for an RGB image $k_3 = 3$ and $k_1, k_2$ are width and height.

Question

Is there a metric to compare the similarity of image filters?

Context

Convolutional Neural Networks (CNNs) learn image filters. As they are randomly initialized, the filters they learn are different each time you train them. I am interested in quantifying those differences.

I could, of course, use any metric for elements of $\mathbb{R}^{k_1 \times k_2 \times k_3}$. However, consider the filters

$$
\begin{align}
m_1 &= \begin{pmatrix}-1&0&1\\-1&0&1\\-1&0&1\end{pmatrix}\\
m_2 &= \begin{pmatrix}1&0&-1\\1&0&-1\\1&0&-1\end{pmatrix}\\
m_3 &= \begin{pmatrix}-0.9&0.1&1\\-0.9&0.1&1\\-0.9&0.1&1\end{pmatrix}\\
\end{align}
$$

For the image

$m_1$ produces

and $m_2$ produces

You can see a difference, but much less than for the result of $m_3$:

This is probably not captured by most metrics. Another idea was to apply the metrics to the processed images on a given dataset, but this would make the results depend on the dataset and be computationally very intensive.

(In case you want to try image filters yourself with Python: https://gist.github.com/MartinThoma/f51a1044c4abc6c7b81915ef96b7cfbd)

The ‘k-translation correlation’ is probably a good candidate for what you are looking for. It measures the maximum correlation between a pair of two filters $\mathbf{W_i}$ and $\mathbf{W_j}$ achieved by translating one filter up to k steps along any spatial dimension and then selecting the maximum thereof:

$$\rho_k(\mathbf{W_i,W_j})=\max_{(x,y)\in \{-k,...,k\}^2\setminus(0,0)} \frac{\langle\mathbf{W_i}, T(\mathbf{W_j}, x,y)\rangle_f}{\left \|  \mathbf{W_i}\right \|_2 \left \|  \mathbf{W_j}\right \|_2}\,,$$

where $T(\cdot, x,y)$ refers to the translation of its first operand by $(x,y)$ and $\langle\cdot,\cdot\rangle_f$ denotes the flattened inner product of the two filters (the second of which is translated). Note that both filters are reshaped to column vectors to perform the inner product. For more details refer to Doubly Convolutional Networks (Zhai, Cheng, Lu, Zhang, in Proceedings of 30th Conference on Neural Information Processing Systems (NIPS 2016)).


If a sparse language is NP-complete then are all NP languages sparse? If a Sparse Language is NP-complete then are all NP languages sparse? We say a language is sparse if $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n}| \leq p(n)$, for some polynomial $p(n)$?

If we only consider the latter half of the question: "are all NP languages sparse", the answer is no. A counterexample is $\{0,1\}^*$. It belongs to NP but is not sparse.

However, you added a precondition: "a sparse language is NP-complete", and $A\rightarrow B$ is true if $A$ is false, so the answer depends on whether there exists a NP-complete sparse language. Since it remains open whether there exists a NP-complete sparse language, your question also remains open.


How to prove that a system is real-time? I'm writing a paper on the system I designed which upon receiving an event, performs a number of calculations and publishes the result to several subscribers. I can calculate the amount of time it takes from the moment the system is informed about the event, to the moment when all subscribers successfully received the calculation results. I perform multiple experiments to measure the amount of time for a various number of subscribers.

In my paper, I'm claiming that my system is capable of real-time responses to the first event. Could you please give me some hints that how I can prove that based on the data I collected? Thanks

It depends on your definition of "real-time system".  A standard definition is: a system is real-time if it will respond within $T$ seconds, with probability at least $P$.  Here you need to fill in the parameters $T,P$; e.g., it might be $T = 1$ millisecond and $P = 0.999$.

How do you prove that this condition is met?  One way is to find a way to generate random workloads, from the same distribution as the system will be exposed to in practice, and count how often the system meets the deadline and how often it doesn't.  Another way is to prove a theorem (e.g., with formal methods) about the maximum time it might take to respond; see the literature on worst-case execution time analysis.  The latter might be particularly challenging in many cases.

There's an entire literature on this topic, that you can read more about.


Must a deadlock necessarily occur if the four conditions exist? I understand the four necessary conditions, mutual exclusion, hold and wait, no preemption, and circular wait, for deadlock to occur. However, does there exist a situation where the four conditions are true and the system is not in a deadlock state?

If a deadlock occurs, there exist the four conditions. However, if there exist the four conditions, is there necessarily a deadlock? What is an example where the four conditions exist, and a system is not in a deadlock state?

If you have a set of processes that wait for each other in a circular way, than you have a deadlock in this particular moment. This means that there is no situation where the four conditions are satisfied and there is no deadlock.

It may happen that a process stops waiting, for example due to some timeout mechanism realized by the developer. This breaks the circular wait relationship and the system continues to work.

The confusion often comes from the fact that conditions 1-3 are prerequisites for condition 4:

Without mutual exclusion in the resource access, there is no reason for the processes to wait on anything, so the circle is never created.
Without hold and wait, you have either only outgoing or only incoming connections for all the nodes (processes) in the dependency structure. Given that, you cannot form a circle.
With preemption in place, you can always break the circle by taking a resource your are waiting for away from another process. Given that, you never end up in a waiting circle.

This shows that conditions 1-3 are system design properties, while condition 4 is a run-time situation. There is programming language research that tries to ge rid of the three design conditions, so that condition 4 becomes impossible by default.


Is $2^n$ steps enough to tell if DTM will run forever? In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time.

My question is: how is it that $2^{|f(x)|}$ steps is enough to tell if machine $M$ will run forever or not?

More precisely, if a deterministic Turing machine has an alphabet $\Sigma$, and a set of states $|Q|$ and consumes at most $f(|x|)$ space then the maximum number of configurations the machine can have is $$|Q|\times f(|x|) \times|\Sigma|^{f(|x|)}$$
This is because the maximum length of the tape portion (cells in fact used by the machine) is $f(|x|)$, the head of Turing machine at any time can be located on one of the $f(|x|)$ cells, the machine may be in $|Q|$ different states, and this portion of the tape can be filled in $|\Sigma|^{f(|x|)}$ different ways (using alphabet symbols).

If $q=|Q|$ and $|\Sigma| = 2$ (binary alphabet) then we have
$$qf(|x|)2^{f(|x|)}$$
different configurations.

Each step of a Turing machine may change machine's state, tape content, or the position of the head. So after $qf(|x|)2^{f(|x|)}$ steps if the machine hasn't yet halted it must repeat the configuration: $\langle$ state, tape content, head position $\rangle$ meaning the machine will loop forever. So I would say it needs $O(f(|x|)2^{f(|x|)})$ steps rather than $O(2^{f(|x|)})$.


Graph theory: determining maximum number of edges Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful for why the maximum number is 5/2|V|.

The following identity is well-known:
$$
2|E| = \sum_{v \in V} d(v).
$$
In words, if we sum all degrees in a graph, we get twice the number of edges. To see this, divide each edge $(x,y)$ into two halves: the $x$-half and the $y$-half. We think of the $x$-half as a half-edge labeled $x$. The left-hand side counts the number of half-edges. On the right-hand side, $d(v)$ counts the number of half-edges labeled $v$, and so in total, the right-hand side also counts the number of half-edges.

If the graph has maximum degree $\Delta$ (in your case, $\Delta = 5$) then
$$
2|E| = \sum_{v \in V} d(v) \leq \sum_{v \in V} \Delta = \Delta |V|,
$$
and so $|E| \leq (\Delta/2) |V|$; there is equality if the graph is $\Delta$-regular (all degrees are exactly $\Delta$).


Trouble understanding how to pick constants to prove big theta So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta.

I understand that the definition of $\Theta$ is as follows:

  $\Theta(g(n)) = f(n)$ if there exists positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$.

In other words, for $f(n)$ and $g(n)$, $f(n)$ can be bounded by $c_2 g(n)$ from above and bounded below by $c_1 g(n)$.

So the example in the book goes:

  Show that $\frac{1}{2} n^2 - 3 n = \Theta(n^2)$.

From the definition of big theta:

$$ c_1 n^2 \le \frac{1}{2} n^2 - 3 n \le c_2 n^2$$

CLRS begins by dividing by the largest order term of $n$ which is $n^2$ to get

$$ c_1 \le \frac{1}{2} - \frac{3}{n} \le c_2 $$

From here we split the problem into two parts, the right-hand inequality and the left-hand inequality.

On the right hand side: CLRS chooses $c_2 \ge \frac{1}{2}$ because for $n \gt 1$, $\frac{1}{2} - \frac{3}{n}$ can never be less than $\frac{1}{2}$ since $\frac{3}{n}$ goes to $0$ as $n$ goes to infinity. (I'm assuming they choose $n \gt 1$ here because if $n=0$ then we would be dividing by $0$.)

Now this is where I start to get lost.

On the left hand side: CLRS chooses  $c_1 = \frac{1}{14}$ (not sure why) and $n \ge 7$. I'm not sure what the significance of these choices is. At $n \le 6$, $\frac{1}{2}-\frac{3}{n}$ becomes negative. But why $\frac{1}{14}$ for $c_2$? I'm just not sure how they arrived at solving the left hand side and the book doesn't really explain it well for me.

For $n \leq 6$,
$$
1/2 - 3/n \le0,
$$
so if you are taking integer value of $n$, put $n = 7$ as it gives $1/14$. This is how he arrived in the conclusion i.e., for $n \geq 7$,
$$
1/2 - 3/n \ge1/14,
$$
because $n$ is in the denominator it will only decrease the value of -ve term, so overall value will increase with $n$, which is the constant $c_1$.


How can I represent state or environment in the $\lambda$-Calculus? I have seen in different tutorials how to represent numbers and booleans in the pure $\lambda$-Calculus, and  how to define some arithmetic and logic operations. But what if I want to represent other constructs, not usually encouraged in pure functional languages, like state (assignment of values to variables) and sequencing (evaluating $e_1$ before $e_2$)?

For example, how would I encode an assignment "$v := e$" (where $v$ is a variable and $e$ an environment)?  And what about encoding "$x := 2; y := y + x$"? (The point is that there is a dependency among statements, and they should be evaluated/executed in the correct order.)

Such a thing is, for the most part, impossible in the pure lambda calculus: all variables represent immutable values.

However, you can fake it in a number of ways.

The simplest is parameter passing. For a function which has a "state", you give it an extra parameter, which is a data structure mapping variables to their values. Any time you alter a variables value, you just create a new store with the updated value, and use it as the new parameter.

This pattern of passing the state to each computation in sequence can be abstracted using a State monad, or something similar. A state monad provides a pattern where the machinery of creating a new store, updating its values, and correctly passing it to future functions.

Monads provide a sequencing operator, which allow for the ordered evaluation that you mention.

There exists calculi which have mutation built into them, but first off, they aren't the pure calculus as you asked for, and in such cases, you don't encode mutation, you add it as a primitive operation.


Finding all edges of an undirected graph which are in some cycle in linear time As a reduction from another problem, I am trying to deal with finding all edges which are part of some cycle in an undirected graph $G=(V,E)$ in time $O(|V|+|E|)$.

My first idea is to use DFS and search for back edges closing cycles, but then the issue is how to add all edges found to the cycle, if we just naively add all edges each time we find a cycle the algorithm might not be linear as each edge can appear in multiple cycles (a k-clique, for example).

So my current "best" approach of counting the cycles is first building the entire DFS tree, noting where back edges are present, and then traversing the tree in DFS from the root, where each time a back edge (going forward down the tree this time) is encountered, mark all edges as being part of a cycle, and if an edge is already marked break the loop.

I can prove the approach is linear, but I'm having issues proving it actually finds all edges as required. And was wandering if there is either an easier approach or a relatively simple proof that my approach works I'm missing.

It is not difficult to prove that an edge is a cut-edge if and only if it does not lie on a cycle. So you can find the set $E'$ of cut edges, and what you are then looking for is $E \setminus E'$.

For finding $E'$, there are several well-known linear-time algorithms. Wikipedia gives e.g., Tarjan's bridge-finding algorithm.


Construct context free grammar from language I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific:

$\lbrace 0^a1^b2^c3^d4^e5^f |a,b,c,d,e,f \geq 0$ and $a+b=d+e\rbrace$.

My thought process has only gone so far. I see that if you add a 0 you must add a 3 or 4, the same is if you add a 1. And for adding a 3 or 4 the case is very similar. My biggest troubles are due to the characters that lay between the pairs of 0s,1s,3s and 4s. I haven't been able to produce a serious attempt yet, but will post it as an edit if I do. Any help would be appreciated.

Edit: Here is a possible solution I have come to:

$S\rightarrow AB$

$A\rightarrow 0A4|C|D$

$B\rightarrow B5|\epsilon $

$C\rightarrow 0C3|E$

$D\rightarrow 1D4|E$

$E\rightarrow 1E3|F$

$F\rightarrow 2F|\epsilon$.

You are right, the point is having nonterminals that sheds 0 and 4, or 0 and 3, or 1 and 4, or 1 and 3, switching from one to the other to get the $0^1 1^b$ and corresponding $3^d 4^e$; once you have that, go to one that repeats to make $2^c$ in between. The $5^f$ is easy to append.


Why are computable functions also called recursive functions? In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming (i.e., functions that call themselfes).

What is the actual meaning of recursive in the context of computability? Why are those functions called "recursive"?

To put it in other words: What is the connection between the two meanings of "recursiveness"?

The founders of computability theory were mathematicians.
They founded what is now called computability theory
before there was any computers.
What was the way mathematicians defined functions that could be computed?
By recursive definitions!

So there were recursive function before
there were any other model of computation like Turing machines or
lambda calculus or register machines.
So people referred to these function as recursive functions.
The fact that they turned out to be exactly
what Turing machines and other models can compute is a later event
(mostly proven by Kleene).

We have the simple definition of a recursive function which is now called
primitive recursive function.
There were not general enough (e.g. Ackermann's function)
so people developed more general notions
like $\mu$-recursive functions and
Herbrand-Gödel general recursive functions that
did capture all computable functions (assuming the Church's thesis).
Church claimed that his model of lambda calculus captured
all computable functions.
Many people, and in particular Gödel, were not convinced that
these capture all functions that can be computed.
Until Turing's analysis of computation and introduction of his machine model.

The name of the field used to recursion theory.
However there has been a successful push in recent decades
to change the name to something more appealing from
recursion theory to something more computer sciency (vs. mathy).
As a result the field is now called computability theory.
However if you look at books, papers, conferences, etc. in the early decades
they are called recursion theory and not computability theory.
Even the title of Soare's own 1987 book
(who was the main person behind the push to change the name
to computability theory)
is "Recursively Enumerable Sets and Degrees".

If you want to know more about the history
a fun and good place to read about it is
the first chapter of Classical Recursion Theory by Odifreddi.


What is the point of finite automata? Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?

Turing machines express all computation, so studying turing machines is studying computation in general; theorems that are true about all turing machines are true about all computations. Necessarily, these have to be extremely general and rather vague or weak theorems. If the only thing you know about a computation is that it's implementable using a Turing machine, that's very little knowledge to work with.

Finite automata are a very particular class of computations. Because they are so restricted, you can do less using a finite automaton, but you can say/know more about one. There are tons of very useful theorems that are only true for finite automata but not for arbitrary computations; algorithms and data structures for working specifically with finite automata. E.g., in practical terms, if you compile a regular expression to a finite automaton, you know for sure that it terminates in linear time on every input, you can optimize that automaton, you can think of very efficient ways to write finite-automata evaluators, seek ways to implement incremental evaluation, etc. - none of these problems are solvable or even make sense for "computations in general".

Think of the difference between turing machines and finite automata as the difference between all natural numbers and prime numbers. How would you answer if someone asked you why do we need to study prime numbers, when we already have the concept of natural numbers?


Embedding trees of diameter four is NP-hard Suppose that $T$ is a tree of diameter four and $G$ is a graph. Deciding, whether $T$ can be injectively mapped to $G$ is NP-hard (there is a simple reduction from the problem of finding an independent set). I want to use this result as a side remark in my Bachelor's thesis. I believe that this should be a well-known problem, though I was not able to google it. Do you know some relevant literature to this?

It is reducible from Independent Set in cubic graphs.

Given a cubic graph $G(V,E)$, construct a bipartite graph $\mathcal{B}(V\dot{\cup}E,\mathcal{E})$, where $$\mathcal{B}(\mathcal{E})=\{(u,e)|u\in V\ \mathrm{is\ incident\ to}\ e\in E\}$$

Create a new vertex $r$ (the root), connect it to all $V$-vertices in $\mathcal{B}$.

Now, if the IS instance asks for an independent set of size $k$, we create $T$ of diameter $4$ as follows:

Make a new vertex $r_T$ as root of $T$. This vertex would have $k$ children. Each of these $k$ children would have $3$ leaves attached to it.

Our reduction then outputs the instance $\mathcal{B},T$ of $\mathrm{TREE\ EMBEDDING}$ problem.

Note that $k>10^9$, otherwise the vertex cover can be decided in polynomial time. So, if there exists an embedding, $r_T$ must be mapped to $r$.

Since all the leaves are pairwise distinct. The image set of $k$ children of $r_T$ is the independent set.