Synchronizing sequence and Synchronizable DFA I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A Synchronizing sequence for $M$ and $q'$ is a string $s\in \Sigma^*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
Say that $M$ is Synchronizable if it has a synchronizing sequence for some state $q'$.
Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$. Moreover, can you improve upon this bound?

I'm more interested in proving that the synchronized sequence is of length of at most $k^3$ then trying to improve upon this bound.
I tried to prove (with no success) that there exists $w\in \Sigma^*$ which $|w| \leq k^2 $ so that: $\delta(q_1,w)=\delta(q_2,w)$ for two distinct states in $M$: $q_1,q_2\in Q$ (thus, $w$ can be read from two states in the automaton and get to the same final state).
If I prove it, I could construct a word $w$ which will be a synchronizing sequence in $M$ and $|w|\leq k^3$ as required.
Any suggestions?

I think you are on the right track:

Consider two states $q_1,q_2$. We claim the following:

If there exists a word $w$ such that $\delta(q_1,w)=\delta(q_2,w)$, then there is such a word $w$ of length at most $k^2$.

The proof of this a standard shrinking argument: if such a word is longer than $k^2$, then during the runs from $q_1,q_2$, a pair of states repeats, and we can shrink $w$.

Now, since you assume the existence of a synchronizing word for all states, you can proceed to construct a word that synchronizes all the states, pair by pair.


Closure properties of finite state transducers Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$
      consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$.
      Prove that FSTs are not closed under this operation $\Delta(T_1,T_2)$.

What I have tried is to create two FSTs $T_1, T_2$ (as 5 tuple functions of form  $(Q, \Sigma, \Gamma, \delta, s, γ)$  where $\Sigma$ - input symbols, $\Gamma$ - output symbols, $δ\colon Q \times \Sigma → Q$ transition function, to prove that the language $S = \{ w \mid T_1(w) \neq T_2(w) \}$ is not regular. I am having trouble creating the two FSTs. Especially defining the transition functions for the two FSTs. Any help with this is appreciated.Pretty much what I am trying to prove is there are two FST's $T_1$ and $T_2$ such that the language $L = \{w \mid T_1(w) \ne T_2(w)\}$ is not regular. To prove this, what I want to do is create the two FST's $T_1$ and $T_2$. I am not sure on how to define a 6-tuple FST. Especially coming up with the transition functions for the two FSTs

It is probably a better idea first to concentrate on the complement, i.e., the equality language $\{ w\in \Sigma^* \mid T_1(w) = T_2(w) \}$.

Also, simple FST's will do, as even for morphisms $h_i: \{a,b\} \to \{1\}^*$, $\{ x\in \{a,b\}^* \mid h_1(x) = h_2(x) \}$ need not be regular.

And I want to add that it has been shown that $\Delta(T_1,T_2)$ is always context-free.


Stable matching with constraints I'm reading through Algorithm Design by Kleinberg and Tardos and was working on Ch1 Q1. The question is about stable matching and their 'proof' is presented by contradiction. I have an alternative argument and want to know if its right. The question paraphrased is:

  Consider a town with n men and n women. Each man as a preference list
  that ranks the women and each women has a similar preference list. Of
  these men and women, k men are bad and k women are bad. So there are
  n-k good women and n-k good men. Each man prefers to match with a good
  women and vice versa. Therefore all preference lists rank the good
  people higher than bad people. Show that in every stable matching
  every good man is married to a good women.

My 'proof':

Assume that there is a pairing where a good man is matched with a bad women. Because there are the same number of good men and women, it means that there is one good woman, currently paired with a bad man, who rejected this good man. If she rejected this good man it means that he must be of lower preference than the bad man she is paired with. But this is a contradiction because a good man cannot be ranked lower than a bad man. It means that the good man is actually bad and there are more bad men than good women and the initial problem statement is false.

I assume you want to start your proof with "suppose there is a pairing where a good man $m_1$ is matched with a bad woman $w_1$".

This indeed means that there exists a good woman $w_2$ matched with a bad man $m_2$ (by the pigeonhole principle). However, the contradiction here does not follow from the fact that $w_2$ prefers $m_1$ but is actually matched to $m_2$ (it is possible for a woman to not be matched with her top ranked man).

The contradiction follows from the fact that a matching which contains $(m_1,w_1),(m_2,w_2)$ is not stable, since $m_1$ prefers $w_2$ and $w_2$ prefers $m_1$.


Average number of slots needed in slotted-Aloha Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same slot. Transmission is as follows: when base $i$ has a packet to transmit attempts with probability $p_i, i=1,2$. Different stations make the random selection independently and corresponding probabilities are $p_1=0.5, p_2=0.25$. Initially the station 1 has 2 packets for station 2, while the other has no package.

What is the average number of slots in order all packets reach their destinations? Then if station 1 has 1 packet for station 2 and station 2 has 1 packet for station 1, what is the average number of slots? We are using slotted-Aloha.

The protocol you are describing is most probably CSMA or slotted ALOHA.

As @wece mentioned, you need also to specify what you do in case of conflict (this is also the main difference between the above mentioned protocols). I would assume that a station sends regardless of the link-status and that a station will retransmit in the next slot with same probability $p_{i}$ in case of collision. This is basically what happens in slotted ALOHA, just that you have individual transmission probabilities for you stations.

You would not refer to the specified protocol as TDM (time division multiplexing), because the channel access is non-deterministic and non-repetitive, although you do have fixed time slots.

To your calculative questions:

1) Station 1 has 2 packets to send:
The probability that 1 successfully transmits to 2 is:

$$P(transmit_{1,2})=P(send_{1})*(1-P(send_{2}))$$

Since we have no packets at station 2, $P(send_{2})$ is zero. This is repeated over potentially many slots, always with probability $p_{1}=0.5$ that 1 will send in a slot. Note that this is the same problem as a simple coin toss. The expected number of sends in n tries (if we had infinite packets at 1) is $E=n*p$. Let's look at only one packet: We only want to know how many tries it takes on average. We can therefore write: $n=E/p$. This yields 2 tries on average for station 1. We can thereafter reason exactly the same way for the second package, because there is no statistical dependence between the events. We thereby obtain #tries = 4. (The same problem for station two would yield 4 + 4 tries.)

2) Now two stations want to send. We therefore have ($\neg$ means not):

