Pumping Lemma Proof (Type of wcw language) I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma.
The structure of the language i think can be explained as (based on definition above) $\{a^{n}b^{n}ca^{n}b^{n} \mid c \in \{a,b\}\}$
Based on pumping lemma, it must have this 3 properties:

$\lvert y \rvert \gt 0$
$\lvert xy \rvert \le p$
$xy^iz\in L$ for all $i \ge 0$.

Based on that, i have $a^{p}b^{p}ca^{p}b^{p}$ and $ 4p+1 \ge p $
Based on 2nd property there must be 9 scenarios (i guessed that from the theory):
One of them should be this one:

x = $\{a^{i}$} $\space $ y = $a^{p-i}$ $\space$ z= $b^{p}ca^{p}b^{p}$

Based on the 3rd property i can use $xy^{2}z$ = $a^{i}$$a^{p-i}$$a^{p-i}$$b^{p}ca^{p}b^{p}$ eventually giving me $a^{p}$$a^{p-i}$$b^{p}ca^{p}b^{p}$, the explaination is: it fails since $a$'s of the start arent the same (in number) with the $a$'s of the end.
If the above is correct how i find the other 8 scenarios and it does make any difference that my $c$ is ($a$ or $b$) instead of a single constant character?

The structure of the language i think can be explained as (based on definition above) $\{a^n b^n ~c~ a^n b^n |c \in \{a,b\} \}$

As explained in the comments, this is a wrong inference. If
$$
L = \left \{ d k d ~|~ d \in \{ a, b \}^{*}, k \in \{a, b\} \right \}
$$
then $d$ can be any finite sequence (of any length) of $a$ or $b$ terminals. Recall that, for an alphabet $\Sigma$, Kleene star is defined inductively as
\begin{align}
\Sigma^0  & = \{ \epsilon \} \\
\Sigma^n  & = \{ \omega a ~|~ \omega \in \Sigma^{n - 1}, a \in \Sigma \} \\
\Sigma^{*}  & = \bigcup_{n \ge 0}{\Sigma^n}
\end{align}
So for example
$$
\{ \epsilon, a, b, ab, ba, abab, abbb, baba \} \subset \{ a, b \} ^{*}
$$
while instead
$$
\{ a^n b^n | n \ge 0 \} = \{ \epsilon, ab, aabb, aaabbb, \ldots \}
$$
To tackle your problem, I can recommend negating the Pumping lemma and then

Fix an arbitrary $N > 0$
Take $\omega = a^N b a^N$ with $d = a^N$ and $k = b$
Equate $\omega = xyz$ and note that it must be $|xy| \le N$ and $|y| > 0$

Can you conclude your proof?

 We just chose our $\omega \in L$. We must show that, whatever our decomposition, $\exists k \ge 0. ~ x y^k z \not \in L$. Let $x, y, z$ be such that \begin{cases} \omega & = xyz \\ |xy| & \le N \\ |y| & > 0 \end{cases} then, whatever $y$, for $k = 0$ you always have \begin{equation} x y^0 z = a^M b a^N \end{equation} with $M \neq N$.  Thanks @plop for strenghening the proof.


What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$? Consider the recurrence
$$
T(n,m) = T(n,m-1) + T(n-1,m) + c,
$$
with base cases $T(n,0) = T(0,m) = 1$.

This is the complexity of a recursive algorithm for the longest common subsequence, I know that the complexity is exponential and equals $\Theta(2^i)$, but I'm not sure if $i=\max(n, m)$ or $i=nm$. Also, how can I demonstrate it using induction?

The function $f(n,m) = \binom{n+m}{n}$ satisfies the recurrence
$$
f(n,m) = f(n-1,m) + f(n,m-1),
$$
with base cases $f(n,0) = f(0,m) = 1$. This already gives you the solution when $c = 0$, assuming that the base cases are $f(n,0) = f(0,m) = 1$.

One function which satisfies the recurrence, though (in general) not the base case, is $g(n,m) = -c$:
$$ g(n,m) = g(n,m-1) + g(n-1,m) + c. $$
This gives the solution when $c = -1$.

Finally, note that any function of the form $\alpha f(n,m) + g(n,m)$ is also a solution of the recurrence. Since
$$
\alpha f(n,0) + g(n,0) = \alpha f(0,m) + g(0,m) = \alpha - c,
$$
we see that
$$
T(n,m) = (c + 1) f(n,m) + g(n,m) = (c+1) \binom{n+m}{n} - c.
$$


Easy way to prove that this algorithm eventually terminates Introduction and notations:

Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that.

Let the notation $x_i \in \mathbb{R}^p$ refer to a $p$ dimensional data point (a vector). I have three sets A, B and C, such that $|A| = n$, $|B| = m$, $|C| = l$:
$$A = \{x_i | i = 1, .., n\}$$
$$B = \{x_j | j = n+1, .., n+m\}$$
$$C = \{x_u | u = n+m+1, .., n+m+l\}$$

Given $k \in \mathbb{N^*}$, let $d_{x_i}^A$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $A$; and $d_{x_i}^C$ denote the mean Euclidean distance from $x_i$ to its $k$ nearest points in $C$.

Algorithm:

I have the following algorithm which iteratively modifies the sets A and B by moving some selected elements from A to B and vis versa, and C remains always the same (do not change). To make it simple: the purpose of the algorithm is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$":

$A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$ ... (1)
$A = A \setminus A'$; $B = B \cup A'$ ... (2)
$B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
$B = B \setminus B'$; $A = A \cup B'$ ... (4)
Repeat (1), (2), (3), and (4) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or ($|A| \leq k$ or $|B| \leq k$)

The algorithm terminates in two cases:

when $|A|$ or $|B|$ becomes less than or equals to $k$
or the most standard case, when $A' = B' = \emptyset$, which means that no more elements moves between A and B.

Question:

How to prove that this algorithm eventually terminates ? I didn't found a convenient potential function which can be strictly minimized or maximized by the algorithm.
I have unsuccessfully tried some functions: the function $\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$ but it is not increasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$ but it is not decreasing at each iteration. The function $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ seems not to be decreasing at each iteration. The function $\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$ seems not to be increasing at each iteration. So what is the convenient potential function which can be show to either increase or decrease at each iteration ? Or should we show that the function decreases but not at each iteration (after some iterations rather) ? How ?

Notes:

The $k$ nearest points to $x$ in a set $S$, means: the $k$ points
(others than $x$) in $S$, having the smallest Euclidean distance to
$x$. You can just take $k = 1$ to simplify the analysis.
I don't know if this may help or not, but I have the following
property for my initial sets $A, B, C$: initially $\forall x_i \in B,
   x_j \in A$, if $x_b \in C$ is the nearest point to $x_i$ and $x_a \in
   C$ is the nearest point to $x_j$ then always $distance(x_i, x_b) <
   distance(x_j, x_a)$. This intuitively means that points in $B$ are
closer to $C$ than points in $A$.
If that makes the analysis easier: it is totally possible to consider a slightly different version of the Algorithm where as soon as a point from $A$ should be moved to $B$, it is moved from $A$ to $B$ (without passing by $A'$), and vis versa for $B$.

Here's the solution for the case $k = 1$:

Assume the algorithm does not terminate.  Since there are a finite number of states of the algorithm (assignments of points to $A$ and $B$), the algorithm state must repeat in a cycle.  Since the cycle goes through different states, there must be a point that switches between $A$ and $B$ infinitely often.

Let $x$ be a point that switches infinitely often in this cycle.  Pick the first iteration of the algorithm within the cycle during which $x$ switches from $B$ to $A$.  For $x$ to switch to $A$, there must have been at least one point $x'$ in $A$, with $d_x^C > dist(x, x')$.  Arbitrarily pick the smallest-labeled such point; define a function $f$ so that $f(x) = x'$.  Note that $x'$ also must switch between $A$ and $B$ infinitely often (because if $x'$ stayed in $A$ permanently, so would $x$), so we can take $f(f(x)), f(f(f(x))),$ etc.

Since we have a finite number of points, the iterates of f must eventually repeat:  $f^n(x) = f^m(x)$ for some $m > n$.  Now look at the corresponding sequences of distances from C:  $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ... $.  Since it repeats, this sequence cannot be uniformly decreasing.  There must be an iterate $o$ such that $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Now, $f^{o-1}(x)$ and $f^o(x)$ are close enough to each other to cause each other to be in $A$, if one of them is.  That is, they're closer to each other than either of them is to $C$:
$d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$  (from definition of $f$)

So as soon as $f^{o-1}(x)$ and $f^o(x)$ are both in $A$, they will keep each other in $A$ forever (see lines 1-2 of the algorithm).  This contradicts the fact that all the iterates of $f$ must switch sets infinitely often.  Thus, for the case when $k = 1$, the algorithm terminates.


Approximately sorting integers by many criteria Given $k$ functions $f_0, f_1...f_k$, a large dataset of size $n$, is there an algorithm that will "approximately" sort the dataset according to all of the functions so that "most" items of the dataset end up close to where they should be if they were sorted by any one of the functions alone.

More formally, if we have the functions $R_k(i)$ which gives the rank of item $i$ if the dataset were sorted with $f_k$, and $R'(i)$ which gives the actual rank of the item, we can define the statistic: $$r_k = 1 - \frac{6\sum_{i=0}^n{(R'(i) - R_k(i))^2}}{n(n^2-1)}$$ (this is the Spearman rank correlation coefficient of the actual against predicted positions)

Is there an algorithm which will increase the total $r = \sum_{i=0}^k{r_i^2}$, either by outright maximising $r$, or some kind of convergent process which can increase $r$ to its maximum?

Obviously, sorting according to just one of the functions will give $r > 0$ but can we do better than this?

I am not really concerned with running time, but anything better than the naive $O(n!)$ of going through all the permutations and computing $r$ would be good.

The motivation for this is to improve branch prediction while searching a large dataset without using any extra space.

I don't know if there is an efficient algorithm that will always produce the optimal solution.  I would suggest looking at heuristics that hopefully will often work well, even if they don't come with guarantees.  One plausible approach would be to use simulated annealing, or some other form of local search.  At any point, you can pick a pair of random indices $i,j$ and consider would happen to $r$ if you swap the items at those two locations; then the simulated annealing algorithms describes the conditions under which you apply that swap vs not.  Repeat until convergence.  There are no guarantees this will give the global optimum -- it get stuck in a local optimum -- but it could be worth a try.

If you are OK with maximizing $\sum_i r_i$ instead of maximizing $\sum_i r_i^2$, the following might work.  You might be able to reduce this to the assignment problem and then apply a standard algorithm for the assignment problem.  In particular, for each item $i$ and each rank $j \in \{0,1,2,\dots,n\}$ create an edge from item $i$ to rank $j$ whose cost is $\sum_k 6(j-R_k(i))^2/n(n^2-1)$.  Then, use an algorithm for the assignment problem to find an assignment that assigns a unique rank to each item.   The sum of the costs of the selected edges will be equal to $k-\sum_i r_i$, so minimizing the sum of the costs will maximize $\sum_i r_i$.  Assigning each item to a unique rank is equivalent to sorting the items; you just put the items in order of their rank.  The assignment problem ensures that no two items will receive the same rank, and every item will receive some rank.

