Rice's theorem for non-semantic properties Rice's theorem tell us that the only semantic properties of Turing Machines (i.e. the properties of the function computed by the machine) that we can decide are the two trivial properties (i.e. always true and always false).

But there are other properties of Turing Machines that are not decidable. For example, the property that there is an unreachable state in a given Turing machine is undecidable$^{\dagger}$.

Is there a similar theorem to Rice's theorem that categorizes the decidability of similar properties? I don't have a precise definition. Any known theorem that covers the example I have given would be interesting for me.

$^\dagger$ it is easy to prove that this set is undecidable using Kleene's Recursion/Fixed Point theorems.

A general theorem that partially covers the example given is that any $\Sigma^0_1$-hard property of the machine will be undecidable. The halting problem is $m$-reducible to the state-reachability problem, so that shows the state reducibility problem is $\Sigma^0_1$-hard.

However, this is not an "if and only if" theorem like Rice's theorem. If every $\Sigma^0_1$ property of the index of the Turing machine counts as a property of the machine, then there is not going to be a nice characterization, because there is not any nice characterization of which r.e. sets are decidable in terms of the index of the r.e. set.


Labeling a limited number of points on the screen I have a map with up to thousands of points on it.

Now I want to label those points on the screen. But this would only make sense for a limited number of points and the label of points close by should not overlap with others.

What would be a way to go about this to not cover the screen with labels?

Aggregate your data, the setting is in 2D, the number of points is small for clustering, and it will solve the task.

You can use k-means, where $k$ will denote number of labels shown on the screen. Putting labels in place of centroids will with high probability give you good place for labels. If this is not good enough you can refine the placement using iterative method on selected labels by treating them as springs with constraint on minimal distance or solving NLP (Natural Label Placement).

Alternatively you can use dbscan algorithm with $\epsilon$ greater than the size of maximal label, this will give you advantage with no refinement needed but in return you lose control over number of labels displayed.

For more in-depth analysis I recommend the doctoral dissertation Automated Label Placement in Theory and Practice by Alexander Wolff.

There are other approaches like Unaligned Collision Avoidance or simulation by flock where the avoiding/pushing is set greater than labels size. This unfortunately will need more tweaking.


Proving that $S^* = (S^*)^*$ I am going through some past exam paper questions on regular languages for some revision, and I am having a bit of trouble with converting general ideas into formal mathematical proofs.

The question is:

  Given regular expression $S$, prove formally that $S^* = (S^*)^*$.

My problem is expressing this in a formal proof. Here is what I have worked through so far (it is a bit all over the place and just a collection of ways to express the problem mostly)

$S^* = (S^*)^*$

this implies:

$S^* \subseteq (S^*)^*$ and $S^* \supseteq (S^*)^*$

if we assume that there exists $w_k$ such that $w_k \in S^*$

then the base case for the proof is:

$k = 0$   $(w_k = \epsilon)$ (empty word, always in $S^*$ and $(S^*)^*$ by definition)

$k = 1$   $(w_k \in S^*)$

and that's kind of where my ability to reason ends.

I think the rest of it will be something like:

$w_{k+1} = w_kx$

ie. $w_k$ concatenated with $x$ where $x \in S^*$

but how can I show that $w_{k+1} \in (S^*)^*$?

Any help to push me in the right direction would be greatly appreciated.

As you observed, to show $S^*=(S^*)^*$ it will suffice to show $S^*\subseteq(S^*)^*$ and $(S^*)^*\subseteq S^*$. Here's a sketch of a proof of both containments.

For a language $A$, define $A^*=\{x_1x_2\dots x_n\mid n\ge 0\text{ and each }x_i\in A\}$. Then (with $n=1$) it's clear that for all $x\in A$ we'll have $x\in A^*$, establishing that $S^*\subseteq(S^*)^*$.

To show containment in the opposite direction, let $x\in (S^*)^*$, then by definition we'll have $x=y_1y_2\dots y_n$ where $y_i\in S^*$ for all $1 \le i\le n$. Then, again by definition, we'll have $y_i=z_{i1}z_{i2}\dots z_{in_i}$ where $z_{ij}\in S$ for all suitable $i$. We'll then have
$$
x=(z_{11}z_{12}\dots z_{1n_1})(z_{21}z_{22}\dots z_{2n_2})\dots(z_{n1}z_{n2}\dots z_{nn_n})
$$
where each $z_{ij}\in S$. Applying the definition of star one more time we see that $x\in S^*$, establishing that $(S^*)^*\subseteq S^*$ and hence the desired equality.


Calculate number of ways to color matrix using inclusion-exclusion principle This was asked in a recent contest.
The question asked to count the number of ways to color an $M \times N$ matrix with $K$ colours such that no two adjacent cells (sharing an edge) have the same color.
In other words, I want to count the number of different graph colorings of a grid graph: the graph of a $N \times M$ grid. The limits were $1 \le N,M \le 8$ and $1 \le K \le 1000000000$.

Is it possible to count the number of colors using the inclusion-exclusion principle, and if so, how? I saw another question that solves the special case (where $M=2$) using inclusion-exclusion, so I'm wondering if that kind of approach can be generalized here.

Not an answer, but related.

The number of colorings of a graph on $N$ vertices with $c$ colors is a polynomial of degree at most $N$ in $c$ known as the chromatic polynomial. As such, it can be calculated by evaluating it at $N+1$ points, say $c=0$ to $c=N$. Your program need $\binom{8+1}{2} = 36$ of these polynomial.

In some cases there are formulas for the chromatic polynomial, but in the case of grids it's an open question to find such a formula, see this question on math.se.


How hexadecimal representation is more compact and intelligible for documentation? My textbook says,
                    "Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as such and converted to the corresponding hexadecimal number. This makes the representation more compact and, as a result, more intelligible."
                 would any body explain it to me plz? Thanks!

This is just the ordinary English language use of the word "compact": taking up less space. As to whether it's more intelligible, eh, that's basically a matter of reader preference and very context-dependent. Probably nobody wants to read "The system supports up to 0x64 users."


Checking validity of formulas in first-order logic Given four formulas in first order logic. Which of the following formulas are not valid? (In logic a proposition is valid if it never evaluates to $\bot$.)

$(\exists x P(x)\to Q)\to (\forall x (P(x)\to Q))$
$((\neg P\to Q)\wedge(P\to R))\to (\neg P\to R)$
$(\exists x(P(x)\to Q(x)))\leftrightarrow  (\forall x P(x)\to\exists x P(x))$
$(\forall xP(x)\to Q)\to (\forall x (P(x)\to Q))$

According to proof by negation, for example if we negate formula in $1$ then we get $\bot$, as a result this shows that $1$ is valid. Instructor said only $4$ is not valid, but I think both $2$ and $4$ are not valid according to proof by negation.

First of all, from this post

Heuristic: To try to determine whether ϕ is valid: If the answer's not
obvious, look for an interpretation where ϕ is false.

So try to proof by negation. Consider $1:$
Let
\begin{gather*}
\phi\equiv(\exists xP(x)\to Q )\to(\forall x(P(x)\to Q)).
\end{gather*}
Now negate $\phi$ then we have:
\begin{gather*}
\neg\phi\equiv \neg(\neg(\exists xP(x)\to Q )\vee(\forall x(P(x)\to Q)))\equiv (\exists xP(x)\to Q )\wedge \neg(\forall x(P(x)\to Q))\equiv (\forall xP(x)\vee Q )\wedge (\exists x(P(x) \wedge \neg Q))
\end{gather*}
so after elimination of quantifiers:
\begin{gather*}
 \neg P(x)\vee Q
\end{gather*}
\begin{gather*}
P(C_1)
\end{gather*}
\begin{gather*}
\neg Q
\end{gather*}
oblivious that if we use resolution, and resolve each clause we achieve $\bot$.
As a result we can say $1$ is valid.
$2$ is not valid, you can use above method or if we set
\begin{gather*}
Q\equiv \top
\end{gather*}
\begin{gather*}
 P\equiv R\equiv \bot
\end{gather*}
as a result $2$ is $\bot$.
Repeat idea that used in $1$ for $3$:(as you know from logic, $A\leftrightarrow B\equiv (A\to B) \wedge  (B\to A)$) so we have:
\begin{gather*}
 \neg(((\exists x(P(x)\to Q(x)) \to (\forall xP(x)\to \exists xP(x)))
\end{gather*}
\begin{gather*}
\wedge
\end{gather*}
\begin{gather*}
(\forall xP(x)\to \exists xP(x)) \to ((\exists x(P(x)\to Q(x))  ))
\end{gather*}
After applying  negation:
\begin{gather*}
\equiv
\end{gather*}
\begin{gather*}
 (((\exists x(\neg P(x)\vee Q(x)) \wedge (\forall xP(x)\wedge \forall  x\neg P(x)))
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\exists x\neg P(x)\vee \exists xP(x)) \wedge  ((\forall x(P(x)\wedge \neg Q(x))  ))
\end{gather*}
Eliminate quantifiers:
\begin{gather*}
 (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x))
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
As you know
\begin{gather*}
 (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x))\equiv \bot
\end{gather*}
So we have:
\begin{gather*}
 \bot
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
\begin{gather*}
\equiv
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
As a result above formula can't equal to $\top$ because we can't resolve some clauses to get $\bot$. So $3$ isn't valid.
$4$ remain as exercise, if you follow described approach for other options, you can see $4$ is not valid.


PAC learnability given information about the expectation of the training/true error Let $ \mathcal{X} $ be a domain set, $ \mathcal{Y}=\{0,1\} $ and $ \mathcal{H}$ an arbitary hypothesis class.

Assuming that there's an algorithm $ \mathcal{A} $ such that for every distribution $ \mathcal{D} $ realizable by $ \mathcal{H}$, it holds that
$ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))] \leq \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_S(\mathcal{A}(S))]+\epsilon_m$ where $ \epsilon_m \rightarrow0 $.

Does that mean that $ \mathcal{H} $ is PAC-learnable?

($L_\mathcal{D}(h) $ is the true error of hypothesis $h$ with respect to the 0-1 loss function)

Well, I think that it's not, but I lack the knowledge to put a finger on the exact reason why.