$$ P(send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$
$$ P(send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$
$$ P(\neg send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$
$$ P(\neg send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$

Only the middle two give a first correct transmission. As in the previously calculation we see that we need 2 tries (or time slots) on average for this to happen. Once this happened, we are back to the first problem, sending one packet with the other station being quiet.

However, at this point it could have been the first or the second station which sent the first packet. We therefore need to account for it: We have 3/4 cases where it was station 1 and 1/4 cases where it was station 2 which transmitted correctly in the first step. This means we can simply add up the number of tries as:
$$\#tries_{first-packet} + \#tries_{second-packet-from-1}*p_{second-packet-at-1} + \#tries_{second-packet-from-2}*p_{second-packet-at-2}$$
$$= 2 + 2 * \frac{1}{4} + 4 * \frac{3}{4} = 5.5$$


How to solve for recurrence with substitution or other methods? Forgive me if I am new, I am trying to learn how to solve recurrences.

I have the following recurrence:

$$T(n) = 2 T(\lfloor\frac{n}{3}\rfloor) + \frac{1}{2} T(\lfloor\frac{2n}{3}\rfloor) + n^2 \text{ if } n>0$$

Now from my understanding is that I am not able to use the following methods.

Master Thereom (because it's not in the form $aT(\frac{n}{b}) + f(n)$)
Tree Method (because of the $\frac{1}{2} T$, you cannot have a node of $\frac{1}{2}$), please correct me if I am wrong.

So which leaves me with the following method:

Only the substitution method, but what I don't understand that is the fact that for the substitution method, you have to guess for the $f(n)$ to substitute into the recurrence.

So my question is, how does one select the correct $f(n)$ to substitute?

Use the Akra-Bazzi theorem. Let $p$ be the solution to $2\cdot(1/3)^p + (1/2)\cdot(2/3)^p= 1$, namely $p = 1$. Compute
$$ S(n) = \int_1^n \frac{x^2}{x^{p+1}} \, dx = n-1= \Theta(n). $$
Then $T(n) = \Theta(x^p S(n)) = \Theta(n^2)$.


CNOT, Hadamard and Φ quantum gates How can somebody use these gates to create other gates like pauli's or other gates? Also how can somebody go from pauli's to CNOT, Hadamard and Φ quantum gates?

This is actually kind of complicated. Basically you can:

Decompose a huge multi-qubit operation into many single-qubit gates, but with lots of controls allowed on each single-qubit gate. Think of it as doing Gaussian elimination: you're factoring the matrix into a bunch of simple row operations.
Gradually reduce the number of controls to at-most-one-per-gate, by repeatedly using a construction based on the fact that every operation has a square root and an inverse.
Factor each single-qubit operation $U$ into $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$. Use that to replace controlled-$U$ gates with uncontrolled single-qubit operations separated by $CNOT$ gates.
Approximate each uncontrolled single-qubit operation with a sequence of $H$ and $T$ gates (which is possible because they correspond to rotations that can approximate any other rotation).

What you're left with is a circuit containing only $CNOT$, $H$, and $T$ gates that approximates the original operation. You need more gates to get a better approximation, but you can get as close as desired. Also the overhead isn't too terrible.

For details of the constructions, and proofs that the errors don't compound in a way that destroys the efficiency of the approximation, you'll probably have to get a textbook or read papers. There's a lot of details.


How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language? I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$  is not a regular language using Pumping Lemma by following way.

Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular language.

Let $0^p 1^{5p}$ be in L, where $p$ is the pumping length.
Now here if the language $L$ is regular language, $0^p 1^{5p}$ can be represented in the form $xyz$ where $|xy| \le p$ & $|y|\gt0$.
Thus, from step 2, we can say that $xy = 0^p$ and $y = 0^j$.
So, $xyz = (0^{p-j})(0^j)(1^{5p})$.
Now pumping the value of y to 2, $xyyz = (0^{p-j})(0^j)(0^j)(1^{5p}) = (0^{p+j})(1^{5p})$, which is surely not in $L$, thus not a regular language.

But how to prove for condition $\{0^n 1^{5n} \mid n \ge 10000 \}$ & for also $n \le 10000$, we can just prove that one of them is not regular and obviously by rules the complement will also be not regular.

The condition $n>10\,000$ makes no real difference. If the pumping length is greater than $10\,000$, your existing proof works. If the pumping length is $10\,000$ or less, then pumping the string $0^{10\,000}1^{50\,000}$ gives you a string that isn't in the language because it has too many zeroes.


Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$ (At the very bottom of this, I will shortly describe the motivation for this question.)

Assume we have a commutative monoid $(G,\circ)$, i.e. a set $G$ with a commutative binary operation $\circ$ that satisfies associativity and the existence of a neutral element. The task is as follows: given some $X \subseteq G$, find a smallest $U \subseteq G$ such that $X \subseteq \langle U \rangle$, where $\langle U \rangle$ is the submonoid generated by the elements of $U$.

Now, if instead of a monoid we had a vector space, the task would be simple: determine the subspace spanned by $X$, and find a base for it. However, this relies on vectors having inverses, which we can't assume to exist in our monoid.

The monoid can be assumed to be fixed, i.e. we don't have to receive it as input, and the only input we receive is $X$. To be more precise, the set $G$ can implicitly be assumed to be $\{0,1\}^n$ for some $n$, and $\circ$ is the component-wise $\max$ operation, which is the same as $\{\text{true}, \text{false}\}^n$ with component-wise $\text{OR}$.

As an example, assume $n=4$ and we want to cover
$$X= \{(0,1,0,1), (1,1,0,0),(1,0,1,0),(1,1,0,1),(1,1,1,1)\}$$

then one optimal solution would be $\{(0,1,0,1), (1,0,1,0), (1,1,0,0)\}$.

Question: what is the complexity of this problem? I have a feeling it's somewhere between a covering problem and a hull problem, but I can't quite put my finger on whether I've come across a variant of this before or not.

The problem arose when a colleague of mine played around with a building block used in LED clocks. They have the structure

 _
|_|
|_|

and each of those seven lines has its own control wire. We only want to use $10$ of the possible $2^7$ configurations of those control wires, so we tried to figure out whether we can build all $10$ configurations using less than $7$ primitives via OR-ing. Since OR over binary vectors doesn't come with inverses, we only have a monoid.

L. J. Stockmeyer proves that SET BASIS is $\mathrm{NP}$-complete.

Reference:
L.J. Stockmeyer, The set basis problem is $\mathrm{NP}$-complete, Tech. Report RC-5431, IBM, 1975

Each vector of your problem can be seen as subset of $\{1, 2, \dots, n\}$. And the component-wise OR operation is corresponding to set union. So a basis for a collection of Boolean vector in your problem is exactly a set basis.


Explaination for Variation of Boyer-Moore Majority voting algorithm Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space.

The intuition behind finding the majority element is understandable as it has to be greater than the count of other elements in the input sequence if a majority element exists.

However, there is a variation of this algorithm to find the elements occurring more than [n / 3] where n is the length of the sequence.

The algorithm goes like this.

  Start with two empty candidate slots and two counters set to 0.
  for each item:

  if it is equal to either candidate, increment the corresponding count
  else if there is an empty slot (i.e. a slot with count 0), put it in that
  slot and set the count to 1
  else reduce both counters by 1

I can understand there will be at most (n /3) - 1 entries so we keep two containers and their counts.

But I'm not sure why the last reduce both by 1 is pivotal to this algorithm. I would be very helpful if you explain the intuition behind this.

Code of the above algorithm

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: nums){
        if (cnt1 == 0 || n == a){
            cnt1++;
            a = n;
        }
        else if (cnt2 == 0 || n==b){
            cnt2++;
            b = n;
        }
        else{ // This part
            cnt1--;
            cnt2--;
        }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Algorithm and code source

Here is a different way to consider the same algorithm, or rather its general form with $k$ counters (in your case, $k=2$). There are $k$ "containers" and a trash bag. Each container will contain one type of element at a time. Initially everything is empty. When we read a new element $x$, we consider the following cases:

If there is a container containing $x$'s, add $x$ to that container.
If there is no container containing $x$ and there is an empty container, put $x$ in the empty container.
If there is no container containing $x$ and there are no empty containers, remove one element from each container, and put $x$ in the trash.

When the algorithm terminates, each of the $n$ elements is either found in one of the $k$ containers, or in the trash bag.

Suppose that element $x$, not found in any of the containers, is found $m$ times in the input. Thus all $m$ copies of $x$ are in the trash bag. Each time an element is put in the trash bag, $k$ other elements are also put in the trash bag together with it. This means that the trash bag contains at least $(k+1)m$ elements, and so $(k+1)m \leq n$ or $m \leq n/(k+1)$.

Consequently, if an element appears more than $n/(k+1)$ times in the input then it will necessarily be found in one the $k$ containers. In other words, the algorithm correctly identifies all elements appearing more than $n/(k+1)$ times.

Note how this analysis crucially depends on the fact that when trashing $x$ in the third case above, we also trash $k$ additional elements together with it.


Common Algorithms without Asymptotically Tight Bounds I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds,  but are there actually common algorithms in computer science that don't have asymptotically tight bounds on their worst case running times?

This is somewhat of an anomaly, but yes - technically you could say that there are such algorithms. For example, consider an algorithm that checks whether a number in unary encoding is a prime - the first thing the algorithm can check is whether the number is even, this takes $O(n)$ time.

If it is, the algorithm rejects, otherwise it applies some primality test that takes $\omega(n)$ (at the very least by first converting it to binary, which takes $\theta(n\log n)$).

The point is that on every input of even length, the algorithm stops "quickly", so there is no asymptotically tight bound.

But this is clearly a stupid example.
One way to avoid this problem is to define the running time of an algorithm on inputs of length $n$ to be the worst case running time on inputs of length at most $n$. This way  you can get a tight bound.


Constrainted Optimization Problem in Matrix Entropy I have a constrainted optimization problem in the (Shannon) matrix entropy $\mathtt{(sum(entr(eig(A))))}$. The matrix $A$ can be written as the sum of rank 1 matrices of the form $[v_i\,v_i^T]$ where $v_i$ is a given normalized vector. The coefficients of the rank one matrices are the unknowns in which we optimize and they have to be larger than zero and sum up to 1.

In a CVX-like syntax the problem goes as follows:
given variable $\mathtt{c(n)}$

$$\text{minimize} \qquad \mathtt{sum(entr(eig(A)))}$$

$$\begin{align} \text{subject to} \qquad A &= \sum c_i v_i v_i^T\\
\sum c_i &= 1\\ c_i &\ge 0\end{align}$$.

Does any have an idea how to solve this efficiently? I already know it probably can't be cast as a semi-definite programming (SDP) problem.

Edit: A colleague informed me that my method below is an instance of the general method in the following paper, when specialized to the entropy function,

  Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Overview

In this post I show that the optimization problem is well posed and that the inequality constraints are inactive at the solution, then compute first and second Frechet derivatives of the entropy function, then propose Newton's method on the problem with the equality constraint eliminated. Finally, Matlab code and numerical results are presented.

Well posedness of the optimization problem

First, the sum of positive definite matrices is positive definite, so for $c_i > 0$, the sum of rank-1 matrices
$$A(c):=\sum_{i=1}^N c_i v_i v_i^T$$
is positive definite. If the set of $v_i$ is full rank, then eigenvalues of $A$ are positive, so the logarithms of the eigenvalues can be taken. Thus the objective function is well-defined on the interior of the feasible set.

Second, as any $c_i \rightarrow 0$, $A$ loses rank so smallest eigenvalue of $A$ goes to zero. Ie, $\sigma_{min}(A(c)) \rightarrow 0$ as $c_i \rightarrow 0$. Since the derivative of $-\sigma \log(\sigma)$ blows up as $\sigma \rightarrow 0$, one cannot have a sequence of successively better and better points approaching the boundary of the feasible set. Thus the problem is well-defined and furthermore the inequality constraints $c_i \ge 0$ are inactive.

Frechet derivatives of the entropy function

In the interior of the feasible region the entropy function is Frechet differentiable everywhere, and twice Frechet differentiable wherever the eigenvalues are not repeated. To do Newton's method, we need to compute derivatives of the matrix entropy, which depends on the matrix's eigenvalues. This requires computing sensitivities of the eigenvalue decomposition of a matrix with respect to changes in the matrix.

Recall that for a matrix $A$ with eigenvalue decomposition $A = U \Lambda U^T$, the derivative of the eigenvalue matrix with respect to changes in the original matrix is,
$$d\Lambda = I \circ (U^T dA U),$$
and the derivative of the eigenvector matrix is,
$$dU = UC(dA),$$
where $\circ$ is the Hadamard product, with the coefficient matrix
$$C = \begin{cases}
\frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\
0, &i=j
\end{cases}$$

Such formulas are derived by differentiating the eigenvalue equation $AU=\Lambda U$, and the formulas hold whenever the eigenvalues are distinct. When the there are repeated eigenvalues, the formula for $d\Lambda$ has a removable discontinuity that can be extended so long as the nonunique eigenvectors are chosen carefully. For details about this, see the following presentation and paper.

The second derivative is then found by differentiating again,
\begin{align}
d^2 \Lambda &= d(I \circ (U^T dA_1U)) \\
&= I \circ (dU_2^T dA_1 U + U^T dA_1 dU_2) \\
&= 2 I \circ (dU_2^T dA_1 U).
\end{align}

While the first derivative of the eigenvalue matrix could be made continuous at repeated eigenvalues, the second derivative cannot since $d^2 \Lambda$ depends on $dU_2$, which depends on $C$, which blows up as the eigenvalues degenerate towards one another. However, so long as the true solution does not have repeated eigenvalues, then it is OK. Numerical experiments suggest this is the case for generic $v_i$, though I don't have a proof at this point. This is really important to understand, as maximizing entropy generally would try to make eigenvalues closer together if possible.

Eliminating the equality constraint

We can eliminate the constraint $\sum_{i=1}^N c_i = 1$ by working on only the first $N-1$ coefficients and setting the last one to
$$c_N = 1-\sum_{i=1}^{N-1} c_i.$$

Overall, after about 4 pages of matrix calculations, the reduced first and second derivatives of the objective function with respect to changes in the first $N-1$ coefficients are given by,
$$df = dC_1^T M^T [I \circ (V^T U B U^T V)]$$
$$ddf = dC_1^T M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)],$$
where
$$M = \begin{bmatrix}
1 & \\
& 1 & \\
&&\ddots& \\
&&&1\\
-1 & -1 & \dots & -1
\end{bmatrix},$$

$$B_a = \mathrm{diag}(1+\log \lambda_1, 1 + \log \lambda_2, \ldots, 1 + \log \lambda_N),$$

$$B_b = \mathrm{diag}(\frac{d_2\lambda_1}{\lambda_1},\ldots,\frac{d_2\lambda_N}{\lambda_N}).$$

Newton's method after eliminating the constraint

Since the inequality constraints are inactive, we simply start in the feasible set and run trust-region or line-search inexact newton-CG for quadratic convergence to the interior maxima.

The method is as follows, (not including trust-region/line search details)

Start at $\tilde{c} = [1/N,1/N,\ldots,1/N]$.
Construct the last coefficient, $c = [\tilde{c},1 - \sum_{i=1}^{N-1} c_i]$.
Construct $A = \sum_i c_i v_i v_i^T$.
Find the eigenvectors $U$ and eigenvalues $\Lambda$ of $A$.
Construct gradient $G = M^T [I \circ (V^T U B U^T V)]$.
Solve $H G = p$ for $p$ via conjugate gradient (only the ability to apply $H$ is needed, not the actual entries). $H$ is applied to vector $\delta \tilde{c}$ by finding $dU_2$, $B_a$, and $B_b$ and then plugging into the formula,
$$M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)]$$
Set $\tilde{c} \leftarrow \tilde{c} - p$.
Goto 2.

Results

For random $v_i$, with linesearch for steplength the method converges very quickly. For example, the following results with $N=100$ (100 $v_i$) are typical - the method converges quadratically.

>> N = 100;
>> V = randn(N,N);
>> for k=1:N V(:,k)=V(:,k)/norm(V(:,k)); end
>> maxEntropyMatrix(V);
Newton iteration= 1, norm(grad f)= 0.67748
Newton iteration= 2, norm(grad f)= 0.03644
Newton iteration= 3, norm(grad f)= 0.0012167
Newton iteration= 4, norm(grad f)= 1.3239e-06
Newton iteration= 5, norm(grad f)= 7.7114e-13

To see that the computed optimal point is in fact the maximum, here is a graph of how the entropy changes when the optimal point is perturbed randomly. All perturbations make the entropy decrease.

Matlab code

All in 1 function to minimize the entropy (newly added to this post):
https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m


Finding Second large element from a set of 4 element Is there any special algorithm of lowest complexity for finding 2nd largest element from a set of 4 elements?

It is known that the exact number of comparisons needed to find the second largest element out of $n$ elements is exactly
$$
n-2+\lceil \log_2 n \rceil.
$$
See for example Jeff Erickson's notes. In our case, this gives $4-2 + \lceil 2 \rceil = 4$ comparisons.

Here is a matching algorithm for $4$ elements. Let the elements be $a,b,c,d$, which we assume to be distinct for simplicity.

Compare $a$ and $b$. Without loss of generality, $a > b$.
Compare $c$ and $d$. Without loss of generality, $c > d$.
Compare $a$ and $c$. Without loss of generality, $a > c$.
Compare $b$ and $c$, and return the maximum.

More generally, if $n$ is a power of $2$, here is how to find the second largest element in $n-2+\log_2 n$ comparisons. First you form a "tournament" by comparing the elements in pairs, then comparing the winners in pairs, and so on, until you find the maximum. This takes $n-1$ comparisons. Then you find the maximum among all $\log_2 n$ elements which "lost" to the maximum, using $\log_2 n - 1$ comparisons.

If $n$ is not a power of $2$ then you add dummy elements with value $-\infty$ to pad the list to the closest power of $2$, and proceed as before. The first phase will take only $n-1$ comparisons (since comparisons with dummy elements need not be performed), and the second will take $\lceil \log_2^n \rceil - 1$ in the worst case (depending on the number of dummy elements which "lost" to the maximal element).


Complexity of "Subtree of Another Tree" I wrote an algorithm for a leetcode question. The question asks:

  Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

My solution for this problem consists of a breadth-first traversal of the first tree s, and a function that checks whether any subtree of s is the same tree as t. The entire solution can be found here.

I am having a tough time figuring out the time and space complexity of this solution.

I understand that the isSame function has a time and space complexity of O(n). (See my explanation below), and the isSubtree function will call isSame for every node in s. However, the size of the input to isSame changes on each call, and I am having a hard time putting both pieces together to get an overall runtime / space complexity.

Explanation of isSame time and space complexity:

For the function that checks whether two trees are the same (isSame), the worst-case time complexity occurs when the trees are indeed equivalent. In this case, we will check every node and do a constant amount of work for each node, and thus our time complexity is O(n), where n is the number of nodes in either tree (they are the same). Furthermore, the function isSame function is recursive, and our time complexity will be linear with the height of the smallest tree. In the worst case, both trees are equivalent, and they have degenerated to a linked list, in which case the number of frames on our call stack will be the same as the height, which is the same as the number of nodes, so that's O(n) for the space complexity.

The time complexity of isSame is not linear in the height of the smallest tree. Think for example of two copies of a complete binary tree (where all nodes have the same value).

That said, the time complexity of isSame is always $O(m)$, where $m$ is the number of vertices in the smallest of the two input subtrees.

Let me assume that the number of vertices $m$ of $t$ is at most the the number of vertices $n$ of $s$ (as otherwise the answer is trivial).

Your algorithm requires time $\Theta(n m) = O(n^2)$ in the worst case.
The upper bound is obtained by simply multiplying the number of vertices of $s$ with the $O(m)$ upper bound to the complexity of isSame.
The lower bound is obtained, e.g., by letting $s$ be a path on $n$ nodes rooted in one of its endpoints and $t$ be a path on $m$ nodes rooted in one of its endpoints (as before, all vertices have the same value). The first $\lfloor n/2 \rfloor$ invocations of isSame require $\Omega(m)$ time each, for an overall time complexity of $\Omega(n m)$.
Notice that this is  $\Omega(n^2)$ for $m=\Omega(n)$.


Rows and columns in quantum-gate matrices read the same - why? I have noticed that for all the matrices representing quantum gates, if we read rows left-to-right and top to bottom, the read the same as columns top to bottom left to right.

Example:

\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1&  0
\end{pmatrix}
(CNOT gate), if we read the values in from the first row, we see 1 0 0 0. Similarly if we read left-most column top to bottom. Second row reads 0 1 0 0, just like 2nd left column etc.

I believe this is a property of all matrices representing quantum gates, but cannot explain why exactly this is the case (and if it is, in fact, guaranteed for every quantum gate?)

A counter-example to your observation is the Pauli Y gate:

$$Y = \begin{bmatrix} 0&-i\\i&0\end{bmatrix}$$

The first row is 0 then -i, but the first column is 0 then +i.

Another example is the X->Y->Z->X gate (a 120 degree rotation around the X+Y+Z axis of the bloch sphere):

$$\frac{1-i}{2} \begin{bmatrix} 1&-i\\1&i\end{bmatrix}$$

The reason the rows often look so much like the columns, particularly for self-inverse operations, is because quantum gates are unitary and the inverse of a unitary matrix is its conjugate transpose. But you can easily break the symmetry by multiplying an individual row (or column) by a phase factor, which produces a different but valid quantum operation.


Solving retreat formulas I want to solve the following formula:
$T(n)=T(n-1 )+ c\cdot\log n $, $T(1)=d$

I though about master but then I realized there is no dividing here so it's not gonna do it,
I tried to expand the formula like this:

$T(n-1)=T(n-2) + c\cdot \log(n-1)$

$T(n-2)=T(n-3) + c\cdot \log(n-1)$

How do I find the general formula?
How do I proceed from here? My professor taught us only master theory, no iteration

If you unroll the formulae you get:
$$T(n) = T(n-1) + c \cdot log(n) = \sum_{i=2}^{n} c\cdot log(i) + d = O(n \cdot log(n)) $$

Last equality is true from the following fact:
$$\sum_{i=1}^n log(i) \ge \sum_{i=\frac{n}{2}}^n log(i) \ge \frac{n}{2} \cdot log(\frac{n}{2}) = O(n \cdot log(n))$$
$$\sum_{i=1}^n log(i) = log(n!) \le log(n^n) = n\cdot log(n) = O(n\cdot log(n))$$


Do RP algorithms exist? I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated.

How can the random coin flip possibilities allow for a guaranteed response of NO when the correct answer is NO, yet return with a probabilistic chance YES or NO when the answer is YES?

Are these actually algorithms we have examples of or is it just a theoretical class without any known examples? If there are examples, could someone please lay one out?

The algorithms you are looking for are also called one-sided-error Monte Carlo algorithms.

The idea is to randomly guess a witness for the input being a YES-instance. If you find one, your answer "YES" is always correct; if you don't find one, you say "NO" even though the correct answer may be "YES" (we want to restrict the likelihood of this event). If the input is a NO-instance we can never find such a witness, so we always output NO correctly.

One well-known example is the Solovay–Strassen primality test.


Reduction variation for the q-coloring problem I'm trying to prove that $q$-COL $\leq^P_m q$-COL$_{2q-1}$, where $q$-COL$_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you can color a graph of any maximum degree with $q$ colours, then you can colour a graph of maximum degree $2q-1$ with $q$ colours", the second is a subset of the first. Am I correct this far?

Assuming the previous assumption is correct, I need to find a function or mapping from $G$ to $G'$. It would seem that I need to pick a vertex $v \in G$, and $v' \in G'$ and colour $v'$ the same as $v$, then follow the pattern of $v$, for up to $2q-1$ connections, and then leave the rest alone.

In my head this works, but I'm fully new in reductions and would appreciate your input about this. I'd also appreciate any pointers on how to formalise it. Thank you!

When proving that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$, what you are really showing is that checking whether a graph with maximal degree $2q-1$ is $q$-colorable isn't any easier than checking whether an arbitrary graph is $q$-colorable. Why is this an interesting statement? Since if we replace $2q-1$ with a small enough number, then checking whether a graph is $q$-colorable does become easier. For example, any graph with maximal degree $q-1$ is $q$-colorable, so checking whether such a graph is $q$-colorable is easy, whereas checking whether an arbitrary graph is $q$-colorable is NP-hard for all $q \geq 3$.

How do you show that $q\text{-}\textsf{COL} \leq_m^P q\text{-}\textsf{COL}_{2q-1}$? You need to transform a given graph $G$ to a graph $H$ with maximum degree $2q-1$ such that $H$ is $q$-colorable iff $G$ is $q$-colorable. The most natural way of doing this is by splitting high-degree vertices. I'll illustrate how to do it for the case $q=2$ (which in reality isn't so interesting — why?), and will let you generalize the construction. Once you do that, you'll also see where $2q-1$ is coming from.