I'm not sure if this works or not.  At one point I thought this would work; then at another point I thought it wouldn't work (but I can't remember why not); and now I'm thinking again that this should work, and give a polynomial-time algorithm to find the exact solution for maximizing $\sum_i r_i$.  As you can see, I've gotten myself totally mixed up here, so I don't trust my thought process.  Double-check all of my reasoning here before placing any reliance on it.  (Even if this doesn't give the optimal answer, it's also possible that it provides a useful initialization for simulated annealing.)


Uniformly random iteration of subtrees I want to iterate through the first $k$ elements of a randomly ordered list containing all subtrees for a given tree. The definition of subtrees that I'm using is: "A subtree of $T$ is a subgraph of $T$ that is also a tree". For example, a tree $A(B(D, E, F), C(G, H))$ should have 62 subtrees if my math is correct.

The amount of subtrees can be calculated as follows. Let us denote by $R(T)$ the number of subtrees of $T$ rooted at $T$. If $T$ is a leaf then $R(T) = 1$, and if tree has children $T_1,\ldots,T_\ell$ then
$$
 R(T) = \prod_{i=1}^\ell (R(T_i) + 1).
$$
Finally, the number of subtrees of $T$ is $\sum_{x \in T} R(T_x)$, where $x$ goes over all vertices of $T$, and $T_x$ is the subtree induced by $x$ (consisting of $x$ and all of its progeny).

By shuffling the order of these trees and listing the first 5, the result might be $C(G), A(B(F)), B(D, E), A(B, C), C$.

I can already generate a full list of subtrees. For larger trees, this quickly becomes impossibly large. I am looking for a way of generating these subtrees without having to generate all of them.

One possible method I've thought of is to keep a count of how many unseen rooted subtrees each of the nodes has left, and decrementing each time a subtree is generated from that node. The probability that a node is selected would be weighted by this counter. I would also have to prevent the generation of duplicates. I was wondering if there is a better way.

If $k \leq (1-\epsilon) N$, where $N$ is the total number of subtrees, then the following approach would work:

Start with the empty list $L$.
Repeat $k$ times:

Pick a random subtree $T'$.
If $T' \notin L$, add it to $L$; otherwise, go back to the previous step.

Since $k \leq (1-\epsilon) N$, the expected number of times it takes to find $T' \notin L$ is at most $1/\epsilon$ throughout the process; it will be much smaller in the beginning. In particular, if $k \ll \sqrt{N}$, then it is highly likely that you will never generate the same subtree twice.

In more detail, the average expected number of repetitions is
$$
\frac{1}{k} \sum_{\ell=0}^{k-1} \frac{N}{N-\ell} \approx \frac{N}{k} \int_0^k \frac{dx}{N-x} = \frac{N}{k} \ln \frac{N}{N-k} \approx \frac{N}{N-k} = 1 + \frac{k}{N-k}.
$$

You can implement the check $T' \notin L$ quickly using a hashtable. In this way, we have reduced your problem to that of generating a uniformly random subtree, which you can do as follows, essentially by reducing the problem of uniform generation to that of counting.

In order to pick the root of the subtree, first compute $R(T_x)$ for every vertex $x \in T$ (you can do this in $O(n)$ for all vertices together if you're careful, where $n$ is the number of vertices). The root is $x$ with probability $R(T_x)/N$ (you can choose $x$ quickly using binary search, for example).

If $x$ is a leaf, then we're done. Otherwise, suppose that $x$ has children $x_1,\ldots,x_\ell$. Your random subtree skips $x_i$ with probability $1/(1+R(T_{x_i}))$ (independently). If it doesn't skip $x_i$, then you generate a random subtree of $T_{x_i}$ recursively.

Here are two other related approaches. The first is to generate all subtrees, permute them randomly in $O(N)$, and then output the prefix of length $k$.

A variant of the first approach uses unranking. By modifying the approach above, you can take an integer in the range $0,\ldots,N-1$ and convert it to a subtree. This goes as follows. Let $x_1,\ldots,x_n$ be an enumeration of the vertices of $T$. The first $R(T_{x_1})$ integers correspond to subtrees rooted at $x_1$. The following $R(T_{x_2})$ integers correspond to subtrees rooted at $x_2$. And so on.

Now suppose we're given an integer $i$ in the range $0,\ldots,R(T_x)-1$, and need to convert it to a subtree rooted at $x$. If $x$ is a leaf, then there is nothing to do. Otherwise, let $x_1,\ldots,x_\ell$ be the children of $x$. We first convert $i$ into $\ell$ numbers $i_1,\ldots,i_\ell$, where $i_j$ is in the range $0,\ldots,R(T_{x_{i_j}})$. If $i_j = R(T_{x_{i_j}})$, then the subtree won't contain $x_{i_j}$. Otherwise, we can generate a subtree of $x_{i_j}$ recursively.

Given the unranking procedure, you can generate a permutation of $0,\ldots,N-1$, take the prefix of length $k$, and convert it to a list of $k$ subtrees. If you have any other way of generating a random sequence of $k$ elements of $0,\ldots,N-1$ without repetition, then you can use it in the same way.


An example where Knuth-Morris-Pratt Algorithm is faster than Boyer-Moore? This page about Knuth-Moriss-Pratt Algorithm compared to Boyer-Moore describes a possible case where the Boyer-Moore algorithm suffers from small skip distance while KMP could perform better.
I'm looking for a good example (text,pattern) that can clearly demonstrate this case.

There is a paper that did a good experiment over these string matching algorithms for different patterns:
"Comparison of string matching algorithms: an aid to information content security"

Also there is a study of these string matching algorithms for Japanese language:
Comparison and Improvement of String Matching Algorithms For Japanese Texts

I hope these are useful to get a sense about algorithms efficiency!


How to reduce this regular expression? I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression?
$$b+aaa^*b+abb^*+a$$
I can feel it's same as $$a^*b+ab^*$$ but how do I proceed to simplify the first one to the second mathematically?

Minimizing a regular expression is PSPACE-hard.  Therefore, if you're looking for a general set of techniques to minimize a regular expression, there's no good solution: there is no good set of techniques that always works and is always efficient.  See https://cs.stackexchange.com/a/12278/755 and https://cs.stackexchange.com/a/43863/755 and https://cstheory.stackexchange.com/q/12361/5038.

Of course, none of these results rule out the possibility of techniques that work for your particular example or that sometimes work.  However, they show that you shouldn't expect any general technique, i.e., any technique that works for all regular expressions and always gives the optimal answer and is asymptotically efficient.

That said, there are some ad-hoc methods you can use.  For instance, by staring at it, you can quickly recognize that

$$abb^* + a = ab^*,$$

since $ab^* = a(b^*) = a(\varepsilon + b b^*) = a + abb^*$.


Need help analyzing the runtime analysis of this algorithm/algorithms in general This is the algorithm I was trying to find the runtime of (doSomething) -
Procedure findMinMax(int A[], int start, int end)
int min = max = A[start]
int i = j = start
for(int k = start; k <= end; k++)
if(A[k] < min)
i = k
min = A[k]
if(A[k] > max)
j = k
max = A[k]

end for
return {i, j}
end findMinMax

Procedure swap(int A[], int i, int j)
int temp = A[i]
A[i] = A[j]
A[j] = temp
end swap

Algorithm doSomething(A[])
Input: array A of N integers
Output: ?
int i = 0
int j = N-1
while(j - i > 0)
int[] minMax = findMinMax(A, i, j)
int min = minMax[0]
int max = minMax[1]
if(min == j && max == i)
swap(A, min, max)
else if(min == j)
swap(A, i, min)
swap(A, j, max)
else if(max == i)
swap(A, j, max)
swap(A, i, min)
else
swap(A, i, min)
swap(A, j, max)
i++
j--
end while
return A
end doSomething

The indenting of the code is bad in the code block, so here is an image of the code with proper indenting if that helps -
The while loop runs n/2 times. This is because i is always incremented by 1 at the end of the while loop and j is always decremented by 1. None of the helper methods called inside of the while loop and none of the other constant time statements called changes i and j, so the while loop ALWAYS runs n/2 times.
Inside of the while loop, the swap functions are called. These are of O(1) constant time and don't affect the runtime. But, findMinMax is also called, which has an O(N) runtime.
In my eyes, I thought that the overall runtime of doSomething would be O(NlogN). The while loop running n/2 times would be equivalent to something like: "for(int i = 0; i < N; i += 2)". That for loop by itself (not considering what is inside of it) has a runtime of O(logN). I figured the same logic applies here and that the while loop has a runtime of O(logN). Multiply that by the runtime of findMinMax which is inside of the while loop body and you get O(NlogN).
However, the answer key disagrees. The answer key states that the runtime of the algorithm is O(N^2).
The reasoning is -

That doesn't really make sense to me. Why was a summation used? I thought they were only used to find runtimes when there was an inner loop dependent on the outer loop. Furthermore, why does 2k or 2k + 1 go inside of the summation?
I also tried using a summation for something like -
for(int i = 0; i < N; i+=2) {
   //O(1) operation
}

I got the summation -

which simplifies to N/2, and thus O(N), since the 1/2 constant gets factored out.
I obviously do not see why a summation was used for the doSomething algorithm runtime calculation, especially since there was no inner loop which depended on the outer loop (i.e. "for(j = i + 1)"). The summation logic didn't even work for that other code block I posted just above.
Any help/clarifications would be appreciated!

I figured out why the runtime is O(N^2).

Yes, the while loop does run N/2 times. However, that is equivalent to -

"for(int i = 0; i < N; i+=2)" which has a runtime of O(N) still.

I confused it with -

"for(int i = 0; i < N; i *= 2)" which has a runtime of O(logN).

The summation also results in the correct answer in this instance.


How is Rank Selection better than Random selection and RWS? I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does:

Tour1's Fitness: 0.87
Tour2's Fitness: 1.22
Tour3's Fitness: 1.03
Tour4's Fitness: 0.58

We rank them using their fitness:

4) Tour2 -- Highest rank (N)
3) Tour3
2) Tour1
1) Tour4 -- Lowest rank (1)

We generate a random number between 1 and 10 (sum of ranks), for example X = 3.
We then loop and sum the ranks until its greater than X and we select the tour, in this example it will be Tour2 since it's rank is 4 and 4 > 3.

What I don't understand is how is this better than just randomly selecting a tour and why is it better than Roulette Wheel Selection? ALso please correct me if I'm missunderstanding the method.

It's about controlling selection pressure. With roulette wheel selection, there are several scaling issues. If you have two individuals p1 and p2 with fitness values 1 and 2 versus having values 1001 and 1002, roulette wheel selection behaves drastically differently. Similarly, suppose the optimal fitness value of your function is at some f(x)=100, and you generate an initial population with fitness values all around 1, and one individual at 20. Roulette wheel selection will drastically favor the one best solution, simply because it's so much better than the others. But early in a run, that's probably a mistake. The population will quickly be taken over by copies of that solution. Just being way better than bad alternatives doesn't tell me enough information to be that aggressive in selecting it.

