Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch I am reading the paper Color Coding by Alon, Yuster, and Zwick. They state a theorem (6.3) that says if $H$ is a graph on $k$ vertices with treewidth $t$ and $G = (V, E)$, then a subgraph of $G$ isomorphic to $H$ can be found in $2^{O(k)}V^{t+1}$ expected time. They do not include a proof, but do state that the proof is similar to the case where $H$ is a forest (namely theorem 6.1, which they do provide a proof of).

As I am trying to understand how they algorithm would work for graphs of bounded treewidth, I was wondering if anyone could provide a proof sketch of the algorithm, as I don't see how it would be similar to the proof of 6.1 - Any help would really be appreciated, as this is for a course project, and I am having difficulties figuring out the algorithm.

A copy of the paper can be found here: http://www.tau.ac.il/~nogaa/PDFS/col5.pdf

The idea is to repeat the proof of Theorem 6.1, only during the recursive construction in the second paragraph, we use the tree decomposition of $H$ rather than $H$ itself. We pick a vertex in the tree decomposition, which correspond to up to $t+1$ vertices of $H$, and split $H$ into two parts $H',H''$ accordingly, applying the algorithm recursively. Since we are dealing with groups of up to $t+1$ vertices at a time, we have to calculate the color sets for sets of $t+1$ vertices rather than for single vertices.

There are many resources online for this general approach, dynamic programming for graphs of bounded treewidth. You can consult Section 2.4 of Hajiaghayi's thesis or a presentation by Marx.


Finding cycles in a graph Given a directed weighted graph $D = (V, A, w)$ with weight function $w \colon A \to [0,\infty)$ and a source vertex $s$.  How can I find, for each vertex $v \in V$ a shortest (with respect to $w$) cycle that contains both $v$ and $s$ (it is allowed to repeat the same arc in a cycle).

Find the shortest path from every vertex to every other vertex. To find the shortest cycle from $s$ to $v$, just concatenate the shortest path from $s$ to $v$ and then $v$ to $s$ which was found earlier


Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string? I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the last letter wasnt in the string before the last letter was read. I only seem to be able to create a NFA that accepts a subset of the language. What is the right way to go about it? I'm very lost.

This is my try at a 2 letter alphabet but i feel like for a 4 letter alphabet the NFA is going to be huge. Is there a methodology I'm completely missing or do I just use brute force?

The idea is to implement the following regular expression:
$$
\sum_{\sigma \in \Sigma} \Sigma^* \sigma \Sigma^* \sigma.
$$
Details left to you. Number of states is $|\Sigma| + 2$.

Let us show that $|\Sigma| + 2$ is the optimal number of states, using the fooling set method. We have to give $|\Sigma|+2$ pairs $(x_i,y_i)$ such that $x_iy_i \in L$ (here $L$ is your language), but for each $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. For each $\sigma$, we have the pair $x_\sigma = y_\sigma = \sigma$. For some arbitrary $\tau \in \Sigma$, we have the two pairs $x_\gets = \tau\tau, y_\gets = \epsilon$ and $x_\to = \epsilon,y_\to = \tau\tau$. You can check that indeed $x_iy_i \in L$ for all $i$. In the other direction:

If $\sigma_1 \neq \sigma_2 \in \Sigma$ then $x_{\sigma_1} y_{\sigma_2} \notin L$.
If $\sigma \in \Sigma$ then $x_\sigma y_\gets, x_\to y_\sigma \notin L$.
Similarly, $x_\to y_\gets \notin L$.


Find the loop invariant of the given while loop I don't know how to find a loop invariant.  I'm not sure where to start.  Can anyone find the loop invariant of the given program and explain your method please.

{n ≥ 0 ∧ i = 0}
while i < n − 1 loop
b[i] := a[i + 1];
i:=i + 1
end loop
{∀j.(0 ≤ j < n − 1 → b[j] = a[j + 1])}

At the end of each iteration you have
$$
\forall j: 0 \leq j < i \implies b[j] = a[j+1]
$$
which you can prove by induction. Thus, when the algorithm terminates, $i$ has reached $n-1$ and you have
$$
\forall j: 0 \leq j < n-1 \implies b[j] = a[j+1]\,.
$$

I figured this out by just asking myself what kind of statement I can make at the end of each iteration. In this case it's that the first $i$ elements have been copied. Then I just turned that into a formal statement.


$\lambda x. \lambda x.x$ vs $\lambda y. \lambda x.x$ Several times, I saw $\lambda$-terms such as $\lambda x. \lambda x.x$, where $x$ is bound by the inner lambda, which I agree.

why not just write it as $\lambda y. \lambda x.x$, so it is clear and you don't need to comment such as "where $x$ is bound by the inner lambda".

what is the point of writing  $\lambda x. \lambda x.x$, why not just write it as $\lambda y. \lambda x.x$? Usually, we don't write long lambda terms, so we have enough names to name bound variables distinctly.
why not just state that "all bound variables should be given distinct names" to avoid such vague terms and explanations?
is there a particular reason for having  $\lambda x. \lambda x.x$?

I believe it is because of the syntax of lambda terms.
I also believe banning such terms is reasonable.

You have basically discovered the Barendregt convention.

Yes, it's silly to write terms such as $\lambda x. \lambda x. x$ when $\lambda y. \lambda x. x$ is $\alpha$-equivalent and clearer.

We could forbid the former form the syntax of the lambda calculus. This however would force us to check $x$ does not occur bound in $M$ every time we craft (introduce) the term $\lambda x. M$.

The Barandregt convention goes further. It stipulates that, when building (introducing) a term $\lambda x. M$ we are always allowed to do that. However, when destructuring (eliminating) a term $\lambda x. M$ we can assume that $x$ was $\alpha$-converted so no to cope with other bound names in $M$, nor with other names that we could have around elsewhere at the moment: e.g., if we are writing a proof involving terms $N$ and $O$, the convention stipulates that $x$ does not occur in $N,O$ as well.

The convention is just a convenient shortcut, made for lazy humans which do not want to spend their time and energy to fix trivialities. Basically, we pretend that $\lambda x.\lambda x. M$ is allowed when it's convenient to do so (introduction), yet we pretend that the same is no longer allowed when convenient to do so (elimination).  It feels a bit like cheating, but one could (in theory) always fix the proof to be perfectly sound.


If A is not in NP, and A reduces to B, does this mean B is not in NP? I know it is true that if A is not in P, and A reduces B, then B is not in P.
But is it true for NP as well?
If A is not in NP, and A reduces to B, does this mean B is not in NP?
Why or why not?
Thanks!

I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions.
Suppose towards a contradiction that $A \not\in NP$, $A \le_p B$, and $B \in NP$.
Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following:

Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $A$ into an instance $f(x)$ of $B$;
Simulate a non-deterministic polynomial-time Turing machine $T$ that decides $B$ on input $f(x)$ ($T$ exists since $B \in NP$);
If $T(x)$ accepts, accept. If $T(x)$ rejects, reject.

This is a contradiction.


Find minimum number 1's so the matrix consist of 1 connected region of 1's Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ can reach another one through a sequence of neighbors.

Example:

100
000
001

Here we need 3 $1$'s:

100
100
111

How can we efficiently find the minimum number of $1$'s to add, and where?

If you model your problem with graphs, Your problem is like Steiner Tree problem:

See here for simplest possible definition.

  Given a weighted graph in which a subset of vertices are identified as
  terminals, find a minimum-weight connected subgraph that includes all
  the terminals.

As you can see it's NPC in general, but in your case your graph is grid graph, may be you can find good solution for it, but for your current example (when terminals are in boundary) you can see Steiner tree in grid graphs paper.

Anyway there are excellent heuristics for Steiner Tree problem, you can apply similar approach to your problem.

P.S: You can assume neighbor 1s are connected nodes, after that you can contract their edges to make a new graph, your new created graph is planar, and if you could solve the Steiner Tree for it you can solve your problem, but may be there is a good solution for your problem which is independent from Steiner Tree.


How to deal with character set in regular expression? In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit or \w to represents word character.
I wonder how they are converted to DFA, since you cannot really create expand edges in alphabet(Unicode).

Take example as: x(2|\d)*y.
The dfa is generated as the following graph.

Apprently 2|\d is the same as \d, the edge '2' is not necessary since it is contained in '\d'. But DFA cannot realize it.

Is there any way to reduce such kind of redundancy?

It also seems regular expression compression becomes very difficult. If we don't expand \d to 0|1|2...|9
E.g. we can hardly say is \w+ equals a*\w+b* or not.

And does those regular expression implemention (e.g. re package in python) consider the redundancy?

Theoretically, NFA or RegEx minimization is PSPACE-complete [1]

Practically, you can throw as many optimizing features to your online regex visualizer websites as current websites do, as long as it does not consume all your server's resources.

[1] Minimizing nfa’s and regular expressions, Gregor Gramlich,, Georg Schnitger


Generating uniformly distributed random numbers using a coin You have one coin. You may flip it as many times as you want.

You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.

Distribution of the numbers should be uniform.

It is easy if $b -a = 2^n$:

r = a + binary2dec(flip n times write 0 for heads and 1 for tails)

What if $b-a \neq 2^n$?

What you're looking for is based on Rejection sampling or the accept-reject method (note that the Wiki page is a bit technical).

This method is useful in these kinds of situations: you want to pick some random object from a set (a random integer in the set $[a,b]$ in your case), but you don't know how to do that, but you can pick some random object from a larger set containing the first set (in your case, $[a, 2^k + a]$ for some $k$ such that $2^k + a \ge b$; this corresponds to $k$ coin flips).

In such a scenario, you just keep picking elements from the bigger set until you randomly pick an element in the smaller set. If your smaller set is big enough compared to your larger set (in your case, $[a, 2^k + a]$ contains at most twice as many integers as $[a,b]$, which is good enough), this is efficient.

An alternative example: suppose you want to pick a random point inside a circle with radius 1. Now, it isn't really easy to come up with a direct method for this. We turn to the accept-reject method: we sample points in a 1x1 square encompassing the circle, and test if the number we draw lies inside the circle.


Asymptotic order of a recursive function \begin{gather*}
T(n)=T(\frac{n}{\log n})+O(1)
\end{gather*}
\begin{gather*}
T(1)=O(1)
\end{gather*}
I try to use substitution method to solve $T(n)$, but because of $\log n$ get stuck. Can we use substitution method for solving $T(n)$?
My attempt:
One step of my extending of $T(n)$:
\begin{gather*}
T(n)=T(\frac{n}{\log n})+O(1)=T(\frac{\frac{n}{\log n}}{\log \frac{n}{\log n}})+O(1)+O(1)
\end{gather*}