My intuition is that even though $ \epsilon_m \rightarrow 0 $, there still may be an arbitrary gap between $ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{D}}(\mathcal{A}(S))] $  and $ \mathbb{E}_{S \sim \mathcal{D} ^M}[L^{0-1}_{\mathcal{S}}(\mathcal{A}(S))] $. Thus, we still don't know how approximately good $ \mathcal{A}(S) $ is.

Can I deduce any promises whether $ \mathcal{A}(S) $ "probably" good (something about $\delta$)?

There's no need for formal proof. Rather, intuition will be appriciated.

$\mathcal{H}$ is not necessarily pac learnable.

Lets break down your statement, you have an algorithm $\mathcal{A}$, which given a set of labeled samples $S\subseteq \mathcal{X}\times \mathcal{Y}$, generates a hypothesis in $\mathcal{H}$. You also know that $\mathcal{A}(S)$ achieves a generalization error which is close to its sample error (the closeness is determined by $\epsilon_m$).

If $\mathcal{A}$ was guaranteeing low sample error, then we were safe. However, this is not necessarily the case, take for example the rather stupid learning algorithm which always outputs some constant $h\in \mathcal{H}$ (and ignores the samples). This algorithm has equal sample/generalization error (so the condition is satisfied), but this obviously does not mean $\mathcal{H}$ is pac learnable (you can implement this algorithm even for $\mathcal{H}$ with infinite VC dimension).


Understanding non-linear dimensionality reduction algorithm (locally linear embedding) I have a question about Locally Linear Embedding. I am trying to study this algorithm and implement it for better understanding. I have read An Introduction to Locally Linear Embedding. However, I don't think I really understood this algorithm. There are several questions I want to ask.

I understand that this algorithm takes some high dimensional data set and reduce it into lower dimensional data set while keeping some geometric features of the original data set. In the article, they use S-shape manifold, sample data from the manifold and reduce it into lower dimension. So I see from the picture that each region on the manifold specified by colors are conserved. But I don't think I understood why do we need this kind of reduction. I don't think it is guaranteed that any data set can be reduced to two or three dimension so that we can visualize the original data set which means how the geometric features are conserved. Can anyone explain this with some example?
I don't really understand how this algorithm can be implemented. The paper shows the reconstruction error $\epsilon(W)=\sum_i \left| X_i - \sum_jW_{ij}X_j \right|^2$ and saysThe weights summarize the contribution of the jth data point to ith reconstruction. I don't understand what this sentence means and how the weight matrix $W_{ij}$ can be constructed. Each $X_i$ represents each column in the data?? Then how can I understand $\sum_jW_{ij}X_j$?? Can anyone explain this?
The paper says that the data reduced into lower dimension can be constructed by the closest points of each data points. How is this work?

Thank you

To answer your first question:

Usually we want to reduce the dimension, because dealing with high-dimensional data is a pain: (a) algorithms for dealing with high-dimensional data tend to have higher computational complexity, and (b) high-dimensional data is hard to visualize and hard to understand.  If you can reduce the dimension without significant loss of effectiveness of the subsequent computational task, that can be useful.


A complicated variant of Weighted Median problem Suppose, we have an array of numbers $x_j$ and their corresponding weights $w_j$ where $\sum_j w_j \gt 1$. Now we need to find $x_m$ such that

$$\sum_{j=1}^{m-1} w_j \lt 1/2 \quad \text{and} \quad \sum_{j=m+1}^{n} w_j \ge 1/2$$

Moreover, $x_m > x_j$, $x_m < x_k$ where $j \ne k$. i.e. a solution should be like this --

$$\underbrace{x_1, x_2, \ldots, x_{m-1}}_{\lt \, x_m}, x_m, \underbrace{x_{m+1}, \ldots, x_{n-1}, x_n}_{\ge \, x_m} \\
\underbrace{w_1, w_2, \ldots, w_{m-1}}_{\lt \, 1/2}, w_m, \underbrace{w_{m+1}, \ldots, w_{n-1}, w_n}_{\ge \, 1/2}$$

Moreover, it was also mentioned that I may use Dynamic Programming that could be bounded by $O(n\lg n)$.

EDIT:

$\{x_j, w_j\}: \quad x_j \text{ is the value and } w_j \text{ is the weight.}$

Example Input: $\{10, 0.4\}, \, \{5, 0.1\}, \,  \{6, 0.9\}, \, \{2, 0.3\}, \, \{3, 0.1\}$

Example Output: $\{2, 0.3\}, \, \{3, 0.1\}, \,  \underbrace{\{5, 0.1\}}_{x_m}, \, \{6, 0.9\}, \, \{10, 0.4\}$

How I tried

Step 1: First sort the list according to $w_j$. -- $O(n \lg n)$

Step 2: Start from the first element from the left, add the weights $w_j$ until
$\sum_j w_j \ge \, 1/2$. The current $x_j$ is the $x_m$. -- $O(n)$

Step 3: Stop, now we have two lists. One is on the left $L=\{x_1, x_2, \ldots, x_{m-1}\}$ and the other is on the right $R = \{x_m, x_{m+1}, \ldots, x_n\}$.

Step 4: Go through the list $L$, if there is any value $x_k > x_m$, move $x_k$ into $R$ at an appropriate position. Do this until all elements in $L$ is smaller than $x_m$. -- $O(n^2)$

Step 5: if $L \ne \emptyset$, $x_m$ is the answer, otherwise $x_1$ is the answer.

The overall complexity will be $O(n \lg n) + O(n) + O(n^2) \approx O(n^2)$. I got confused about the DP stuff at the end of the question, so I was wondering if there is really any way to do it in $O(n \lg n)$ (or better), how do I build the optimal substructure in the case of DP?

A tip: this problem becomes much easier if you sort the $x$'s into increasing order.  (If you sort by the $w$'s, your life will be much much harder.)

More precisely, you should sort the entries so the $x$-values are in increasing order, resolving ties so the $w$-values are in increasing order.  This amounts to lexicographic order on $(x,w)$.  This way, if $i<j$, then $x_i\le x_j$ and either $x_i<x_j$ or $w_i\le w_j$.

Once the elements are sorted in this way, you can solve this problem with a linear scan.

Just scan from left to right (i.e., from $i=1$ to $n$), keeping track of the sum of the weights seen so far (i.e., $w_1+w_2+\dots+w_i$).  When this sum transitions from less than $1/2$ to greater than $1/2$, you've found the weighted median.  At the very end, if there are multiple elements with the same $x$-value as the one you found, scan leftwards to find the first element with the same $x$-value as the one you initially found.

Running time: $O(n \lg n)$.  It takes $O(n \lg n)$ time to sort, plus $O(n)$ time for the linear scan.  No need for fancy dynamic programming.

My thanks to Dukeling for helpful comments and corrections!


Asymptotic notation? can someone pls help
How do I prove

2⌊lg n⌋ = Θ(2⌈lg n⌉)
2 ⌈lg n⌉+⌊lg n⌋ = Θ(n2)

I'm not too good at maths.
I know,
lim ( n -> infinty) = f(x)/g(x) if we get a real constant the statement is true.

First, observe that $\lfloor \log N \rfloor < 2\lceil \log N \rceil$ holds for all $N \geq 2$.
Let $n_0 = 2$, $c_1=2$, $f(N)=2\lfloor \log N \rfloor$, $g(N) = 2\lceil \log N \rceil$.
So $$f(N) \leq c_1 \cdot g(N)$$
holds for all $N \geq n_0$.
Next, observe that $\lfloor \log N \rfloor > \frac{1}{2}\lceil \log N \rceil$ is true for all $N \geq 2$.
Let $c_2 = \frac{1}{2}$.
Thus,
$$f(N) \geq c_2 \cdot g(N)$$
Therefore, $$f(N) \in \Theta(g(N))$$
But the second question, it is obvious that the statement is incorrect, so I'll not be proving here.


Find a pushdown automaton for { x#y ∣ x ≠ y } I was told to built a PDA that recognizes the following language:

$$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$

My attempt is basically to push $x$ to the stack for every $1$ and $0$ read. And then pop them for the second half. If it finishes and the stack is still not empty, it will be accepted. Or if it hasn't finished reading but the stack is empty already it will also accept.

Am I approaching this correctly?
I can easily do the CFG but I'm told that it's easier to do the PDA from scratch rather than converting it since it needs to be in CNF.

Any help appreciated

Since you have a marker $\#$ separating $x$ and $y$, the solution is
rather easy. The PDA must first decide non-deterministically whether
it will attempt to check that $|x|\neq|y|$ or whether $x$ and $y$
differ for their $i$-th symbol, i.e. whether $x_i\neq y_i$. This
corresponds to two distinct sets of states.

The first case can be dealt with as you suggest.

In the second case, the automaton scans the input, and stores a symbol
$a$ in its stack to keep count. At the $i$-th symbol, chosen
non-deterministically, it decides to check whether that is the symbol
rank for which $x_i\neq y_i$. So it memorizes the synbol $x_i$ in its
finite control (meaning that the states now used have a component
indicating whether a $0$ or a $1$ was found). Then, the PDA scans the
input without memorizing anything until it scans the symbol $\#$. Then
it start scanning the $y$ part, popping the stack for each symbol
read. When the stack is empty, it is reading the symbol $y_i$, and it
can check whether it is different from $x_i$ memorized in the finite
control. If it is different, the PDA can accept the string, and does
not even need to scan the rest.

If the end of the string is reached before the stack is empty, the
automaton can accept too, though this can also be handled by the first
case.


An efficient algorithm to decide if a triangulation is 3-colourable I don't know how to start with the following exercise:

  Design an efficient algorithm to decide whether a given triangulation with $n $ points is $3$-colourable.
  The triangulation is given by a sorted edge list, where every edge is given by the indices of its two end points. Further, for every edge there are given the indices of the points with which the edge forms a triangle in the triangulation (two indices for interior edges and one index for edges on the boundary of the convex hull). Give proof for the correctnesss of your algortihm.

Below is an example.

I've heard about the BFS and DFS algorithms in lecture, but I don't see how I could apply this here. I'd be thankful for any help.

Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces.

Pick an arbitrary triangular face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex of $F'$. Continuing in this way, attempt to color all vertices. If you're successful, the graph can be 3-colored. Otherwise, the graph cannot be 3-colored.

This algorithm is very similar to the one for deciding whether a given graph can be 2-colored.


Major Field Test Sample Questions (need further clarification) I have several questions that do no make sense for me.

First Question:
A stack can be implemented with an array A[0..N-1] and a variable pos. The push and pop operations are defined by the following code.

push (x)
  A[pos] <- x
  pos <- pos – 1
end push

pop ( )
  pos <- pos + 1
  return A[pos]
end pop

Which of the the following will initialize an empty stack with capacity N for this implementation?

a)pos <- -1