Ranked selection just looks at the rankings and so doesn't have this problem. Whether you're a little better or a lot better, we can precisely control how aggressively to exploit those better solutions.

Darrell Whitley is generally credited with the idea of Rank-biased selection in [1]. He published code for performing selection using this method. I've cleaned up that code a bit below. You'd have to integrated it with your own code to properly get the population size, etc., but it should be fairly self-explanatory aside from the actual formula -- that you can just take on faith or go read Whitley's GENITOR paper for details.

// return the index into the population of the selected parent.
// population must be sorted by fitness first
Chromosome select_parent(Population pop)
{
    double bias = 1.5;
    int index = (int)(pop.size() * (bias - sqrt(bias*bias - 4.0*(bias-1) * rand01()))
        / 2.0 / (bias-1));
    return pop[index];
}

The bias term governs how strongly we want to favor higher ranked individuals. You could tweak that to increase or decrease selection pressure, though in practice, I've never changed it from the default value of 1.5 given in the Whitley paper.

The only other detail is that I invented a notation for "rand01" to mean a function that returns a random floating point number in the interval [0.0, 1.0).

[1] https://www.researchgate.net/profile/Darrell_Whitley2/publication/2527551_The_GENITOR_Algorithm_and_Selection_Pressure_Why_Rank-Based_Allocation_of_Reproductive_Trials_is_Best/links/5632149808ae3de9381e72c5/The-GENITOR-Algorithm-and-Selection-Pressure-Why-Rank-Based-Allocation-of-Reproductive-Trials-is-Best.pdf


Determine page number and offsets for address references I'm working on learning operating systems and I've come across a strange question that I don't know how to answer.

The question is:

  Assuming a 1-KB page size, what are the page numbers and offsets for
  the following address references (provided as decimal numbers)?

  21205

The notes and slides I have are very confusing and I can't find anything quite like this from my searches. I understand that a 1KB page size means that it's 2^10 but what do I do after that exactly? Most descriptions I see involve splitting that in half and using the first half as your offset and the other half as the page number but then I see others saying not to do this and my notes, as I mentioned, are useless. I'm sure this is extremely easy but I feel like I've been given only 1/3 of the knowledge needed.

Any help would be greatly appreciated!

Addendum

I took a step back for a little while and I think I realized where my confusion was coming from.

I determined that 21,205 is within the range of 2^15, so it's a fifteen bit number. If I subtract the size of the page (10) from the size of the number (15) then that should, in theory, give me a page number of 10 and an offset of 5.

The next bit is pure speculation on my part but I'm assuming that I then take the decimal form of 21,205, which is 101001011010101, and segment it accordingly. The first ten bits (1010010110) equals 662 and the last five bits (10101) equals 21.
So my tentative answer is

Page Number = 662 & Offset = 21.

Is this at all reasonable or do I do it completely wrong?

I think Page numbers will be given by first 5 bits and last 10 bits will give the offset. With the first 5 bit first you locate which page no. you want to go and then remaining 10 bits will tell you the offset at that page taking you at the exact location


How do you find all integers in a sorted array of size n that appear n/k times? I try to find the solution to this problem:
How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time?
I could only find this question, where O(klogn) solution was provided.

Let's start with the case $k = 2$, and assume that the algorithm is comparison-based.
I claim that any algorithm that finds even a single element appearing $n/2$ times must know an index $i$ such that $A[i+1] = A[i+n/2]$. Indeed, suppose that this is not the case, and let us assume for simplicity that the entries of $A$ are real numbers. Let us say that the algorithm known the following values:
$$
A[i_1] = \cdots = A[j_1] < A[i_2] =\cdots = A[j_2] < \cdots
$$
It is consistent with the algorithm's knowledge that $A[i_1-1] < A[i_1] < A[j_1+1]$ and so on, and with a little effort we can arrange that there is no element appearing $n/2$ times.
Consider now the $n/2+1$ arrays of the following form: there is a run of $n/2$ many $0$s starting at some position $j \in \{1,\ldots,n/2+1\}$, and the rest of the elements are unique. In each such array, there is a unique choice for the index $i$ mentioned above. Thus the decision tree representing the algorithm has at least $n/2+1$ leaves, and so it must have depth $\Omega(\log n)$.

In the general case, the algorithm should know an index $i$ such that $A[i+1] = A[i+n/k]$ for each element which is output. We can partition the array into $k/2$ parts of size $2n/k$, and consider $(n/k+1)^k$ examples as before, where the $r$th element appearing $n/k$ times is in the $r$th part. This gives a lower bound of $\Omega(k\log(n/k))$, matching your upper bound for nearly all values of $k$.
(The algorithms can probably be slighly improved to give a matching upper bound.)


Can the decision version of an optimization problem in NP, be in P? It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore could check whether a a tour exists which costs at most $K$.

Lets assume we are talking about an optimization problem which is either NP or NP-hard. Can the corresponding decision problem ever be in P?

NB: What I am trying to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time?

Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of decision problems, and NP-hardness is a property of decision problems. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the corresponding decision problem is in NP or is NP-hard.


What is a fractional matching? For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation of what a fractional matching is. How does it compare to an integral matching?

If this question seems too basic, could I please have a link to somewhere that explains it?

Given a graph $G=(V,E)$, we can represent a matching as a function $f$ from the edges $E$ to $\{0,1\}$ such that for each vertex $v\in V$, we have $\sum_{w\in N(v)} f(v,w) \leq1$, where $N(v)$ is the neighbourhood of $v$, i.e. the set of its adjacent vertices. (We have equality for a perfect matching) In this representation, $f(e)=1$ means the edge $e$ is part of the matching.

A fractional matching can then be represented by a function $f'$ from the edges $E$ to the continuous interval $[0,1]$, with the same constraint, i.e. $\sum_{w\in N(v)} f'(v,w) \leq1$. So, intuitively, each vertex is 'divided' over its incident edges such that it is participating in at most one edge 'in total'.


Check if a given polynomial is primitive I try to estimate error detection capabilities of arbitrary CRC polynomials. One important criteria is if a given polynomial is primitive. So I need an algorithm to check that. My goal is to write a C or C++ routine.

Unfortunately I only found analytical solutions for the problem on the web.

Is there some numerical algorithm for testing a given polynomial for primitivity?

Please consider that my mathematical knowledge wasted away during the last two decades. Any algorithm descriptions, pseudo code or code in a common programming language would be very helpful.

In order to check that a degree $n$ polynomial $P$ over $GF(2)$ is primitive, you first need to know the factorization of $2^n-1$ (you can look it up in tables, or use a CAS). Then, you test that $x^{2^n-1} \equiv 1 \pmod{P(x)}$ (using repeated squaring to do this efficiently), and that for every prime factor $p$ of $2^n-1$, $x^{(2^n-1)/p} \not\equiv 1 \pmod{P(x)}$.

You can also just use a CAS (computer algebra software). For example, using the free software Sage you can do

F.<x> = GF(2)[]
(x^8+x^6+x^5+x+1).is_primitive()

For more on the relevant mathematics, see the Wikipedia article.


Get specified bit in addition of two large binary numbers I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large.

At first I tried running a loop over them and keeping track of carry bits. This wasted time, because the aim is to get the bit at a specific position in this sum.

So I modified my approach in following way. Starting from the specified index, I am looping until I find a 0 bit in same position on both numbers; I add only those parts to each other and return the bit at the specified position.

This seems okay, but is this the best I can do? Recall that I want to get the value of one specific bit of the sum, given by its position.

Your method will indeed work, but for two $n$-bit numbers it will still take $O(n)$ time. There is a much faster way to solve your problem, with running time $\Theta(\log n)$, known as carry-lookahead addition. The downside is that in my experience teaching this technique, people have a hard time wrapping their heads around it. You can find online sources, here and here, and some algorithm or computer organization texts cover it. It's a really interesting algorithm, well worth taking the time to figure it out.


Vertex cover in bipartite graph from Hopcroft-Karp Algorithm Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover.  I've implementated the Hopcroft Karp algorithm to find a maximum matching in the bipartite graph. I would like to get the minimum vertex cover from this.

Is there any way of adjusting Hopcroft–Karp so that it produces the minimum vertex cover, other than the obvious way of just computing the matching and then passing that to an algorithm that computes the corresponding cover?

The Wikipedia page on König's theorem gives an algorithm that converts a maximum matching to a minimum vertex cover. I'm not sure that an algorithm for finding maximum matching can be tweaked to an algorithm for finding minimum vertex cover in any other way, though it's perfectly possible.


efficient algorithms for factoring polynomials Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within the context of the field of integers but I wouldn't mind the rationals as well.

Do you know of Berlekamp's algorithm and the  Cantor–Zassenhaus algorithm?

http://en.wikipedia.org/wiki/Berlekamp%27s_algorithm

http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm

Unless I'm misunderstanding your question, there is no field of integers- they form a ring but don't have multiplicative inverses


How to interprocess communication and scheduling algorithms interact? I was listening back to a lecture I had, hinting on what we should revise for our upcoming exam. Since then I've covered all the parts, but having difficult in decrypting the following

  You might want to look at the interaction between scheduling algorithms and interprocess communication.

I understand both interprocess communication and scheduling algorithms but don't have an opinion/nor can find one on the link between the two. If anyone could inform me I'd really appreciate it.

Such interaction arises when a high-priority task needs to communicate in some way with a low-priority task. Scheduling algorithms may need to take into account such communication. For example, see http://en.wikipedia.org/wiki/Priority_inversion .


Are turing machines and formal languages the same mathematical object? Turing's objective while building his concept was to formalise how humans do abstract reasoning.

Now correct me if I am wrong but that reasoning seems just an exercise where you manipulate a set of formal statements i.e. strings with no semantics attached to it.

So if Turing machines is the same as reasoning, is there an isomorphism (or something like that) between formal languages and Turing machines?

No, they are not the same thing. A language is a set of words over some finite alphabet. A Turing machine is a 7-tuple as defined in the Wikipedia.

For some languages it is convenient to to characterize them by a TM that recognizes them. For every language that can be recognized by a TM there is an infinite number of TMs that recognize the same language, so you'd have to impose some additional criteria if you want to make that unique.

This might sound like a good start for an isomorphism, but unfortunately there are infinitely many languages that can't be recognized by TMs. This can be seen by a simple counting argument. The set of all possible words over a fixed alphabet is isomorphic to the natural numbers. Hence the set of all languages over that alphabet (=the set of all subsets of the words) is uncountable. On the other hand, there are only countably many Turing machines. So not only can't "recognition" be made into an isomorphism, there can't be an isomorphism of any kind since that would imply that the set of TMs has the same cardinality as the set of languages.


Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ and, since $\overline{A_{\mathrm{TM}}}$ is not Turing-recognizable, then $L$ is not Turing-recognizable.