What you are asking is really, how many times do you need to apply the transformation $m \mapsto \frac{m}{\log m}$ in order for a value to drop from $n$ below some constant $C$; if the answer is $f(n)$, then $T(n) = \Theta(f(n))$.
Given $n$, define a sequence by $n_0 = n$ and $n_{i+1} = n_i/ \log n_i$. We would like to know the minimal value of $t$ which satisfies $n_t < C$.
Taking logarithm, we see that $\log n_{i+1} = \log n_i - \log\log n_i \geq \log n_i - \log\log n$. Since $\log n_0 = \log n$, this shows that $t \gtrsim \frac{\log n}{\log\log n}$.
In the other direction, as long as $n_i \geq \sqrt{n}$, we have $\log n_{i+1} \leq \log n_i - \log \log \sqrt{n} \leq \log n_i - \log \log n + \log(1/2)$. Hence we get from $n$ down to $\sqrt{n}$ in roughly $\frac{\log n}{\log\log n}$ steps. We then get down to $\sqrt[4]{n}$ in roughly $\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \approx \frac{\frac{1}{2} \log n}{\log\log n}$ steps. Continuing in this way, we see that $t \lesssim \frac{2\log n}{\log\log n}$ (summing the series $1+\frac{1}{2}+\frac{1}{4} + \cdots = 2$).


How hard is finding the discrete logarithm? The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.

I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what approaches (i.e. algorithms) are the best for accomplishing this task.

The wikipedia link above doesn't really give very concrete runtimes.  I'm hoping for something more like what the best known methods are for finding such.

Short answer.
If we formulate an appropriate decision problem version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes NP, coNP, and BQP.

A decision problem version of Discrete Log.
The discrete logarithm problem is most often formulated as a function problem, mapping tuples of integers to another integer. That formulation of the problem is incompatible with the complexity classes P, BPP, NP, and so forth which people prefer to consider, which concern only decision (yes/no) problems. We may consider a decision problem version of the discrete log problem which is effectively equivalent:

  Discrete Log (Decision Problem). Given a prime $N$, a generator $a \in \mathbb Z_N^\times$ of the multiplicative units modulo $N$, an integer $0 < c < N$, and an upper bound $b \in \mathbb N$, determine whether there exists $1 \leqslant L \leqslant b$ such that $a^L \equiv c \pmod{N}$.

This would allow us to actually compute loga(c) modulo N by binary search, if we could efficiently solve it. We may then ask to which complexity classes this problem belongs. Note that we've phrased it as a promise problem: we can extend it to a decision problem by suspending the requirements that $N$ be prime and $a \in \mathbb Z_N^\times$ a generator, but adding the condition that these restrictions hold for any 'YES' instance of the problem.

Discrete Log is in  BQP.
Using Shor's algorithm for computing the discrete logarithm (Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer), we may easily contain Discrete Log in BQP. (To test whether or not $a \in \mathbb Z_N^\times$ actually is a generator, we may use Shor's order-finding algorithm in the same paper, which is the basis for the discrete logarithm algorithm, to find the order of $a$ and compare it against $N-1$.)

Discrete Log is in  NP ∩ coNP.
If it is actually the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, a sufficient certificate either for a 'YES' or a 'NO' instance of the decision problem is the unique integer $0 \leqslant L < N-1$ such that $a^L \equiv c \pmod{N}$. So it suffices to show that we can certify whether or not the conditions on $a$ and $N$ hold. Following Brassard's A note on the complexity of cryptography, if it is both the case that $N$ is prime and $a \in \mathbb Z_N^\times$ is a generator, then it is the case that
$$ r^{N-1} \equiv 1 \!\!\!\!\pmod{N} \qquad\text{and}\qquad r^{(N-1)/q} \not\equiv 1 \!\!\!\!\pmod{N} ~~\text{for primes $q$ dividing $N-1$} $$
by definition (using the fact that $\mathbb Z_N^\times$ has order $N-1$).

A certificate that the constraints on $N$ and $a$ both hold would be a list of the prime factors $q_1, q_2, \ldots$ dividing $N-1$, which will allow us to test the above congruence constraints. (We can test whether each $q_j$ is prime using AKS test if we wish, and test that these are all of the prime factors of $N-1$ by attempting to  find the prime-power factorization of $N-1$ with only those primes.)
A certificate that one of the constraints on $N$ or $a$ fail would be an integer $q$ which divides $N-1$, such that $a^{(N-1)/q} \equiv 1 \pmod{N}$. It isn't necessary to test $q$ for primeness in this case; it immediately implies that the order of $a$ is less than $N-1$, and so it is a generator of the multiplicative group only if $N$ fails to be prime.


Algorithm to return largest subset of non-intersecting intervals I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.

i.e. Given a set of intervals $I =  \{I_1, I_2, \ldots, I_n\}$ of the real line, we need to output a set of intervals $O = \{O_1, O_2, \ldots, O_k\}$ such that

$O$ is a subset of $I$.
For any $i \neq j$, $O_i$ and $O_j$ are non-intersecting.
$k$ is the maximum possible.

Example: if the intervals are $[1,100], [2,3], [4,5], [6,7], [3,20]$ we should return $\{[2,3], [4,5], [6,7]\}$.

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem).

We first sort the intervals by their right end point. Suppose the sorted order is
$I_1, I_2, \ldots, I_n$.

Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval being the rightmost interval in that set. We pick the interval which gives the maximum (as any non-intersecting set has a rightmost interval).

This we do using dynamic programming.

Suppose we have computed the sizes (say $S_1, \ldots, S_n$) for intervals up to $k-1$.
Now you want to compute for $I_k = [L_k, R_k]$.

Pick $L_k$, and do a binary search in $[R_1,R_2, \ldots, R_k]$. Say $R_j \lt L_k \lt R_{j+1}$.

Now all the intervals $1,2,\ldots,j$ do not intersect $I_k$ (and all others up to $I_{k-1} \cap I_k$). Thus we need to pick the max among $S_1, S_2, \ldots, S_j$ and add $1$ to it. This maximum can also be computed dynamically, in a separate array, along with the $S$.

This can be implemented so that the whole algorithm runs in $O(n \log n)$.

We can also modify this algorithm a little to give you the actual intervals which form the non-intersecting set.


Why does λz.zq reduce to q? The way I see it, it should not be further reducible. I'm thinking λz.zq is like

lambda z: z(q) # Python, not lambda calc

and you do not know z nor q so it is not further reducible.

The below derivation (where I am wondering about the last steps) is from the new Haskell book:

It is $\beta$-reduction defined in terms of substitution (rename ($\alpha$-conversion) first if necessary):

$$(\lambda z. zq) (q) \to_{\beta} [z/q](zq) = qq. $$

In Haskell, $\lambda z.zq$ defines an anonymous function which takes a single parameter (represented by $z$) and performes $zq$.


Improving Time Bound of this Algorithm past $O(n^2)$ I recently came across the following interesting problem - one is given a sequence of Xs and Ys such as XXYXYXYYXYXXXYX, and consider a sequence to be good if, as you start at the left and move right, the number of Xs is greater than or equal to the number of Ys at any point except at the very end, at which the two quantities must be equal.

One must determine the number of points at which changing either a single X to Y or a single Y to X in a given sequence will yield a good sequence.

I initially considered traveling through the sequence linearly and checking if toggling the letter at that point would yield a good sequence, however that approach is on the order of $O(n\cdot n)=O(n^2)$ in the worst case where n is the length of the sequence. However, I was wondering if there was some faster method to do it.

EDIT: I made the observation that for any sequence, if the number of possible changes is greater than 0, than only one type of change will work (either changing an X to Y or Y to X) given the condition at the end that the number of X and Y must be equal.

Here is a hint. Suppose the sequence contains $n-1$ Xs and $n+1$ Ys, so that you need to change some Y to X. You can compute for each position $k \in [1,\ldots,2n]$ the number of Xs minus the number of Ys; let's call that a "report". Changing a Y to an X affects the report in a certain, easy to describe, way. On the other hand, whether a sequence is good corresponds to a very simple property of the report.

Putting everything together, you should get an $O(n)$ algorithm.


Is the term page replacement actually a misnomer? My understanding is that "page replacement" entails replacing the contents of a frame to bring in a new frame in it's place corresponding to a new page. Since it is not the page, but the frame that changes, shouldn't this process be called "frame replacement"?

Is the term page replacement actually a misnomer?

No.

A page is the entity in virtual memory.
A page frame is the real memory into which it is mapped.

So it is the page, not the frame, that is replaced.

The metaphor is that the (virtual) page is the picture around which the frame is placed. You move the frame to picture different pages. See here.


Hardness and directions of reductions Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard.

As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By conflating one of the colors in the 3-coloring you have a 4-coloring, ergo 4-coloring is hard.

That's the how. But why is this a proof that 4-coloring is hard? Is it that you can use the solution to the 4-coloring problem to solve the 3-coloring problem? If so, how? If not, why is it a valid proof?

Bonus q: Must the polynomial reductions be able to go in both ways?

Edit: if you would be able to explain why this is so by an example you would do the internet a favor. I couldn't find this explained in a concrete way anywhere.

A reduction from a problem $A$ to another problem $B$ is a transformation $f$ of any instance $a$ of $A$ into an instance $f(a)$ of $B$, such that

$$\qquad\qquad x∈A ~~⇔~~ f(x)∈B \qquad \qquad (E)$$

If $f$ is a transformation preserving the complexity you are interested in (e.g. $f$ is a polynomial transformation if you consider $\mathsf{NP}$-hardness) then the existence of an algorithm $\mathcal A_B$ solving $B$ implies the existence of an algorithm solving $A$: it is enough to run $f$, then $\mathcal A_B$.

Hence the existence of such a reduction from $A$ to $B$ means that $B$ is not easier than $A$. It is not necessary to have a reduction the other way.

For example, for graph coloring. You can reduce 3-coloring to 4-coloring but not in the immediate way. If you take a graph $G$ and you choose $f(G)=G$ then you will have that $x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$ but you don't have $f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$ of course. The conclusion is that the equivalence $(E)$ is not respected, so $f$ is not a reduction.

You can build a correct reduction $f$ from $3\mathsf{COL}$ to $4\mathsf{COL}$ but it is a little more complicated: for any graph $G$, let $f(G)$ be the graph $G$ extended with another node $u$ that is linked with an edge to every other node.