b)pos <- 0

c)pos <- 1

d)pos <- N - 1

e)pos <- N

I have zero idea for this question and I dont understand what is being asked

Second Question: Consider the following recursive function

int Fun ( int n )
if ( n == 4 )
  return 2
 else
  return 2 * Fun ( n + 1 )
 end if
end Fun

What is the value returned by the function call Fun(2)?

a)2

b)4

c)8

d)16

e)24

The answer is C but I got 6 cox this is how I did it, because n is 2 and it not 4 so it return 2 * (2+1) which is equal to 6

Third Question: Following is a definition of a widget and a declaration of an array A that contains 10 widgets. The size of a byte, short, int, and long are 1,2,4 and 8 bytes, respectively. Alignment is restricted so that an n-byte field must be located at an address divisible by n. Th fields in a struct are not rearranged padding is used to ensure alignment. All widgets in A must have the same size

struct widget
  short s
  byte b
  long l
  int i
end widget

widget A[10]

Assuming that A is located at a memory address divisible by 8, what is the total size of A, in bytes?

a)150

b)160

c)200

d)240

e)320

The answer is D but I dont understand why is it D and not C.

I will try my best to explain the first question.

They are basically asking what value pos need to be in order for the stack to be empty. Since we are using an array as a stack, we have a choice between 0 or N-1. Looking at the code, Pop increment pos and push decrement pos. We want to follow pop because it pops the first element and so on to the last element. If we pop all elements in the array it will equal N-1 values. The answer should be D.


Average Time Complexity of Searching An Array Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must also be done, so $\frac{2n}{2} = n$?

It sounds like you're talking about a linear search.  If we assume that the key is equally likely to be in any of the $n$ locations in the array, then the expected location is $\frac{n+1}{2}$.  A linear search for this element would then require $O(\frac{n+1}{2}) = O(n)$ time.


Closure of regular languages under "inverse second half" Theorem. Show that if $L$ is regular, then so is
  $$
\varphi(L)=\left\{w \in \Sigma^{*} \mid \text {there exists an } \alpha \in \Sigma^{*} \text { with }|\alpha|=|w| \text { and } \alpha w \in L\right\}
$$
  Proof. Let $L$ be a regular language. Because $L$ is regular, there exists a DFA $M$ that accepts it. We construct out of $M$ a $\lambda$NFA $M'$ whose language is $\varphi(L)$.

  We can think of a computation of $M$ as moving a token across the states of $M$. The machine $M'$ will reuse the states of $M$, but will use three tokens: white, red and blue.
  Initially, the blue token is put on $q_0$ (the initial state of $M$), and the white and red tokens are put on a nondeterministically guessed state (both tokens on the same state).

  Describe the transitions of $M'$.
  Describe the acceptance condition of $M'$.

Could someone please help me with that? I research regular expressions, DFAs, NFAs, and conversions between all of theses, but I still don't know how to solve this question.

The white token is a placeholder, which just remembers the original state of the red token (of course, the roles of these two tokens can be switched); this is the state at which $M$ would be after reading $\alpha$. The red token corresponds to the $w$ part of the word, and the blue token to its $\alpha$ part.

When reading a symbol, the red token advances according to the rules of $M$, the white token stays put, and the blue token guesses a symbol and advances according to the rules of $M$ (in effect, it guesses one symbol of $\alpha$).

The machine accepts if the blue and white tokens are at the same state (so we guessed correctly the state at which $M$ is after reading $\alpha$), and the red token is at an accepting state of $M$ (so $\alpha w \in L$).


How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time? This looks like a typical divide and conquer algorithm, but with a few tricky parts.

It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) restriction, but I'm confused about the specifics. When I try to come up with the algorithm, I think about making k comparisons with varying elements that are ceil(n/k) apart, but I don't see how recursively doing anything like that with broken up halves of the array would do anything beneficial.

Given this sorted array:

A = [1, 2, 3, 4, 4, 4, 4, 5]

If k = 1, then we do one comparison between A[0] and A[7] and we're done.

If k = 2, we can't do much because there's no good way to make 2 meaningful comparisons. And if we're going to split it in half and check again to fulfill the log(n) time requirement, the 4's would get split up.

Any ideas?

Let m = ceil [n/k], so you want numbers occurring m or more times. Since the array is sorted, if you check array elements a [m-1], a[2m-1], a[3m-1] etc. you find all the integers you want (and some you don't want).

So you start with x = a [m-1]. If x == a [2m-1] then you found a number, and you can remove a[3m-1], a [4m-1] etc. as long as they are equal to x.

If x != a [2m-1], then you use binary search to find the largest i from m-1 to 2m-2 that is equal to x, and check whether x = a [i - m + 1]. That's the idea, you have to be a bit careful to implement it.

Since at most you do k binary searches in subarrays of length m, the time is O (k log m) = O (k log (n / k)) which is quite a bit better than O (k log n) when k is large (and if k is small then the execution time is small anyway).

A bit more careful implementation: You want to find all integers in a sorted array that occur at least m times. Let's call these integers "heavy". Let c = 0; throughout the algorithm you have found all heavy numbers before a [c], and there is no array element before a [c] that is equal to a [c].

If c + m - 1 ≥ n then you are done. Otherwise let i = c + m - 1 and x = a [i]. There can be no element in a [c] to a [i - 1] that is heavy and different from x, so the question is whether x is heavy.

Let j = i; and as long as j + m < n and a [j + m] = x, let j = j + m. Use binary search to replace j with the largest index from j to min (j+m-1,n-1) containing an element equal to x. So now a [i] to a [j] are all equal to x, and there is no element at a [j+1] equal to x.

If j ≥ i + m - 1 or a [j - m + 1] == x then x is heavy. In any case, replace c with j + 1 and continue.

We increase c at least by m at the cost of one binary search in an array of length m or less, or we increase c by m again in constant time.

PS. You could improve the execution time slightly as follows: You always check for the last number in an interval of size m-1 which is equal to x. Depending on where that last number is found, the algorithm makes more or less progress. To improve the worst case, you replace binary search by something slightly less balanced that is faster when the result is at the left end of the interval, so that there is less work if there is less progress.


Dijkstra and A* Algorithms: Why is A* faster? I am learning about Dijkstra's Algorithm and the A* Algorithm and I have manually worked through the graph attached here, which is supposed (I think) to demonstrate that the A* Algorithm is faster than the Dijkstra one. The sequence in which I chose the nodes is indicated by the circled numbers. I can see that the process is fairly simple but there are plenty of possibilities for human error, so please bear with me.

My course book says that the A* will be quicker.

I can't see why this is true. Have I worked through the graph incorrectly?

It seems to me that both methods require that all nodes must be visited so where is the increase in efficiency?

I have read what I can on Stack Overflow about this so please don't point me at earlier posts unless there is a very good reason.

I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods:

Dijkstra algorithm is an exploration method that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the queue.

You may run this algorithm to find the shortest path from a specific node $s$ to a specific node $t$. But you can also use it to determine global properties of the distances from $s$. Or for instance, build a tree that let you backtrack the path from $s$ to any vertex.

A* algorithm is basically a Dijkstra method that use an additional heuristic to sort the nodes of the queue. On distance problem, this heuristic is generally based on the euclidian distance from the node to the aim. It favorises the exploration of the nodes that are more likely to go in the good direction. So this specialization of Dijkstra algorithm is only used to go from a specific node $s$ to a specific node $t$. It is generally largely faster but does not guarantee to find the optimal path (in the ver).

I suggest you play with this  pathfinding simulation tool


Resource Allocation Graph: Two processes want the same resource In the example below, is this guaranteed to be safe? I see two processes that require the same resource. It's not a direct cycle but it seems to be a possible deadlock where P0 could get held up.

Where is the problem here?is there a missing edge from ur graph?....As I see it : R3 could be assigned to P1 till it finishes, then to P2 (or vice verca), finally when both P1 & P2 finishes P0 could get R1,R2 (freed by now)


Are the functions always asymptotically comparable? When we compare the complexity of two algorithms, it is usually the case that either $f(n) = O(g(n))$ or $g(n) = O(f(n))$ (possibly both), where $f$ and $g$ are the running times (for example) of the two algorithms.

Is this always the case? That is, does at least one of the relationships $f(n) = O(g(n))$ and $g(n) = O(f(n))$ always hold, that is for general functions $f$,$g$? If not, which assumptions do we have to make, and (why) is it ok when we talk about algorithm running times?

Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and
$$
g(n) = \begin{cases}
 1 & \text{if $n$ is odd},
\\\
 n^2 & \text{if $n$ is even}.
\end{cases}
$$
Moreover, functions like $g(n)$ do actually arise as running times of algorithms.  Consider the obvious brute-force algorithm to determine whether a given integer $n$ is prime:

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

This algorithm requires $\Theta(1)$ arithmetic operations when $n$ is even, $O(\sqrt{n})$ operations when $n$ is composite, but $\Theta(n)$ operations when $n$ is prime.  Thus, formally, this algorithm is incomparable with an algorithm that uses $\sqrt{n}$ arithmetic operations for every $n$.

Most of the time when we analyze algorithms, we only want an asymptotic upper bound of the form $O(f(n))$ for some relatively simple function $f$.  For example, most textbooks would simply (and correctly) report that IsPrime(n) runs in $O(n)$ arithmetic operations.  Typical upper bound functions are products of exponentials, polynomials, and logarithms (although more exotic beasts like factorials and iterated logarithms also show up occasionally).  It is not hard to prove that any two such functions are comparable.

See also this MathOverflow question.


Is there a standard way to define a formal language transformer? I'm about to study a system that takes words in a formal language $L$ and converts them into words in a different formal language $L'$. In other words: a formal language transformer. I was wondering if there is literature on formal language transformers, some standard way of studying, and defining them?

All I found are a 1995 paper by Cousot & Cousot on program analysis where formal language transformers are mentioned, but not really studied, and a 2005 presentation by Jaeho Shin that mentions the Cousot & Cousot paper. But maybe I'm looking in the wrong place or maybe I'm using the wrong vocabulary?

After all the effort in defining and studying the very many kinds of formal languages, it seems strange to me that nobody has bothered studying their transformations into each other.

Without knowing what kind of transformation you compute, it's unlikely that there's a useful word. Assuming that any two inputs are processed independently of each other, you're looking at (computable) function(al)s from $A^* \to B^*$ with two alphabets $A$ and $B$.

Here are some specific kinds of transformations:

string homomorphisms,
finite-state transduction, or
the transducer equivalent(s) of any automaton model.


Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$ I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=\Omega(n^{\lg_b^{a+\epsilon}})$. However, I have tried to prove this statement, and was unable to do so.
The question is how to prove that the regularity condition of master theorem case 3 always holds on the two above-mentioned functions.

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$,
$$
a(n/b)^k < cn^k.
$$
We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.

If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take
$$
f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)}
$$
Then
$$
f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}).
$$
On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.