Suppose therefore that $q = 2$. First of all, we number the neighbors of all vertices. For each edge $(v,w)$, there are numbers $i,j$ such that $w$ is the $i$th neighbor of $v$, and $v$ is the $j$th neighbor of $w$. Now, we replace each vertex $v$ of degree $d$ with a path $v_0,\ldots,v_{2d}$, and connect $v_{2i}$ and $w_{2j}$ if $w$ is the $i$th neighbor of $v$ and $v$ is the $j$th neighbor of $w$. Note that all vertices now have degree at most 3. The construction works basically since the vertices $v_0,v_2,\ldots,v_{2d}$ all get the same color — I'll let you work out the details.


Prove by induction that a recurrence has solution $T(n)=\Theta(n^2 \log_{3}n)$ Prove by induction that $T(n)=\Theta(n^2 \log_{3}n)$ where
$$T(n)= \begin{cases} 1 & \mbox{if } n=1,\\ 9T(\lceil n/3 \rceil)+n^2 & \mbox{otherwise.} \end{cases}$$
The base case for $n=1$ seems to work, but I am unable to do the induction step.


Fast polynomial calculation over $\mathbb{Z}_{487}$ Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j )$ for all $j = 0, . . . , 242$ by calculating three polynomials $a
_0 (x), a_1(x), a_2(x)$ of degree at most $80$ for $81$ different values of $x$.