I think that $\overline{L} = \{M\mid L(M) \text{ is finite} \}$ and that it means that $L(M)$ contains a finite number of strings.

I don't know how to construct a Turing machine that can prove $A_{\mathrm{TM}}\le_\mathrm{m} \overline{L}$.

Recall that the input to the halting problem is a pair $(\langle M\rangle, w)$ and we must accept this input if $M(w)$ halts, and reject it otherwise.

We want to decide the halting problem by reduction to $\overline{L}$.  That is, we need to produce a computable function $f$ that takes an input $(\langle M\rangle, w)$ and produces a string in $\overline{L}$ if $M(w)$ halts and a string that is not in $\overline{L}$ if $M(w)$ does not halt.

There's a small mistake in your reasoning in the question that's worth mentioning at this point, but it doesn't make any real difference.  Strings in $L$ are descriptions of Turing machines that accept infinitely many inputs.  That means that a string is in $\overline{L}$ if either it's a description of a Turing machine that only accepts finitely many inputs, or if it's not a description of any Turing machine at all.

However, we can ignore the strings that don't describe Turing machines and design a function $f$ such that $f(\langle M\rangle,w)$ is always the description of a Turing machine and that Turing machine accepts only finitely many inputs if $M(w)$ halts, and is one that accepts infinitely many inputs if $M(w)$ doesn't halt.

Hint: $\emptyset$ is finite and $\Sigma^*$ is infinite.  Transform $(\langle M\rangle,w)$ into the string $\langle M'\rangle$ such that $M'$ will accept nothing if $M(w)$ halts and will accept everything if $M(w)$ doesn't halt.

There's another hint below, which you can see by mousing over the yellow box. But try to figure it out on your own, first.

   Hint 2: the reduction is very similar to the one used to prove that the problem "Does $M$ halt on the empty input?" is undecidable.


Compute the edit distance between two words in which substitution is not allowed How do I compute the edit distance between two words in which substitution is not allowed?
The allowed operations include insertion (with cost 1) and deletion (with cost 1), but not substitution.
How is this supposed to be computed without substitution?

You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.
Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M[i][j]$ is the edit distance between $u_1…u_i$ (or $\varepsilon$ if $i = 0$) and $v_1…v_j$. The answer is then $M[n][m]$.
Now note that for $0< i\leq n$ and $0< j \leq m$:

if $u_i = v_j$, then $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\\M[i-1][j-1] & (\text{no modification})\end{array}\right.$
otherwise, $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\end{array}\right.$


Point in Polygon Problem: Has anybody invoked the line integral? Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements the function worked well enough, but I felt there was a better way. I found inspiration in Gauss's Law. Charges and the electric field aside, it boils down to, in 2D, a (contour) line integral. In a plane, the integral $\int_C d\theta = 2\pi$ if the point lies within the contour, and is zero if the point lies outside. With this in mind I reformulated the algorithm for arbitrary polygons:

double sum_theta = 0`
for( int i = 0 ; i < n_vtx ; i++ )
{
    int    j         = (i + 1) % n_vtx;
    XYPT   p_i       = ngon[i];
    XYPT   p_j       = ngon[j];
    XYPT   vector_i  = p_i - p_o;                 // vector from point o to vertex i
    XYPT   vector_j  = p_j - p_o;                 // vector from point o to vertex j
    double cp        = vector_i.cross( vector_j ) // cross product
    double dp        = vector_i.dot  ( vector_j ) // dot   product
           sum_theta+= Atan2( cp, dp );

}
if( sum > pi ) return INSIDE;
else           return OUTSIDE;

I'm not asking if this works. It does, rather well. (And I see no reason to replace it; I like its simplicity and elegance.) My question to this forum is largely of curiosity: Indeed, how much slower is this method than doing it by ray-casting (which can present gotchas) and intersection count; or by counting winding number (WN)? The application this services never has self-intersecting polygons (so, it seems, WN has no particular advantage) and the vertex count is never excessive (n_max ~ 25).

Any thoughts?

Summing the angles around a point is equivalent to calculating the winding number around that point. It will give you a correct answer in the general case.

Going more in depth, I'll try to show that your proposed algorithm has many drawbacks.

Algorithmic runtime

Algorithmically, your proposed algorithm must iterate over all $N$ points. Because of that, we can assume it runs in $\Theta(N)$ time.

In contrast, a ray casting algorithm checks against edges, of which there are $N$. The algorithm can be optimized using grids or quadtrees to reduce the amount of calculations needed. Since the ray might intersect all edges, that algorithm runs in $\mathcal{O}(N)$ time.

We can conclude that the ray casting algorithm will never perform worse than the angle sum.

Gotchas

You mentioned the ray casting algorithm as having gotchas. I'll assume you refer to the problems occurring when the ray crosses a vertex or an edge directly. First, your proposed algorithm has the same problem. What if the point you choose is on a vertex or an edge?

The solution to the problem for both algorithms is to define strict rules. That is, from the start, decide (or parametrize the algorithm) so that points on edges or vertices of the polygon are either all included or all excluded.

As an aside, the solution for ray casting's problem of intersecting vertices and edges can be solved using a similar rule. When a vertex is on the ray, it must be considered to belong to one side of the ray (more here).


Show that maximum disjoint set problem is NP Complete I have been thinking on this problem but couldn't come up with a good reduction yet. First part of the proof, i.e L is being in NP, is okay. However, I cannot find a proper reduction from 3-CNF-SAT to MAXIMUM-DISJOINT-SET problem.

Edit 1: MDS definition
MAXIMUM-DISJOINT-SET problem: We are given a collection S of
sets. We would like to find the maximum number of disjoint sets in S. K sets are said to be disjoint sets if they have no element in common(Wikipedia description).

I have tried the following ideas so far:

Let each clause in 3-CNF form be a set with each literal being its element. Our decision problem is "is it possible to find at least k-many disjoint sets?
If we put each literal of a clause to a set and distinguish between a literal and its negation, it does not work since phi = $(x_1 \lor x_1 \lor x_1)$ and $(\neg x_1 \lor \neg x_1 \lor \neg x_1)$ is not satisfiable but it is considered as disjoint set.
If we negate back all negated literals, then the set phi = ($x_1$ $\lor$ $x_2$ $\lor$ $x_3$)
and $(\neg x_1 \lor \neg x_2 \lor \neg x_3)$ is considered as non-disjoint although this function is satisfiable.

Any help is appreciated.

Given MIS is NP-Complete, we can reduce MIS to MDS. Let $G = (V,E)$ the graph we have for MIS problem. For every vertex $v_i \in V$, create a set $S_i$ with edges of $v_i$, however, be careful that write each edge element as $v_iv_j$ even if it is $v_jv_i$. Reduction is completed after creating the sets $S_i$. There is an independent set in $G$ of size $m$ if, and only if, there are $m$ disjoint sets where sets are taken from independent set's vertices.

This reduction can be performed in polynomial time since we traverse each vertex $v$ and its edges. It can be performed in $O(V+E)$. Additionally, given a collection of sets, we can verify if they are disjoint and there are at least $k$ of them in polynomial time.

Consequently, MDS is NP-Complete


Running time of naive primality tester A naive approach to checking if $n$ is prime is:

Prime(n):
    for i=2, 3, ..., sqrt(n):
        if i divides n then return "composite"
    return "prime!"

I remember something about how measuring the complexity of this algorithm must be done in terms of the number of bits in $n$. In that case, I think that we also can't assume that checking whether $i$ divides $n$ can be done in $O(1)$ time.

So, I don't think this algorithm runs in $O(\sqrt n)$ time. What is its complexity?

Firstly, you need to figure out what is the length of your input. Your input is $n$ so you need log(n) bits. Denote this number as $m$ not to get confused. Division takes either linear of m or constant time, depending on your model. So the question is how many time you gonna run it. Clearly, sqrt(n) times where $n=2^m$ so this algorithm runs in $O(2^{\frac{m}{2}})$ time.


Largest weight-limited connected subgraph: NP-complete? When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of having the longest network. Let's abstract that into the following problem:

Let a graph $G$ be given, $G = (V, E)$.
Associate a terraforming cost with each vertex, $C : V \mapsto \{0, 1, 2, 3\}$.
You're given some number of spades, $s$.

Your goal is to find a set of vertices $V^*$ such that:

You can afford to build on all of them, $\Sigma_{v \in V^*} C(v) \leq s$
They're all next to each other: the graph $(V^*, V^* \times V^* \cap E)$ is connected.
It is the largest such set: for all $V'$ which satisfy the previous conditions, $|V^*| \geq |V'|$.

The decision version takes a threshold parameter $k$ and asks "is there a vertex set $T$ with size $|T| \geq k$ and which satisfies the first two criteria?"

What is the complexity of this problem? By eyeball, it's obviously in NP; is it NP-complete? Is it well-studied under some name unknown to me?

The decision version is NP-complete so the problem is NP-hard. The following is a reduction from 3SAT.

For an instance of 3SAT with $n$ variables $x_1,\ldots, x_n$ and $m$ clauses, create a graph as follows:

For each variable $x_i$ create two vertices $v_i^0, v_i^1$ with cost $1$. Create an edge between each two vertices of these $2n$ vertices, i.e. the $2n$ vertices induce a clique.
For each variable $x_i$ create a vertex $v_i$ with cost $0$, and two edges $(v_i, v_i^0)$ and $(v_i,v_i^1)$.
For each clause $c_l$ with variables $x_i,x_j,x_k$, create a vertex $u_l$ with cost $0$, and three edges $(u_l, v_i^{b_i})$ (if the literal is positive, $b_i=1$, otherwise $b_i=0$, and the same below), $(u_l, v_j^{b_j})$ and $(u_l, v_k^{b_k})$.

Then we ask if there is a connected vertex set $T$ with size at least $2n+m$ and the sum of cost is no more than $n$.

Now if the instance of 3SAT has a feasible solution where $x_i=b_i$, we can make $T$ consist of all $v_i$s, $u_l$s and $v_i^{b_i}$s.

On the other hand, if $T$ exists, because you can afford at most $n$, at most $n$ vertices among $v_i^0, v_i^1$s are chosen, thus all $n+m$ vertices with cost $0$ must be chosen. This means:

Since $v_i$ is chosen, at least one vertex of $v_i^0$ and $v_i^1$ is chosen. Because at most $n$ vertices among $v_i^0, v_i^1$s are chosen, exactly one of $v_i^0$ and $v_i^1$ is chosen. We assign $x_i$ accordingly.
Since $u_l$ is chosen, at least one corresponding literal has value $1$, thus the clause is satisfied.

So the instance of 3SAT has a feasible solution.


Master Method to solve recurrences is 'a' related to 'b'? The master method allows us to solve certain recurrences of the form

$$T(n) = aT(n/b)+f(n)\,,$$

where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further restrictions that aren't important for this question.

The above recurrence describes the running time of an algorithm that divides a problem of size $n$ into $a$ subproblems, each of size $n/b$. This is intuitive in the case that $a=b$ (for example, merge sort divides the list into two parts of size $n/2$) but are there any examples of recursive algorithms that follow this schema but where $a\neq b$?

No it's not always the case that $a=b$, since you might not necessarily use every sub-problem. Consider for example, the binary search algorithm. In the algorithm, you have a sorted array that you break into two sub-problems of the same size ($b=2$), but only recurse on one of them ($a=1$). In this case, the recurrence would look like: $$T(n) = T(n/2) + O(1)\,.$$

For an algorithm like merge-sort however, not only is the problem broken into two sub-problems of equal size, but you recurse on both sub-problems before merging the results. In this case, you have that $a = b = 2$, and so, the recurrence looks  like: $$T(n) = 2T(n/2) + O(n)\,.$$


Multiple choice knapsack dynamic programming Giving a the following:

A list of a store items $T=\{t_1, t_2,...,t_n\}$.

A list of prices of each item $P=\{p_1, p_2,...,p_n\}$.

A list of quantities of each item $Q=\{q_1, q_2,...,q_n\}$respectively.

And total bill $M$.

Our goal is to find any possible list of items that its total value is equal to $M$ using dynamic programming.

My question does 0/1 weighted Knapsack problem help, where $M$ can be the capacity of the knapsack, and the weight of each item equal to the quantity of the item. If there is any other better approach  I would appreciate any references.

It turned out we can achieve it in $O(nM)$ time where $n$ is the number of distinct items in the store, and $M$ is the final bill.

We can build a 2-dimensional array with size $C[T, M]$ as follows:

$C[i, j] = 1$, if there exists a way to add items from $\{t_1,t_2,...,t_i\}$ that adds up to $M$.

$C[i, j] = 0$, if we cannot find items that adds up to $M$.

Finally, it's useful to use one extra row and column to make the calculation easier in the recursive solution.


What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$? Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are written in binary. What is the best known time complexity for determining whether there exists an integer $x$ such that $x^k \equiv c \pmod{N}$?

We are given the prime factorization of $N$ because this problem is thought to be hard on classical computers even for k = 2 if we do not know the factorization of $N$.

This question was inspired by this answer, where D.W. stated that the nonexistence of a solution to $x^3 \equiv 5 \pmod{7}$ can be checked by computing the modular exponentiation for $x = 0,1,2,3,4,5,6$, but that if the exponent had been 2 instead of 3, we could have used quadratic reciprocity instead. This lead to my discovery that there are a large number of other reciprocity laws, such as cubic reciprocity, quartic reciprocity, octic reciprocity, etc. with their own Wikipedia pages.

If $p$ is prime, then $x^k\equiv c \pmod p$ has a solution if and only if $c^{(p-1)/g} \equiv 1$ where $g=\gcd(k,p-1)$.  The solution is given by $x \equiv \sqrt[g]{c^h} \pmod p$ where $h^{-1} \equiv k/g \pmod{p-1}$.  You can take $g$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by Adleman, Manders, and Miller.  (Strictly speaking, this algorithm requires either reasonable number theoretic assumptions or randomization.)  Given one solution $x$, the other solutions will have the form $x \beta^i$ where $\beta$ is an element of order $g$ modulo $p$.

If $p^m$ is a prime power and $\gcd(p,k)=1$, then you can use Hensel lifting to test whether $x^k \equiv c \pmod{p^m}$ has a solution.  In particular, let $x_i=x \bmod p^i$ and $c_i=c \bmod p^i$ and $y_i = (x_{i+1} - x_i)/p$ and $d_i = (c_{i+1} - c_i)/p$.  Now find $x_1$ such that $x_1^k \equiv c_1 \pmod p$.  If this has no solution, then neither does $x^k \equiv c \pmod{p^m}$, so we can terminate immediately.  Otherwise, we're next going to try to find $x_2$ such that $x_2^k \equiv c_2 \pmod{p^2}$.  Writing $x_2 = x_1 + p y_1$ and $c_2 = c_1 + p d_1$, we obtain the equation

$$(x_1 + y_1 p)^k \equiv (c_1 + d_1 p) \pmod{p^2},$$

or equivalently,

$$k x_1 y_1 \equiv (c_1 - x_1^k)/p + d_1 \pmod p.$$

If $k x_1 \not\equiv 0 \pmod p$, then we can let $y_1 = ((c_1 - x_1^k)/p  + d_1) \cdot (k x_1)^{-1} \bmod p$ and we have a solution for $x_2$.  Otherwise, test whether $x_1^k \equiv c_2 \pmod{p^2}$; if it is, then setting $x_2=x_1$ gives a solution, otherwise there is no solution and we can terminate.  Repeat the same process to find $x_3$, then $x_4$, etc., until you have found $x_m$.  While there may be multiple possible solutions for $x_1$, there is no need to branch and try all of them, because either all will be extendable to $x_m$ or none will.

I am not sure what to do if $\gcd(p,k)=1$.  Perhaps someone else can fill in this gap.

If $N$ is a product of prime powers $p_1^{m_1} \cdots p_n^{m_n}$, then you can use the Chinese remainder theorem to check for a root modulo each of the $p_j^{m_j}$.  A root exists modulo $N$ if and only if it exists modulo each prime power; and once you've found a solution for each prime power, you can combine them with the CRT to obtain a solution modulo $N$.

Proof for first paragraph: If $p$ is prime, then there exists an element $\alpha$ of order $p-1$; assuming $x \equiv \alpha^X \pmod p$ and $c \equiv \alpha^C \pmod p$, we find that the equation has a solution if and only if $Xk \equiv C \pmod{p-1}$ has a solution, which is equivalent to the stated condition in the first paragraph.


Can most programs (except the IO part) be re-written as a sequence of matrix operations? I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to render the 3D world in a game) by processing the data in memory. All of these tasks could be done through a sequence (probably a graph) of matrix and vector operations, such as multiply, add, sum, etc.

For instance, I used to work for a car pool company, there was a piece of code to decide which car should respond to user. That logic was implemented with c++ stl containers and flow controls like if/else/break. Then I realized that it can be re-written as logistic regression (the business logic is stored in the linear predictive model) , with certain precision.

In this sense, matrix operation is a programming language by itself.

Can anyone share any thoughts here? Is there any introductory discussion wiki that I can read ?

If you regard the output of a program as a function of its input then matrices can be used to represent some programs, namely those where the output is a linear function of the input. So a program that takes two arguments $a$ and $b$ and returns $a+b$ and $a-b$ could be represented by the matrix

$\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

But most programs are not linear functions. For example, if the program instead returns $a^2+b^2$ and $a^2-b^2$ how will you represent that as a matrix ?


Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$? In the wiki page of Vertex Cover, it is claimed that an exhaustive search algorithm can solve the problem(the decision version of vertex cover problem) in time $2^{k}n^{O(1)}$.

Intuitively, with a fixed parameter $k$, in the worst case, the exhaustive search needs to check whether every vertex subset of size $k$ is vertex cover. The number of vertex subset of size $k$ is $\dbinom{n}{k}$, and we have $\dbinom{n}{k}=O(n^{k})$. Meanwhile, the number of steps to check a vertex subset of size $k$ is $O(kn)$, since we only need to verify whether the number of edge connected to or contained in the vertex subset is $m$, where $m$ is the number of edge in the graph. Thus, the time complexity of the exhaustive search is $O(k n^{k+1})$.

Is there any problem with my above analysis? And how to get a exhaustive search algorithm of time complexity $2^{k}n^{O(1)}$?

The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading.

The classic algorithm goes as follows:

If all edges are covered, succeed.
If you already have chosen $k$ vertices, fail.
Consider the first uncovered edge.
One of its endpoints must be in the vertex cover. This leads to two possibilities, on which you recurse. In each branch of the recursion, continue at 1.

The recursion has depth $k$ and branches binarily. Thus there are $2^k$ paths in the search tree. Each step can be processed in polynomial time.

[EDIT]

Success in Step 1 means that the current candidate set is indeed a vertex cover, so the algorithm may accept.

Failure in Step 2 means that the current candidate set cannot be extended to a vertex cover of size $k$, so the search must continue in another branch.

Also, thanks to chi for pointing out an ambiguity.


Lower bound and worst case scenario We know that the lower bound is the minimum amount of work needed to solve a problem.  So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say algorithm y, then the lower bound efficiency calculated  from this algorithm y is the least time this problem x can be solved through . So why do we calculate the lower bound efficiency for this algorithm on the worst case input ? why not on the best case input ? I mean lower bound is the minimum amount of work which therefore occurs on the best case scenario . Every time I see a decision tree algorithm problem to solve the lower bound of some sorting algorithm , the usual word is always mentioned "the worst case lower bound is blah blah blah" which confuse me so much ! Someone please fix my understanding :( .

When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative.

You can convince yourself that almost every algorithm can be adapted to have a best-case complexity of $O(n)$, where $n$ is the size of the input, by simply running a preliminary check that verifies if the input instance belongs to some class of instances for which the solution is trivial.

Just to give a concrete example: the best case for every sorting algorithm can be made $O(n)$ if you just check whether the input sequence of numbers is already sorted.

The focus is often on the worst-case complexity. Once you decide that you want to compare algorithms with respect to their  worst-case complexity, it also makes sense to ask how quickly a problem can be solved.

It is usually impossible to give a sharp bound to the time needed to solve a problem, therefore one seeks upper and lower bound.

An upper bound of $O(f(n))$ tells you that there is some algorithm that solves the problem in $O(f(n))$ worst-case time.

A lower bound of $\Omega(g(n))$ tells you that no conceivable algorithm can take  $o(g(n))$ time to solve the problem.

Just to be clear: a lower bound on the time needed to solve a problem is expressed as a function of the input size $n$ and is the smallest amount of work that is necessary to solve all instances of size $n$. Intuitively (not a formal definition) you can think of it as $\min_{A \in \mathcal{A}} \max_{I \in \mathcal{I}_n} T(A,I)$ where $\mathcal{A}$ is the set of all possible algorithms that solve your problem, $\mathcal{I}_n$ is the set of all instances of size $n$, and $T(A,I)$ is the time needed by $A \in \mathcal{A}$ to solve instance $I \in \mathcal{I}_n$.

What you seem to have in mind instead is $\min_{A \in \mathcal{A}} \min_{I \in \mathcal{I}_n} T(A,I)$.

A lower bound for a problem is useful to establish how "hard" that problem is to solve (problems that require more time to solve are harder, this would make little sense if we looked at the easiest instances instead), and to measure how far an algorithm is from being optimal.
For example Merge Sort solves the sorting problem in the optimal amount of time because its running time (asymptotically) matches the $\Omega(n \log n)$ lower bound for the sorting problem (in the comparison-based model).


Do all decidable problems lie in the class NP? All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a non-deterministic Turing machine in a polynomial time and in exponential time by a deterministic Turing machine.

Do we have a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable?

No to the question in your title; yes to the question in the body of your post.

By the non-deterministic time hierarchy theorem, every decidable NEXP-hard decision problem is "a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable".


Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input arrays, with all permutations of the numbers being equally likely) is concerned?

Or perhaps, has a case been made for the assertion that a generalization is not possible?

The asymptotic expected running time of quicksort is $\Theta(n \log n)$: this is true for all three pivot methods you mention.

Wikipedia says that the expected number of comparisons is approximately $1.386 n \log n$ when using a random pivot, and approximately $1.188 n \log n$ when using median-of-three pivot.  There's some experimental evidence that the number of comparisons might be about $1.094n \log n$ when using a ninther pivot for large arrays, median-of-three for medium-sized arrays, and single element for small arrays.  See the following research paper:

Jon L. Bentley, M. Douglas McIlroy, "Engineering a Sort Function".  Software Practice and Experience, 23(11):1249-1265, Nov 1993.

(This paper is cited in the Wikipedia article I mentioned above.)

I'm not familiar with the "uniform shuffle" pivot selection method.  It sounds equivalent to choosing a random element and using that as the pivot.


Brzozowski algebraic method for NFA Currently I have a graph (basically, a state graph) in Scala which is similar to an NFA

some nodes have multiple in/outgoing edges
single start state
there might be multiple final states
a state can contain self loops where a symbol is consumed
no epsilon transitions

What i'm trying to do is generate a regular expression from this graph.
I've found the following topic using Brzozowski algebraic method: https://cs.stackexchange.com/q/2392

However, it seems to be for DFA's, so my question:

can I use Brzozowski algebraic method OR Transitive closure method with my NFA, or do i need conversion first?

I need an algorithm that can be done by a computer to automatically generate a regex from a given graph.

Brzozowski's algebraic method is safe as long as you don't have epsilon transitions. It even works if your transitions are labelled by languages not containing the empty word. It may also work if some transitions contain the empty word, as long as you can eliminate them, as in the example below:

the system can be written as
\begin{align*}
 X_1 &= (a^*b + a)X_2 + b^*X_3 \\
 X_2 &= (a+b)X_1 + bX_3 + 1 \\
 X_3 &= aX_1 + aX_2 + 1
\end{align*}
Replacing $X_3$ by $aX_1 + aX_2 + 1$, and observing that $a + b^*a =
b^*a$, we obtain the equivalent system
\begin{align*}
 X_1 &= (a^*b + a)X_2 + b^*(aX_1 + aX_2 + 1) = b^*aX_1 + (a^*b + b^*a)X_2 + b^* \\
 X_2 &= (a+b)X_1 + b(aX_1 + aX_2 + 1) + 1 = (a + b + ba)X_1 + baX_2 + b + 1\\
 X_3 &= aX_1 + aX_2 + 1
\end{align*}
We deduce from the second equation
$$
 X_2 = (ba)^*((a + b + ba)X_1 + b + 1)
$$
and replacing $X_2$ by its value in the first equation, we obtain
\begin{align*}
 X_1 &= b^*aX_1 + (a^*b + b^*a)(ba)^*((a + b + ba)X_1 + b + 1) + b^*\\
   &= (b^*a + (a^*b + b^*a)(ba)^*(a + b + ba))X_1 + (a^*b +
   b^*a)(ba)^*(b + 1) + b^*
\end{align*}
Finally, the language recognised by the automaton is
$$
 X_1 = \bigl(b^*a + (a^*b + b^*a)(ba)^*(a + b + ba)\bigr)^*[(a^*b +
 b^*a)(ba)^*(b + 1) + b^*]
$$
since $1$ is the unique initial state.

Now, if you want to implement this algorithm, you may end up with more complicated regular expressions. For instance, the sentence "observing that $a + b^*a = b^*a$" might be difficult to implement. Other useful simplifications
like $a^* + 1 = a^*$ or even $K + K = K$ or $K + L = L + K$, where $K$ and $L$ are regular expressions, are also not easy to implement and require more sophisticated rewriting systems.


Definition of an immune set I'm reading a theorem about existence of a simple set.
The definition of an immune set can be found from here

A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ is infinite, but for every index ${\displaystyle e}$, we have ${\displaystyle W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I}$. Or equivalently: there is no infinite subset of ${\displaystyle I}$ that is recursively enumerable.

I am not able to understand this definition, because I couldn't come up with example.

Standard construction of a (co-c.e.) immune set

Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory.

The standard example of an immune set is as follows. Consider the set
$$P = \{\langle m, n\rangle \mid n > 2 m \land n \in W_m \},$$
where $\langle {-}, {-}\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is an acceptable pairing function. There is a computable selection function $f$ for $P$, i.e., a partial function $f$ such that: for every $m \in \mathbb{N}$, if there is $n \in \mathbb{N}$ such that $\langle m, n \rangle \in P$ then $f(m)$ is defined and $\langle m, f (m) \rangle \in P$. (Why does such an $f$ exist? Exercise!)

Observe that $f$ is defined at infinitely many values. Indeed, there are infinitely many $m \in \mathbb{N}$ such that $W_m$ is infinite, and at least at all of those $f(m)$ is defined.

Now let $S$ be the image of $f$, i.e.,
$$S = \{n \mid \exists m \in \mathbb{N} . f(m) = n\}.$$
We claim that the complement $I = \mathbb{N} \setminus S$ is immune:

Because $f(m) > 2 m$ for every $m$ at which $f$ is defined, the set $I$ is infinite. Indeed, among the numbers $0, 1, \ldots, k$, at most $k/2$ can be enumerated by $f$, so at least all the rest will be in $I$.
Suppose we had an infinite c.e. set $U \subseteq I$. There is $m$ such that $U = W_m$. Because $U$ is infinite, $f(m)$ is defined, hence $f(m) \in W_m = U \subseteq I$. On the other hand, by the definition of $I$ we also have $f(m) \in S \not\in I$, a contradiction. Therefore $U$ cannot be infinite.

The intuition behind the construction

Here is an informal explanation of $I$. The set $I$ has to satisfy two opposing conditions:

$I$ must be large enough (infinite).
$I$ must not be too large (for every infinite $W_m$, it has to avoid an element of $W_m$).

If we only cared about the first condition, we would take $I = \mathbb{N}$. If we only cared about the second condition, we would take $I = \emptyset$. But the two conditions work against each other.

Our first atempt could be this: for each infinite c.e. set $W_m$, pick an element $f(m) \in W_m$, let $S = \{f(m) \mid \text{$W_m$ is infinite}\}$ and let $I = \mathbb{N} \setminus S$. Then we satisfied the second condition, since $f$ enumerated one element of each infinite $W_m$, and we avoided all of those. However, there is no guarantee that $I$ is large enough – what if $S = \mathbb{N}$?. We can do better by making sure that

$f$ is computable so that $I$ will end up being co-c.e.
force $f$ to pick ever larger elements, so that we can be sure that it skips lots of numbers, which then end up being in $I$.

We achieve both of these with our constuction.

Let me finish with an interesting observation. In the effective topos, an immune set is an example of a subset of $\mathbb{N}$ which is neiter finite nor infinite.


Don't understand one step for AVL tree height log n proof I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand.

Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since we're looking for minimum number of nodes, let its children's minimum number of nodes be $N_{h-1}$ and $N_{h-2}$.

Proof:

$$N_h = N_{h-1} + N_{h-2} + 1 \tag{1}$$
$$N_{h-1} = N_{h-2} + N_{h-3} + 1 \tag{2}$$
$$ N_h = (N_{h-2} + N_{h-3} + 1 + ) + N_{h-2} + 1 \tag{3}$$
$$ N_h > 2N_{h-2} \tag{4}$$
$$N_h > 2^{h/2} \tag{5} $$

I do not understand how we went from (4) to (5). If anyone could explain, that'd be great. Thanks!

You can continue as same as line 4 the process like that:

$$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>\cdots$$
As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of times that we substract $2$ from $h$.

$$ N_h > 2N_{h-2}>\cdots>2(2(2(2(2h^{h-10}))))> 2^{\frac{h}{2}}$$


Can we prove that a time machine is impossible using the Halting Problem? Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ith day of the month. Basically it describes the present.

If we put this machine in a Halting Machine it should say whether the machine would halt. i.e. whether it would rain on the ith day of the month.

Since the Halting Machine is not possible, a time machine is not possible.

Is there any fault in my reasoning?

When we say that no Turing machine decides the halting problem, we mean just that – the mathematical model of a Turing machine has a certain limitation, not being able to compute the halting problem. Turing machines are supposed to model what is computable in the physical world, but this is not a mathematical fact. If the physical world turns out to be richer, all results on Turing machines will still hold, it's just that their real-world interpretation will be weaker.

What you show in your question is that if time travel is possible, then Turing machines are not a good model for the notion of computation. The fact that Turing machines cannot solve the halting problem has absolutely no bearing on the reality of time travel.

Moreover, you misrepresent the Turing machine model. A Turing machine has no access to the real world, so it cannot halt if it rains on a specific day. All it has access to is its (potentially infinite) tape. In fact, Turing machines cannot be realized in full generality in the real world (since their tape is potentially infinite) – they are abstract machines which are supposed to model some features of reality.


How "add" could be implemented in only bitshift operations Typically, add/subtract/multiply/divide are primitive operations in an Instruction Set Architecture (ISA). I am interested to know if they can instead be implemented efficiently using only bitshift operators. I'm interested to know what sequence of bitshift operations can reproduce the addition operation.

This is impossible, a shift does not combine two operands.


How to synchronize a 2d cellular automaton in $\Theta(\sqrt{n} \log n)$ steps Let's assume we have given a two dimensional cellular automaton with an initial configuration where alls cells are in an quiescent state, expect for one square of cells. Let $n$ be the number of cells in that square. We want to synchronize all cells in the square, so we basically want to solve the firing squad synchronization problem.

Synchronizing all cells in $\Theta(\sqrt{n})$ is rather easy: All cells at the left and right border of the square serve as generals and we synchronize each row separately with any standard 1-dimensional FSSP algorithm. A row of $k$ cells with generals at both ends can be synchronized in $\Theta(k)$ steps (in our case: $k=\sqrt{n}$).

What I want to do, is to synchronize the whole square in $\Theta(\sqrt{n} \log n)$, so I need to slow down the synchronization process by a factor of $\log n$. But I have no idea how to do so.

A naive solution could be that each general first launch a binary counter in its row and counts the current time until $k\log(k)$ steps and then run the FSSP. To do this you just need to detect the value of $k$ and compute $k\log(k)$ in less than $k\log(k)$ steps: sending a signal back and forth toward the other end while incrementing a binary counter gives you k written in binary in roughly $2k+\log(k)$ steps, so you also know $\log(k)$ (length of the counter). Within the $\Theta(k\log(k))$ steps left you have much more time than necessary to compute the product $k\times \log(k)$. And you're done.

I'm pretty sure that (1) there are more elegant solutions, (2) there is a general acceleration/slowdown theorem that could also be used here.


Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete? I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this  :

https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg

I wonder if the following is possible ? Which means, P = NP, but not all of them are in NP-Hard :

Edit : I want to add this : I'm not here to say if the original image is wrong or right, I'm just here to ask a question if my image contains a possible situation. In other words, is it correct to assume that all 3 images are possible ?

Actually, your version is correct and Wikipedia's is wrong! (Except that it has a tiny disclaimer at the bottom.)

If $\mathrm{P}=\mathrm{NP}$, Wikipedia claims that every problem in $\mathrm{P}$ is $\mathrm{NP}$-complete. However, this is not true: in fact, every problem in $\mathrm{P}$ would be $\mathrm{NP}$-complete, except for the trivial languages $\emptyset$ and $\Sigma^*$.

You can't many-one reduce any nonempty language $L$ to $\emptyset$, because a many-one reduction must map "yes" instances of $L$ to "yes" instances of $\emptyset$, but $\emptyset$ has no "yes" instances. Similarly, you can't reduce to $\Sigma^*$ because there's nothing to map the "no" instances to.  However, if $\mathrm{P}=\mathrm{NP}$, then every other language in $\mathrm{P}$ is $\mathrm{NP}$-complete, since you can solve the language in the reduction.

So, just to make it explicit:

your diagram is correct;
Wikipedia's isn't (unless you read the tiny disclaimer);
the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$" contains the two languages $\emptyset$ and $\Sigma^*$, and nothing else;
the area you've labelled "$\mathrm{P}$, $\mathrm{NP}$-complete" contains every other language in $\mathrm{P}$ and nothing else.


Predicting the next number output by a random number generator Given a start of a sequence of random numbers generated by some random number generator (of which we don't have the implementation), can we predict the next numbers in the sequence?

For example, having a series of random numbers like this

40 46 15 37 9 4
32 26 5 33 17 21
12 19 13 36 25 29

These are the output numbers from a random number generator and I want to know the pattern that was used to generate them.

It is a well-known fact concerning (cryptographically secure) pseudorandom generators (PRGs) that pseudorandomness is equivalent to next-bit unpredictability. That is, distinguishing the output of a PRG from the uniform distribution is just as hard as predicting its next bit of output (when the PRG works on a uniformly distributed seed). This goes back to a result by Yao.

Further reading:

Yao's test
Next-bit test
Pseudorandomness

If we are talking about standard (i.e., not necessarily cryptographically secure) random number generators (RNGs), then things are a bit different. If the RNG simply has to fulfill a set of heuristics, then it can be the case that it does so despite being (almost) fully predictable. (As an extreme example, consider the rather naive heuristic $\lim_{n \to \infty} E(|G(1^n)|_0) = \lim_{n \to \infty} E(|G(1^n)|_1) = \frac{1}{2}$, that is, the string $G(1^n)$ tends to have just as many zeroes as ones and the "generator" $G(1^n) = 0^{\lfloor \frac{n}{2} \rfloor} 1^{\lceil \frac{n}{2} \rceil}$.)

Breaking such an RNG would involve statistical tests and ad hoc methods; your chances of success depend on what the heuristics are and how much computational power and RNG data you have available. Without having detailed these things, it cannot really be said whether it is feasible to break it or not.


find the optimal combination Suppose I have these values with weights --
$$
x_1 = 2\\
x_2 = 4\\
x_3 = 5\\
$$
There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\cdot,\cdot)$, lets say the function values are like this --
$$
f(x_1,x_2) = 10\\
f(x_2,x_3) = 12\\
f(x_3,x_1) = 14\\
$$
What I am doing is running $O(n^2)$ loop (trying all combinations) and keeping the best pair, i.e. $\{x_3, x_1\}$

Is there any faster way to do this ? because my dataset can get arbitrarily large (10,000) and instead of 2 elements, I may need to compute the same with k elements ($k < \text{number of data points}$)

Sorting: Unfortunately, sorting is not possible, actually the weights that I am getting is from a function, the function takes $k$ data point (any combination) at a time and returns a value, i.e. $w = f(x_i, x_j, \ldots, x_k)$ so I need to pick the $k$ subset with the best (or you can say highest) $w$ value.

please help.

If I understand you correctly, the order of the inputs to function F does not
influence the output W, so order is not important.
I'm deducing this from the three possible subsets in your example  at the top
where K = 2 and N = 3.

For a set of N elements, and a function F taking K inputs where order of
inputs does not matter, the complexity to
find all possible W outputs I don't think is O(N ** K). I'm using ** as to the
power of.

I would think it is  the same problem as finding the number of ways to choose
K elements from a set of N elements disregarding order. I think one could also
say the number of partitions of K elements over a set of N elements.

The number of ways to choose K elements from a set of N elements is:

N // since you are choosing from a set of N elements
* (N - 1)  // since next you are choosing from a set of N - 1 elements
* (N - 2)  // same reasoning as above
...
* (N - (K - 1))  // just before you have chosen K elements
* (N - K)  // you have chosen the K-th element

Sort of like factorial, but from N -  K + 1 up to N, which is the same as N! / (N - K)!.

Lastly,   we have to disregard order of the elements, and there is K! ways to
order K elemetns, which brings us to:

N! / (N - K)! / K!

As each W is calculated you can simply keep the highest yealding inputs, and
when you have tried all inputs you will be guaranteed   to have found the
right set of inputs.

So, supposing the above is correct (it worked for small mental verification of K = 2,
N = 4 and K = 3, N = 4 and K = 3, N = 5) then I suppose the complexity
analysis is O(N! / (N - K)! / K!) and not O(N ** K).

If you know F then you could optimise it, to get a linear improvement, or
maybe find inputs that could be omitted to get an even bigger speedup.

Without knowing F you are stuck with trying everything.

One other thing you could do is employ memoization to avoid having to evaluate
F for similar inputs.


How to design a turing machine for a context-free grammar? what are the steps? How to design a Turing machine for a context-free grammar? what are the steps? for example, What are the steps to design a Turing machine for the following grammar with alphabet $\{a,b\}$.

$S\rightarrow aX\mid b$
$X\rightarrow bS\mid aX\mid \varepsilon$

This is what I come so far for the above example, in the link, any help appreciated.

You should first construct a PDA for your grammar. You can then use the tape in stead of the stack. When pushing something in the stack, write it on the tape of the TM from left to right. When poping the stack, read the tape then move the head left if necessary.
There is no other change (states and transitions can be the same).


Check if two separate ranges have some number in common We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there is at least one same number in those two ranges.

We don't need to answer the queries online, so we can sort them in different ways.

I tried different things with segment trees, but I don't have working ideas

You can get $\tilde{O}(NM)$ preprocessing time and $O(1)$ time per query.

Assume for simplicity that $N$ and $M$ are powers of $2$.
For each index $i = 1, \dots, n$ and $h = 2^0, 2^1, \dots, 2^{\log N}$, let $A[i, h]$ be the set of the elements in positions from $i$ to $i + 2^h -1$ in $A$. Define $B[j, k]$ similarly.

Let $R[i, h, j, k]$ be true if $A[i,h] \cap B[j, k] \neq \emptyset$ and false otherwise.
You can compute each $R[i, h, j, k]$ in constant time by exploiting the following relations:
$$
R[i, h, j, k] = R[i, h-1, j, k] \vee R[i + 2^{h-1}, h-1, j, k]  \quad \mbox{for }h>0
\\
R[i, h, j, k] = R[i, h, j, k-1] \vee R[i, h, j + 2^{k-1}, k-1]  \quad \mbox{for }k>0$$

where $R[i, 0, j, 0]$ is true iff the i-th element of $A$ equals the $j$-th element of B.

There is an intersection between the elements of A in positions $i, i+1, \dots, i+\ell_A - 1$ and the elements of B in positions $j, j+1, \dots, j+ \ell_B - 1$ iff the following condition is true:
$$
R[i, h, j, k] \vee R[i + h, h, j, k] \vee R[i, h, j + k, k] \vee R[i + h, h, j + k, k],
$$
where $h = \lfloor \log \ell_A \rfloor$ and $k = \lfloor \log \ell_B \rfloor$.


Why are DCFL not closed under concatenation or Union whereas CFL is? I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves Union is not possible.

However, DCFL is a proper subset of CFL (unambiguous) and CFL is closed under union and concatenation. So how can a proper subset not inherit the global properties of its parent set ?

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily deterministic CFL.


What is the correct time complexity of the following code I was wondering what is the correct time complexity expressed in terms of big O on this type of loop:

for(i=1;i<=n;i++)
    for(int j=1;j*i<=n;j++)
        // O(1) code here

The inner loops will make $n + \frac{n}{2} + \frac{n}{3} + \dots + \frac{n}{n}$. I know that this type of formula is $O(n \log n)$, so is this the correct time complexity on this piece of code?

$$n+\frac{n}{2}+\cdots +\frac{n}{n}$$

$$= n(1+\frac{1}{2}+\cdots +\frac{1}{n})$$

Now it is a well-known fact that $1+\frac{1}{2}+\cdots +\frac{1}{n} \le c \log n$, where $c$ is some constant.

$$\le cn(\log n)$$

So the overall Runtime is $\mathcal{O}{(n \log n)}$.


How is Memory Access Time of Processor calculated? In the Art of Assembly ebook, I have read that 8088 processor require four clock cycle to access memory (in whatever clock speed & memory speed is). How is it calculated? Is it time for processor to prepare for calculate address and put data on the bus?

The 8088 is $16 bit$ microprocessor with $8 bit$ data bus, it requires $2$ cycles to access word. During the second read counter is automatticaly incremented. In 8088 $1$ cycle is needed to apply valid physical memory address (and read or write). The missing $1$ cycle is for preparation. The cycles are not calculated, simply read from specification steps performed.

Cycle:

acquire valid address to address bus.
RD (or WR) signal is issued, DEN is asserted (if WR then data is put onto the data bus). DEN connects data bus buffers to external data.
allow memory to access data, if RD the data bus is sampled ot the end of cycle.
bus signals are deactivated, data sampling is finished (RD). If WR data is transfered to memory.


Does godel's incompleteness theorem still hold if we have a TM that can do an infinity amount of computations? I have heard whisperings that if we have a turing machine that is allowed to compute infinitely many steps in finite time, then we can solve the halting problem.

This made me wonder, if we have such a TM, do Godel's incompleteness theorems then not hold anymore?

My intuition is: If the TM can make an infinite amount of computations, it can simply check the truth-value of any formula, by checking all natural numbers. e.g. if we have a formula $\forall x \phi (x)$, the infinite-TM can simply check for every natural number $n$ whether $\phi(n)$ holds.

There is some ambiguity in how to define these new machines, essentially based on the question whether we can nest the "bursts of doing infinitely many steps in some finite time" or not. In the weakest interpretation, we essentially just get an oracle Turing machine with access to the Halting problem. In the strongest, we get the Infinite Time Turing Machines (ITTM).

Both machines can easily decide the ordinary Halting problem. However, the proof of non-computability of the Halting problem uses very little prerequisites. In particular, it shows that none of our machines can solve their own Halting problems.

So while an ITTM can decide truth of all basic arithmetic formulas (by just searching through the natural numbers whenever required), they cannot decide all $\Sigma^1_2$-formulas. And to properly define and work with ITTMs, we need $\Sigma^1_2$-formulas. So we have just pushed undecidability further out, but we have not removed it.

A $\Sigma^1_2$-formula is one of the form
$$\exists A \subseteq \mathbb{N} \ \ \forall B \subseteq \mathbb{N} \ \ \phi(A,B)$$
where $\phi$ is a formula which contains only quantification over numbers, but not over sets of numbers.


PAC-learning definition I am new in this field. In the book Foundations of Machine Learning by Mehryar Mohri, Afshi Rostamizadeh, and Ameet Talwalkar. The authors define the generalized error of a hypothesis as

$ R(h) = \Pr_{x \sim D}[h(x) \neq c(x)] = E_{x \sim D}[1_{h(x) \neq c(x)}]$

which is a number. However in the Definition 2.3 a concep class $C$ is said to be PAC-learnable if

$Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] \geq 1 - \delta$

for any $m \geq poly(1/\varepsilon,1/\delta,n, size(c)) $. Since by definition $R(h) = \Pr_{x \sim D}[h(x) \neq c(x)]$ is a number, What does this mean $Pr_{S\sim D^{m}}[R(h_{S}) \leq \varepsilon ] $ and $h_{S}$ in formal terms? The authors explain that $h_{S}$ depends on the sample $S$, but the question is how?

Another reason I have this question is due to the fact that every $h$ is defined as a function $h: \mathcal{X} \to \mathcal{Y}$ and the distribution $D$ is defined on $\mathcal{X}$, not on the hypothesis set $H$ where for each $h \in \mathcal{H}$, $h: \mathcal{X} \to \mathcal{Y}$.

$R(h)$ is not necessarily a number, it is a deterministic function of $h$. So, it would be a number if $h$ is deterministic, but if $h$ is a random variable, then $R(h)$ is also a random variable.
We consider $S \sim D^m$, a dataset that consists of $m$ i.i.d. samples, assumed to be drawn with respect to $D$. Accordingly, $h_S$ denotes the function that we end up with when we observed this fixed dataset $S$ (hence the subscript $S$).
Like you said, $R(h)$ is just a number for a given fixed $h$. However, in the case of $Pr_{S\sim D^m}(R(h_S))$, $h_S$ is NOT fixed and hence, neither is $R(h_S)$. Notice that it depends on the random dataset $S$ and as a function of a random variable, it is also a random variable.
Here is an example I just made up to demonstrate what these concepts correspond to:

Suppose you have a system that keeps spitting out pictures of animals and you want to classify them. Let's say, $\mathcal{Y} = \{\text{cat, dog, rat}\}$ and $\mathcal{X}$ is the set of all pictures that this picture generator can spit out that shows one of these three animals. Then, $D$ is defined over $\mathcal{X}$ because it describes the probability of observing a specific picture, for all possible pictures. Then, $S$ is $m$ observed pictures from this picture generator, sampled in i.i.d. fashion. These are concepts that are independent from your learning system, but only related to the nature of the problem you're dealing with.
Suppose you believe the best way to classify which animal is in a picture is to use a convolutional neural network (CNN) of a specific size and architecture and is trained using a certain algorithm. Then, you are restricting your hypothesis set $H$ as the set of all CNNs of that architecture and size that can be obtained via your specified training approach. If you instead decided to use SVMs, you would have ended up with a different $H$. Since $S$ is random, the CNN you'll obtain (i.e. $h_S$) is also random.

Notice there is an inherent randomness in $h_S$ due to the randomness in $S$, but there can be even more randomness if your training algorithm is non-deterministic. So, depending on the training approach that takes you from $S$ to $h_S$, $h_S$ can be a random variable even for a fixed $S$ (think about stochastic gradient descent).
Long story short, due to these random factors at play, $R(h_S)$ is not just a number, but a random variable.


lambda calculus beta reductions: ((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a)) My question is in continuation to lambda calculus reduction: (((lambda f (lambda x (f x))) (lambda y (* y y))) 12)

given the input:

((((lambda f (lambda x ((f x) f))) (lambda y (lambda g (g (* y y))))) 2) (lambda a a))

I want to understand the order of reductions that I should take. in the above mentioned question it was suggested to me to apply left most reduction.

I want to check if this is a valid 1st step towards leftmost reduction:

Or should f= λy.λg.g(*y y) instead ?
What it might boil down to is: am I allowed to solve the sub-trees up before applying the solution from the right subtree on the left sub-tree?

$$
(\lambda f. \lambda x .f x f)
(\lambda y.\lambda g. g (* y y))
2
(\lambda a. a)
$$

The leftmost redex $(\lambda a.b)c$ is

$$(\lambda f. \lambda x .f x f)(\lambda y.\lambda g. g (* y y))$$

with

$a = f$
$b = \lambda x .f x f$
$c = (\lambda y.\lambda g. g (* y y))$

Don't forget to make sure that $x$ doesn't exist in $c$, because if so then doing an immediate beta reduction would change the meaning of the expression.  So the redex reduces to:

$$(\lambda x .(\lambda y.\lambda g. g (* y y)) x (\lambda y.\lambda g. g (* y y)))$$

Overall giving

$$
(\lambda x . (\lambda y.\lambda g. g (* y y)) x (\lambda y.\lambda g. g (* y y)))
2
(\lambda a. a)
$$

The next redex is $(\lambda y. \cdots)x$


Comparing two algorithms for all-pairs shortest paths I read in my notes:

If we use Dijkstra $|V|$ times ($|V|$ number of vertices) for finding all-pairs shortest paths in graph $G$, we get time complexity for Dijkstra algorithm as $O(VE+ V^2 \log V)$, and if we run Bellman–Ford algorithm $|V|$ times, we get time $O(V^2E)$.

The above details are not important.
I read too, that Dijkstra's algorithm works better for sparse graph, that is, $O(VE+ V^2 \log V)$ is better than $O(V^2E)$ asymptotically for sparse graphs.
I think sparse graphs are graphs satisfying $ |E| = O(V)$  or $E=o(V^2/\log V)$. In fact, I have two misunderstandings:

Which one is more common as the definition of a sparse graph?

According to 1, how we can intuitively understand that $O(VE+ V^2 \log V)$ is better asymptotically than $O(V^2E)$? At least I think the reverse is true.

There is no standard definition for sparse graphs. Some common definition include graphs in which $E = o(V^2)$, $E=O(V^{2-\epsilon})$, $E = O(V^{1+\epsilon})$, $E=O(V^{1+o(1)})$, $E = O(V\log^C V)$, and $E = O(V)$.
In most situations, it is safe to assume that the graph is connected, and so $E \geq V-1$. In such cases, $VE + V^2\log V = O(V^2 E)$, and so an upper bound on the running time of the form $O(VE + V^2\log V)$ is better than an upper bound of the form $O(V^2 E)$: indeed, the former implies the latter.


A variant of hitting set problem? Is this also a NP-hard problem? Let's start from finding a minimum hitting set problem. Given a collection of sets $U=\{S_1,S_2,S_3,S_4,S_5,S_6\}=\{\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}\}$,  it is easy to know that a minimum hitting set is $\{2,4\}$.

I am thinking what this "hitting set" problem would be if the set $S$ is also a collection of sets.
For instance, given
$S_1=\{\{1,2,3\},\{3,4\},\{1,2\}\}$,
$S_2=\{\{3\},\{3,5\},\{1,3\}\}$,
$S_3=\{\{2,5\},\{4\},\{1,5\},\{1,10,6,7\}\}$,
and in this new problem, the "hitting set  $H$" should be a set that:
1. For each $S_i$, there must exist an element $s$ which is a subset of $H$;
2. The cardinality of $H$ is as small as possible.

Therefore, we can see that $\{3,4\}$ is a solution.

It looks like I am trying to select an element from each set where each is a collection of sets, and then the cardinality of the union of these selected elements is as small as possible.

Does anyone have an idea to solve this problem? Do you think it is a variant of hitting set problem? Is it an NP-hard problem?

The special case of your variant where every set $S_i$ contains only single-element sets are exactly the standard hitting set problem, so this variant is at least harder than the standard hitting set problem, thus is NP-hard.


Create Shortest Path tree for every node after Floyd Warshall in O(nm) Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after execution of Floyd Warshall. We were asked to think about why this is not $O(n(n+m))$ and for which graphs we really would have to do $O(n^2)$ work and if it really is $O(n^2)$ for these graphs.
The Output should be all shortest paths trees $T_v$ for any $v \in V$
I can clearly see running DFS on every node as start node and checking if an edge is part of the shortest path or not results in O(n(n+m)) which doesnt give the desired result.
I came up with the following ideas:

I thought about if I can state that n >= m/2 if we exclude all isolated nodes in $O(n)$ first, so $O(n^2) = O(nm)$ what would result in $O(nm)$ over all.
Another possibility regarding DFS would be adding edges for other trees which hold the same edge. I came up to use a $nxm$ Matrix wheter a node was added or not and keep track of visited nodes to add edges for every node. But since I have to go through all nodes every time and check for matrix entry, which does not improve that much over all.
I also thought about path construction using a next matrix, which can be created during floyd warshall though I have to do it for every combination of two nodes in two for loops and every one recursive call is worst case $O(n)$ which results in $O(n^3)$. It would get better only if a can skip loops and edges though I can´t see an efficient way to achieve this.

Do you see any flaws within in my statements above and might any of these possibilites leed to the disired outcome? How can it be solved?

Compute all pair to pair distances $D[u,v]$ for $u,v \in V$ using Floyd-Warshall.
For each vertex $s \in V$ construct a graph $H_s$ as follows:

For each edge $e = (u,v)$ check whether $D[s,u] + D[u,v] = D[s,v]$. If the answer is yes the (directed) edge $(u,v)$ belongs to at least one SPT from $s$, and you add $e$ to $H_s$.

This requires time $O(n \cdot m)$ and each graph $H_s$ is encoding all SPTs from $s$. To get a single SPT from $T_s$ each $s$ compute any spanning arborescence of $H_s$ rooted in $s$. This can be done, e.g., via a BFS.


Find Correlations in Vectors of symbols Given a set of vectors, lets say that each coordinate is populated from an alphabet (meaning set of symbols, numbers, etc) (particular or shared alphabets are indistinct).

Is there any standard procedure for performing the following task ?

Look for sets of positions that "make the same choice" in several vectors.

That means: a subset of indices where, when we project to just those indices, there's some value that's taken on by many of the vectors.

An example:

Input
[0,-,0]
[0,+,+]
[+,+,+]
[0,0,0]
[-,+,+]

Output

2 coordinates involved ( 2 and 3), appearing in 3 vectors: x2=+ and x3=+
1 coordinate involved (1), appearing in 2 vectors:  x1=0

A possible solution would be generating (in Apriori terms) a "transaction" that contains indexed symbols and mine that for frequent itemsets.