$ACC^{0}$ vs Poly-size circuits of bounded degree We know that NEXP $\not\subset ACC^0$ (Ryan Williams'10 Result). Also, We know that even $\Sigma_{2}^{P}$ cannot have polynomial circuits of bounded degree i.e. $SIZE(n^k)$ for some $k \in N$ (Kannan's Result). Does this give a hint towards $ACC^0$ is far more powerful than polynomial circuits of bounded degree? Are they even comparable?

$ACC^0$ and $SIZE(n^k)$ are probably incomparable for all $k$.

$ACC^0$ is conjectured not to contain $Maj(x_1,..,x_n)$, which has linear size circuits (think about the naive Turing machine for majority and transform it into a circuit, things are much easier when you don't have a depth restriction). This shows that it probably holds that $SIZE(n)\not\subseteq ACC^0$.

On the other hand, $ACC^0$ does allow you to use polynomially many gates (with no degree restriction). We will show that under a certain assumption, for every $k\in\mathbb{N}$ it holds that $ACC^0\not\subseteq SIZE(n^k)$. Consider the problem of deciding whether a graph contains a $c$-size clique (where $c$ is a constant independent of the input).

This problem is obviously in $AC^0$ (for all $c\in\mathbb{N}$), since you can, in the first level, link all subsets of $c$ vertices into AND gates to check whether they form a clique, and in the second level link all the results from the previous level into an OR gate.

If this can be done using $SIZE(n^k)$ circuits, then $\mathsf{NP\subseteq P/Poly}$, since we can construct polynomial size circuits for CLIQUE. The circuit for $n$ vertices graph needs to be able to check the existence of an $1,2,...,n$ clique. Since finding $c$-cliques is in $AC^0$ for all $c$, and we assumed $AC^0\subseteq SIZE(n^k)$, we have an $n^k$ size circuit for each possible clique size, combining those will result in an $n^{k+1}$ size circuit for clique on $n$ vertices graphs, which puts $\mathsf{NP}$ in $\mathsf{P/Poly}$.


Complexity of negation cancellation Consider propositional logic over the connectives $\land$, $\lor$, and $\lnot$. Notation: $| \alpha |$ is the length of formula $\alpha$.

We are given a formula $\phi$. Cancel all cancellable negations in $\phi$ by applying all possible valid biconditionals (EDIT: such as the examples below) to get $\phi'$; for clarity we note that $\phi \leftrightarrow \phi'$. We are also given that $\phi'$ is monotonic. Are there examples where $| \phi' |$ must grow exponentially, or is $| \phi' |$ bounded by a polynomial? If there's an example of exponential growth, please show it.

EDIT: The following biconditionals are examples of what I'm trying to get at, formulas which can be used to cancel negations while preserving equivalence. The procedure would presumably be to unify the left-hand side of the formula with $\phi$ via unification and substitute the right-hand side as appropriate per unification.

$$\alpha \land (\lnot \alpha \lor \beta) \leftrightarrow \alpha \land \beta$$ $$\lnot \lnot \alpha \leftrightarrow \alpha$$

I suspect the answer is that in general $\phi'$ might need to be of exponential size, but I am not certain.  There are known examples of a boolean circuit $C$ (with negations) of polynomial size that computes a monotone function, while the smallest monotone boolean circuit $C'$ (with no negations) has exponential size.  See http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf and Simple example of exponential gap between monotone and non-monotone circuits.  It's possible that perhaps this could be extended to an argument that covers your case as well: if there is a polynomial-size formula $\phi$ corresponding to $C$ (this would need to be checked), the results above imply that any monotone formula $\phi'$ computing the same function would need to be of exponential size, so there would necessarily be an exponential gap for some functions, no matter what set of substitution rules ("biconditionals") you use.  The gap in this argument is verifying whether Tardos's example can indeed be computed by a polynomial-size circuit; it's not clear whether it can, as circuits are more powerful than formulas, and I haven't verified this, but perhaps you can do so.


How could one prove that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ? Using induction I am currently working on ways to prove this and got stuck proving it with induction.

Any tips?

How could i prove  that for every finite alphabet Σ, ∀ n ∈ ℕ. |Σⁿ| = |Σ|ⁿ?

One way would be to show an isomorphism between strings and ordered sets, then the result is a direct consequence of properties of set cardinalities (namely that $|A \times B| = |A|\cdot|B|$ for any two sets $A$ and $B$).

Let's assume that you don't want to do that (for a start it's probably more work to do it properly - but very quick to do it in a hand-waving manner).

The first step is that we need to show that for a set of string $S$ and an alphabet $\Sigma$, $|S\circ \Sigma| = |S|\cdot|\Sigma|$, where $\circ$ is the concatenation operator (overloaded for sets as well as strings). This is not hard of course: each string $s \in S$ and each $\sigma \in \Sigma$, the string $s \circ \sigma$ is in $S \circ \Sigma$ and this string is different for every choice of $s$ and $\sigma$.

Next we can inductively show that $|\Sigma^{n}| = |\Sigma|^{n}$.

Base Case:

$\Sigma^{0}$ is the set of strings obtained by concatenating elements of $\Sigma$ $0$ times, i.e., just the empty string $\varepsilon$ (or $\lambda$ if you're that way inclined :D). So $|\Sigma^{0}| = 1$. Of course $\alpha^{0} = 1$ for any $\alpha \in \mathbb{N}$, so $|\Sigma^{0}| = 1 = |\Sigma|^{0}$.

Inductive Hypothesis

Assume that $|\Sigma^{k}| = |\Sigma|^{k}$.

Inductive Step

$\Sigma^{k+1} \ = \Sigma^{k}\circ\Sigma$, therefore $|\Sigma^{k+1}| = |\Sigma^{k}\circ\Sigma|$, which we have established is $|\Sigma^{k}|\cdot|\Sigma|$, by the inductive hypothesis (and power laws) $|\Sigma^{k}|\cdot|\Sigma| = |\Sigma|^{k}\cdot|\Sigma| = |\Sigma|^{k+1}$, which is what we wanted to show.


Averaging a list of variances In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. For mean, I simply do the averaging by:
$\mu = \frac{\mu_1+\mu_2+.....+\mu_n}{n}$
However, for the variance, I can't figure out to average n variances. For only two I found this answer here
$\sigma^2 = \frac{1}{2}(\sigma^2_1 + \sigma^2_2) + (\frac{\mu_1-\mu_2}{2})^2$
But how about n variances?
thank you

Let's assume you have $n$ datasets, $x_k$ is the $k$th dataset. It's length we denote by $l_k$, its elements are $$x_k =\big\{x_k(1), x_k(2), \dots, x_k(l_k)\big\},$$
and its mean and variance are respectively
\begin{align}
\mu_k &= \frac{1}{l_k}\sum_{i=1}^{l_k} x_k(i),\\
\sigma_k^2 &= \frac{1}{l_k}\sum_{i=1}^{l_k} x_k(i)^2 - \mu_k^2.
\end{align}
Then, noting that $l_k\mu_k = \sum_{i=1}^{l_k} x_k(i)$:
\begin{align}
\mu &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^n\sum_{i=1}^{l_k} x_k(i)\\
\mu &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^nl_k\mu_k
\end{align}
and in similar fashion
\begin{align}
\sigma^2 &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^n\sum_{i=1}^{l_k} x_k(i)^2 - \mu^2\\
\sigma^2 &= \frac{1}{\sum_{k=1}^nl_k}\sum_{k=1}^nl_k\left(\sigma^2_k + \mu_k^2\right) - \mu^2
\end{align}
When $l_k = N$ for all $k$ the above simplifies:
\begin{align}
\mu &= \frac{1}{n}\sum_{k=1}^n\mu_k\\
\sigma^2 &= \frac{1}{n}\sum_{k=1}^n\left(\sigma^2_k + \mu_k^2\right) - \mu^2
\end{align}
however when the datasets have different sizes the above does not simplify, and you need to take that into account.


Construct a PDA for the complement of $a^nb^nc^n$ I am wondering if this is even possible, since $\{a^n b^n c^n  \mid n \geq 0\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\{a^n b^n c^n  \mid n \geq 0\}$ from the rest of $\{a^*b^*c^*\}$ might as well accept it, which sounds contradictory to me.

I guess I need to take advantage of the non-deterministic nature of PDAs but I'm out of ideas. If you could offer some advice I would very much appreciate it.

No, this is context-free. To accept $a^nb^nc^n$, you need to make sure that three numbers are equal. To accept $a^*b^*c^* \setminus a^nb^nc^n$, you just need to make sure that you're in one of the following three cases:

The number of $a$s is different from the number of $b$s; or
The number of $a$s is different from the number of $c$s; or
The number of $b$s is different from the number of $c$s.

Write a PDA for each of these cases, then combine them by jumping nondeterministically to each one from the start state.


Why Can't Reverse Hashing Prove $P \neq NP$? Lets assume a hashing algorithm that runs in polynomial time and produces a hash that is mathematically impossible to reverse. As far as I know, the $P=NP$ problem states that if they are indeed equal, then if an algorithm exists to verify a solution in polynomial time, then an algorithm exists to find a solution in polynomial time. In this case, we can verify a solution by just running it through the hashing algorithm and comparing the final results. However, there cannot exist an algorithm to find a solution, since the hash is impossible to reverse.

Give a polynomial time hash function that takes exponential time to compute the inverse of.

That’s an open problem. It can’t currently be used to resolve $P$ vs $NP$ because no one knows if there is an example of such a function. In CS, we often assume that $P\neq NP$ and that there are cryptographically secure hashes, but that’s an (experienced based) assumption, not a probable fact.


An explanation for Barendregt use of Y combinator in an equation I am going through the following lecture notes on lambda calculus by Barendregt and Barendsen :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

Here at page 12 , after introducing fixed point theorem a small exercise which is an attempt to prove the following has been posted :
$ \exists G  \forall X $ $GX =SGX $.

It first proceeds to  the implication

$Gx$ = $SGx$

which implies :
$G$ = $ \lambda x .SGx $

which implies :
$G $ = $ (\lambda gx.Sgx)G$

and then it concludes that :

$G$ = $Y$ $( \lambda g x.Sgx)$ where $Y $ is the fixed point combinator .

I am unable to figure out how was G found out to be  $Y$ $( \lambda g x.Sgx)$ in the last step ? How was this conclusion reached up to ?

The Y combinator satisfies the equation $Y f = f(Y f)$. Hence $g = Yf$ solves the equation $g = f g$. In your case, the function $f$ is $\lambda g x.Sgx$.


How to show that the set of machines which accept languages in $\mathrm{NP}\smallsetminus\mathrm P$, is decidable only if $\mathrm P=\mathrm{NP}$? I'd like your help with proving that the language
$$L=\{\langle M \rangle \mathrel| L(M) \in \mathrm{NP}\smallsetminus \mathrm{P} \}$$
is decidable iff $\mathrm{P}=\mathrm{NP}$.

If $\mathrm{P}=\mathrm{NP}$, I get that it's the language of empty Turing machines. So $L$ is a $\text{co-RE}$ problem — but that's not what's being asked, so I got confused.

I know that in order to show $\mathrm{P}=\mathrm{NP}$, I need to show problem which it's $\mathrm{NPC}$ and $\mathrm{P}$ as well.

Any help?
Thanks!

There are two cases to consider.

Assume that $\text{P=NP}$. Then $L=\{\langle M\rangle \mid L(M)\in \emptyset\}=\emptyset$. The empty language is decidable; as no word belongs to it, it is trivial to decide whether a word belongs to it or not.
Assume that $\text{P}\neq\text{NP}$. Now your result follows directly from Rice's theorem.


Termination of Moore's algorithm to minimize deterministic automata I use Moore's algorithm to minimize DFA as concluded below.

We start with the complete graph with vertices Q and edges E = { {p, q} | p = q ∈ Q }
We mark all edges {p, q} ∈ E with p ∈ F and q ∈ F
As long as there exist marked edges in E, we repeat the following procedure. We choose some marked edge {p , q } ∈ E. Then we mark all unmarked edges {p, q} ∈ E with {p , q } = {p · a, q · a} for some a ∈ Σ. Afterwards we remove the edge {p , q } from E.
All marked edges are eventually removed.

Then I guess a new minimal automata is obtained by joining the states linked by the remaining unmarked edges. Is it true?

If so, what about this case?

States: {1, 2, 3}
Alphabet: {a, b}
Start: 1
Final: {3}
Transition: {(1, a, 2), (2, b, 3)}

By Moore's algorithm, at the end of loop we will have one unmarked edge between state 1 and 2.
As my guess above, the next step is joining both states.
But the result doesn't make sense.

Most minimization algorithms assume automata to be complete s.t. for every state p and alphabet a, there is a transition where (p, a, q). Hence, for the case, we need to add one more state as a sink state.
The DFA becomes:

States: {1, 2, 3, 4}
Alphabet: {a, b}
Start : 1
Final : {3}
Transition :
{(1, a, 2), (1, b, 4), (2, a, 4), (2, b, 3), (3, a, 4), (3, b, 4),
(4, a, 4), (4, b, 4)}

By Moore's algorithm:

Picking edge(3,4) causes we mark edge(2,1) and edge(2,4) by b-transition.

Picking edge(2,4) causes we mark edge(1,4) by a-transition.

Now we don't have any unmarked edges left. Hence, no states has to be joined.


Partition array - elements non-negative and negative. Minimal number of replacements of elements I consider following problem:
It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$.
The problem is: replace elements such that negative numbers precede the non-negative. For our example: $[-2, -324, -2, 321,0,213,1]$.
Additional requirement is that algorithm should do minimal number of replacements.

My approach
Let's use partition from qsort algorithm - pivot is always $0$. It does $\lfloor n/2\rfloor $ replacements.
I think that it is minimal number. It is because of pesimistic case:
$|[1,1,..,1,-1,-1,...-1]|=n$  - in this case we must do at least $\lfloor n/2\rfloor $ replacements.

Can you give me algorithm that do less than $\lfloor n/2\rfloor$ replacements ?

Hint:

Create a new array $B=[]$ where $B[i]=1$ if  $A[i]<0$ and $2$ elsewhere.
You can prove that sorting $B$ is same as performing said operation on $A$

So now, We have to sort an array which only contains two values.
You can do this by a greedy algorithm, whose proof you can obtain by the principle of Induction.

As an extra hint: Let $B=[1.....1,2.....2,1,........]$. where  C is another segment of the array. You have to do something now.

Trust me this is great help. You can continue from here.

As for why it requires fewer(or equal) than $n/2$. The proof is quite easy, once you've devised the algorithm.


Term of System F whose type-erasure is $2(2)$ If $2$ is the Church numeral $\lambda fx. f(f(x))$, then is there a closed term $t$ of System F of type $\forall \alpha ((\alpha \to \alpha) \to (\alpha \to \alpha))$ such that the type-erasure of $t$ is the untyped term $2(2)$?

Consider the System F version of two:

$$ T = \Lambda \alpha.\lambda f:\alpha\to\alpha. \lambda x:\alpha. f(f(x))$$

We can then search for a term $M$ of the form

$$ M = \Lambda \alpha. T \tau_1 (T \tau_2) $$

and try to find types $\tau_1,\tau_2$, possibly depending on $\alpha$, such that $M : \forall \alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Surely $M$ becomes $2(2)$ after type erasure.

I'll leave finding $\tau_1,\tau_2$ as an exercise. Think about what is the type of $M$, and require it to be the wanted one: this provides $\tau_1$. After that, choose $\tau_2$ so that $M$ is well-typed.


Are there any problems that require exponential time in quantum computing? Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with a quantum computer?

I've checked the Complexity Zoo and couldn't find any complexity class mentioned there that fits this description.

Most problems that require exponential time on a classical computer also require exponential time on a quantum computer.  For example EXPTIME-complete problems will require exponential time on either a classical or a quantum computer.

The class of problems solvable in polynomial time on a quantum computer is called BQP.  It is believed unlikely that BQP contains the NP-complete problems.  Thus the NP-complete problems probably take exponential time on quantum computers.

One of the most interesting problems that is known to be in BQP, but believed not to be in P is the integer factoring problem.  But integer factoring is believed unlikely to be NP-complete.


What is a ridge - Hill climbing I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?

The same answer you'd get on The Great Outdoors Stack Exchange: it's one of these.

Photo: ridge from Mount OtenSho to Mount Tsubakuro, Japan. By Alpsdrake; public domain; from Wikipedia

On a plateau, your value doesn't change much if you move in any direction. On a ridge, your value doesn't change much if you move in one direction, but it falls a lot if you move in the other directions.


Variant of greedy algorithm for vertex cover Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?

Input: $G = (V,E)$

Set $C \gets \emptyset$ and $E' \gets E$.
while $E' \neq \emptyset$ do:

Pick any edge $(u,v) \in E'$.
$C \gets C \cup \{u\}$.
Remove from $E'$ all edges incident to $u$.

return $C$.

No, this is a terrible algorithm. Consider a star graph: the vertices are $x,y_1,\ldots,y_n$, and the edges are $(x,y_1),\ldots,(x,y_n)$. Your algorithm goes over the edges in an arbitrary order, and always picks the $y$ vertices. It ends up with $n$ vertices rather than the optimal $1$ vertex solution.


What is implied probability, in the context of universal codes? From Wikipedia:

  Each universal code, like each other self-delimiting (prefix) binary
   code, has its own "implied probability distribution" given by $ p(i)
 ={2}^{-\ell(i)} $  where $\ell(i)$ is the length of the $i$th codeword and $p(i)$ is the corresponding symbol's probability

What is "implied probability"?

Given that prefix code are not fix-length codes, then I don't get what "implied probability" means, for example, given a 3 bits length code, implied probability is ${2}^{-3} = \frac{1}{8}$ but what does it mean? is it about choosing the code between others? or choosing random between all possible of three bits? as here we are talking about prefix codes, so length will vary among codes, so there could be only one code of three bits, so probability of get it would be 1? Any clarification will help!

The idea is the following:

the following tree $T$

$
\\
\emptyset
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
0 \ \ \ \ \   1
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
00 \ \ \ \ \   01\\
\\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \   011
$

of depth 3 is constructed by

Taking an object labeled as $\emptyset$ that has probability 1 and splitting it in half into two pieces which we label as $0,1$; who each acquire equal probabilities 1/2 individually.
Taking the object labeled as $0$ that has probability 1/2 and splitting it in half into two pieces which we label as $00,01$; who acquire equal probabilities 1/4 individually.
Taking the object labeled as $01$ that has probability 1/2 and splitting it in half into two pieces which we label as $010,011$; who each acquire equal probabilities 1/8 individually.

This is essentially the "unwrapping the Huffman algorithm in reverse." You are asking the wrong question, you should be asking "Why label it this way?"

The idea behind the Huffman coding scheme is that

$0,1$ each cost 1 unit of "communication complexity" or "space complexity" depending on your interests
$00,01$ each cost 2 units of "communication complexity"
$010,011$ each cost 3 units of "communication complexity"

You should read chapter 5 of Cover and Thomas

and this Wikipedia article on the kraft inequality is probably helpful too. however, if you want a proof of the infinite kraft inequality you need chapter 5 of Cover and Thomas.

The idea is to continue this (type of) procedure unto infinity so that we get a something the following tree $T_\infty$

$
\\
\emptyset
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
0 \ \ \ \ \   1
\\
|   \ \setminus \\
|   \ \ \ \setminus \\
00 \ \ \ \ \   01\\
\\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ 010 \ \ \ \ \   011 \\
\ \ \ \ \ \ \ \ \ \ |   \ \setminus \\
\ \ \ \ \ \ \ \ \ \ |   \ \ \ \setminus \\
\ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \   0101
$

which has infinite depth.  Each time you "split" a string, you maintain a "partition of unity" i.e., you maintain a probability distribution. The kraft inequality states that if your code was constructed in this manner, i.e.,
$$
\sum_{i : \text{leaf of }T_\infty} 2^{-l(i)} = 1
$$
then the code is optimal.

  In other words if you have a set of binary strings $\mathcal{S}$ and the function
  $$p(s) = 2^{-l(s)}$$
  turns out to actually satisfy the kraft inequality, i.e.,
  $$
\sum_{s \in \mathcal{S}} 2^{-l(i)} = 1,
$$ then it is an optimal code. Therefore forming a probability distribution and being an optimal code are equivalent.

One can further prove that all such codes have a tree that witnesses their optimality.


Can a regular expression based "grammatic" be programatically minimized? I have a list of pairs like (regex, substitute) that take quite long to apply to some input text so I was thinking about optimizing them a bit.

From my knowledge for each regular expression there is a deterministic finite automaton that accepts the same language, and as its possible to merge DFAs merging two regex should be possible...

My question is now how does this interact with the fact that I want to replace something and not just match it.

Basically: given two pairs of a regex and its replacement in a specific order:

1. /\./    -> "Found #DOT#"
2. /#DOT#/ -> "something"

Is it programmatically possible to create a new pair:

   /\./    -> "Found something"

that applied to some input creates the same result?

Note: are e.g. Python regex even regular in the sense of theoretical informatic? (I mean would I get problems with e.g. look-arounds?)

My reason for asking: there are some regex-chains in my collection that just replace things with other things so that other regex can replace these things but that's only to keep it simple enough for a human to understand, a computer doesn't need to comprehend the regex.

I will describe a way that you could optimize the operation "find the first pattern that matches the input".  Given a way to do that, you can repeatedly apply that operation: i.e., repeatedly find the first pattern that matches the input, apply the substitution, then repeat.

However, I'm not sure that this will be any better in practice, so this might be useless (unless the number of regexps is quite small).

Union of NFAs

Any (language-theoretic) regular expression can be converted to a nondeterministic finite automaton (NFA) that recognizes the set of strings matched by the regexp (e.g., via Thompson's algorithm).

So, you can build a NFA for each pattern; and there are standard ways to build a NFA to represent the union of two or more NFAs, i.e., a NFA that accepts any input that is accepted by at least one of the NFAs.  In particular, you use the product construction.

You can modify the product construction to find the first NFA that accepts an input.  Let $N_1,\dots,N_k$ be $k$ NFAs.  Each state of the new NFA is of the form $(q_1,\dots,q_k)$ where $q_i$ is a state in $N_i$.  A state $(q_1,\dots,q_k)$ is accepting if any of the $q_i$ are an accepting state in $i$.  Also transitions are defined following the product construction, except that all transitions out of an accepting state go back to itself.  If $(q_1,\dots,q_k)$ is accepting, then find the smallest $i$ such that $q_i$ is accepting in $N_i$; this indicates that the $i$th regexp was the first match.

In principle you can use standard algorithms to run this NFA on the input, or convert the NFA to a DFA via the powerset construction and then run this DFA on the input.  In principle this provides a way to find the first matching pattern.  In practice you might run into problems: running this NFA on the input might be no faster than running all regexps; and converting to a DFA might cause you to run out of available memory.


Match dictionary to misspelled word, corner cases I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the dictionary D (Levenshtein distance).

The dictionary can contain 500.000 words so a linear search through it can tend to be quite costly. The tricks I've come up with so far includes;

Check if D contains wi (distance = 0) before beginning search
Since a lower bound for the Levenshtein distance is abs(w1.length-w2.length) I don't calculate the Levenshtein distance for two words if their length-difference is greater than the smallest Levenshtein distance I've found so far
I re-use parts of my Wagner-Fischer-matrices if two words I've searched for after one another have letters in common
I calculate all the words you can get using one operation on wi and check if any of those are in the dictionary data structure (of the 'physical' dictionary) -> if so I return them and stop the search (since I've already checked that the word isn't in the dictionary).

Are there any more cases in where I can manage to skip searching through the whole thing? I've thought about calculating all words that you can get with a distance of two from a word, but it feels like it's too costly combinatorically..

Are we talking about a dictionary containing words of some language? Then there are many, many tricks you can use.

Your dictionary may contain 500,000 words, but people don't use that many. And they don't make arbitrary spelling mistakes, but typically only a small number. So you could have a second dictionary containing previous results. If I enter "wierd" you find "weird" after a lengthy search, but then you add "wierd" to a second dictionary.

You can look at the word and decide what is most likely the correct spelling. Like "messsage" is probably "message", without consulting your dictionary. You could map "messsege" to "m, vowel, s, vowel, g, optional vowel", and have a second dictionary for mapped words, which would tell you that your word is likely either "message" or "massage". This will work best for complicated words that nobody knows how to spell correctly.

If you know that your word was typed on a keyboard, there are errors that are more likely than others. If you know that your word was scanned by a scanner, there's a completely different set of errors, like "wam" might really be "warn" (nobody would make that mistake typing on their keyboard). For keyboard entry, the user's fingers might have moved to a different position on the keyboard. Like "leubpard" is "keyboard" with the right hand moved one position to the right. That's a case where simple algorithms fail completely.

Split your dictionary into the 5,000 most common and the 495,000 less common words. Most likely you find a good match within the first 5,000 and can remove most items in the large list that cannot be better.


How to prove if an algorithm is reentrant? I think, maybe some formalism could exist for the task which makes it significantly easier.

My problem to solve is that I invented a reentrant algorithm for a task. It is relative simple (its pure logic is around 10 lines in C), but this 10 lines to construct was around 2 days to me. I am 99% sure that it is reentrant (which is not the same as thread-safe!), but the remaining 1% is already enough to disrupt my nights.

Of course I could start to do that on a naive way (using a formalized state space, initial conditions, elemental operations and end-conditions for that, etc.), but I think some type of formalism maybe exists which makes this significantly easier and shorter.

Proving the non-reentrancy is much easier, simply by showing a state where the end-conditions aren't fulfilled. But of course I constructed the algorithm so that I can't find a such state.

I have a strong impression, that it is an algorithmically undecidable problem in the general case (probably it can be reduced to the halting problem), but my single case isn't general.

I ask for ideas which make the proof easier. How are similar problems being solved in most cases? For example, a non-trivial condition whose fulfillment would decide the question into any direction, would be already a big help.

One approach is to design your code so it is "safe by construction", so re-entrant calls cannot happen.  For instance, one way to do this is to use mutual exclusion to ensure that your method can't be invoked again while it is in the middle of running, to ensure you'll never have two instances running at the same time.  For instance, this kind of approach is often used to ensure that interrupt handlers are correct: they often clear interrupts at the beginning and re-enable them at the end.

Another method is to take whatever code you already have and try to prove it will continue to function correctly even in the presence of re-entrant invocations.  Here you can pick your favorite formal logic for reasoning about program correctness.  For instance, you can use Hoare-style logic to specify the intended functionality and prove it correct.  Then, you consider a tweaked version of your code, where before and after each statement, there is a (non-deterministic) possibility of a recursive invocation of the method being externally invoked; now you prove that the tweaked version continues to meet the spec.  You can replace Hoare logic with any other method for program verification.


How to remove a universal quantifier in Lean theorem prover I am working with two binary relations: g_o and pw_o, and I've defined pw_o below:

constants {A : Type} (g_o : A → A → Prop)

def pw_o (x y : A) : Prop := ∀ w : A, (g_o w x → g_o w y) ∧ (g_o y w → g_o x w)

I need to prove the following:

theorem prelim: ∀ x y z : A, g_o x y ∧ pw_o y z → g_o x z :=

I start with these tactics:

begin

   intros,

   cases a with h1 h2,

end

And I have this:

x y z : A,
h1 : g_o x y,
h2 : pw_o y z
⊢ g_o x z

Since pw_o is defined with a universal quantifier, I'd like to substitute w with x, then I would have (g_o x y → g_o x z) ∧ (g_o z x → g_o y x). After isolating the first conjunct with the "cases" tactic, I can use modus ponens on that first conjunct and h1.
How can I tell Lean to replace w in the definition of pw_o with x and replace x and y in the definition of pw_o with y and z, respectively?

I've found an answer to the question I've posed. Here are the tactics I've used:

begin
   unfold pw_o,
   intros,
   cases a with h1 h2,
   let h3 : A := x,
   let h4 : (g_o x y → g_o x z) ∧ (g_o z x → g_o y x) := h2 x,
   apply (h4.left h1),
end

I've unfolded pw_o to make the universal quantifier explicit. After I've isolated pw_o y z as a hypothesis, I've replaced all occurrences of w with x. Since h4.left is a function from g_o x y to g_o x z, I've applied it to h1, which is a term of g_o x y, to obtain a term of g_o x z, which was the ultimate goal.


Uniform sampling over non-standard simplex Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex

I want to sample one point from a non-standard simplex with vertices at:

$s_{i}\vec{e_{i}}$, where $\vec{e_{i}}$ is the $i^{th}$ vector in the standard basis, and $s_{i} \ge 0$.
the origin is : $\vec{0}$

How to do that? It seems to be no longer a special case of the Dirichlet distribution.

Hit-and-run sampling would need a lot of cycle to diffuse throughout the simplex. When I only need one point, the other points are wasted.

Currently, $n \approx 15$

According to Wikipedia the $n$-simplex is the set defined by:

$$S = \left \{ \mathbf{x} \in \mathbb{R}^n \; | \; \mathbf{x} = \sum_{i=0}^n \mathbf{u}_i\theta_i , \; \mathbf{u}_k \in \mathbb{R}^n , \;\; \theta_k > 0 \;\forall k, \;\;\sum_{i=0}^n \theta_i = 1\right \}$$

Note that the $\boldsymbol{\theta} = (\theta_0, \dots, \theta_n)^T$ is the standard $n$-simplex.

Hence in order to sample from $S$, compute a linear combination of the vertices $\mathbf{u}_k$ with the weights given by a sample of the standard simplex.

Which is the same as the following random process:

Consider the matrix of vertices $U = [\mathbf{u}_0 \; \dots \; \mathbf{u}_n]$, then a sample in $S$ is given by:

$$\boldsymbol{\theta} \sim \text{Standard-Simplex}$$
$$\mathbf{x} = U \boldsymbol{\theta}$$

Note that in your case the vertex $\mathbf{u}_k = s_k \mathbf{e}_k$.


Does modern type theory include specifications and implementations? Good programming practice distinguishes between specification (at the API level) and implementation. I would have thought that this same distinction would be found in type theory. Perhaps I just don't understand what I'm reading, but I don't see it.

Apologies if I'm completely off (and corrections appreciated), but it seems that in type theory one adds new computation/rewrite rules, which in effect are at the implementation level, i.e., they compute something. (They may be "declarative," but they are used for computation.) I don't see how one adds anything like a specification.

A type $T$ is a specification. A term $t$ of type $T$ is an implementation together with a proof of correctness.

Dependent types are more expressive than simple types found in programming languages. Via the propositions-as-types correspondence they allow us to express logical statements which comprise a specification, rather than just "bare" typing information.

For instance, the type
$$\prod_{k : \mathbb{N}} \sum_{m : \mathbb{N}} \mathsf{prime}(m) \times (k < m)$$
can be read in any of the following ways:

As a proposition: for every natural number $k$ there is a prime $m$ larger than $k$.
As a type: the type of functions which take as input a number $k$ and output a triple $(m, p, q)$ where $m$ is a number, $p$ is a proof that $m$ is prime, and $q$ is a proof that $k < m$.
As a specification: implement a function which takes a number and returns a prime larger than it.

Fancier specifications can be expressed just as well. For instance, we can express the specification for a dictionary as a dependent sum (or a record type if it's available)
$$\sum_{D : \mathsf{Type}}
  \sum_{K : \mathsf{Type}}
  \sum_{V : \mathsf{Type}}
  \sum_{\mathsf{empty} : D}
  \sum_{\mathsf{add} : K \to V \to D \to D}
  \sum_{\mathsf{lookup} : K \to D \to 1 + V}
  \cdots
$$
which is read as follows: we need to specify the type of dictionaries $D$, the type of keys $K$, the type of values $V$, the empty dictionary, and the addition and lookup functions. The $\cdots$ would express the required properties of dictionaries, i.e., logical statements governing the behavior of a dictionary.


Looking for some more details on "Turing" devices I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I understand they are a sort of a basis for CS topics).

I've also seen comments by some members mentioning turing-completeness (Particularly when dealing with programming languages) and was just looking for some clarification.

I did search around before posting this and haven't been able to find a similar post or a website that describes this in terms that I have been able to understand or decipher.  Thanks.

A Turing machine is a simple theoretical/conceptual computational device based on state.  Computation is done through state transitions based on the machines current state.  It is popular in Computer Science theory due to how models and proofs can be built off of it.  Wikipedia has a far more detailed write up on Turing machines than is practical to put here and a general discussion of Turing machines is probably off topic for IT Security.  Computer Science is probably a good place to ask more about Turing machines in general, since they are a fundamental conceptual device for Computer Science theory.

In case you are a visual-learner, interestingly enough, there exist physical incarnations of the abstract device.


UV Projection of 3D shape onto 2D images Given a 2D image of a human face and the corresponding 3D shape, how do I project the shape onto the images to extract texture patches from them to form a partial UV map?

I've accomplished this by positioning the mesh in a known position (such as the origin), placing the image in front of it so that from the camera's point of view they align as desired. Then it's simply a matter of shooting a ray from each polygon's vertices through the image towards the camera. Wherever the ray intersects the image, that's your (u, v) point for that vertex.


Universal hash function for strings of unbounded length Is there a (weakly) universal hash function for strings without any assumption of the string length?
I did not find one on Google / Wikipedia.

Any such hash function must have an infinite key.
Suppose that your hash function maps binary strings to some alphabet $\Sigma$ of size $m > 1$. We can identify binary strings with natural numbers, and so can think of the hash function as a function $h\colon K \times \mathbb{N} \to \Sigma$, where $K$ is the (finite) set of keys.
For each $n \in \mathbb{N}$, we can look at the function $h_n\colon K \to \Sigma$ given by $h_n(k) = h(k,n)$. There are finitely many possible functions $h_n$ (at most $m^{|K|}$), and so there must exist $n_1 < n_2$ such that $h_{n_1} = h_{n_2}$. In particular, $\Pr_k[h(k,n_1) = h(k,n_2)] = 1$, and so $h$ is not even a weakly universal function.


ZK proof that I possess a ZK proof for membership in $L$? A zero-knowledge proof system for a language $L$ is an interactive
proof system where a prover $P$ (a Turing machine) tries to convince a
verifier $V$ (a polynomially bounded Turing machine) in a sequence of
message exchanges that $x \in L$ so that $V$ learns nothing from the
interaction except whether $x \in L$ or not.

Question. Is it known how iterate this, i.e.: how to produce a ZK proof that I
possess a ZK proof for membership in $L$?

Yes, it's possible. There is a ZK proof for every language in NP.  Roughly speaking, this means that if there's a way for someone to prove it (by giving a polynomial-size witness/proof), there's a way to prove it with a zero knowledge proof.

For instance, if you have a transcript of a ZK interaction, there's a polynomial-time algorithm to verify whether the ZK interaction should be accepted by the verifier, so it's possible to prove in ZK (i.e., it's possible to give a ZK proof) that you know a transcript of a ZK interaction that would be accepted by the verifier.  However, this might not be quite what you want, because this doesn't prove that the randomness was chosen randomly by the verifier.

Here's a better instance of what you're looking for.  Look up non-interactive zero knowledge proofs.  Suppose I know a string $p$ that is a valid non-interactive zero knowledge (NIZK) proof of some statement $s$.  Moreover, there is a polynomial-time algorithm that allows verifying whether $p$ is a valid NIZK proof of $s$.  Therefore, there's a way I can use a ZK proof to prove to Alice in zero-knowledge that I know a string $p$ that is a valid NIZK proof of $s$, without revealing $p$ to Alice (because this is proving a NP statement).

That said, this probably isn't useful.  What would be the point?  I don't think this lets Alice conclude anything more than if I just proved in ZK to her that $s$ is true.


Relativization results in class separation We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal.

Is there natural complexity classes that has been shown to be equal but are separate under some oracle?

Yes, check out the classes IP (interactive polynomial time) and PSPACE (polynomial space).

In 1988, Fortnow and Sipser [1] showed  that these two classes have contradictory relativizations, that is, there exist oracles $A$ and $B$ ($A$ can be chosen to be $\text{PSPACE}$ itself) such that
$$\text{IP}^A = \text{PSPACE}^A\text{, and}$$
$$\text{IP}^B \neq \text{PSPACE}^B .$$

Later, Shamir [2] showed that $\text{IP} = \text{PSPACE}$.

Chang et al. furthermore showed that for a random oracle $A$, $\text{IP}^A \neq \text{PSPACE}^A$ [3].  See ibid. for a nice introduction and overview.
This result actually disproves the Random Oracle Hypothesis which states that

  the relationships between complexity classes which hold for almost all oracles must also hold in the unrelativized case [3].

References

[1] Fortnow, L. & Sipser, M., Are there interactive protocols for co-NP languages?, Inform. Process. Lett. 28, No. 5 (1988), 249-251.

[2] Shamir, A. IP = PSPACE, in "Proceedings, IEEE Symposium on Foundations of Computer Science, 1990," pp. 11-15.

[3] Chang, R., Chor, B., Goldreich, O., Hartmanis, J., Håstad, J., Ranjan, D., & Rohatgi, P. (1994). The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1), 24-39.


Prove that any subtree in a red-black tree has at least $2^{bh(x)} -1$ internal nodes I'm reading the book Introduction to Algorithms. In the book, in the initial step of proving that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$, they prove that any subtree rooted at any node $x$ in a red-black tree has at least $2^{bh(x)} -1$ internal nodes. However I couldn't wrap my head around this proof.
They do an induction where this holds for the base case when $x$ is a leaf by $2^{bh(x)}-1 = 2^0 - 1 = 0$. However, when they do the induction, they say that  a child of node $x$ has at least $2^{bh(x)-1}-1$ internal nodes (by the way isn't the correct way to put is to start with subtree rooted at a child of node $x$...?). This part confuses me a little bit, is it too trivial to say that it has $2^{bh(x)-1}-1$ nodes given that $bh(x)$ is the black-height (the number of black nodes on any simple path from a node not including itself), or is this related to the rules of the red-black tree which are:

Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

It turns out trivial. I think I found the answer myself. First of all, $bh(x)$ gives us the black-height rooted from the node x. A subtree rooted from node x, in the worst case (in terms of the number of nodes it has) should not include any red nodes. Any node should be there in order to satisfy the $bh(x)$ number and nothing more. In that case we would boil down to a perfect subtree of the height $bh(x)$ and we now that a perfect binary tree has $2^{bh(x)}-1$ nodes. This is the least number of nodes it can have.
The subtlety in the question is that since we are considering the child of a node x that has $bh(x)$, it has at least $2^{bh(x)-1}-1$ nodes due to the possibility of losing 1 black-height by walking from x to its child.
PS: Even though what i wrote above seems sensible to me and maybe gives insight to the lemma even without the need of induction, after a little bit of careful reading, that claim is nothing but the just the induction hypothesis that holds for the leafs and propagates to the top of the three.


What is the difference between Big O and asymptotic notation? Are the two interchangeable or is there a difference?

Bachmann–Landau notation or asymptotic notation is collection of notations one of which is Big-$O$. So they are not interchangeable, because as asymptotic notation also is known little-$o$, big-$\Omega$, big-$\Theta$ etc.
Historically this symbol was introduced by German  mathematician Paul Bachmann and then adopted by German number  theoretician  Edmund Landau and American mathematician L.E. Dickson . Big-$O$ was shorthand for function rate of growth, which is called its order.
History also can be viewed in the book by Florian Cajori - A history of mathematical notations-Dover Publications (1993), page 31.


Difference between auxiliary space v/s space complexity I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$.

So, if someone asks me what's the Space complexity of merge sort, heapsort or insertion sort then what should I tell them $O(1)$ or $O(n)$?

Also, note in case of selection sort, I've read it's Space Complexity is $O(1)$ which is auxiliary space.

First consider the definitions below:

$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.

$\mathbf{Space \space Complexity}$ is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity $\textit{includes}$ input size.

I can see where your confusion comes from; usually, when we say "Space complexity of Mergesort" we mean its Auxiliary Space, because we obviously cannot improve the space we use for the input itself. As such, some of the statements in your question are not correct.

$\bullet$ Mergesort has Auxiliary space of $O(n)$ (in its common use) since you allocate a new array, and Space complexity of $O(n)$

An example between the two would be:

If we compare Quicksort and Mergesort, they both have a space complexity of $O(n)$ and run at $O(n\log n)$ time, but Mergesort requires Auxiliary space of $O(n)$ while Quicksort requires Auxiliary space of $O(1)$

Finally, to answer your question: usually the intention while asking about "space complexity" is indeed Auxiliary space, although there is some ambiguity here in regard to the formal definitions above. To be pedantic, you can separate the two space complexity types in your answer.


Why do pushdown automata use a stack? I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?

There are several possible layers to your question.

Why must PDAs have a stack? -- By definition! That's just how it is.
But why are they defined like that? -- Somebody thought it might turn out interesting. And apparently it did, because many people (read: the entire field) has agreed to use that definition.
Why is it interesting? -- See reinierpost's answer.
Why does my teacher choose to teach PDAs? -- That's a multi-facetted issue; see here for a similar question. The answers carry over.

I'd like to expand on the second bullet a little. How do different definitions come about?

If you take finite control with different memory models, the resulting classes of automata have very different capabilities. In fact, that's a huge part of what automata theory concerns itself with. Once you realize that playing around with definitions can lead to interesting concepts, it's only natural for researchers -- a curious bunch! -- to try and explore the space of possible models.

To list just a few examples of ideas people have had:

finite memory --> regular
single stack --> context-free
single queue --> Turing-complete
two stacks --> Turing-complete
infinite tape --> Turing-complete
heaps --> we don't really know
monoids --> all kinds of interesting things

And so on and so on.

Note that you can also modify other elements:

The alphabet -- make it infinite, or continuous.
The transition function -- make it a relation, or allow $\varepsilon$-transitions.
The state set -- make it infinite, or allow multiple starting states.
The inputs -- make them infinite, or trees, or timed sequences.
Additional restrictions -- use tapes but allow only movement in one direction, or allow to scan k times (alternating directions or always left-right?)

Interesting things can happen!

That's the beauty of mathematical definitions: you usually get something. Then you can spend many months on finding out what it is you got. Maybe it's interesting, maybe not. Maybe it's useful (a dreaded question after talks!), maybe not. But it always is.


Difference between graph-partitioning and graph-clustering What is the difference between graph-partitioning and graph-clustering in graph theory?

Graph partitioning and graph clustering are informal concepts, which (usually) mean partitioning the vertex set under some constraints (for example, the number of parts) such that some objective function is maximized (or minimized). We usually have some specific constraints and objective function in mind. However graph partitioning and graph clustering, as vague informal concepts, are pretty much the same.


Validating a sequence of points as a convex hull I'm familiar with the classical convex hull calculation algorithms. The lower bound for computing the CH of a set of points $P$ is $n\log(n)$.

However, what if I'm given a sequence of points and told they form a CH? One check is to "walk the points" in order and check for "left turns" (CCW). However, this doesn't handle the case of self-intersections (you could imagine a counter-example that "winds around starting from the center" making only CCW turns.

I've been told this "validation" can be done in $O(n)$ time, but to check for self-intersection naively, I see $O(n^2)$ time.

My next thought is to run Graham's Scan. Since the points are presumably on a CH, it takes $O(n)$ to find the lower left point, say $p_0$, and from there, I THINK you can guarantee that all points $p_1, p_2,\dots,p_n$ are already sorted by angle between $p_0$ and $x$-axis. As you move the three-point-window forward along the hull, the points ahead are still properly sorted. The reasoning for $O(n)$ then follows per normal reasoning for Graham's scan, minus the need for $O(n\log n)$ sorting.

1) Is my assumption, in bold, correct?
2) Is there an easier method that wouldn't involve running Graham's scan?

The answer is easier than you think. As you remarked you should check if you take always CCW or CW turns. But of course, this might result in a curve that is self-intersecting. But you can detect this easily, just sum up then angles of the "turns". Since your curve is closed this angle sum is a multiple of $2\pi$. If it winds up exactly once it does not self-intersect. In this case the angle sum is $2\pi$. Thus you are left with checking, if the angles sum up to $2\pi$.

See this paper for analogues in higher dimension.

Interestingly, in the smooth version (CCW turn is here positive sectional curvature), for a 1d curve you still have to check the winding number, but by an old theorem of Hadamard,  if higher dimensional (immersed) manifolds have positive sectional curvature everywhere, then they enclose a convex body.


Decidability of equivalence of two context free grammars I got a question regarding the decidability of equivalence of two context free grammars:

  Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free grammars.

This question is taken from Sipser's book on theory of computation.

My current idea is given that $G$ and $H$ are CFG's, we know that there exists push down automata that accept the languages described by $G$ and $H$. We can simulate a PDA on a Turing machine and hence, we can convert the problem to the equality of Turing machines, such that $M_1$ and $M_2$ are TMs and $L(M_1) = L(M_2)$ which is known to be undecidable.

My question is, are these steps fine to do (with a bit more formalism)?

Let me prove that the problem of determining whether $x = 0$ is undecidable.

Let $A$ be a Turing machine that accepts only $x$, and let $B$ be a Turing machine that accepts only $0$. Then $x = 0$ iff $L(A) = L(B)$, so according to your argument, determining whether $x = 0$ should be undecidable.

I hope that this example helps you understand why your reasoning doesn't work. Instead, try to to use the fact that CFG universality (given a grammar $G$ over $\Sigma$, does $L(G)$ equal $\Sigma^*$?) is undecidable.


Recursion for runtime of divide and conquer algorithms A divide and conquer algorithm's work at a specific level can be simplified into the equation:

$\qquad \displaystyle O\left(n^d\right) \cdot \left(\frac{a}{b^d}\right)^k$

where $n$ is the size of the problem, $a$ is the number of sub problems, $b$ is the factor the size of the problem is broken down by at each recursion, $k$ is the level, and $d$ is the exponent for Big O notation (linear, exponential etc.).

The book claims  if the ratio is greater than one the sum of work is given by the last term on the last level, but if it is less than one the sum of work is given by the first term of the first level. Could someone explain why this is true?

The total work is given by the sum of a geometric progression. In particular, let $r = a/b^d$, then total work = $O(n^d)\times (1+r+r^2+\ldots+r^p)$, where $p$ is the maximum depth.

Let $S = (1+r+r^2+\ldots+r^p)$.

If $r>1$, then $S = \frac{r^p-1}{r-1}+r^p = O(r^p)$.

If $r<1$, then $S \leq 1+r+r^2+\ldots = \frac{1}{1-r} = O(1)$.


voting scheme for peaceful coexistence Many areas in the world suffer from conflicts between two groups (usually ethnic or religious). For the purpose of this question, I assume that most people of both sides want to live in peace, but there are few extremists who incite hatred and violence. The goal of this question is to find an objective way to filter out those extremists.

Imagine a town with 2 conflicting groups, A and B, each has N people. I propose the following voting scheme (which I explain from the point of view of group A, but it's entirely symmetric for the other group):

equality-rule: The number of people in each group must always remain equal.
expel-vote: At any time, each person of group A can claim that a certain person of group B is "extremist", and start a vote. If more than 50% of the people in group A agree, then that certain person is expelled from town.
counter-vote: To keep the equality-rule, a single person of group A should also leave the town. This person is selected by a vote between the people in group B (i.e. each person in group B votes for a single person in group A, and the one with most votes is expelled from town).

My intuition is that:

On one hand, this scheme encourages people to be nice to people of the other group, so that they won't be subject to expel-votes.
On the other hand, the equality rule encourages people to think twice before starting an expel-vote, because this will put them in danger of expel in the counter-vote.

[ADDITION]
Several questions can be asked about this scheme, for example:

Under what conditions does it diverge to a situation where people vote and counter-vote, until the number of citizens in one of the groups reaches 0?
Under what conditions does it stabilize on a situation where the two group has more than 0 citizens?
Under what conditions, the stable number of citizens is more than half the initial number?

Note that this scheme does not even try to reach an objective measure of "extremism". The only goal is stability.

I would like to know, has this voting scheme has been studied in the past?

If a person owns property in the town, then when voted out, they presumably forfeit the property.  This creates an economic incentive to systematically rob minority groups via things like the Spanish Edict of Expulsion which expelled the community of Jews that had thrived prior to the Reconquista from Spain.  Although the decree technically allowed them to sell their possessions (at firesale prices) before fleeing, they were not allowed to take the proceeds with them:

  And we likewise give license and faculty to those said Jews and Jewesses that they be able to export their goods and estates out of these our said kingdoms and lordships by sea or land as long as they do not export gold or silver or coined money or other things prohibited by the laws of our kingdoms, excepting merchandise and things that are not prohibited.

Such incentives might be sufficient for cartels to arise.  A cartel that can corner the market on readily available portable wealth can combine that control with bloc voting to vote out an identifiable minority group in such a way that they have little option but to liquidate assets through the cartel making the cartel members wealthy.

Any analysis should take into account such incentives.  Game theory, since it does not by itself model irrational tendencies like in-group/out-group bias, might have a hard time predicting such things.