So first of all I divided $a(x)$ into sub-polynomials, simply by:
$$\begin{align*} a(x)=x^{162}\cdot&\left( a_{242}\cdot x ^ {80}+...+a_{163}\cdot x+a_{162} \right)+\\
& x^{81}\cdot\left( a_{161}\cdot x ^ {80}+...+a_{82}\cdot x+a_{81} \right)+\\
&\left( a_{80}\cdot x ^ {80}+...+a_{1}\cdot x+a_{0} \right)\end{align*}$$

Now I have shown that $2^{243} = 1 \mod 487$, and that for every $1\leq a \leq 242: \,\,\, 2^a \neq 1 \mod 487$.

I wanted to use this so that I can choose distinct $x_i$ by $x_i=2^i \mod 487$ for all $0\leq i \leq 242$. Now I thought taking triples, and for that I had two ideas:

Choose triples $x_i,x_{i+1},x_{i+2}$ for each $0\leq i\leq 242$ such that $i = 0 \mod 3$.
Choose triples $x_i,x_{i+81},x_{i+162}$ for each $0 \leq i \leq 80$.

In any case, given a trio, I wanted to calculate only $a_2(x_i), \,a_1(x_i), \,a_0(x_i)$, and then using them to calculate $a(x_i),\,a(x_{i^{'}}),\,a(x_{i^{''}})$, where ${i^{'}} $and ${i^{''}}$ will be the next in my trio (depending on which idea to choose).

The problem is, I either got confused and all that's left is obvious, or I just can't seem to make those last few steps. If Im on the right way, can someone help me here? Or perhaps I should choose other trios? Or if not, maybe there's a hint that can help me out?

You can very efficiently compute $a(x_j)$ for each of those 243 values of $x_j$ by simply evaluating $a(\cdot)$ using Horner's rule.  The running time is 243 evaluations of $a(\cdot)$, and each evaluation requires 243 modular multiplications and 243 modular additions.  That's a total of $243^2 \approx 2^{16}$ modular multiplications.  Consequently, the total running time will be extremely efficient, even without trying to split this into three polynomials $a_0(x),a_1(x),a_2(x)$.

If you want a more efficient method, a better approach is to use a Discrete Fourier Transform.  You can use a DFT over $\mathbb{Z}_{487}$ to evaluate $a(x)$ at 256 different points in running time that's asymptotically $O(n \lg n)$, where here concretely $n = 256$.  [Alternatively, you could use the Number-theoretic transform for $\mathbb{Z}_{487}$ to evaluate $a(x)$ at $486$ points, and do all your calculations in $\mathbb{Z}_{487}$.]


Is this variant of ATM decidable? Ok so I understand how $\mathrm{ATM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$}\}$ is undecidable.

Is this because $w$ is a variable?

What if the parameter is fixed?

Consider $\mathrm{BTM} = \{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts the string 101}\}$.

BTM is decidable right? The diagnolization problem here doesn't seem to apply because it would seem trivial to build a Turing machine that is 100% capable of accepting only the input "101" and rejecting every other possible input, correct?

And our machine would always reject itself as an input, since it only accepts "101", right?

You can show that $\mathrm{BTM}$ is undecidable with a simple reduction from $\mathrm{ATM}$.

Let $\langle M,w\rangle \in ATM$. We define the reduction function $f$,  $\mathrm{HP} \leq \mathrm{BTM}$ as follow:

$f(\langle M,w\rangle) = M_w $, Where $M_w$ on every input $x$, runs $M$ with input $w$. if $M$ stopped, then $M_w$ accepts $x$. if $M$ rejects, then $M_w$ rejects. Clearly, if $\langle M,w\rangle \in ATM$ then $L(M_w) = \Sigma^*$, and in particular $101 \in L(M_w)$. if $\langle M,w\rangle \notin ATM$ then   $L(M_w) = \emptyset$, and $101 \notin L(M_w)$.

Because $\mathrm{ATM} $is undecidable, so is $\mathrm{BTM}$.

It should be intuitive that $\mathrm{BTM}$ is undeciadble, because given a turing machine $M$, you can't tell if $M$ will halt with input $101$