The transformation is complexity-preserving (polynomial, here);
if $G$ is in $3\mathsf{COL}$ then $f(G)$ is in $4\mathsf{COL}$: just use the fourth color for $u$;
if $f(G)$ is in $4\mathsf{COL}$ then you can prove that all the nodes except $u$ have a color that is not $u$'s, hence $G$ is in $3\mathsf{COL}$.

That proves that $f$ is a reduction and that $4\mathsf{COL}$ is harder than $3\mathsf{COL}$. You can prove the same way that $n\mathsf{COL}$ is harder than $m\mathsf{COL}$ for any $n≥m$, the interesting proof being of the fact that $3\mathsf{COL}$ is harder than any $n\mathsf{COL}$.


Compression type that can be searched Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?

Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space.  These are essentially compressed suffix arrays or suffix trees, which have a lot of literature.

Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/select data structures).  There are a range of issues that arise depending on whether one wants simple boolean containment predicates, the offset of each occurrence, or more complicated suffix tree operations; the former can be done in less space and time than the latter.

There's also an entire book about searching and selective decompression of strings: "Compressed Data Structures for Strings: On Searching and Extracting Strings" by Rossano Venturini, published 2014 Springer Science & Business Media.


Approximate Similarity Search I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length)  and I have a query string(P) (or set of strings) that needs to find similar strings former set. My implementation is the following (assuming length is 64 and similarity is defined as hamming distance less than 15)

  Divide each string in T into 16 parts and store each part in a hash table  where key is the hash value and value is a vector
  containing the indices of strings. Ex < 198675, {2, 7, 8, 456}> [I
  have 16 such hash tables for each portion of the string]
  For a query string P, divide it into 16 parts and for each part collect the set of indices(if present) from each hash table and
  then take the union of all. That becomes a small search space.
  Calculate the hamming distance between the query and the resulting set of strings.

I have implemented in C++ and it's working fine, but I am still wondering how could I make it more faster. Any suggestions would be appreciated.

Your method is reasonable.  There are other possibilities as well.

Randomized algorithm: locality-sensitive hashing

Here is a randomized algorithm that finds all matches with high probability (probability $1-\epsilon$ where $\epsilon$ is exponentially small, but not zero).  It will probably be more efficient.

Build 100 tables.  Each table is constructed as follows: Randomly pick a subset of 8 positions (out of the 64 possible positions).  Now a string is hashed by keeping only the 8 characters from those 8 positions, and the string is stored in the hashtable keyed on that hash.  For instance, if the positions associated with a particular table are $i_1,i_2,\dots,i_8$, then the string $S$ is hashed by hashing $S[i_1],S[i_2],\dots,S[i_8]$ and using that hash value as the key to store $S$ in the table.  Each table has a different and randomly generated subset of positions.

Store each of the millions strings in all 100 tables.  When you get a query string $Q$, look it up in each of the 100 tables to find all possible matches, take the union of those possible matches, and calculate the Hamming distance between $Q$ and each possible match.

This is very similar to your method, but each "part" is longer (8 characters instead of 4 characters), so there will probably be many fewer "false matches" from the hashtable.

There is no guarantee that this approach will find all valid matches, but most likely it will.  The probability that a valid match is not found is

$$(1-(49/64)^8)^{100} \approx 0.0000035,$$

so missing a match is unlikely.  You can tune the probability of a missed match by adjusting the number of tables, and you can adjust the parameters ($8,100$) to find the setting that gives you the best possible performance.

This is effectively a form of locality-sensitive hashing (LSH).  There may be other schemes worth investigating.  You could also look at MinHash.

Trie

Another approach is to store the dictionary of millions of strings in a trie data structure.  Given a query string $Q$, you can start traversing the trie, doing a recursive breadth-first search  to explore all paths that are at distance at most 15 from $Q$.  For many paths, you'll be able to immediately terminate the search.


Figuring out whether LL(1) grammar has an $\varepsilon$-free variant This question arose out of a concrete problem I had, which was to find an $\varepsilon$-free variant of the following LL(1) grammar $G_0$ that I developed for a Lisp-like language $L$ (I found a monotone LR(0) variant):