Please explain this formal definition of computation I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts::

  Let $A$ be a finite set of letters. Let $A^*$ be the set of all strings in $A$ (the set of all ordered sequences $x_1$ $x_2$ ... $x_n$ where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j \le N$:

  $f((\sigma, j)) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$
  $f((\sigma, j)) = (\alpha \psi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$
  $f((\sigma,N)) = (\sigma, N)$

Not being a computer scientist, I have trouble grasping the whole passage. I kind of get the idea that is behind a system of opcodes, but I haven't progressed effectively in understanding. I think that the main problem is tat I don't know how to read it effectively.

Would it be possible to explain the passage above so that I can understand it, and give me a strategy in order to get in the logic in interpreting these statements?

We are missing some context so I have no idea what point Knuth is trying to make, but here's how to interpret a Turing machine this way. Perhaps it will help you understand what's going on. In general, a good way of getting a grip on a concept is playing with it. In the case of programming paradigms, that means writing a program. In this case, I will show how to write any program.

Suppose the tape of the Turing machine has symbols $\{0,1,\epsilon\}$ (where $\epsilon$ stands for "empty"), and add one more symbol which represents the location of the head $H$. Your states are going to be pairs of the form $(q,\alpha)$, where $q$ is a state of the Turing machine, and $\alpha \in \{0,\ldots,14\}$. We also identify $(F,0)$ with $N$ for any final state.

On (non-empty) input $x$, your starting point will be $(Hx,(s,0))$, where $s$ is the starting state. The difficult part is to encode states. Suppose that at state $q$, upon reading input $x$, you replace it with $a(q,x)$, move in direction $D(q,x) \in \{L,R\}$, and switch to state $\sigma(q,x)$. For the $\theta$s, we have
$$
\begin{align*}
\theta_{q,0} &= 0H0, & \theta_{q,1} &= 0H1, & \theta_{q,2} &= 0H\epsilon, \\
\theta_{q,3} &= 1H0, & \theta_{q,4} &= 1H1, & \theta_{q,5} &= 1H\epsilon, \\
\theta_{q,6} &= \epsilon H0 & \theta_{q,7} &= \epsilon H1, & \theta_{q,8} &= \epsilon H\epsilon, \\
\theta_{q,9} &= H0, & \theta_{q,10} &= H1, & \theta_{q,11} &= H\epsilon, \\
\theta_{q,12} &= 0H, & \theta_{q,13} &= 1H, & \theta_{q,14} &= \epsilon H.
\end{align*}
$$
For the $a$s, we have $a_{q,i} = (q,i+1)$ for $i < 14$, and $a_{q,14} = (q,14)$, though we should never really get that far. For the $b$s, we have
$$
\begin{align*}
&b_{q,0} = b_{q,3} = b_{q,6} = b_{q,9} = (\sigma(q,0),0), \\
&b_{q,1} = b_{q,4} = b_{q,7} = b_{q,10} = (\sigma(q,1),0), \\
&b_{q,2} = b_{q,5} = b_{q,8} = b_{q,11} = b_{q,12} = b_{q,13} = b_{q,14} = (\sigma(q,\epsilon),0).
\end{align*}
$$
Now it remains to determine the $\psi$s. Let $a_0 = a(q,0)$. If $D(q,0) = L$ then
$$
\begin{align*}
\psi_{q,0} &= H0a_0, & \psi_{q,3} &= H1a_0, & \psi_{q,6} &= \psi_{q,9} = H\epsilon a_0.
\end{align*}
$$
If $D(q,0) = R$ then
$$
\begin{align*}
\psi_{q,0} &= 0a_0H, & \psi_{q,3} &= 1a_0H, & \psi_{q,6} &= \epsilon a_0 H, & \psi_{q,9} &= a_0H\epsilon.
\end{align*}
$$
Next, let $a_1 = a(q,1)$. If $D(q,1) = L$ then
$$
\begin{align*}
\psi_{q,1} &= H0a_1, & \psi_{q,4} &= H1a_1, & \psi_{q,7} &= \psi_{q,10} = H\epsilon a_1.
\end{align*}
$$
If $D(q,1) = R$ then
$$
\begin{align*}
\psi_{q,1} &= 0a_1H, & \psi_{q,4} &= 1a_1H, & \psi_{q,7} &= \epsilon a_1 H, & \psi_{q,10} &= a_1 H\epsilon.
\end{align*}
$$
Finally, let $a_\epsilon = a(q,\epsilon)$. If $D(q,\epsilon) = L$ then
$$
\begin{align*}
\psi_{q,2} &= H0a_\epsilon, & \psi_{q,5} &= H1a_\epsilon, & \psi_{q,8} &= \psi_{q,11} = H\epsilon a_\epsilon, \\
\psi_{q,12} &= H0a_\epsilon, & \psi_{q,13} &= H1a_\epsilon, &\psi_{q,14} &= H\epsilon a_\epsilon.
\end{align*}
$$
If $D(q,\epsilon) = R$ then
$$
\begin{align*}
\psi_{q,2} &= 0a_\epsilon H, & \psi_{q,5} &= 1a_\epsilon H, & \psi_{q,8} &= \epsilon a_\epsilon H, & \psi_{q,11} &= a_\epsilon H\epsilon, \\
\psi_{q,12} &= 0a_\epsilon H, & \psi_{q,13} &= 1a_\epsilon H, & \psi_{q,14} &= \epsilon a_\epsilon H.
\end{align*}
$$

Now apply $f$ repeatedly until you get stuck. If you follow the construction, you will see that we have simulated the running of the Turing machine.


What is the difference between deterministic and confluent? I understand deterministic as a function for some input will always give the same output, and these inputs and outputs can be sets of values represent by a predicate.
I understand confluent as convergence of a rewriting system, ie the rewritten terms always converge to some term, which could also represent a predicate.
It seems like these definitions are very similar in what they achieve.
Would all deterministic systems be confluent and vice versa?
Or is determinism really about the paths taken and exact timmings of computations to reach an answer, ie a deterministic algorithm must always have the same trace of paths for every run?
Also there is a notion of choice in non-deterministic algorithms, how does this fit in?
I feel like these definitions should work across sequential and concurrent systems, but for concurrent systems the exact timings are less important as the scheduler controls this.

If a binary relation is confluent and terminating, then the map from initial state to final state is total and deterministic.  The converse also holds.
If a binary relation is confluent, the binary relation need not be a function.
You'll have to decide what you mean by "deterministic" and whether you refer to what the original state ultimately leads to (then the answer to your question is yes, as mentioned in the first paragraph of this answer) or whether you refer to the behavior in a single step of the system (then the answer is no, as mentioned in the second paragraph of this answer).


Response time of scheduling a DAG where each vertex is a task Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have $x$ threads that can execute those tasks.

Is there a (simple) formula to determine the response time (or at least an upper bound) for the given setup using any work-conserving scheduler?

Found it! This problem is NP-complete when the goal is to minimize total execution time.

The scheduling problem (P1) is the following. We are given
(1) a set $S = \{J_1 , \ldots , J_n\}$ of jobs,
(2) a partial order $\prec$ on $S$,
(3) a weighting function $W$ from $S$ to the positive integers, giving the number of time units required by each job, and
(4) a number of processors, $k$.

Please see the following paper, which immediately discusses it from the introduction onward:
J.D. Ullman. Np-complete scheduling problems. Journal of Computer andSystem Sciences, 10(3):384 – 393, 1975.
There are a few other cases that may be of interest that are discussed in the paper:

When $\prec$ is empty (no edges in the DAG)
(P2) When $W(J_i) = 1$ for all $i$.
(P3) When $k = 2$ and $W(J_i) \in \{1, 2\}$ for all $i$.

You can show 3-SAT reduces to (P2) through and intermediate problem (P4) that Ullman discusses. Then it is clear that (P2) reduces to (P1).


Constructible enumerable set We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also constructible enumerable.

To show this do we have to construct a Turing machine for the union and one for the cartesian product?

Hints:

For $S_1 \cup S_2$, use the same idea in the proof that the natural numbers and the integers have the same cardinality. The proof goes by listing the integers in sequence:
$$ 0,1,-1,2,-2,3,-3,\ldots $$
You can think of $S_1$ as $0,1,2,3,\ldots$ and of $S_2$ as $-1,-2,-3,\ldots$.
For $S_1 \times S_2$, use the same idea in the proof that the natural numbers and the positive rationals have the same cardinality. The proof uses the "diagonal method", and consists of listing the rationals sorted by the maximum of the numerator and the denominator:
$$ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \ldots $$
In this case $S_1=S_2$ are both $1,2,3,\ldots$.


Recursive language subtracted from recursively enumerable language This is a homework problem but I am awfully confused. The problem reads as follows:

If $L_1$ is recursively enumerable but not recursive, and $L_2$ is recursive, then which of the following is the strongest true statement about the set difference $L_1 - L_2$?

a. It must be recursively enumerable and not recursive.

b. It might be neither recursively enumerable nor recursive.

c. It must be recursively enumerable and it might be recursive.

d. It must be recursive.

I understand exactly what a recursive language and recursively enumerable languages are. A recursive language is one for which there exists a Turing machine which halts and decides whether the string is in the language for all strings of the alphabet. A recursively enumerable language is one for which there exists a Turing machine which halts and accepts if the string is in the language, but may halt and reject or not halt for strings that are not on the language.

So an example of a recursively enumerable language would be all C programs which do not contain an infinite loop (since we obviously won't halt if the program does). I am a tad bit confused on finding an example of a recursive language.

So subtracting a recursive language from a recursively enumerable language means that, if I try to think this through, there exists a turing machine which may halt and accept all strings in the language, and removing a recursive language only means we remove some strings which would be halted on and accepted.

So I am leaning towards c, but I am very fuzzy. Any pointers?

The language that contains all input strings is recursive. Just create a Turing machine that always outputs true. So take that to be $L_2$. $L_1 - L_2$ would be the empty no matter what $L_1$ is. The empty language is also recursive. So now we have an example of a recursive language arising from $L_1 - L_2$.

The language that contains no input strings (the empty language) is recursive. Just create a Turing machine that always outputs false. So take that to be $L_2$. Now $L_1 - L_2 = L_1$ which is not recursive.

So $L_1 - L_2$ may or may not be recursive.

Now we are left with b) and c). To decide between these we can note that the language is always recursively enumerable.
Proof:

Iterate outputs from $L_1$ but only output them if they are not contained in $L_2$ (check by a Turing machine which always terminates). We now have a Turing machine that outputs all elements of $L_1 - L_2$.

So $L_1 - L_2$ is always recursively enumerable.


Transitivity of quasi-reducibility A set $A$ is quasi-reducible to $B$ ($A \leq_Q B$) if there is a recursive function $f$ such that $$x \in A \iff W_{f(x)} \subseteq B$$
Or equivalently $$ x \in \overline{A} \iff W_{f(x)} \cap \overline{B} \neq \emptyset $$
Where $W_{e}$ is the domain of the recursive function of index $e$, i.e. $W_{e} = \{y : \varphi_{e}(y) \downarrow\}$.

Everywhere I look it says the transitivity of the relation is easy to see, but for some reason it doesn't click for me.

Ok I think I have found it.

Let $A$, $B$ and $C$ such that $A \leq_Q B$ and $B \leq_Q C$, respectively by the recursive functions $f$ and $g$. Let
    \begin{align*} h : x,y \mapsto & \text{ find } b \in W_{f(x)} \text{ and } c \in W_{g(b)} \text{ such that } y = c \\
  & \text{ return } 0
\end{align*}
By $s$-$m$-$n$ we have a recursive function $s$ such that $\varphi_{s(x)}(y) = h(x,y)$.

Assume $x \in A$. If $y \in W_{s(x)}$, then $\exists b \in W_{f(x)}$ and $\exists c \in W_{g(b)}$ such that $y = c$ so $b \in B$ and $c \in C$ by the assumed reductions, so $y \in C$ and $W_{s(x)} \subseteq C$.

Now if $x \in \overline{A}$, then $\exists b \in W_{f(x)} \cap \overline{B}$ and $\exists c \in W_{g(b)} \cap \overline{C}$, so $h(x,c)\downarrow$ and $c \in W_{s(x)} \cap \overline{C}$.

So we can conclude $A \leq_Q C$.

Let me know if you think there's a problem with this.


Are parser combinators equivalent to scannerless parsing? From what I can see, parser combinators are equivalent to scannerless parsing.  I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in the google generally. But, it seems they are. I didn't code the low-level rules separately or using different syntax than higher order ones.

Am I correct that parser combinators are simply scannerless parsing?  Or is there a difference that I am overlooking?

It may be that both are commonly used together (that's the kind of estimation which is very sensible to perspective effects), but they are in principle different.

Scannerless means that the parser is directly fed the stream of characters instead of getting tokens recognized by a scanner with white spaces and comments removed.  You can use whatever kind of parsers you want to parse the characters.

Parser combinators is a way to build a parser for a complex language from parsers for simpler one.  The stream of symbols on which the bottom parsers are working may be a stream of tokens recognized by a scanner or a stream of characters.

That said, it is possible to hold the point of view that a scanner is a parser combinators (combining regular expressions) and thus that parser combinators are always scannerless parsers (if you are using different tools for both, that seems a quite abstract point of view). But even then, it is possible to have scannerless parsers which are using other parsing techniques.


delaunay sweep circle initialization I recently came accross an interesting "sweep circle" algorithm for delaunay triangulation [1].

It's basic idea is seeding with a trivial triangulation (3 points), then gradually extending it outwards (points are sorted by their distance from a chosen origin - the sweep-circle center) while preserving the legality of the triangulation by flipping triangles if needed, always starting from the new one, and continueing to neighbouring triangles of flipped ones.

I've implemented it, and it works nicely, but I still struggle with making the seeding part flawless.

The thing is :

In order to ensure that each new point is outside of the current envelope ("frontier" in the article), you have to make sure that the swept points are closer to the origin than the unswept points.
In order to find where to connect the new point, you have to have the origin inside the envelope (so angular sort of the envelope and binary search will do).

Starting at some iteration this will natuarally happen, but the problem is making it happen for the seed points.

So what I aim at is finding an origin which fulfills :

Be inside the seed triangulation.
Have the seed points the closest points to it (have the sweep circle strictly containing the seed points empty of other points).

The article suggests taking some average point as the origin, and start with the 3 points closest to it, but this clearly fails if these 3 points are on the same side of the chosen origin, so they form a triangle that is not containing it.

A different but somewhat similar algorithm [2] is suggesting choosing an arbitrary point, then taking the point closest to it, and the point that creates the smallest circumcircle with the other two, and fix the origin as the center of their circumcircle, but that's clearly not working either, unless these 3 points happen to form an acute triangle (is this circle even ensured to be empty of other points?).

Currently I use a similar idea - arbitrary point + 2 closest points to it, as the first 3 points, but I fix the origin as some point inside the formed triangle (e.g their average), which basically works, but can fail in principal.

I'm looking for another simple way to do it, or a way to detect when the proposed method is not working and fix it in a clever way involving the point that "ruined it", before the iterations begin and without having to deal with more than 2 seed triangles (4 points), or having to make many iterations or guesses at init stage.

I know I can take the first point and shift it by some small $\epsilon$ towards inside the triangle, and it should work, as long as it's smaller than say the minimum distance bewteen 2 points, but I'm looking for a clever solution, and I am especially interested in a solution that can chose an integer origin for a set of integer points, for then the whole algorithm can be implemented using only integral arithmetics (faster, less error prone).

Bottom line :

I think it all comes down to this :

Given a set of n points in the plane, find a point O which lies strictly inside the triangle formed by the 3 points of the set closest to it (to O).

But I guess that put in the context, there might be solutions to implementing a working version of the algorithm that bypass this question.

References :

A faster circle-sweep Delaunay triangulation algorithm by Ahmad Biniaz and Gholamhossein Dastghaibyfard (2011)
S-hull:  a fast radial sweep-hull routine for
Delaunay triangulation by D. A. Sinclair (2016)

I just realized that my question is irrelevant to making the algorithm work.
I mixed the radial and angular atributes of the points and mistakably thought them to need to be based at the same origin, but that's just confusing semantics.
Actually, the radial origin decides on the order of insertion of points and if set correctly, ensures no new point will apear inside an existing triangle, and the angular origin only helps to find the projection of a new point on the envelope (frontier / convex-hull in the case of [2]), so the angular origin indeed needs to be inside the seed envelope, but the radial origin need not. Moving the angular-origin inside the seed envelope will affect the actual progression of the algorithm, but will not affect correctness.

This makes things a lot easier - taking arbitrary point of the set, or somewhere in the plane and find the 2/3 points closest to it will work in general position, but it may result in a colinear triplet.
Following [2] and taking a point from the set, its nearest neighbour, and a 3rd point that creates the smallest circumcircle with them will always work as this is a delaunay triangle (nearest-neighbours are always delaunay edges, and the 2 triangles based on this edge have to create an empty circumcircle, so one of them has to be the smallest) which makes the circumcircle empty of other points, so using its origin as the radial origin is correct.

To do this for integers, we may take the second approach and round the result (checking for super-edge-cases), or take the first approach which is more straight forward for integer radial origin, and restart if we find a colinear triplet, or when the triangle is too obtuse to contain an integer point in its interior.
The last condition is only for making the algorithm fully integral (e.g for machines wihout Floating Point Arithmetics), but using precalculated float pseudo-angles [3] (avoiding use of slow atan2) and comparing them later in the binary search (tree), might be faster than using fully integral orientation test by demand.

pseudo-angles


Are two states equivalent in a DFA if on the same input the states transition to each other? Suppose you have three states in an DFA $q_{1}$, $q_{2}$ and $q_{3}$, all non-accepting. Suppose $a$ and $b$ are two symbols, such that:

$\delta(q_{1},a)=q_{2}\\ \delta(q_{2},a)=q_{1}$

and

$\delta(q_{1},b)=q_{3}\\ \delta(q_{2},b)=q_{3}$

Are the states $q_{1}$ and $q_{2}$ considered equivalent?

"We say that states $p$ and $q$ are equivalent if:

  For all input strings $w$, $\hat{\delta}(p,w)$ is an accepting state if and only if $\hat{\delta}(q,w)$ is an accepting state."

  (John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2001. Introduction to automata theory, languages, and computation, 2nd edition.)

So if the automaton doesn't accept any strings, there cannot be a string that distinguishes the two states, and therefore there cannot be an equivalence between two states.


No polynomial time approximation algorithm better than $n^{1 − ε}$ What does this sentence mean?

For all $ε > 0$, it is NP-hard to approximate MAX CLIQUE to within $n^{1 − ε}$.

Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity should go remarkably higher. Right? In which order?

The sentence means that for every $\epsilon > 0$ there is a polytime reduction $f_\epsilon$ that takes an instance $\phi$ of SAT into a pair $(G,k)$ such that:

If $\phi$ is not satisfiable then $G$ has no $k$-clique.
If $\phi$ is satisfiable then $G$ has an $n^{1-\epsilon} k$-clique.

An $n^{1-\epsilon}$-approximation algorithm for MAX-CLIQUE can be used to distinguish the two cases.

The running time of $f_\epsilon$ indeed depends on $\epsilon$, which probably appears in the exponent, that is, $f_\epsilon$ runs in time $n^{g(\epsilon)}$, where $g(\epsilon)$ tends to $\infty$ as $\epsilon \to 0$.


Whether the algorithm is polynomial or not with input size which is not polynomial A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time.

Is this true or false? and why? any idea?

This depends on how precisely the words are meant.

In computer science, we often lack perfect (or even good) information about the behavior of algorithms. As a result, we tend to approximate or create upper bounds and talk about those instead of actual behavior. In most contexts, when you say “the algorithm requires superpolynomial space” what you mean is that in the worst case, we cannot prove that the algorithm uses less than superpolynomial space.

This is very different from the literal interpretation of your words, where an algorithm requires superpolynomial space if there exists an input for which it use superpolynomial space.

So why does this matter? Writing $k$ units of space generally requires at least $k$ units of time in the contexts where we are interested in doing space analysis. Therefore if the algorithm in fact requires superpolynomial space, it must require superpolynomial time. Additionally, if we cannot prove it doesn’t require superpolynomial space, then it follows that we cannot prove that it doesn’t require superpolynomial time. However, it is possible for us to not be able to prove that it doesn’t require superpolynomial space and in fact requires polynomial time.

Additionally, it’s possible that in your context writing $k$ units of space can be done in much less than $k$ time. There do exist computation models where space is much cheaper than time in this sense, but in those contexts we rarely care about space complexity, because it’s so cheap.

So, the answer in most contexts is no, but it’s very important to think carefully about what your words mean.


Does randomness make exponential difference? Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the problem is NP-hard or not, right? Is there any NP-hard problem that can be solved in expected poly-time using a randomized algorithm? What are the consequences if such a thing exists?

It is a common belief that P=BPP. This means that any randomized polynomial time algorithm can be derandomized. The idea of the proof is to use a deterministic pseudorandom number generator to supply the randomized algorithm random bits. Such a pseudorandom number generator exists, for example, if SAT takes exponential time to solve (roughly).

Polynomial identity testing is usually presented as a slightly different kind of problem (or rather as several different kinds of problems), but again the common belief is that one should be able to do it deterministically.

(As common beliefs go, some people disagree.)


Markov Chain w/ non-stochastic matrix I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum to 1. However,the probabilities on edges entering the node do sum to 1. Therefore the transpose of the transition matrix IS stochastic.

I've built up a model in excel and noticed a few properties of this "transpose markovian process":

all nodes reach the same steady state value.
the steady state *is* dependent on the initial state (unlike a markov process).
the steady state value can be computed as S0 x MT (the initial state vector times the transpose of the markovian steady state vector... obtained by transposing the transition matrix and solving as a markov process).

My question is this: Is there a name for such a process? In searching for it I've found it to be beyond obscure, so my hope is some well-informed human can catalyze me with some search terms.

No, there's no standard name for a process where the transpose of the transition matrix is stochastic (at least, to my knowledge).

However, this process is the time-reversal of a Markov process.  That's a remarkable and descriptive property that just about completely characterizes this process.  In particular, it seems likely that many things we'd want to know about such a process can be derived from the fact that it's the time-reversal of a Markov process, plus known facts about Markov processes.

Anyway, if you need to describe the process, "time-reversal of a Markov process process" is probably about as good as you're going to get.


Is graph search of shortest (optimal) path an instance of optimisation? I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm.
I am not too familiar with graphs / trees and their search.
But it does seem like all possible solutions can be represented as a graph and a graph search algorithm can then be used to explore the space and determine the "shortest" (or could be some other criterion) path. It seems that this is what Breadth First Searcha and Dijkatra algorithm are doing. Is this correct? Is tree search actually linked to a more general concept of optimisation?

Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an initial solution, i.e. some path from A to B, and eventually find the shortest path  between A and B after considering multiple such paths. But this is not the case, as these algorithms both construct partial solutions before eventually getting a complete solution.

On other hand, it is true that locally, the distance to some node is at first estimated by some path and possibly later improved, so there is some similarity here. However, the incremental approach to a solution is an important aspect in these algorithms, which doesn't occur in gradient-based optimisation, as these cases usually don't even have a concept of a partial solution which can be extended into a full solution.


Non-Deterministic FSA to Deterministic FSA, Two initial states My method of conversion is by creating a reachable set tree and each set within the tree would represent the new states.

I have never dealt with FSAs that has 2 or more initial states. How do i create my reachable set tree with two or more states?

The powerset construction converts an NFA to a DFA. You then "optimize" the result by removing states which cannot be reachable from the start state. When the NFA has multiple starting states, you do exactly the same thing. The starting state of the new DFA is the state corresponding to the set of starting states in the NFA (compare that to the usual case, in which the starting state of the DFA is the signleton consisting of the starting state of the NFA).

Given a DFA, you can compute the set of reachable states iteratively: the starting state is reachable; any state which it points to is reachable; any state which these point to is reachable; and so on. (Technically, this is known as BFS. There are also other algorithms, such as DFS.)


Reference needed: lower bound on sample size for determining which side of coin is biased with high probability I am looking for a reference to see if the following problem has been addressed before.  Suppose we know that a coin is biased with probability $p>\frac{1}{2}$, but we are unsure if the coin is biased for heads or tails.  I want to know a lower bound on a sample size $n$ needed to determine with high probability which side the bias is in favor of i.e. with probability at least $1-\delta$ so the answer would be $n=\Omega(g(p,\delta))$ or something like that.

Thanks for any help!

Yes.  You need approximately $\sim 1/|p - 1/2|^2$ observations (that many are necessary and sufficient), assuming $p$ is close to $1/2$.  I've omitted constant factors, but the constant is small.  The exact constant will depend on the degree of confidence you want, but it will vary as something like $\log (1/\delta)$ (or lower): $\delta$ drops exponentially fast in the number of observations.

For more details and analysis, see https://cstheory.stackexchange.com/q/22328/5038.  You might also be interested in https://cstheory.stackexchange.com/a/30938/5038.


structure of cache when CPU uses words smaller than the main memory As the title says, i have the following excersice:

An associative mapping cache with four lines in each set, can store in each line two words of 16 bits each. It can store 4K words, that they have length 32bits from Main memory. The CPU is 16 bits and the address that he produces is 24 bits length. So the solution is shown below:

I can understand why set has 10 bits, or why tag is 12, but I can't figure out the word select and byte select signals. Also how can this cache store two words as the image shows (Word 0 and Word 1), when the line size is 16 bit, but the word size from Main Memory is 32 bits.

So the question is a bit confusing because there are two types of words: CPU words that are 16 bits, and memory words that are 32 bits. This can happen when the CPU registers have 16 bits but the memory chip is organized in such a way that the minimum accessible unit (a word) is 32-bit. The cache will always read/write multiple of memory words, in this case one word per line. Since the CPU word is 16 bits, each memory word (32 bits) actually holds two CPU words, those are the Word 0 and Word 1 on the picture.

Now, when the CPU accesses memory, the cache will find which lines corresponds to the request. This line contains 32-bit, but maybe the CPU only wanted 8 bits, so we have to extract those 8 bits from the line. In this example, bit 1 will select between Word 0 and Word 1 (which are CPU words). The resulting word still has 16 bit, so we use bit 0 to select between the low or high 8 bits of that word.

If you still find confusing, forgot about Word 0 and Word 1 and just imagine that each cache line stores 4 bytes (=32 bits). Now to select one byte in 4, you need to discriminate based on the lower 2 bits of the address. If the cache had 8 bytes per line, then you would use 3 bits. And so on. In general, the format of an address is

| Tag | Index | Offset |

where Index selects the line (there are many way of doing so) and Offset selects the byte within the Line.


Can this language be called regular? Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of digit such that when viewed as numbers, satisfy the mathematical equation x+y=z.

For example, the string 123#45#168 is in this language because 123 + 45 = 168.

Is this language regular and why ?
I was trying to apply the Pumping Lemma, but am unsure of how to complete the proof. Could anyone please help ?

Hint:

 Consider the special case where $y=0$.


Dimension Reduction - Which feature should remove to reduce the dimension of the matrix Let's suppose that we have the following 2 tables:

If we want to reduce the dimension by one(in every table) which feature we should remove and why ?

I am confused about the way that i should work generally in this type of problems.

In the first table, X2 is an unnecessary feature. You can check that for any row, the value of Y that you obtain after reversing the value of X2 is always unaffected. Instead, X1 and X3 are both individually necessary; this can be seen for example by comparing the first row with the fifth row (for X1) and with the second row (for X3).

In the second table, X1 is an unnecessary feature. The value of Y is solely determined by whether X2 is large or small; say, larger or smaller than 0.5. Hence a linear classifier based on X2 can predict Y with full accuracy. Instead, no linear classifier based on X1 only can correctly predict Y; for example, the value of Y is 1 for X1=0.6931, becomes 0 for X1=0.7465, and becomes 1 again for X1=2.7361.

For the first type of problem, you can look at each feature individually and check whether the results indeed depend on it or not, by comparing corresponding rows as I did in the example.

For the second type of problem, you can look for non-monotonicity (as I did in the example with the X1 feature), in which case you can exclude the non-monotone feature, at least if you are looking for a linear model.


Fair cake-cutting when players join late The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide a cake over $n$ players, but then a new player arrives and wants a share.

Usually, fair cake division requires a lot of effort (for example, requires the players to answer many queries), especially when the number of players is large.

Is it possible to use the existing division of the cake over $n$ players, in order to create a new division of the cake to $n+1$ players, with minimal additional effort (i.e. substantially less effort than re-distributing the cake from scratch)?

Assume the cake/area is a circle $C$ with radius $r$. Then, we can create
$n$ fair pieces by the canonical cake cutting and thus assign each player an area
of $\frac{\pi r^2}{n}$. We can then assign the $(n+1)$th a small circle around the center,
and subsequent new players rings around that one (swallowing part of the inner circle),
and so on. In this way, every player gets one contiguous piece/plot which shrinks
in a monotone way for the first $n+1$ players, and moves towards the center for
those joining later.

Working out the numbers is simple; for the first new player, simply solve

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

to get the radius for his plot. For the second, solve

$\qquad\begin{align}
  \pi r_1^2 &= \frac{\pi r^2}{n+2} \\
  \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2}
\end{align}$

to get (outer) radii for both new players, and so on.
It seems that player $n + i$ gets outer radius $r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$
after $k$ additional players have joined, but I did not prove this.

This is what you get for $n=6$ and $k=0,1,2,3$:

[source]

The same idea works for regular polygons with $n$ sides. If you assume a rectangle
as basic form, you can do a similar thing by assigning the first $n$ equally sized
columns and the following players rows (starting at one side).


What is a Huffman tree for a Block-Code? We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ".

I have created a Huffman tree for the string w.

We get the following table:

Now I want to create a Huffman tree for a Block-Code with length of block $4$.

Do we maybe take each consecutive 4 letters, i.e., {aabc, eefg, eebd, aabb, ceef, fghd, cbbe, efbb, bbgh, hie} to make the tree?

But then the last one is of length 3 and not 4.

So, do we choose in an other way the blocks?

In your context, a block code of length $\ell$ encodes $\ell$ letters at a time. The domain thus consists of all words over the alphabet of length $\ell$. Unless you're told otherwise, the assumption is that the individual letters are independent - the probability of a word $\sigma_1 \dots \sigma_\ell$ is the product of the probabilities of the individual letters.


Lambda calculus :difficulty in getting hang of induction and conversion I am going through the book on lambda calculus by Hindley and Seldin .
They introduce the syntactic equivalence of expressions and proving them by a technique named "induction" , which has not been directly defined in the book .

(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

The above are the rules given for substitution in the book. I have some difficulty in understanding (d).
Why is it so that $$  [N/x] ( \lambda x . p) = ( \lambda x . p) $$ ? How to justify this ? Why can't this be defined to be or equal to  $$( \lambda N . p) $$ ?

In the definition of substitution $[N_1/ x]N$, we describe how to replace all free occurrences of the variable $x$ by the expression $N_1$ throughout the expression $N$.

The formation rules defining the syntax of $\lambda$-calculus expressions $e$ are

$$ N ::= x \mid \lambda x.P \mid N_1 N_2 $$

where $x$ ranges over a set of variables. One should think of the abstraction $\lambda x.P$ as a function with argument $x$ and body $P$ – or using standard programming terminology, we think of it as a procedure with formal parameter $x$ and body $P$.

In $\lambda x.P$, the variable $x$ is not free within $P$, so a substitution $[N/x](\lambda x.P)$ cannot change anything.

Moreover, writing $\lambda N.P$ does not make sense; the argument/formal parameter must be a variable.

If you are still puzzled, think of an applied lambda-calculus with integer numerals and consider the expression $\lambda x. x +7$ that informally denotes a function that adds $7$ to its argument. Your proposed substitution rule would give us that $[14/x](\lambda x. x+7)  = \lambda 14. x +7$. What would that even mean? (I have no idea.)

By the way, the notion of induction is not esoteric at all. Induction is a central proof technique in mathematics and in computer science, and one cannot understand the lambda calculus without being familiar with it. See https://en.wikipedia.org/wiki/Mathematical_induction for an introduction.


Theoretical speed gain of quad core vs. single core I first asked this question at cstheory, but they suggested to ask my question here, so here it goes ...

I'm working on my masters thesis and I need to have theoretical value of the (average) speed gain that a quadcore processor brings compared to a singlecore processor, when they both use the same frequency. So for example the speed gain of a 2 GHz singlecore vs. 2 Ghz quadcore.

Somewhere on the internet I've read that a quadcore is 2.6 times faster than singlecore, but the author didn't mention any source so I cannot use that in my thesis.

I've been trying to calculate some things myself, but didn't come to a conclusion. I tried like this:

threads | quad core | single core | ratio
--------|-----------|-------------|-------
1       | 1         | 1           | 1
2       | 2         | 1/2         | 4
3       | 3         | 1/3         | 9
4       | 4         | 1/4         | 16
5       | 3+1/2     | 1/5         | 17.5
6       | 2+2(1/2)  | 1/5         | 15
7       | 1+3(1/2)  | 1/5         | 12.5
...

This table represents the timeslices available to execute a task (I've taken a fair 50/50 usage for each thread). For example when using a singlecore and a application uses 3 threads, each thread can work 1/3 of the time, while with a quadcore each thread can work 100% of the time, because 3 threads can be spread accross a separate core. After playing with some calculations in Excel, I could not come to any conclusion.

I'm a bit stuck and need some fresh ideas on how to get a theoretical number that represents how much faster a quad core is (on average) compared to a single core. Maybe some of you know some empirical numbers with a good reference to the source? Anyway, all the help is welcome, because I'm a bit stuck and this is the last part I need to cover in my thesis.

Thanks!

There is no absolute value of how much faster a quad-core would be compared to a single-core. As the comments have said, it very much depends on exactly what you are doing whether it will be faster or slower. Even live performance testing may not give a fair answer since it won't model exact runtime behaviour.

In any case, if you are looking for a theoretical model it certainly is possible, though, as you can quickly see, not practically possible.

First you need to understand the architecure of the chips of the involved. When you move from single-core to quad-core not all resources are actually quadrupled. In particular the memory is still a shared resource. This memory is then split between a series of caches, some of which are shared, and some of which are not shared. Each cache is connected to the other caches either by a dedicated bus, or a shared data bus. Each of these caches, and buses, has a real bandwidth and latency number. This is not likely published, but with some very focused tests can be obtained.

Second you need to understand how the application will be using memory. How this memory is shared and the order in which it is accessed. For a single thread you could, in theory, calculate the amount of time it spends loading data from the various cache levels. For a multi-core case a key value is how often you attempt to write to the same memory. In this case you will invoke the chips cache-coherency algorithm. This algorithm is usually documented (to some degree) and the time to synchronize can be reasonably well measured.

Combine these together and you'll see that with perfect knowledge of how the program behaves and how the processor behaves you would be able to calculate the theoretical gains of increasing the number of cores. In pratice this simply won't be possible for all but the simplest of programs (but even then the way the chips manage memory is complex enough to make the problem too difficult).

What you should get from this description is primarily that processor speed alone is not the only problem. Memory is often the key bottleneck. When svick says perfectly parallelized he means they don't share memory. In this case your threads will approach the maximum 4x speed gain as the memory contention is low. However, they still share some memory cache for reading (L3 and main memory on Intel) and thus could still be limited by the total memory bandwidth.

If you wish to look at a degenerate example lookup "false sharing". In such cases the total speed goes down as more processors are added.


Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$ having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function is in $\Omega(n)$ or in $\Omega(n^2)$? For example, is $n-\log n$ in $\Omega(n)$ or in $\Omega(n^2)$?
I cannot ignore the log function and am not sure how to deal with it.  Polynomials and logs when multiplied I find OK. But I have a mental block over this one so help would be appreciated

You are right that you cannot a priori ignore additional terms, although morally you can as the "smaller" terms do not contribute to the asymptotic growth.
As an example $f(n) :=n+\log n$ is in $\Theta(n)$. Why? Going back to the definition, we want to show that $f(n)$ is in $O(n)$ and in $\Omega(n)$. Showing $f(n)\in \Omega(n)$ is immediate, as $f(n) \geq n$ for all $n>0$.
To show that $f(n)$ is in $O(n)$, simply notice that for large enough $n$ (say $n>N$ for some constant $N$) we have $\log n \leq n$ and thus $f(n)\leq 2n$ for all $n>N$. By definition $f(n)\in O(n)$.


I need to present a regular expression for the following languages: 1.
L2 = E{0,1)

All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either
0's or 1's.

2.
All words that does not contain “bbb” as substring.

i think this is :( e + b + bb)(a + ab + abb)*

Thanks in advance!

Your point 2, is obviously correct.

As for the point 1, we construct the automaton: let's remember how much more 0's we've read than 1's. Then we have transitions:

S0  by 0 to S1
S0  by 1 to S-1
S1  by 0 to S2
S1  by 1 to S0
S-1 by 0 to S0
S-1 by 1 to S-2
S2  by 1 to S1
S-2 by 0 to S-1

S0 is initial, only S0 is final. This way we are sure, that in whatever state we are, the number of $0$'s and $1$'s that were read so far differs by at most $2$ and in the final state the number are the same.

Then the language is
$$ \Bigl(0(01)^*1+1(10)^*0\Bigr)^*$$

The large parenthesis corresponds to all paths from S0 to S0, and we can repeat it as many times as needed.


Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells as suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

What are the implications of splitting on non-midpoints?
What needs to be taken into consideration when selecting among several non-midpoint candidates?
Does splitting on non-midpoints affect any of the convergence properties
of the algorithm?

Another way to ask this is: Are there split points that are better than the a-priori selected midpoints?

In Rupert's refinement algorithm, if the circumcenter of a "skinny" (poor quality) triangle were inside the domain and its location is "sufficiently" far away from other points in the triangulation, the algorithm terminates. When the circumcenter is inserted, it is at least a certain distance from all other points (equal to the circumradii), so it will eventually run of space to add more points. Luckily, the ratio of the circumradii and length of the smallest side of a triangle is a function of the smallest angle in the triangle. Therefore, if a skinny triangle is defined as a triangle whose ratio is greater than 1 (corresponds to a minimum angle of 30 degrees), the algorithm is guaranteed to terminate.

But what if the circumcenter is outside the domain? That is when the midpoint on the "nearest" boundary edge is inserted. When the midpoint is inserted, it introduces two short edges whose length is equal the half the length of the original edge. In addition, all points within the diametrical circle of the original edge are deleted so that there are no "even-shorter" edges introduced. And because these two new edges may be shorter than the previous shortest edge in the mesh, during the next step, we should introduce the circumcenter only if the ratio (cumcumradii : shortest length) is greater than some quantity that is strictly greater than 1. In the pdf you shared, it is shown that the ratio should be $\sqrt2$.

If you inserted a point not on the midpoint, but somewhere else on the edge, you will create an edge shorter then half the length of the boundary edge. This edge may be much shorter than the current shortest edge in the mesh. So the ratio that guarantees termination will be greater $\sqrt2$.

To answer your specific questions:
1. Implication: weaker termination guarantee
2. The length of new edges created should be considered. If they all happen to be large, you can happily add a non-midpoint vertex into the mesh. If the boundary edge is a light year long, and other mesh edges are orders of magnitude shorter, you can split the edge almost anywhere ... almost (see below).
3. Yes, splitting on non-midpoints affects termination guarantees.

BUT .....

Alper Ungor's paper attempts to insert off-circumcenter points instead of the circumcenter.

And this paper also allows for insertion of non-midpoint vertices into the mesh. But in the limiting case, it reverts to mid point insertion.


Paxos made simple -- two details I'm missing two details from Paxos made easy

P1. An acceptor must accept the first proposal that it receives.

What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon receiving a proposal: acceptor memorizes the proposal as most recent proposal; if acceptor is not waiting with a running countdown, a countdown of Xmsec is set up; upon a countdown timeout acceptor accepts the most recent proposal

I'm not proposing the above rule as better or more interesting -- rather I'm posing a question of which exactly requirement is fulfilled by following P1.

Observe that P1a subsumes P1.

What does this mean? That P1a is more general? Fulfilling P1a fulfills P1? At least scenario mentioned in section 2.4 suggest P1a does not imply P1. What am I missing?

What exactly is the reason for rule P1?

The paper says:

  We use the customary asynchronous, non-Byzantine model...

In other words, it assumes that everything can take an arbitrarily long time to happen, but no messages are corrupted in transit and all agents obey the protocol.

What this means is that it would be perfectly fine to write the timeout-based rule as you describe, but it would be harder to describe and analyse and yet it would not satisfy any different properties from a protocol that has no timeouts: the asynchronous model already allows for arbitrary delays and message-reordering, so adding any further delays and message-reordering doesn't gain anything.

  What does "P1a subsumes P1" mean?

It means it replaces P1. The sentence after P1 starts ...

  But this requirement raises a problem.

... which means that P1 isn't the correct requirement. The correct requirement is in fact P1a.


What language should this NFA recognise? I am trying to figure out which language does the following NFA (taken from a Sipser's book "Introduction to theory of computation") recognise

From my understanding, this NFA accepts strings that contain at least two $1$s, but this is not precise, because, e.g., between the two ones we could have a $0$ or nothing ($\epsilon$). We can also have any number of $0$s or $1$s after these two $1$s.

My guess is that this NFA recognises a language whose strings contain the substrings $11$ or $101$, but I am not sure.

Can you help me defining the language that this NFA recognises?

In general, what is the best way to see what language is recognised by a NFA?

Don't overthink it; your intuition is correct. The only strings that get you from the start state to the final state are $<anything>11$ or $<anything>101$. Once you're in the final state, any subsequent inputs are also accepted, so the language accepted by this FA is, as a regular expression, $(0+1)^*(11+101)(0+1)^*$, which is obviously all strings containing 11 or 101.


Measuring the difficulty of a sequence-to-sequence problem using automata theory Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string.
However, I want to measure the difficulty of a sequence-to-sequence (seq2seq) problem.
For instance, what is the difficulty of the following seq2seq problem associated with counting as follows:
$\Sigma = \{a, b, 1, 2, 3, T \}$ where $T$ is a terminal symbol.
$A = \{xT \}_{x \in \{a1, a2, a3, b1, b2, b3\}^*}$
$B = \{sT \}_{s \in \{a, b\}^*}$
A seq2seq function $f:A \to B: w_1d_1 \cdots w_nd_n T \mapsto \underbrace{w_1 \cdots w_1}_{d_1} \cdots \underbrace{w_n \cdots w_n}_{d_n}T$ where $w_i \in \{a, b\}$ and $d_i \in \{1, 2, 3\}$.
To go further, is there any way to convert a seq2seq problem into a language recognition problem?
Moore machine or Mealy machine equipped with an output function deals with similar problem where  the length of the output is equal or less than that of the input.

Finite-state transducers capture a class of seq2seq problems that correspond to the notion of regular languages, which could be thought of as the "easiest" problems in automata theory.  Your example function $f$ can be implemented by a finite-state transducer.


What is the requirement for bubble sort to complete in 1 pass? I am working on a problem where you're given $n$ distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete.
e.g., if n=3, then the following permutations would only require 1 pass
1 2 3
1 3 2
3 1 2
2 1 3

But
3 2 1
2 3 1

would require more than 1 pass. Apparently the answer is $2^{n - 1}$, but I am not sure how to prove this for the general $n$ case.
My question is, what are the general constraints for a sequence to allow for it to be sorted with 1 pass of bubble sort?
It is difficult for me to come up with a generic formula to generate the permutations for larger $n$.

I'm assuming that a pass of bubble sort on the array $A[1],\ldots,A[n]$ proceeds as follows:

If $A[1] > A[2]$ then swap $A[1]$ and $A[2]$.
If $A[2] > A[3]$ then swap $A[2]$ and $A[3]$.
...
If $A[n-1] > A[n]$ then swap $A[n-1]$ and $A[n]$.

Bubble sort halts after a pass in which no swaps were made.
As is evident, if bubble sort halts after one pass, then the array must have been sorted.
When does bubble sort halt after two passes? If after the first pass, the array is sorted. In this case, if we know which swaps were made, then we can recover the input permutation. Furthermore, different sets of swaps correspond to different initial permutations. It follows that there are $2^{n-1}-1$ permutations that cause bubble sort to halt after exactly two passes. Together with the identity permutation, it follows that there are $2^{n-1}$ permutations that cause bubble sort to halt within two passes.
How do these permutations look like? Suppose that the first $k$ swaps are made, and then the following swap isn't made. Since the first $k$ swaps are made but the following one isn't made, at the end of the pass the first $k+1$ elements of the array will be $A[2],\ldots,A[k+1],A[1]$, which must correspond to the permutation $1,\ldots,k+1$. Hence the original permutation started $k+1,1,\ldots,k$.
From here, it's not too difficult to describe all $2^{n-1}$ permutations. Starting with the identity permutation, partition it in an arbitrary way, and rotate each part one step to the right. For example, when $n = 3$ we get:

$1|2|3 \to 1|2|3$.
$1|23 \to 1|32$.
$12|3 \to 21|3$.
$123 \to 312$.

Each division in the partition corresponds to a step in the pass during which there was no swap.

Here is another way of describing these permutations: they avoid the patterns $231$ and $321$. This means that for any $i<j<k$, it cannot be that $A[k] < A[i],A[j]$. To prove this, we show that any permutation above satisfies this constraint, and then prove the converse.
Consider any of the $2^{n-1}$ permutations above, and let $i<j<k$. Since each element in a part is smaller than each element in a subsequent part, $A[k] < A[i]$ is only possible if $i,j,k$ are all in the same part. Moreover, $A[k] < A[j]$ for indices $j<k$ in the same part only if $j$ is the first element in the part, which is impossible since $j>i$.
Suppose now that we are given a $(231,321)$-avoiding permutation. Let $i$ be any index such that $A[i] > i$. All elements in $i,\ldots,A[i]-1$ must appear before all elements in $A[i]+1,\ldots,n$, since otherwise there will be a copy of $231$. Furthermore, the former must appear in increasing order, since otherwise there will be a copy of $321$. Therefore the part of the array that follows $A[i]$ is $A[i],i,i+1,\ldots,A[i]-1$.
Imagine now scanning the array in the order $A[1],A[2],\ldots$. The first time that $A[i] \neq i$, necessarily $A[i] > i$ (since we've already seen all smaller elements), and so the following elements are $i,\ldots,A[i]-1$. When we continue the scan, again the first time that $A[i] \neq i$ we must have $A[i] > i$ (since we've already seen all smaller elements), and so on. Therefore the array is of the form above.