$$
\begin{array} \\
P & \rightarrow & (EP \\
  & | & \varepsilon \\
E & \rightarrow &iE \\
  & | &sE \\
  & | &nE \\
  & | &(EE \\
  & | &)
\end{array}
$$
where the start symbol is $P$. With this grammar, the leftmost derivation of $\omega = (i()sn)(inn)$ is
$$
\begin{array} \\
P & \Rightarrow_L (EP \\
  & \Rightarrow_L (iEP \\
  & \Rightarrow_L (i(EEP \\
  & \Rightarrow_L (i()EP \\
  & \Rightarrow_L (i()sEP \\
  & \Rightarrow_L (i()snEP \\
  & \Rightarrow_L (i()sn)P \\
  & \Rightarrow_L (i()sn)(EP \\
  & \Rightarrow_L (i()sn)(iEP \\
  & \Rightarrow_L (i()sn)(inEP \\
  & \Rightarrow_L (i()sn)(innEP \\
  & \Rightarrow_L (i()sn)(inn)P \\
  & \Rightarrow_L (i()sn)(inn)
\end{array}
$$
My problem is that the parser generated by this grammar accepts the empty string, and I would like to exclude that.
So I am looking for an $\varepsilon$-free LL(1) grammar $G_1$ that generates $L-\{\varepsilon\}$. I have tried several times without success, leading me to doubt whether $L-\{\varepsilon\}$ is simple deterministic.

The solution is to simply start in a slightly different starting state before starting the main recursion:

$$
\begin{array} \\
S & \rightarrow & (EP\\
P & \rightarrow & (EP \\
  & | & \varepsilon \\
E & \rightarrow &iE \\
  & | &sE \\
  & | &nE \\
  & | &(EE \\
  & | &)
\end{array}
$$


Finding a 5-Pointed Star in polynomial time I want to establish that this is part of my homework for a course I am currently taking.  I am looking for some assistance in proceeding, NOT AN ANSWER.

This is the question in question:

  A 5-pointed-star in an undirected graph is a 5-clique. Show that
  5-POINTED-STAR $\in P$, where 5-POINTED-STAR = $\{ <G>$ $: G$ contains a
  5-pointed-star as a subgraph $\}$.

Where a clique is CLIQUE = $\{(G, k) : G$ is an undirected graph $G$ with a $k$-clique $\}$.

Now my problem is that this appears to be solving the CLIQUE problem, determining whether a graph contains a clique with the additional constraint of having to determine that the CLIQUE forms a 5-pointed star.  This seems to involve some geometric calculation based on knowledge of a 5-pointed star.  However, in Michael Sipser's Theory of Computation, pg 268, there is a proof showing that CLIQUE is in $NP$ and on page 270 notes that,

  We have presented examples of languages, such as HAMPATH and CLIQUE,
  that are members of NP but that are not known to be in $P$. [emphasis added]

If CLIQUE is not in $P$, why five pointed star be in $P$?  Is there something I'm not seeing?
Remember, this is a HOMEWORK PROBLEM and A DIRECT ANSWER WOULD NOT BE APPRECIATED.  Thanks!

If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?

If there is a 5-clique, one of this subsets is a clique.

Spoilers below:

   There are ${|V| \choose 5}$ possible subsets to check, that is, at most $|V|^5$ options, which is polynomial in the input. This is NOT the case for an arbitrary $k$, since $|V|^k$ might be exponential in the input, and this is why $\text{CLIQUE} \notin P$ (unless P=NP, agghh.).


Algorithm for graph with nodes grouped into sets I have a weighted graph. The nodes of this graph are grouped into sets, and each node has only one corresponding set (no overlapping). Nodes in the same set do not have edges between them. An edge only connects nodes that are in different sets.

I want to select one node from each set, such that the total weight of the edges between these nodes is minimized. Between two sets, I will only be traversing one edge.

Only some sets are adjacent to each other, they are not all interconnected. But some sets do have multiple neighbours. When one set is adjacent to another, the nodes in these two sets form a complete bipartite graph.

Are there any algorithms to accomplish this? And is there a name for this type of graph?

The special case of zero-one weights is already NP-hard. In fact, even determining whether there is a choice such that the total weight is zero is NP-hard. See this question on cstheory.se. (You can arrange that all the weights are, say, $1$ or $2$, and then the condition that two connected parts are fully connected is satisfied.)


Time complexity of proximity search in distance matrix I am a high school student computationally studying the 3-dimensional structure of chromosomes by 40 kilobase loci. In a nutshell, loci that are close in space tend to express their genes at the same time ― loci are different stops on a 3D-winding DNA chain.

The best way to understand the 3D structure is by gathering what are basically distances between loci.

Now I have an $n\times n$ ($n$ = number of loci studied) matrix where the $(i,j)$ entry is the distance between locus $i$ and locus $j$. I also have a (somewhat miraculous) 3-dimensional of the same chromosome that maps each locus to a certain point in a 3D $(x,y,z)$ coordinate system.

My task is to find all of the loci within a certain radius of locus $L$. With the matrix, I would have to go to $L$ and traverse many nearby locus-distance chains, possibly for a long time, before being any bit certain that I had everything I wanted (i.e. brute force). With the spatial model, I would only have to conduct a simple search within that radius.

Here is my question. What is the complexity of finding nearby loci in the 3D model and the 2D matrix with respect to loci count and radius size (whichever you think is more complex)? (Compare the two complexities and give both.)

I am not very studied in CS, but here is what I guess:

$$C_\text{2D search best-case} = O(n^2)$$
$$C_\text{2D search worst-case} = O(2^n)$$

Best-case is what you'd expect, and worst-case would be going through every permutation of the distance.

$$
C_\text{3D search any case} = O(n)
$$

This is just my rather fallible intuition.

There are a number of candidate techniques you could use.

The simplest is just naive search.  Given a locus $L$, just scan over all $n$ loci and see how close each one is to $L$.  You might measure "close" as Euclidean distance in the 3D coordinate system.  Naive search takes $O(n)$ time, since you have to examine each locus and you do $O(1)$ work for each locus you examine.  In your example, it appears that $n=40,000$, so this might be perfectly efficient, given your miraculous mapping to 3D space.

If you want to do this task many times, you can preprocess the data you have to make subsequent queries faster.  For instance, one candidate is to use the techniques described in the following question: Find all neighbors at a certain distance, in 3 dimensions  Basically, you have the 3D coordinates for each locus, so you store those 3D points in a k-d tree or octree.  Now given the 3D coordinates of a locus $L$, you can quickly scan the tree to find all neighbors that are near $L$ in 3D space.  The asymptotic running time of these algorithms is hard to analyze, but it might be something like $O(\lg n)$ times the number of loci that are close to $L$.

If you didn't have the miraculous map to 3D coordinates, there are alternative approaches that use just the $n \times n$ matrix of edit distances, but they will be slower.  For instance, if you have precomputed the $n\times n$ matrix, then you can use naive search: given a locus $L$, scan over all $n$ loci and see how close each one is to $L$ using the edit distance matrix.  This will take $O(n)$ time, since you have to consider all $n$ loci and it takes $O(1)$ work for each look-up in the matrix.

Unfortunately, precomputing the $n \times n$ matrix of edit distances will probably take $O(n^2)$ time, or maybe even slower.  (Therefore, unless you're going to do many queries, it is not clear that precomputing the matrix of edit distances is worthwhile.)

Anyway, even if you have the precomputed distance matrix, I don't know of any way to use nearest-neighbor search techniques to get the running time below $O(n)$ time.  This is a significant difference from the case where you have the miraculous 3D map: if you have the miraculous map to 3D coordinates, it looks like you can make search much faster.


How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$? I came with this interesting question and could understand how did we get to this equation:
$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$

But in the next step, it reached to the following step which I cannot understand. Please help me out in understanding this:

$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$
Reference: Problem 6.3.3, CLRS. Difficulty understanding the solution of heap problem in CLRS book?

Thank you.

Before starting, let me note that there seems to be an "off by 1" issue with the way that height is measured. It seems that you should replace $h$ throughout with $h+1$.

First of all, let us notice that $2^{\lfloor \lg n \rfloor} \leq 2^{\lg n} \leq n$.
Therefore
$$
(k-1)2^h + k(2^{h-1} + 1) \leq n.
$$
Next, notice that
$$
(k-1)2^h + k(2^{h-1} + 1) = k(2^h + 2^{h-1} + 1) - 2^h.
$$
Therefore
$$
k(2^h + 2^{h-1} + 1) \leq n + 2^h.
$$
This immediately implies that
$$
k \leq \frac{n + 2^h}{2^h + 2^{h-1} + 1} \leq \frac{n + 2^h}{2^h + 2^{h-1}} = \frac{n + 2^h}{(3/2)2^h}.
$$

Now, $h + 1 = \lfloor \lg n \rfloor \le \lg n$, and so $2^{h+1} \leq n$, implying $2^h \leq n/2$. Therefore
$$
k \leq \frac{n+2^h}{(3/2)2^h} \leq \frac{n+n/2}{(3/2)2^h} = \frac{(3/2)n}{(3/2)2^h} = \frac{n}{2^h} \leq \left\lceil \frac{n}{2^h} \right\rceil.
$$


Why is it not a good idea to branch a thread outside of a parallel region while other threads are still executing? Say I have $n$ threads executing in a parallel region and one of them leaves the parallel region when others are still continuing to execute in the parallel region. Why this is a $BAD$ idea? For example you can consider this program.
$OMP PARALLEL IF(EXECUTE==true)

10 sum(id)=next(id)

30 result(id)=sum(id)*9.8
   if(converged(result(id)) goto 20
   go to 10

$SOMP END PARALLEL
   if(not_FINISHED) goto 30

20 print *,id

In this code we are branching out of the parallel region. I have read that its a $BAD$ idea to do so, but I have not got the reason. So it will be very helpful if someone can shed some light on this.

OS functions are called to create and join a thread.
The main thread waits for all created thread to return (join).  When a thread jump out in middle, the main thread will wait infinitely. In the example you have given one of the spawned thread jumps to a location in main thread. It will proceed and the program will eventually end. Any thread can exit/close the program. It may be the case that other spawned threads are in different stages of their execution and since parent (main) thread has exited, they will terminate inflight as well.
A lot of resources allocated to the abruptly terminated threads by OS, will waste. A properly terminated thread releases all the resources allocated to it properly, improperly terminated threads won't.


A way to express LTL (varient) to enforce a stream of data to satisfy some linear time logic Linear Time Logic (LTL) is used for system verification. In my case, I am investing some time, to see the feasibility of using LTL this time to enforce a constraint on a stream of data. Enough of generalities, let's take a simple example:
The operator UNTIL in the expression u Until v in LTL means, event u until v, it is a general formula that an infinite number of signal traces could satisfy. see it's definition here:
page4
like:
u,u,u,v,v,v,...
u,u,u,u,u,u,...
u,v,v,v,v,v,...

In my case, I want to enforce an LTL like formulae to a system receiving a stream of data; Again let's take the same operator Until.
let's say we have two input signals, one for constant u, and one for constant v.
u,u,u,u,u,u,...
 , , , ,v,v,...

The stream processor taking these inputs, if it is an "UNTIL*" node, would output:
u,u,u,u,v,v,...

The reason I differentiate UNTIL with an asterisk is the whole point of the question, "u UNTIL* v" is only true when v is taken as output as soon as it appears in the second stream, it is one single trace satisfying "u UNTIL* v" given our input signals. How to express this constraint ?! LTL seems very general for this "constraint enforcing mechanism".
note: Please bear with me, I am no computer scientist, nor a mathematician, I am an average programmer who tries to learn new things.

This is an interesting question.
It is not directly an LTL (Linear Temporal Logic) question -- rather a question about whether there is an algorithm or tool that takes an input stream and modifies it a somewhat minimal way to satisfy a given LTL property.
Whether that you want can be done or has been done depends on what exactly the allowed modifications to the stream are. In your example, you are, in a sense, remixing two streams. Note that LTL is defined over alphabets in which every character can have multiple propositions that are TRUE at the time. So in your example, you could have just mixed the u and v stream together to obtain:
u,u,u,u,{u,v},{u,v},....

This would have satisfied the LTL formula as well. If the way in which you remix is that the proposition in the output stream is always a subset of the propositions set in the input stream, then you can use reactive synthesis to obtain a transducer that does the stream mixing/fixing. However, this will only work if for every output stream there actually is a way to perform the mix.
If there is some quantitative notion of mixing/fixing, then quantitative synthesis may be a research area that may have some results. But you would need a description of the precise stream modification optimization criterion to see if any of the results from that area are applicable.


Looking for a contex-free grammar for the following language I want to derive a context free grammar for the following language on alphabet $\Sigma=\{a,b\}$:

$\qquad\displaystyle \{ xax'yby'z \mid x,y,z\in\Sigma ^*, |x|=|x'|, |y|=|y'|, |z|=|x|+|y|\}$

I am convinced that this language is context-free because this is part of my proof to a theorem given in textbook, but haven't yet seen a context-free grammar for it.

Hint: you want to measure size of $x$ and $y$, and still have the sum of the two in the end. so when you read them, you will need twice their size: one for $x'$, and one for $z$.
Start with designing a PDA, it seems easier than a grammar.
Then you can use a PDA-to-grammar translation to get the wanted grammar.


Shortest Path on an Undirected Graph? So I thought this (though somewhat basic) question belonged here:

Say I have a graph of size 100 nodes arrayed in a 10x10 pattern (think chessboard). The graph is undirected, and unweighted. Moving through the graph involves moving three spaces forward and one space to either right or left (similar to how a chess knight moves across a board).

Given a fixed beginning node, how would one find the shortest path to any other node on the board?

I imagined that there would only be an edge between nodes that are viable moves. So, given this information, I would want to find the shortest path from a starting node to an ending node.

My initial thought was that each edge is weighted with weight 1. However, the graph is undirected, so Djikstras would not be an ideal fit. Therefore, I decided to do it using an altered form of a depth first search.

However, I couldn't for the life of me visualize how to get the shortest path using the search.

Another thing I tried was putting the graph in tree form with the starting node as the root, and then selecting the shallowest (lowest row number) result that gave me the desired end node... this worked, but was incredibly inefficient, and thus would not work for a larger graph.

Does anyone have any ideas that might point me in the right direction on this one?

Thank you very much.

(I tried to put in a visualization of the graph, but was unable to due to my low reputation)

If the edges in the graph only represent valid moves between certain positions, using Dijkstra's would work just fine. However as the graph is unweighted it would be overkill. A simple breadth-first-search will give the optimal answer.


Prove that a model of infinite tapes is stronger then turing machine model I want to prove that if we have a model, $A$, with unbound number of tapes, then
$A$ is stronger then Turing Machine model. Can you help me with example of such a language that $M$ will fail but $A$ will give an output? thanks.

It is a standard proof that Turing machines with any finite number of tapes are equivalent to single-tape Turing machines, since you can code any fixed number of tapes on a single tape.

If you allow a Turing machine to have an infinite number of tapes, then you can decide any language $L$. To do this, first copy the input $x_1\dots x_\ell$ so that the $i$th tape contains the symbol $x_i$ in its first cell. Now move all the tape heads back to position $1$ and enter some special state $q_\mathrm{decide}$. Recall that the transition function decides what to do based on the state the machine is in at the moment, and what is under each of the infinitely many heads. So just define it to accept from state $q_{\mathrm{decide}}$ if there is some $k$ such that it sees $w_1, \dots, w_k$ under the first $k$ heads and $w_1\dots w_k\in L$, and every other head sees the blank character; otherwise, it rejects.

Note that there is a philosophical problems with write down the transition function if $L$ is undecidable, but the function certainly exists.


How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round? Found this in solutions of a test as being true

If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$.

How does the above scenario apply for multiplying different numbers? Isn't it possible that squaring is a special operation since it is just 1 number? . I would see this making sense.

If you can multiply two n-bit integers in time $O(n \, log \,n)$, then you can square an n-bit integer in time $O(n \,log \,n)$.

Of course, we can suppose we are able to do sum and difference in linear time. Now, if we want to calculate $h\cdot k$, we can find in linear time $a$ and $b$ such that $h=a-b$ and $k=a+b$: take $a=\frac{k+h}{2}$ and $b=\frac{k-h}{2}$. Then $h\cdot k=(a-b)(a+b)=a^2-b^2$, so we only need to square two numbers of at most $n$ digits (if $h$ and $k$ have $n$ digits, then also $\frac{k+h}{2}$ has at most $n$ digits) in $O(n\log(n))$ and take their difference in $O(n)$.
Actually, this works if $h$ and $k$ have the same parity, else $a$ and $b$ are not integers; if it is not the case, then you can write $h\cdot k=h\cdot(k-1)+h$ and proceed as above.


Trying to remove ϵ rules from a formal grammar resulted in L(G) ≠ L(G') I am trying to remove ϵ rules from the following grammar (after applying the remove redundant symbols algorithm): $G = (\{S,A,B,C\},\{0,1\},P,S)$, where the productions are
\begin{align}
&S \to AB \mid C \\
& A \to 0A1 \mid \epsilon \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
The result of applying the remove ϵ rules algorithm is:
\begin{align}
&S \to B \mid C \mid AB \\
&A \to 0A1 \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
but then, when I re-apply the remove redundant symbols algorithm (as I should do) I get:
\begin{align}
&S\to B \mid C \\
&B \to 0B \mid 0 \\
&C \to 0C0 \mid B
\end{align}
(as $A \Rightarrow^*$ will never result in a terminal word)
The problem is, that $010$ is generated by the original grammar but not by the latter grammar.
in fact, not a single word that contains 1 in it belongs to the latter grammar, as 1 could only have been achieved via $A$!
What have I done wrong? Why are the two grammars producing different languages? They are supposed to be the same.

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately.
How does the $\epsilon$-removal work? Suppose that we want to remove the production $A \to \epsilon$. How can this production be used in a derivation? Whenever $A$ appears on the right-hand side of a production, we can remove it by applying $A\to\epsilon$. Hence, in order to get rid of the production $A\to\epsilon$, we simply replace each production $X \to \alpha$ by all possible productions obtained by removing occurrences of $A$ in $\alpha$. (This may result in productions of the form $X \to \epsilon$, which we need to handle separately.)
In your case, this means that we need to augment the production $A \to 0A1$ with the production $A \to 01$ obtained by erasing $A$ on the right-hand side.
What is a good way of finding such bugs? You describe three grammars: the original one, the one obtained after removing $\epsilon$ productions, and the final one obtained by removing redundant symbols. The first one generates $010$, the last one doesn't. The first step is to check which of the two transformations introduced the mistake, and you can do that by checking whether the second grammar generates $010$.
It turns out that the second grammar doesn't generate $010$. In order to understand what went wrong, you can take a derivation of $010$ in the first grammar, and see why it cannot be reproduced in the second grammar. One such derivation is $S \to AB \to 0A1B \to 0A10 \to 010$. In the second grammar, all but the last steps are still available, so the problem lies with the production $A \to \epsilon$, which the second grammar isn't able to simulate.


What is your approach to unveil the boundary cases when designing an algorithm? When designing an algorithm for a given problem, sometimes I find it hard to foresee or clarify to myself what the boundary/edge/corner cases are. Not being able to come up with a decent number of the possible boundary/edge/corner cases causes one to make implicit assumptions about the problem at hand, which yields overlooked cases not to be accounted for, which is not good.

When reviewing the classic "Programming Challenges" by Steven S. Skiena and Miguel Revilla, one can read the following:

  This is why it is so essential to review the specifications carefully. Even when you may be sure that your program is correct, the judge may keep saying no. Perhaps you are overlooking a boundary case or assuming something which just ain’t so. Resubmitting the program without change does you absolutely no good. Read the problem again to make sure it says what you thought it did.

I think it would be useful to sort come up with a method to, given a problem statement and the problem's input domain, assist the algorithm designer with unveiling boundary cases.

On one hand, knowing the upper and lower boundaries of your input data, helps you choose data types that can represent said values.

Another useful technique I do, is to ask myself, per each explicit assumption I can extract from the problem specification, what must exist for that assumption to be valid? For example, if I am told that all values will be given as a sorted array, does that mean that the given list will never be empty?

I would like to continue putting together a set of thumb rules to assist ourselves in uncovering boundary cases.

A good answer for this is over at Software Engineering https://softwareengineering.stackexchange.com/questions/72761/how-do-you-identify-edge-cases-on-algorithms

In general look at zero, empty string, max values, odd/even, nulls, sorted/random data where applicable including repeated testing with random data.

Also "think of everything that can go wrong" https://www.quora.com/How-do-you-identify-edge-cases-on-algorithms.


Algorithm for finding strongest connection for a user on social network I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:

Problem 6-1. [30 points] I Can Haz Moar Frendz?

Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a burgeoning social network
website. She needs to implement a new friend suggestion feature. For two friends u and v (friendship is undirected), the EdgeRank ER(u, v) can be computed in constant time based on the interest
u shows in v (for example, how frequently u views v’s profile or comments on v’s wall). Assume
that EdgeRank is directional and asymmetric, and that its value falls in the range (0, 1). A user
u is connected to a user v if they are connected through some mutual friends, i.e., $u = u_0$ has a
friend $u_1$, who has a friend $u_2$, . . . , who has a friend $u_k = v$. The integer k is the vagueness of the
connection. Define the strength of such a connection to be
$$S(p) = \prod_{i=1}^kER(u_{i−1}, u_i)$$
For a given user s, Alyssa wants to have a way to rank potential friend suggestions according to
the strength of the connections s has with them. In addition, the vagueness of those connections
should not be more than k, a value Alyssa will decide later.

Help Alyssa by designing an algorithm that computes the strength of the strongest connection
between a given user s and every other user v to whom s is connected with vagueness at most
k, in O(kE + V) time (i.e., for every pair of s and v for v ∈ V\{s}, compute the strength of the
strongest connection between them with vagueness at most k). Assume that the network has |V|
users and |E| friend pairs. Analyze the running time of your algorithm. For partial credit, give a
slower but correct algorithm. You can describe your algorithm in words, pseudocode or both.

After reading the problem, the first intuition I got is to:

Do a BFS from the source node s and stop the BFS as soon as kth level is reached.
And, while doing the BFS, calculate and maintain the strength that each node encountered has with s
At the end, when the BFS stops after the k levels, we iterate the strengths stored, and find the one with maximum value.

Here is the (pseudo/Python)code for the same:
def find_strongest_connection(graph, source_node, k):
    nodes_discovered = deque()

    # source is already discovered
    strengths = {source_node: 1}
    parents, levels = {source_node: None}, {source_node: 0}
    nodes_discovered.append(source_node)

    while nodes_discovered:
        parent_node = nodes_discovered.popleft()

        current_level = levels[parent_node] + 1
        if current_level > k:
            break

        for current_node in graph.adj[parent_node]:
            if current_node not in levels:
                # current_node is now discovered
                strengths[current_node] = strengths[parent_node] * ER(parent_node, current_node)
                parents[current_node], levels[current_node] = parent_node, current_level
                nodes_discovered.append(current_node)

    strongest_connection, max_strength = None, -1
    for connection, strength in strengths.items():
        if strength > max_strength:
            max_strength = strength
            strongest_connection = connection

    return strongest_connection, max_strength

To me, this solution looks correct. But when I was going through the solutions provided by MIT for the problem set, I see they are first transforming the graph, and then applying the Bellman-Ford's algorithm. What I want to know is that am I missing something really basic in my understanding of the problem and the algorithm that I have come up with?
I am asking this because seeing the complex solution provided in the solution set is making me doubt my overly simple solution. Unfortunately, I cannot think of a case, where my solution would fail. If there is any issue with my algorithm, any hint would be much much appreciated.
PS: I am not a student looking for an answer to my homework. I am a full time working professional.

Your algorithm doesn't work.  BFS doesn't explore all paths.  One of the paths you haven't explored might have much higher strength than all the ones you have explored.  There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview).  I'll let you have the fun of finding it.


Simple regular expression problem new to automata theory and this is quite difficult for me so I'd appreciate a hint in the right direction if possible.

We want to find a regular expression for the language $L$ over $\Sigma = {a,b,c}$ where $L$ is the language of all strings of even length, contain $a$ at least once, and after the final $a$ letter there are no $b$s.

for example - $bcbabaca$ is a valid word.

Best thing I could come up with is somewhat akin to $R = ((a+b+c)(a+b+c))^*a((a+b+c)(a+b+c))^*$ and it has to be something like that since we need to control the length of the word to make it even, but still its no good and im having difficulties.

You're almost there.

$((a+b+c)(a+b+c))^∗$ gives you strings of even length.

$((a+b+c)(a+b+c))^∗a$ gives you strings of even length plus an $a$.  That is, odd-length strings that contain at least one $a$ and end with an $a$.

Now, we're told that there are no $b$s after the last $a$. And there are certainly no $a$s after the last $a$, because that's what "last" means! So there can only be $c$s after the last $a$.

So, the answer is going to have to look something like $((a+b+c)(a+b+c))^∗ac^*$. That's not quite right, because it doesn't force the whole string to be even-length and it does force the last $a$ to be in an odd-numbered position in the string (whereas, hint, it should be able to be even or odd).

I'm going to stop there because you showed enough in the question that I think you can finish this yourself, now.


$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable? I have known that:

  A function $\Bbb N → \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.

Now I am considering about the partial functions. Is it the fact that:

  A partial function $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive if and only if its graph is a recursively enumerable subset of $\Bbb N^2$.

If it is true (or one direction is true), may I please ask for a proof? Or some reference would be also appreciate (I searched it but did not obtain any useful result).

Note: It is from a math course (and I have asked in the math site). And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine and I have no skill of coding). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please?
Thanks!

I have done some search but I cannot find some helpful material. Any reference would be appreciate to. Thanks a lot.

A $k$-ary relation $R \subseteq \mathbb{N}^k$ is recursively enumerable if its indicator function $f_R$ defined by

$$f_R(n_1,\ldots,n_k) = \begin{cases} 1 & \text{if } R(n_1,\ldots,n_k) \\
0 & \text{otherwise} \end{cases}$$

is a partial recursive function.

So if $f: \mathbb{N} \rightarrow \mathbb{N}$ is a partial recursive function, it is easy to see that the graph

$$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set. We have $f_{R_f}(m,n) = 1 - \mathrm{sg}(f(m) - n)$, where $\mathrm{sg}(n)$ is the primitive recursive function that is $0$ for $n=0$ and $1$ otherwise. Since we can express the indicator function $I_{R_f}$ of the graph as the composition of partial recursive functions, we therefore conclude that it is also a partical recursive function.

Conversely, if $$R_f = \{ (m,n) \mid f(m) = n \}$$

is a recursively enumerable set with indicator function $I_{R_f}$, then

$$f(m) = \mu n. [ (1 - I_{R_f}(m,n)) = 0 ] $$

Here $\mu n.P(n)$ denotes unbounded mineralization over the unary predicate $P(n)$.


How to write a regular expression to match a string that starts with the same pattern that it ends with Let's say we want to write a regular expression that matches a string that ends with the same pattern that it begins with.

Let's say that we have an alphabet composed of the binary symbols: {0,1}

We should make a regular expression to create a language that is composed of words (W) with the following pattern:

W=w1w2w1 and w1 and w2 are words from the closure of the {0,1} alphabet.

I do not know how to approach this task. I am not convinced it is even possible because there is no way we can memorize anything inside a regex.

The only operators that we should use are the following three:
-Concatenation
-Star (closure)
-OR

Since you asked how to approach it, a good starting point for these sorts of problems is to start by understanding the language.  Try writing down all words in the language of length 1; all words of length 2; all words of length 3; all words of length 4; and see if you can spot any possible patterns (about which words are in the language and which aren't).  Then, see if you can prove your guess.

Finally, use that to help you brainstorm ideas for how to express this as a regular expression.

Make sure to read How to prove a language is regular? carefully.


Efficient algorithm to map two differently-sized sets of numbers as closely as possible? The problem

I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped if they are farther apart then 0.18. As many numbers should get mapped as possible.

Also, the sets are not necessarily the same size. So, consequently, some numbers of the larger set won't get any mapping.

Example:

Is there a reasonably efficient algorithm that finds a mapping like this? Or, is there a term for this specific problem so that I can research algorithms on my own?

My research

Through googling I encountered this question, which led me to the term "Euclidean Bipartite Matching Problem" which seems to be the term for a problem very similar to mine. However, my problem is slightly different than the Euclidean Bipartite Matching Problem.

So basically, I'm looking for an efficient algorithm for the 1-dimensional Euclidean Bipartite Matching Problem except that the two sets of numbers can be of differing size, and the distance between two numbers must not exceed 0.18.

My attempt

I've already coded my own implementation, however... it doesn't work properly and is pretty complicated too so that I'm not even sure why it doesn't work.

As for the basic idea behind my implementation: let's call the first set the red numbers and the second set the blue numbers (apparently that's the terminology used in the Euclidean Bipartite Matching Problem). Now;

go through all red numbers, and for each:

find the closest blue number within a ±0.18 range
if the blue number is already assigned to a different red number:

if the existing assigned red number is nearer than our red number, skip this blue number

assign our red number to the blue number
if we overwrote a previously-assigned red number in the process, make the red number find itself a new blue number (i.e. make the red number go through steps 1-4 again)

(I'm doubtful that this implementation is even correct) but yeah, this is what I tried so far.

Are there well-known algorithms to do this task, so that I don't have to create a wonky, non-functioning, slow implementation myself? Or in general, is there a term for this specific problem? Then I could google for that term and find what I need.

I'll be happy about any answer or pointers :)

This can be solved by reduction to the unbalanced assignment problem.

Build a bipartite graph where the vertices are the two sets of numbers, and there is an edge from a vertex in one set to a vertex in the other set if and only if the distance between the numbers is less than or equal to 0.18. Set the weight of each edge to the distance between the two numbers.

The goal is to find a minimum-weight maximum bipartite matching in this graph. Some minimum-weight bipartite matching implementations will do this directly.

If you only have access to an implementation that requires a fixed output matching size, you can still solve this by adding extra edges with arbitrarily huge weights (any value larger than 0.18 times the size of the smaller vertex set) to make a complete bipartite graph. Then throw out any mappings in the output that have the arbitrarily huge weights. This works because the minimum weight guarantee ensures that as few as possible of the edges with arbitrarily huge weights will be chosen in the output assignment.


Analyzing programs with multiple for-loops If they were all linked to make a condition such as ($1 < i < j < k < n$), I know how to solve, but the last loop is disconnected so I have no clue on how to do these...

the ones like

for(i = 1 to n);
   for(j = i to n);
      x++;

I can use $1 \leq i \leq j \leq n$ and use $x_1 + x_2 + x_3 = n-1$ and find out the general solution which is $\frac{n(n+1)}{2}$. But disconnected loops I have no idea. Consider the following for loops.

    for(i = 1 to n);
       for(j = i to n);
          for(k = 1 to i*n);
              x++; (constant time)

    for(i = 1 to n-1);
        for(j = i+1 to n);
            for(k = 1 to j);
                x++; (constant time)

I need to find the general solution.

From your comments, it seems that you are incorrectly calculating the number of loops. And since I do not where to start from for you, I will start from a basic level - please ignore whatever you know or find obvious. I am also going to assume that the semi-colons after each for loop are not present - otherwise in many programming languages, the variable x will be incremented only twice, once after each apparently nested loops.

Counting how many times each loop executes can be written as a discrete summation. For example, a simple for loop from $1$ to $n$, where $1$ operation takes place, can be seen as $\sum\limits_{i = 1}^{n}1 = n$. That is, the loop will execute $n$ times (or the increment statement will be executed $n$ times). Nested loops can be counted as nested summations. When evaluating any summation, consider the iterating variable as the variable, and treat everything else as a constant.

Consider the first set of nested loops. The number of executions/number of times x is incremented can be written as:
$$T_1(n) = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1$$
Notice the upper and lower limits on each summation, and compare with your loop variables and ranges. We start evaluation from the innermost loop as follows:
$$\begin{align*}
T_1(n) & = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1 = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}in \\
&= \sum\limits_{i = 1}^{n}\left(in \sum\limits_{j = i}^{n}1\right)  \ \ \ \ \ \ \text{(considering $j$ as the only variable)} \\
&= \sum\limits_{i = 1}^{n} \left(in(n - i + 1) \right) = \sum\limits_{i = 1}^{n}((n^2 + n)i - ni^2) \\
&= \sum\limits_{i = 1}^{n}\left((n^2 + n)i\right) - \sum\limits_{i = 1}^{n}\left(ni^2\right) \\
&= (n^2 + n)\sum\limits_{i = 1}^{n}i - n\sum\limits_{i = 1}^{n}i^2 \\
&= n(n+1)\cdot \frac{n(n+1)}{2} - n \cdot \frac{n(n+1)(2n+1)}{6} \\
&= \frac{n^2(n+1)(n+2)}{6}
\end{align*}
$$

You can verify that if x is initially 0, this will be its value after the first set of nested loops. For the second set, I will provide the the summation and answer, leaving the actual work up to you.

$$T_2(n) = \sum\limits_{i = 1}^{n-1}\sum\limits_{j = i+1}^{n}\sum\limits_{k = 1}^{j}1 = \frac{n(n-1)(n+1)}{3}$$

As others have pointed out, since the two blocks of nested loops are serial, you can just add the number of times each has executed to get the final count as $T(n) = T_1(n) + T_2(n)$. This will give you the number of times x has been incremented. This simple mechanical process should help you out in most instances of nested loops.


What is the time complexity of calling successor $n$ times during tree traversal? According to some sources, the time complexity of finding the successor of a node in a tree is $O(h)$. So, if the tree is well balanced, the height $h=\log n$, and the successor function takes time $O(\log n)$.
Yet, according to this stackoverflow post on the time complexity of an inorder traversal of a binary search tree, if you call the successor function $n$ times, the time complexity is $O(n)$.

What resolves the apparent contradiction between:

  If I call the sucessor function once, the time complexity is $O(h)$, which could be $O(n)$ or $O(\log n)$, depending on the kind of tree.

AND

  If I call the successor $n$ times, the time complexity is $O(n)$ in a balanced tree.

Shouldn't tree traversal take $O(n^2)$ or $O(n\log n)$ time?

Gist: The time complexity of calling the sucessor function multiple times is not merely the product of the number of calls and the worst-case bound, though that product does encompass the worst case. Rather, if the function going to be called from every node, a more sophisticated analysis can establish a tighter worst-case bound for specific trees and implementations of the successor function.

At best, tree traversal takes at $O(n)$ time: $n-1$ calls are made to the successor function, which takes constant time. One simple example of this is the traversal of a linked list, which has a successor function that immediately returns a pointer to the next node with no additional computation.

The worst "reasonable" tree traversal would take $O(n^2)$ time: $n-1$ calls are made to the successor function, which searches all $n$ nodes before determining the successor. For example, if we have an unsorted tree and the successor is defined to be the next largest element (rather than based on its position in the tree). Of course, we could sort the tree first in time $O(n\log n)$ and in general, if we expect to call the successor function $n$ times, it would be wise to preprocess the tree so that it can be traversed in one of the three canonical ways: inorder, preorder, or postorder.

Ok, time to clear a misconception! Let's ask what's the best-case and worst-case scenarios for the successor function are when we have an inorder traversal of a binary search tree:

Remember that in inorder traversal, the left subtree is visited, then the parent node, then the right subtree. So an inorder traversal on the above tree gives us $[A,B,C,D,E,F,G,H,I]$.
(For contrast, preorder traversal would have given us $[F,B,A,D,C,E,G,I,H]$). We start at the beginning of the tree at $A$. From $A$, the successor function checks to see that it has no right subtree (it doesn't) before finding its closest ancestor for which it is the descendant of the left child. But wait! I didn't tell you that each node had knowledge of its ancestors, so we potentially have to search the entire tree just to determine where $A$ is! So now we split into two cases:

Worst-case: Assuming that our node has no right subtree, if the tree was a binary search tree, we could find the node in $O(\log n)$ time. But worst-case, it's not a binary search tree; in fact, it has no structure, so every call takes $O(n)$ time, but if we're consistent about how we search, the total number of steps to find the node's successor is at least $\sum_{x=1}^{n}x=\frac{(n)(n+1)}{2}=O(n^2)$.
Best-case: Each node has a link to its ancestor, so from $A$ to $B$ takes two steps (check for right subtree; back up to ancestor for which it is the left child). The successor function that takes the most steps is from $E$ to $F$, for which $E$ first checks that it has no right subtree, then checks to see if it is the left child of $D$ (it isn't), or the descendent of the left child of $B$ (it isn't), and finally if it is the descendent of the left child of $F$ (it is). That took $O(h)=O(\log n)$ steps, but most calls to the function won't take that many steps. Quoting the SO post, "observe that each edge in the tree gets visited at most twice (once from parent to child and once from child to the parent)" so the total number of nodes visited is $2n$ and hence $O(n)$ worst-case bound.

Another way to appreciate that the average call to successor is $<\log(n)$ is to consider a balanced tree with $n$ nodes and roughly $n/2$ leaves. Half of all successor function calls will be to an ancestor, half of which are from the left child ($\frac{1}{4}n$) and thus takes only one generation/step, $\frac{1}{8}n$ go back two generations, $\frac{1}{16}n$ go back three. Hopefully you see the pattern: $\sum_{i=1}\frac{i}{2^{i+1}}$ converges to $1$. And the other half does the step-analogous $\min$ function (searching it's right subtree for the leftest child), so it also converges to $1$. The expected time is thus $2$ (if I've done my math carefully). So that's $n-1$ calls to a successor function that on average takes ~$2$ steps $\rightarrow O(n)$ time.


Counting solutions to system of linear equations modulo prime I have implemented Gaussian elimination for solving system of linear equations in the field of modulo prime remainders. If there is a pivot equal to zero I assume the system has no solution but how to calculate number of solutions of such systems when all pivots are non-zero? (i.e. one and more solutions)

The integers modulo a prime form a field, so all assumptions done applying Gaussian eliminations work exactly the same. Luckily, there are no numerical instability problems. The system can be inconsistent (no solutions), underdetermined (several solutions modulo $p$) or have a unique solution modulo $p$.


Context-free and context-sensitive grammars in FSM with counters Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them counter automata. Before execution, each counter $c\in C$ is set to zero. Every transition, aside from reading a character (possibly $\epsilon$), performs a counter operation – it either increments or decrements some counter $c$ by one ($c{+}{+}$ and $c{-}{-}$, respectively). Decrementation of a counter is forbidden if the counter is set to zero. Acceptation is done by accepting states, regardless of counter values.
Alphabet is of finite size.

Is every context-free language accepted by a counter automaton?
Is every language accepted by counter automata a context-sensitive one?

Please note that counter automata differ from counter machines (at least I can't prove that they're equal). The counters mustn't go below zero and there's basically only JUMP NOT ZERO operation available, aside from INCREMENT and DECREMENT.

I think that we can simulate a finite stack using a finite number of counters. We'd remember both the top and the bottom of the stack in states, and counter values would represent symbols on stack. Unfortunately, this stack would have fixed size. I don't know how to continue.

These counter automata have power incomparable to pushdown automata. In particular they are strictly weaker than counter machines as they have no proper zero test (if zero then .. else ..).
Technically they are known as partially blind multicounter. Blind as they cannot act on zero, partially as they store only nonnegative numbers, and block when a counter is less than zero.
As a language accepting device they are equivalent to Petri nets.
They have been studied for instance by Greibach.


How to find longest recurring pattern from lage string data set? I need to find the substring that is from a 100,000 characters this substring must be most repeated and it need to be longest substring for example

TYUFRIETEYM0SQZLHBCTN0W1KA9HELAT4LTQ14W7ZW484GSK1XTNOBJ2R6AMGW9KU36G7ITMPF315Y7ESYPR1XE2C1953J0DXUNBJLNTDG7IHS63854SGSS7YDEFJYSFP0DLL54GK6NUZ5UU5FRIETEYCPNGHIJOX23QOVSCBYHKE7HRIETEYV0H49I5SX9CW967CDGKX3TYCVNVBNCFGGDGDGDDFIIPGDSDVGDDSRGDGVCZAQRIOPKLMVFGCDGDTYGSDCBGDUSLVAQEFCGDGRIETEYDGDFG

In above character set there is two substring one is GD and other is RIETEY algorithm able to identify RIETEY because it is longest the substring, also pattern must occur at least twice to be considered a recurrence and patterns will not overlap.

I found a algorithm but it only work for less that 100,000 characters

any suggestion for this problem  ?

This problem is well-studied; it's aptly called longest repeated substring problem.

It can be solved in linear time by creating a suffix tree with Ukkonen's algorithm; the longest repeat corresponds to the labelling of the longest path from the root to an inner node which you find using breadth-first search.

This does not exclude overlapping substrings. Keep track of the smallest $m$ and largest $M$ starting index of sequences nodes represent while creating the tree; a node at depth $n$ (counted in symbols on the path) represents a non-overlapping repeat if and only if $M - m \geq n$.


How to design a top-1 select algorithm to maximize a variable and minimize other variable? I want to implement an algorithm thats select the best group, which maximize the variable A and minimize the variable B.

For instance, I have the following groups:

G1 - A = 10 B = 2

G2 - A = 10 B = 3

G3 - A = 12 B = 1

G4 - A = 10 B = 4

and so on...

One solution could be the sorting the groups by A and resolve ties by selecting the B, but this is not the case here.. it is a tradeoff. I need to select a group with a good tradeoff.
How can I do this tradeoff? any suggestion?

This question is not answerable.  Only you can tell us what counts as a good tradeoff, for you.  You need to pick a single objective function that combines A and B into a single quantity.  We can't tell you how to do that, because that will depend on what makes sense for your particular application domain.

For instance, maybe it's best to choose the item with the highest value of $A/B$.  Or maybe it's best to choose the item with highest value of $A-B$.  Or maybe its' best to choose the item with highest value of $100A-B$, or $A-100B$, or $A + 1/B$, or $100A + 1/B$.  We can't tell you.  You will need to analyze your application to determine what the right objective function is.  Take a look at your specific application and understand what is a measure of benefit or cost that is meaningful in your application domain, and then figure out how that depends on $A$ and $B$ ... and use that as the objective function to maximize.


How do I represent this regular expression in regular grammar? Question: Is the regular expression and regular grammar equivalent?
I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its equivalent grammar. So I am also asking for some help or tips to convert regular expression to regular grammar.
*Key
() -> empty string*
Regular Expression :
a* (ba (cf* (g (f + j)* b f*)*  e)* a)*
Regular Grammar:
S-> aS| ()
F-> f F| ()
Q-> fQ | jQ | ()
G -> gQB|()
C-> cFGE| ()
E-> eC
M -> baCA|()
A -> aM
LM = {L1 | L1= SM }

They are equivalent in the sense that every language that can be represented with a regular expression, can be represented with a regular grammar; and vice versa.
Also, you can convert any regular grammar to a regular expression that generates the same language, and vice versa.


Can all types of computational problems be modeled as decision problems? Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision problems that if you solve those problems you get the result of the original problem?

colloquially: can all types of questions you can ask a string be answered by (a series of) results from YES NO questions? So the game is: you are given a question about a string, you are allowed to ask the string only YES NO questions. The string responds with answers to your YES NO questions that are computable. Can you compose all the answers you receive to narrow in on THE SINGLE answer to the original question (not a spread of answers / not some result but with a probability attached)?

Decision problems can be modeled as word to language membership. On the surface, this only models the functions that go from f:{0,1} * -->1 not all the other types of functions. Some g: {0,1} * -->{0,1} * for example. But I have a feeling the answer could be yes...

Yes.  Every computation problem can be viewed as computing a function $f:\{0,1\}^ \to \{0,1\}^*$: on input $x$, the algorithm outputs $f(x)$.

Here is a corresponding decision problem: given $x$ and $i$, determine whether the $i$th bit of $f(x)$ is 1.  If you can solve that decision problem, you can solve the original computation problem.

(Strictly speaking, you also need a way to decide whether the length of $f(x)$ is $i$; that can be addressed by defining the decision problem as taking inputs $x,i,b$; if $b=0$, then the problem is to determine whether the $i$th bit of $f(x)$ is 1; if $b=1$, the problem is to determine whether the length of $f(x)$ is $i$.)


Can x86 Instruction Set be changed with microcode update? How I understand microcode translate an instruction to microinstructions. And CPU has a unit that stores all possible of microinstructions. These microinstructions can be changed, because it load every time after boot from motherboard. Can instruction set be changed?
I am sorry if i ask strange question, if I misunderstood , please correct , thanks
and again I am sorry if my English grammar is bad. (google translate)

That depends completely on the CPU. Some CPUs don't use microcode at all. Some CPUs use a mixture of hardcoded instructions and microcoded instructions. This mixture can be anywhere between almost all hardcoded and only a few microcoded instructions to almost all microcoded and only a few hardcoded instructions.
For CPUs that have microcode, the microcode could be either modifiable or not modifiable.
If all instructions are microcoded (there are no hardcoded instructions) and the microcode is stored and loaded in such a way that you can load a different one at will, then it would theoretically be possible to load microcode that implements a completely different instruction set.
However, the feasibility of that still depends on the internal design of the CPU. An extreme example would be the Transmeta Crusoe and Efficeon CPUs. These were 128 bit VLIW designs internally, and in order to execute x86 code, they had a software layer called Code Morphing Software, which was essentially an interpreter and JIT compiler from x86 to the internal VLIW code. The Code Morphing Software was running entirely in the standard RAM. This makes it sound like it should have been very easy to just load a different version of the Code Morphing Software and turn the CPU into an ARM or PowerPC or SPARC or MIPS CPU, right?
Well, not according to Linus Torvalds, who worked for Transmeta at the time. He was asked this exact question, and his answer was that the internals of the CPU are so specifically optimized for interpreting x86 code that writing a CMS implementation for, say, MIPS would be no different (and no more performant) than simply writing a MIPS emulator for x86 … which already exist anyway.
On the other hand, the CPUs of the Xerox Alto, Dandelion, Dolphin, and Dorado workstations were explicitly designed to be microcoded for different use cases. They would run completely different microcode depending on whether they were running Interlisp, Smalltalk, or the Star system. For example, the Smalltalk system implemented the most important instructions of their VM in microcode, so that in some sense, the CPU could directly execute (parts of) Smalltalk byte code. You could say that when running the Smalltalk system, Smalltalk byte code was the ISA!


use of unconditional transfer of control instruction I did not understand why unconditional transfer of control instruction is used in cpu.So if we already know we have to jump to an instruction and skip  some instruction irrespective of any condition then why do we not avoid writing those instruction as they will not be executed and replace them with instruction that will be executed after jump instruction

To implement if-then-else, when you get to the end of the "then" branch, you need to jump unconditionally past the "else" branch. The breaks in a C switch statement are also unconditional jumps.

You could probably also implement tail recursion by replacing "call" instructions with jumps.


Find shortest path of R,G,B Graph Let $G=(V,E)$ be a directed graph, $ω:E→\mathbb{R}$ a weight function, and $s,t\in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Each edge has the color R or G or B. Find the shortest path under the condition:

we can use green edge after using at least one red edge
we can use blue edge after using at least one red edge and at least one green edge.

The shortest path do not have to be colorful.

Let's look at the form of the allowed paths. As a regular expression, it looks like:

$$r^*\ |\ r(r|g)^*\ |\ rr^*g(r|g|b)^*$$

We can test the three cases separately and then choose the shortest path found among the three cases.

The first case is easy: just remove all the green and blue edges and then find the shortest path from $s$ to $t$ as normal. Of course, there may not be a path from $s$ to $t$ in this red-only subgraph; if this happens, we can say the distance for this case is $\infty$.

For the second case, start with the original graph and remove all the blue edges, leaving only red and green edges. Then add a new vertex $s^\prime$, which has a directed edge to each vertex $v$ exactly when there is a red edge from $s$ to $v$ in the original graph. Then check for the shortest path from $s^\prime$ to $t$ in this modified graph; this corresponds exactly to the shortest path from $s$ to $t$ in the original graph that has the form $r(r|g)^*$. Again, if no such path exists, we can return $\infty$ from this case.

See if you can figure out the third case now.

I have asked and answered a more general form of this question here.


why swap function is use in union find algorithm? How rank or size array is used for optimization void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

Q1.why we need this swapping?
can't we do like this without swapping

if (size[a] < size[b])

        parent[a] = b;
        size[b] += size[a];

Q2.what is the difference between size array and rank array.Is Rank means the height of a node and size means no of node in that tree which contains this node

To answer your first question, it is a matter of style. If you do it your way, then the code appears twice. Code duplication is more prone to bugs, since you have to duplicate every change that you make, taking care (in this case) to switch $a$ and $b$.


Check if a binary tree is a perfect tree I'm trying to write an algorithm to check if a given binary tree is a perfect binary tree, and of course with the lowest complexity.

I was thinking to calculate the height of the tree $h$ and the number of the nodes $n$, then if $2^{h+1} -1 = n$, it's a perfect tree.
But then again, it's not very efficient.

The I thought to find the minimum tree height, and maximum tree height, and if they are equal, it's a perfect tree.
But also this case, isn't much of improvement.

Any idea how to make it better?

Assuming you are given the root and nothing else, this problem has a lower bound of $\Omega(n)$.

An informal proof:

Consider an adversary who creates a perfect tree of height $h$ and size $n$. Now this adversary also has one extra node whose parent has yet to be determined.

The adversary, being sneaky, doesn't determine the parent of this node until you've checked every other node in the tree. To be more precise, the parent of this extra node will be the very last leaf node you check.

Clearly this will take $\Omega(n)$ time for any algorithm to determine this adversary has an imperfect tree.

That being said, you could find algorithms with a better expected time. For example, you could try non-deterministic algorithms such as random walks of the tree, then compare the lengths of these random walks to give a probability of perfectness. Although in any case, you won't do better than $O(n)$.


Is function `number of TM which terminates on an empty word` computable? Let f: N → N be a function where f(n) = number of Turing Machines over input alphabet {0, 1}, states: {0, 1, ..., n} and work alphabet {_ (blank), 0, 1, ... n} which terminates on a empty word.
Is f computable?

Let's call a TM which solves this problem K.
It feels like this problem is uncomputable. If we can't even determine if particular TM halts on an empty word (Halting problem reducing to the blank tape halting problem), then intuitively finding number of TMs with this property should be even harder. But I can't think of any reduction since this problem doesn't utilize any particular TM in input, its input is just a number (in the question I linked above - BLANKHALT, TM takes a machine as an input so we can provide a specific machine - anything we want - for example machine from instance of the HALT problem, but this is not a case in this problem).
At first I wanted to reduce BLANKHALT problem: I wanted to measure its number of states, alphabet, run the K TM with number of states BLANKHALT instance has and while counting the number of TMs which terminated on empty word, check if this is BLANKHALT machine I have just asked for. BUT I cannot do this, since I cannot assume K even enumerates the TMs, right? If K existed, it might have a magical way to solve the question, without checking all possible TMs one-by-one, right?

Is that proof correct?

Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size.

This TM works as following:

Using blackbox for f, calculate f(n)
Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n}
Simulate each machine on empty input BUT we don't check TM machine one by one. We check TMs STEP BY STEP. That means for each TM we make its one step.
When TM terminates, add 1 to counter
When counter reaches f(n), then we know which machines terminates and which don't. We have solved halting problem. Contradiction

The key is we  don't simulate TM machines one by one, but step by step, thus we don't get looped and we always terminate.


Approximating the runtime of a practice problem I'm studying for an algorithms exam and came upon the problem :

    for (i = 0; i < n * n; i++) {
        i++;
        for (j = 0; j < (log(n) * log(n) * log(n)); j++) {
            j++;
        }
    }

I figure that line 1 costs $ c_1(n^2) $, line 2 costs $ c_2(n^2 - 1) $, line 3 costs $ \sum_{j=0}^{n^2} \log(j)^3 $, and line 4 costs $\sum_{j=0}^{n^2} \log(j)^3 - 1 $. Am I on the right track? If so, what do the summations get simplified to?

Those lines with the increments matters for the final complexity function, but do not take them in count as it will only make things messy. The function can be simplified as follow:

The outer for runs $\frac{n^2}{2}$ times, and for each of it's iterations it runs $\frac{log^3{n}}{2}$ times.

We can call the complexity function $T(n) = \frac{n^2}{2} * log^3{n}$ which leads to $O(n^2 log^3{n})$.


Crafting a Context Free Grammar I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem earlier where I was to construct a CFG of $a^ib^jc^k$ with $i \ne j$ OR $j \ne k$. Obviously I separated the problem into two parts, $i$ not being $j$ and the other part being $j$ not being $k$. Taking the left part into account I wrote out the  following:

$$\begin{align*}
S &\to aSbTc \mid aS \mid bT \\
T &\to bTc \mid bc \\
D &\to cD
\end{align*}$$
Am I correct in this for $i$ not being $j$ or is there something in my head thats wrong in thinking through this?

The rules like "onions" with various layers that you describe in your question can be thought of as a build order for how you will construct a string -- eg. "first I will build this part of the string, and then I will build this other part" or "I need to build these two parts at the same time in order to ensure that they are synchronized".

A good general strategy for constructing a context free grammar is to
determine this build order and then have a production rule that
represents each stage and/or each possibility of your build order.
You should be able to point to each nonterminal and explain the "meaning"
or type of string that nonterminal is trying to construct.

For the example of $a^ib^jc^k$ with $i \ne j$, one possible build order could be:

Produce $a$'s and $b$'s in equal number (this is like $a^ib^j$ where
$i = j$. Try writing a grammar for this first.)

At some point, the number of $a$'s and $b$'s have to diverge, so pick either $a$ or $b$ and produce an unbounded number of that character (this is like $a^ib^j$ where $i \ne j$. Try taking the grammar you have from 1) and adding production rules to be able to do this.)

Now just produce an unbounded number of $c$'s at the end. (this is the desired $a^ib^jc^k$ with $i \ne j$.)

A good question to ask yourself:
Why do we have to have more than one production rule to construct $a^ib^j$ where $i \ne j$? If I want the number of $a$'s and $b$'s to be equal, it makes sense that I'd have to build them at the same time, but if I want $i \ne j$, why can't I just do something like:
$S \rightarrow aS\ |\ Sb\ |\ \varepsilon$
which says "produce some number of $a$'s and then produce some number of $b$'s"?


Are these two relations on integers partial orders? Are the following relations $R_1$ and $R_2$ defined on the set $\mathbb{Z}$ of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.)

$a$ $R_1$ $b$ if and only if $a = 2b$.
$a$ $R_2$ $b$ if and only if $a^2|b$.

Would someone help me understand?

Let's look at all the different criteria (reflexivity, symmetry or antisymmetry, and transitivity) for the first relations, $aR_1b\Leftrightarrow a=2b$ :

a) Is it reflexive, or antireflexive, or neither?  For this we want to test $aR_1a$ — or in other words, whether $a=2a$.  This can hold if $a=0$, but otherwise it never holds.  So on $\Bbb{Z}$ the relation is neither reflexive nor antireflexive; but on $\Bbb{N}$ (the set of 'whole numbers', not counting 0) it would be antireflexive, since $a=2a$ can never hold there.

b) Is it symmetric, or antisymmetric, or neither?  Here we want to compare $aR_1b$ and $bR_1a$ where $a$ and $b$ are distinct values; in other words, can we have both $a=2b$ and $b=2a$?  Dividing by 2, the latter is equivalent to $a=\frac{1}{2}b$, and the only way we can have both $a=2b$ and $a=\frac{1}{2}b$ is to have $b=0$, in which case $a=0$ — but since we said that $a$ and $b$ had to be distinct, this can't hold.  In other words, if we have $aR_1b$ for $a\neq b$ we can never have $bR_1a$; the relation is antisymmetric.

c) Is it transitive?  (Note that we never ask about 'antitransitivity', even though the concept hypothetically makes sense).  For this, we want to figure out if $(aR_1b)\wedge(bR_1c)\implies(aR_1c)$ — in other words, if $a=2b$ and $b=2c$, is $a=2c$?  Well, if $a=2b$ and $b=2c$, then we have $a=2b=2(2c)=4c$, so it's definitely not the case that $a=2c$; this relation is not transitive.

Since this has the feel of homework, I'll let you do the second one yourself, but it should be relatively straightforward (as long as you know a little bit about divisibility).  For looking at reflexivity, you'll have special cases again where $a=0$ and also where $a=\pm1$ to keep an eye out for; for symmetry you should be able to use the divisibility to say something about the relative order of $a$ and $b$; and for transitivity you should try to figure out how to 'staple' the two conditions $a^2|b$ and $b^2|c$ together to see if you can figure out whether $a^2|c$.


Amortized time for dynamic array I'm struggling to understand one part from the book "Cracking the coding interview".
The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full and we have to reallocate.

Inserting $X$ elements take $O(2X)$ (because $\frac{X}{1} + \frac{X}{2} + \frac{x}{4} + \ldots + 1  \approx  2 X$)

I perfectly understand until this point but I don't understand second sentence:

  "Therefore, $X$ insertions take $O(2X)$ time. The amortized time for each insertion is $O(1)$."

How did she came to this conclusion?

You should read more precisely the definition of amortized analysis. As we have $X$ operations here, the time complexity of these operations should be divided by the number of operations to find the amortized complexity of the algorithm. Hence, $\frac{O(2X)}{X}$ is the amortized complexity of the insertion algorithm which is $O(1)$.