Where is knowing the 2^k largest elements in a array useful?

If you implement a solution to the problem in an obvious way using quickselect with partitioning ($\log_2 n$ selects, with the $i$th one costing $n/(2^i)$), you will end up with an array partitioned in such a way that it is essentially Williams's binary heap.


Which attributes to consider for credit card fraud detection on an ATM?

Location based trends
Number of transactions from a particular ATM in a particular location, compared to the home area. So if the user usually uses a small set of ATMs near to their address, and then suddenly there are 5 large transactions from an ATM on the other side of the country.
Another little suggestion
If it was up to me, I would use a system where the attempted transaction is given a suspiciousness rating, where each factor is given a score and then the overall decision whether or not to authorize the transaction is based on the average score. This would also allow you to prioritize different factors.
Does that make sense? (Sorry, it's my first post, I'm still getting used to the etiquette)


Efficiently computing minimal elements over partially ordered sets

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it.  This will output all of the minimal sets.  The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is the number of minimal elements.  Or, to put it another way, if each set contains $m$ elements, the running time will be approximately $O(n(k+\log n)m)$ basic steps.

Why sort by size?  This is an optimization.  The smallest set is guaranteed to be minimal (there is none of smaller cardinality in the list, so none of its subsets can be in the list), so size is a useful trick to identify a set that must surely be minimal.

Without sorting by size, the worst-case running time is likely to end up as $O(n^2)$ set comparisons (or $O(n^2 m)$ basic steps), which is worse when $k \ll n$.

Here is an optimized version of that algorithm.  Let $M$ be a data structure that stores a set of sets, as a trie: for instance, the set $\{1,3,6,7\}$ corresponds to the word $1367$ and is stored in the trie accordingly.  Initially, $M$ is empty.  Repeat the following: take the next set $S$ from the list; check whether any set in $M$ is a subset of $S$; if not, insert $S$ into $M$; finally delete $S$ from the list (or advance your pointer to the next element in the list).  The "check..." operation can be performed fairly efficiently using a recursive traversal of the trie.  At the end, once you've gone through the entire list, output $M$.

The worst-case running time of the optimized algorithm remains the same.  In practice the running time might be improved significantly, perhaps to as fast as $O(nm)$ basic steps in some cases if you are lucky (but don't count on it).  You can try both and see which works better in practice on the kind of workloads you are dealing with.


Grokking pseudo-code for solution to gas station problem

The second implementation is correct (so Theorem 2.2 survives): If the condition $c(v) > c(u)$ causes the inner while to halt, that same value of $v$ will be give the optimal value for every following value of $g$, simply because the condition is independent of $g$.


What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not

I am answering my own question. As @rici made a comment, I misunderstood the meaning of Greek letters in the discussion of Follow sets in the book I am reading. Greek letters mean sequences of symbols.

Using the definition,

  If there is a production B-> $\alpha$ A $\gamma$, then First ($\gamma$)
   - {$\epsilon$} is in Follow (A)

First(BCD) is in Follow(X) where

  A -> XBCD

BCD corresponds to $\gamma$ in the definition.


"Implied atomic propositions" in propositional boolean formula

Suppose we had a TM $M$ which, given $F$ and some atomic $A$ occurring in $F$ it can efficiently (PTIME) decide whether all models of $F$ make $A$ true, i.e. whether $F \models A$.

Then we can efficiently decide the validity of any formula $G$ as follows.

Take $A$ to be any atom not in $G$. Craft $F := \lnot (G \land (\top \lor A))$, and use $M$ to decide if $F \models A$.

We then have
$$
(F \models A) \iff (F \models \bot) \iff \models \lnot F \iff \models G \land (\top \lor A) \iff \models G
$$

The first $\iff$ is nontrival, but easy to prove by considering the models where $A$ holds, and the others where $\lnot A$ holds, and exploiting our choice of $A$. It is left as an exercise ;-)

So, we constructed a polynomial reduction of validity to this problem.
Since validity is coNP hard, we deduce this problem is also coNP hard.


Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)?  Because that allows us to answer questions that are fascinating, questions like "Are there problems that are even harder than the halting problem?".  I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, fun, and lead to a deep theory.  Just as not all art has to be directly useful, not all theory has to be directly useful.

Why are oracle Turing machines important, more broadly?  They are used widely in computer science theory, to help us study the relative difficulty between different problems.  They help us encode the notion of Turing reductions.  They help identify some barriers to proving results in complexity theory, like proving that $P \ne NP$ (see e.g. relativizing proofs).  They are useful in other places as well.

See also Are there any existing problems that wouldn't be solvable with a halting oracle?, Are all undecidable/uncomputable problems reducible to the Halting problem?, and Reductions among Undecidable Problems.


Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I could do QuickSelect (j - i) times to get all the elements

Overkill. Two calls to QuickSelect and one linear pass are sufficient.


If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals?

No. $\Sigma$ is the set of symbols that the strings in the two languages are over ("the alphabet"). So $c$ is one symbol, and $Y$ is the set of all the other symbols in the alphabet. These will all be terminals when the CFG is constructed in the proof.

What the theorem is saying is that if you have a context-free language $L$ that uses only symbols from $Y$, then $L$ is also regular if and only if the new language where you prepend a $c$ to every string in $L$ (i.e. $cL$) is also regular.

At this point there's no mention of a CFG, so there's no terminals or nonterminals. The proof is where the CFG is introduced as a consequence of $L$ being context-free. Note however that this proof is very very truncated, there's a lot of detail and reasoning left out, so it's a lot harder to follow than it should be if you don't already see the reason that the theorem is true. There's also a series of mistakes in it.


Clarification for a class of Turing machine problems

The question does not mention replacing "ba" by spaces.     It does not say that you can have spaces between the symbols in the output word. Is the blank character even in the output language?


Which grows asymptotically faster, $\log \sqrt{n}$ or $4 \log n$?

The asymptotic growth of
$4 \log n$ is referred to as $\Theta(\log n)$.  You will have to look at
the definition of asymptotic growth to see why that is the case, but
intuitively, it is the growth of a function when we discard constant
factors and only look at the function "in the limit".
You have found out that the difference between the two functions "is
1/8", which makes sense, and which would put these two functions in the
same "growth class".
When it comes to $\Theta\left(\log ( \sqrt n ) \right)$, it is, as you
likely have found out
$$\Theta\left(\log ( n^{1/2} ) \right) = \Theta\left( \frac{1}{2}\log n
\right) = \Theta\left(\log n \right).$$


Transform Standard-Dual program to Canonical-Dual program

Yes. For each variable $y_i$, just add the constraint $-y_i \leq 0$, and then you don't have to assume that $\vec{y} \geq 0$.


Nodes in a binary search tree that span a range

I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though.

Find the extremal two nodes $\ell \leq p \leq q \leq u$ and their common ancestor $a$ in $O(h)$ time. If nodes $p$ and $q$ are the same, return $S = \{p\}$.

While $p$ is the left child of its parent and its parent is not the common ancestor, let $p := \text{parent}(p)$. Similarly for $q$ but with being the right child as criterion.

Now if $p$ and $q$ are both the direct children of $a$ let $S = \{a\}$ and you are done. Otherwise initialize $S = \{p, q\}$ and repeat:

$p := \text{parent}(p)$
If $p = a$ break.
Add the right child of $p$ to $S$.

And to finish up, do the same for $q$ but adding the left children instead. Note that the first iteration of the above loop can add $p$ or $q$ to the set while it is already in it. If you use an array instead of a proper set you want to make a special case for the first iteration.

In the worst case this adds $2h + O(1)$ elements to $S$. This can be necessary too, consider a full binary tree where the range includes all but the smallest and biggest node.


Want to know the time complexity inner for loop which is partially iterating the array

It is $O(n^2)$. Consider array = [n, n-1, n-2, ..., 1].

BTW, you could implement this in $O(n)$ by scanning from the end of the array:

Suppose the next-increasing-value (NIV) of a[i+1] is x.
We want to find the NIV of a[i], which we observe that:

If a[i+1] > a[i], then the NIV is a[i+1]
If x > a[i], then the NIV is x
Otherwise, a[i] is already the maximum value, so the NIV = -1.

Using this we could work backward from a[n-1] to a[0] to find the NIV of each entry in $O(n)$ time.


Constant folding vs. Constant propogation

Based on these two websites: http://www.compileroptimizations.com/category/constant_folding.htm and
http://www.compileroptimizations.com/category/constant_propagation.htm

The difference is that constant propogation is not saving a variable to the stack, because we know its a constant (like x = 10;) and can simply plug it in everywhere (say if you had an expression y = x + x + x => y = 10 + 10 + 10) it is used in machine code. Whereas, constant folding is simply evaluating expressions that use constants and substituting the result into the machine code (like y = 10 + 10 + 10; => y = 30;)


Asymptotics of a function that decreases as n increases

If you use suitable definitions, you'll find that your function is in

$O(2^n)$,
$O(n^4)$,
$o(1)$ and
$\Omega(-n^2)$,

among many others. It's likely that the question (implicitly) asks for sharper bounds; I'll leave that for you to figure out.


Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

It follows from the definitions that $f(n) = O(g(n))$ iff $g(n) = \Omega(f(n))$, in the same way that $a \leq b$ is equivalent to $b \geq a$. Therefore in order to prove $f(n) = \Theta(g(n))$, it suffices (and necessary) to prove $f(n) = O(g(n))$ and $g(n) = O(f(n))$.

The "quick" way to prove that $\binom{n}{2} = \Theta(n^2)$ is
$$
\binom{n}{2} = \frac{1}{2} n^2 + O(n) = \frac{1}{2} n^2 + o(n^2) = \Theta(n^2),
$$
where the last equality is a general result: $cf(n) + o(f(n)) = \Theta(f(n))$.

In practice, we take the following fact as well-known: if $P$ is a polynomial whose leading coefficient is positive then
$$ P(n) = \Theta(n^{\deg P}). $$
Using this, you can immediately deduce $\binom{n}{2} = \Theta(n^2)$.


Comparing A* search to Simulated Annealing

"Energy" is just the output of your cost function that you define for the SA problem. You are right that the two algorithms seem to have two different purposes, and in most cases, I would say that is true. However, you could pose a pathfinding problem as a simulated annealing problem, depending on how you define your cost (energy) function.

Let's say you have a cost function that equals the total cost to get from point A to point B. Your SA algorithm would try to find the minimum in this cost function, but imagine how difficult that may be. Your cost surface could potentially by many-dimensional. Plus, there is no guarantee that your cost surface is smooth, so finding that minimum on this enormous cost surface may be computationally intractable.

I think you've stated well many of the differences, but the next step is to try to understand the benefits/drawbacks of each algorithm solving the problem they are best suited for.


shortest notation for "set of all maps from $A$ to $B$"?


Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem

I'm not sure I follow your proof. To use Myhill-Nerode, you need to show that the number of equivalence classes under the indistinguishability relation $I_L$ is infinite. What follows is how I would approach this; you're probably best qualified to compare this to what you've done to see whether your proof is relying on the same assumptions, making the same points, and reaching the same conclusions for the same reasons.

Consider the string $w = 0^{2^n + 1}$. This is not a string in $L$. To create a string that is in $L$ by appending to this string, we can append $0^{2^n-1}$, of length $s = 2^n - 1$. There is no other string $s'$ shorter than $s$ such that $ws' \in L$.

Therefore, we immediately have that $w = 0^{2^n + 1}$ and $w' = 0^{2^m + 1}$, $n \neq m$, are distinguishable strings with respect to the indistinguishability relation $I_L$; they belong to different equivalence classes, since the set of strings we can append to $w$ to get a string in $L$ is different from the set of strings we can append to $w'$ to get a string in $L$ (recall that the shortest string in the first set is of length $2^n - 1$, whereas the shortest string in the second set has length $2^m - 1$).

Since $i$ and $j$ vary freely over the natural numbers, we must have an infinite number of equivalence classes over $I_L$. Since the Myhill-Nerode theorem tells us that regular languages must have only a finite number of such equivalence classes (remember, each of these equivalence classes corresponds to a single state in a minimized DFA for the language), this language must not be regular.


What does $|w|$ mean in the statement " $|w|$ where $w \in L \subset \Sigma^*$"?

Usually, $\Sigma^*$ denotes the set of all strings obtainable from an alphabet $\Sigma$.

Most probably, $L$ is a language and $w$ is a word. A language is a subset of the alphabet $\Sigma^*$, thus $L \subset \Sigma^*$.

A word, on the other hand, is a single string obtained from the language $L$.

As an example:

$\Sigma = \{0,1\}$
$\Sigma^* = \{0, 01, 10, 11, 100, 101, \dots, 1011001001, \dots\}$
$L \gets$ all strings containing an even number of zeroes
$w \gets 100010$

And $|w|$ is probably the length of $w$.


There could not be an edge from u to v in a DAG, if w is before v in a topological order

Assume that there is path $u \rightarrow v$ as well. Then we have a cycle. What does this mean in terms of topological order? Can there be such an order? Whether u comes first or v comes first depends on where you start!


A loop invariant is an expression that is true through all iterations. But it should also lead to the post-condition being true when the loop terminates. Although c-a=1 is true, It doesn't help you in achieving the post-condition.

Intuitively, You would want the invariant to be a*N + b = M because that's what division is and that's what guarantees that you'll get the post-condition ( a=quotient, b=remainder) when the termination condition ( b < N ) is true.

The formal proof should follow from this idea.


Uniformity definition means that there is a deterministic Turing machine running in logarithmic space $\mathsf{L}$ that generates the description of the $n$th circuit from the unary encoding of $n$.

To have a better idea of what this is talking about, assume that we have a Turing machine $M$ in $\mathsf{P}$. Then for every input size $n$ we can generate a circuit of size $poly(n)$ that compute $M$ on inputs of size $n$. So we obtain a family of circuits $\{C_n\}_{n \in\mathbb{N}}$. However these circuits are not arbitrary independent circuits but coming from a single machine $M$.

The definition is good for large classes like $\mathsf{P}$ but it doesn't work for small complexity classes. For those classes we use deterministic logarithmic time $\mathsf{DLogTime}$ in place of $\mathsf{L}$. In place of printing the whole circuit we just require it to compute any given bit of the description of the $n$th circuit in logarithmic time.


Is pumping lemma for regular languages "closed" against Kleene star?

In order to show the pumping property of a string like $x_1x_2 \dots x_n$, where each $x_i\in L$ you can distinguish two cases. Either $x_1$ is "short", which means you can pump $x_1$ completely and stay within $L^*$, or $x_1$ is "long" and you can pump "inside" $x_1$.


Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

Let me start with a counterexample where your algorithm gives the wrong answer: i.e., where $N$ is composite but your algorithm concludes it is prime.  Suppose $N=91$ and $a=9$.  Then $a^{(N-1)/2} = 9^{45} \equiv 1 \pmod{91}$, so $a$ passes your check to be a QR.  Also, $a^{(N+1)/4} = 9^{23} \equiv 81 \pmod{91}$ and $81^2 \equiv 9 \pmod{91}$, so this passes your second test, your algorithm will conclude that 91 is prime.  However, 91 is not prime: $91=7 \times 13$.  Thus your algorithm has drawn the wrong conclusion in this case.  This demonstrates that your algorithm can output incorrect answers in at least some cases.

Actually, there is a more serious problem with your algorithm.  There is no number $N$ where your algorithm will ever output "composite".  It thinks that all numbers are primes.  More precisely, for every $N$, your algorithm will either loop forever (trying to find a number that passes the QR test, in vain), or will terminate and output "prime".  So, your algorithm is about as wrong as could be.

You can see this by applying some number theory.  You have a test whether $a$ is a QR and a second test based on the square root insight.  If $a$ passes the first test, it will pass the second one.

Here's why.  Your QR test succeeds if $a^{(N-1)/2} \equiv 1 \pmod N$.  Your second test succeeds if $(a^{(N+1)/4})^2 \equiv a \pmod N$.   The latter is equivalent to $a^{(N+1)/2} \equiv a \pmod N$.  But $a^{(N+1)/2} \equiv a \times a^{(N-1)/2} \pmod N$.  Therefore, if $a^{(N-1)/2} \equiv 1 \pmod N$, then (multiplying both sides by $a$) we immediately see that we must have $a^{(N+1)/2} \equiv a \pmod N$.

Each of the $k$ passes of your algorithm basically amounts to looking for an $a$ that passes the first test, and then checking whether it passes the second test -- but based on the prior insight, we see that any $a$ that passes the first test will be guaranteed to pass the second test as well.  Thus, if the algorithm ever finds any value $a$ that passes the QR test, the second test will automatically pass and the algorithm will output "prime".

The lesson to learn: any time you think you have an algorithm that looks promising, it's worthwhile to code it up and try it on some test cases and see if it seems to work well.  Trying it on a few test cases is not a substitute for a proof of correctness, but it can be a helpful way to weed out some incorrect algorithm quickly.

Finally, on to your real question: can we use something like this to build a primality test? Well, you can think of the Miller-Rabin primality test as loosely based on something like this.  They are based on a characterization of what the square roots of $1$ should look like, if $N$ is prime.  If you encounter a square root of $1$ that is not $1$ or $-1$, you can conclude that $N$ is not prime.  However, it's not limited to numbers $N$ of the form $N=4k+3$, so in that sense it is definitely different.


Is my decomposition of R into 3NF is lossless and preserving all dependencies?

So My decomposition is lossless and preserving all dependencies but there is no need for relation R3(E, C, B) because we already have A which can derive B in R1.


The first condition makes no sense whatsoever to me, and neither condition is expressed in the most obvious way. I can't imagine why you'd ever want to define halting in that way.

A Turing machine halts exactly when it enters the HALT state.  It's as simple as that.  The only alternative I've ever seen is to have two halting states, corresponding to accepting and rejecting the input. In that case, the machine halts exactly when it enters either one of them.

Your source seems to be adopting a different approach, in which "HALT" is not a state but an action of the machine in the same class as "move the tape head left" or "move the tape head right". That's unusual, but not problematic in its own right. However, neither definition of halting is the one that I would expect.

The second one is the closest: the machine halts if it decides to stay in its current state, leave the current character on the tape and make the HALT action. But this is still strange – surely the HALT action on its own should halt the machine, regardless of what state the machine moves to and what it writes on its tape at that step? For example, the behaviour of hte machine at the next step would seem to be undefined if $\delta(q,a)=(q',a',\mathrm{HALT})$ and $q'\neq q$ and/or $a'\neq a$.
The first definition is very unnatural. I can see no motivation for saying that the machine halts only if it's in a state where seeing any character whatsoever would cause it to stay in the same state, leave the tape as it is and making the HALT action. In fact, this is basically defining the state to be a halting state in the way that Turing machines are usually defined. If one wanted to go down that route, why not just use the conventional HALT state instead of making HALT an action of the machine?

Note, however, that these definitions of halting, and the standard one, are all equivalent in that they can simulate each other. So, whichever of these definitions you use, the same class of problems can be computed by Turing machines.


Algorithm for storing polygon edges into grid

Bresenham's method is one possibility, however do be aware that as originally presented, it produces the best discrete approximation to the line, which isn't exactly what you want. You want the grid cells which include the polygon, which means that (say) left-edges should be rounded down and right-edges should be rounded up. Wu's algorithm effectively enumerates all of the cells which a line passes through, so it would probably be easier to modify that.

Do bear in mind that on a lot of modern CPUs, floating point arithmetic is extremely efficient compared with integer arithmetic, especially now that we have SIMD execution units. It can actually be more efficient in some cases since the register file and execution units for floating point are typically independent of those used for integer computations. Bresenham is still important, of course, but it's probably worth considering other methods.

Another algorithm that may be worth considering is Pineda's method, which is used by many (if not most) GPUs to scan-convert triangles into fragments. The question asked about polygon edges specifically, not the interior of polygons, but you might find some useful ideas there.

If raw speed is important, one advantage of Pineda's method is that you can enumerate which 4x4 cells the polygon touches, and then calculate individual grid entries in parallel using SIMD arithmetic. This should be very fast on modern hardware.


Solving Recurrence relation with master method?

You are claiming that "we can prove that $af(n/b) \leq cf(n)$". There are two problems with this claim:

This is now what you actually need in order to apply the master theorem. The master theorem needs you to show that there exists $c < 1$ for which $af(n/b) \leq c f(n)$ for all large enough $n$.
You haven't proved your claim.

Reiterating, to prove the claim you need to come up with a value of $c < 1$ such that the following inequality holds for large enough $n$:
$$
9 (n/3)^3  \log(n/3) \leq cn^3 \log n.
$$
This holds for $c = 1/3$, since
$$
9(n/3)^3 \log(n/3) < 9(n/3)^3 \log n = \frac{1}{3} n^3 \log n.
$$


Pumping Lemma: Proving L={0^n 1^m |m ≤n^2} is not a CFL

What you have done up to now is correct. The idea is that you should prove that the 'pumping' fails for all possible partitions of $w$. You have considered just two families of partitions, namely, the one for which
$vxy\in0^+$ and the one for which $vxy\in1^+$.

You are missing the cases in which the sliding window (ie. $vxy$) crosses
the boundary between $0$ and $1$.

Hence, next step is to consider the following cases (here $|w|$ is
the length of $w$):

1) $vxy=0^{|vx|}0^h1^k$ where $h,k\geq 1$ and $h+k+|vx|\leq p$

2) $vxy=0^{|vx|}1^{|y|}$ where $|y|>0$ and $|vxy|\leq p$

3) $vxy=0^{|v|}0^h1^k1^{|y|}$ where $h+k=|x|>0$ and $|vxy|\leq p$

4) $vxy=0^{|v|}1^{|xy|}$ where $|v|>0$, $|xy|>0$ and $|vxy|\leq p$

All of the above cases can be easily solved with the technique you used with the former ones.


Does NP mean verifiable in polynomial time or solvable in polynomial time?

NP is a class of problems whose solution is verifiable in polynomial time on a deterministic Turing machine.
Alternatively, NP is a class of problems whose solution is solvable in polynomial time on a nondeterministic Turing machine.

Please look here.


Computing FOLLOW sets for a LL(1) grammar

The follow set of something translates to asking: what symbol can come next in the string we are trying to read with the grammar rules the machine has?

Let's say we take a string "abba". The input tape symbol will end the string with $ as the delimiter. So we can say that 'a', 'b', 'b', 'a' and '$' are the symbols that the read/write head of the parser will see while evaluating this string. I am taking the below production rules for this grammar.

S->AB
A->ab|a
B->baB|E

The string "abba" can be evaluated in the following manner:

S->AB
 ->abB
 ->abbaB
 ->abbaE

In the above case, Follow(A) = {b,$}.

'b' is part of the set because B's production follows A's production, S->AB, and whatever is the first letter that B produces will follow the last letter A produces.

Similarly, $ is part of the set because of B's epsilon production.
When B is evaluated using rule B->E, then for Follow(A) there is no first letter produced by B.

In such a case where the Follow(A) is an epsilon production,

S->AE | using B->E

Then Follow(A) becomes Follow(S) which is $.

If you look at the string "abba", once the last a is read the only symbol that can come after the string is $.

As a generalization, if X->ABC and C->E, then Follow(B) = Follow(X).

In your question's example, evaluating Follow(A') results in only two possibilities where A' is on the RHS and can have a following symbol. Below are the two productions that can result:

A->bA'
A'->aA'

Unfortunately, out of the two one is Follow(A') = Follow(A') as per the rule I have mentioned in last line of the answer.

Hence we can only consider the other follow which is

Follow(A') = Follow(A)

i.e.

Follow(A) = First(B)

In a practical sense, if we have

S->ABC

and

A-> bA'
A'->aA'|E

Then whenever we have an A production, it will further lead to either A -> baA' or A->b (if we take A'->E).

In both cases the only thing that can follow A' is whatever is the first of B.

In a similar manner we can compute the same for Follow(B') and Follow(C').


Simplification of a multi-index Boolean expression towards computation in fewer steps

It is equivalent to

$$\bigwedge_{k=1}^{N} \bigvee_{i_k=1}^{M} x_{i_k k}.$$

This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.


How can we generate a grammar for $\{a^n b^n c^n d^n; n > 0\}$ if it is NOT context free?

Your grammar generates the language $\{a^ib^jc^kd^\ell \mid i,j,k,l \geq 1\}$, which is larger than $\{a^nb^nc^nd^n \mid n \geq 1\}$. For example, your grammar generates $abcdd$, which is not of the form $a^nb^nc^nd^n$.
That said, you can generate $\{a^nb^nc^nd^n \mid n \geq 1\}$ using a context-sensitive grammar. Moreover, unrestricted grammar can generate all recursively enumerable languages.


In the shor's quantum circuit, what is the transformation of the modular operating gates?

It's a modular multiplication gate. It permutes the states such that, for all $k$ below $N$, state $|k\rangle$ becomes state $|k \cdot c \pmod{N}\rangle$ where $N$ is the number being factored and $c = b^{2^{2n-1}} \pmod{N}$ is a classically computed constant and $b$ is the base value chosen randomly at the start of the algorithm.


NP-hardness given some reducible language

Hint: if $A$ is NP-hard, and it can be reduced in polynomial time to $B$, what can you say about $B$? Then if you have a polynomial time algorithm for $B$, what does that imply? (Check out the definition of NP-hardness and NP-completeness).


How does one know what statements in Coq require Induction?

Coq allows one to prove mathematical theorems in a completely formal way. At first, this copes with our experience of doing maths, which is far more informal.

Most of the time, people doing maths are not exposed to mathematical logic. They do not know, for instance, how to define the set of real numbers. Or even the set of natural numbers. Numeric sets are simply taken for granted, together with their operations and related properties. On top of these "basic facts" people build more complex theorems. Essentially, the "basic facts" are used as if they were axioms.

Note that one could work at a similar level in Coq, if one wishes. One can import the Arith Coq library, which provides the basic facts of arithmetics, and exploit those.

However, the underlying logic of Coq does not take those properties for granted. The type of natural numbers, for instance, is not a primitive concept in the logic, but rather something which is defined using induction. Since that makes nat an inductive type, virtually every proof about naturals will require induction. (This also holds in set theory, e.g. Zermelo-Fraenkel, where naturals are also defined in a sort-of inductive way.)

Arithmetical operators are also defined using induction. Using a simplified syntax, one could define multiplication as

x * 0     = 0
x * (S y) = x + (x * y)

or, alternatively,

0 * x     = 0
(S y) * x = x + (y * x)

Both definitions are equivalent. However, using the first one will result in us being able to prove x * 0 = 0 "without induction" -- it follows by definition. In Coq, we can simply write reflexivity and let the system expand the definition for us.

By comparison, 0 * x = 0 is not a trivial equation which follows from the definition: to expand the definition we need to know what is the second argument of the multiplication, but here it's merely an unknown x. Hence, for this we do need induction over x. There's no way around that.

Note that, if we used the second definition instead, we would prove 0 * x = 0 immediately, and instead require induction for x * 0 = 0. So, no definition is strictly better than the other one.


Convex-hull of a star shaped polygon in O(n)

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$.

In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.


Designing a DFA that accepts strings such that nth character from last satisfies condition

Hint: Your language can be described by the regular expression $\{0,1\}^*1\{0,1\}^3$.

Another hint: Your DFA can remember the last $4$ characters (and maintain that information). You will also need states to handle the case in which less than $4$ characters have been seen so far.


Can you write a program that alters another program semantically?

Your idea fails (assuming all P are allowed), and that's not by accident.

You can not find an input for with P halts in finite time.
P may never halt, in which case that line in your program loops;
thus, the program behaves exactly the same as P.
You can skip finding k and do

alter(P, x) =
  P(x) + 1

This is the same idea as you have (note how it alters the semantics on
 all inputs on which P halts) but does not require us to find
 an input on which P halts.

However, it's still fails for the never-halting program -- but, at least,
 only that one!
What if we just output 1 or any other value sometimes?
 That takes care of never-halting P, but for each such
 hack with a static, computable "abort and output c"-criterion
 -- that includes runtime bounds! -- we can build easy counterexamples.
 Idea: if ( criterion ) then c else something.

So that looks bad; we can't compute uncomputable criteria! And we have to "decide"
after finite time for any fixed x (otherwise the never-halting P skrews us).

When prospects are this bleak, it's sometimes wise to try the other direction.
What if the problem can not be solved, that is alter does not exist?
In fact, given sufficient background in computability, it is clear that such
a function can not exist.

Assume any computable, total function $\mathtt{alter} : \mathbb{N} \to \mathbb{N}$.
We understand natural numbers as (the numbers of) programs in some
Turing-complete programming language $\phi$.
More specifically, let $\phi$ be a suitable numbering of all (partially) computable functions;
we then denote by $\phi_i$ the function computed by program $i$.

Now, by Kleene's recursion theorem
there is some index (program) $i^*$ so that $\varphi_{i^*} = \varphi_{\mathtt{alter}(i^*)}$,
that is $\mathtt{alter}$ has no effect on $i^*$, semantically.
Stronger versions show that there are infinitely many such $i^*$ so there's no hope fixing this.

In summary, no such program alter that works on all input programs can exist.

If you allow only P that halt for at least some x, your approach works; the proof is elementary (show that alter is computable, and that alter(P)(k) != P(k) for some k).


Is every language in PTime also context-sensitive?

It is an open question to separate $\mathsf{L}$ (that is, $\mathsf{DSPACE}(\log n)$) and $\mathsf{P}$ (what you call PTime), so in particular we have no example of a polytime language which requires superlogarithmic space.


Can a recurrence relation be translated to a composite function of itself?

static float f(int n,int m)
      {
         if((n==1)||(m==0)) return (1,1);
         return ((3*n - 2*m)/2,n);
      }

That way $\underbrace{f\circ f\circ \dots \circ f}_{\text{n times}} (1,0)=(a_n,a_{n-1})$.

Is that what you wanted?


You can solve this problem with dynamic programming. Your states are
dp[day_number][worked_sofar]. here is a recursive implementation:
#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
int n, k1, k2;
int solve(int day, int sofar){
    if(day > n || sofar > k2)return 1;
    if(dp[day][sofar] != -1)return dp[day][sofar];
    int ans = solve(day + 1, sofar + 1);
    if(sofar >= k1)ans += solve(day + 1, 0);
    return dp[day][sofar] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> k1 >> k2;
    dp.assign(n + 1, vector<int>(k2 + 1, -1));
    cout<<solve(1, 0);
    return 0;
}

```


Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

On the contrary, it's certainly important practice, and is a huge area of research!

Perhaps a better question might be, "why is proving programs correct not common in practice, or not a main feature of an undergraduate curriculum?"

There's a few reasons for this:

Proving programs correct is hard. The proofs often end up being long and tedious proof-by-cases, and will usually have less interesting intellectual content that you'd see in most math proofs.
You need a formal semantics for whatever language your program is specified in. For real world programming languages, developing such a semantics is often difficult, since there are possibly corner cases or odd compiler behaviors that are difficult to model
Proving a program correct only proves that it matches a given specification. What if there's a bug in the specification?
Proving a program correct assumes that it's being compiled by a correct compiler, or run by a correct interpreter, which almost never the case.

Things also change by what you mean by a "program". For example, in real world algorithms research, almost every time someone publishes a new algorithm, they will provide a proof of correctness. Usually this is working on pseudocode with a simple but straightforward semantics, so lots of the formal details from above aren't an issue.

Also, just to counter your claim that it's not an area of research:

The entire field of Dependent Types is focused on proving real, running programs correct using type theory. There are lots of great projects in this area, like DeepSpec.
Formal methods is an entire field devoted to proving program correct, usually adapting methods from hardware verification to software.


Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

The first four lines of your argument were correct; all you missed was the proper generalization. In general, we see that
$$
T(n) = c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)
$$
Now we want to drive $T(n-2j)$ down to a value we know, namely $T(1)=c$. To do this we'll need $n-2j=1$ and so we set $j=(n-1)/2$, giving us
$$\begin{align}
T(n) &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)\\
     &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{(n-1)/2-1}+\alpha^{(n-1)/2} c\\
     &= c(1+\alpha+\alpha^2+\dotsb+\alpha^{(n-1)/2})
\end{align}$$
and this is just a geometric series, so I'll leave the last steps to you.


Suppose first that $L \in \Sigma_2^P$. Then there exists a machine $T(x,y,z)$, running in time $\mathit{poly}(|x|)$, such that
$$
x \in L \Leftrightarrow \exists y \forall z \, M(x,y,z) = T
$$
Using the reduction in Cook's theorem, given $x,y$, we can express $\exists z \, M(x,y,z) = T$ as a SAT instance. Therefore given a SAT oracle, we can verify that $y$ satisfies $\forall z \, M(x,y,z)$. This shows that $L \in \mathsf{NP}^{\mathsf{NP}}$.
In the other direction, suppose that $L \in \mathsf{NP}^{\mathsf{NP}} = \mathsf{NP}^{\mathsf{SAT}}$. There is thus an oracle Turing machine $M(x,y)$, running in time $\mathit{poly}(|x|)$, such that
$$
x \in L \Leftrightarrow \exists y \, M^{\mathsf{SAT}}(x,y) = T.
$$
(The notation $M^{\mathsf{SAT}}$ means running $M$ with a SAT oracle.)
How can we tell that $M^{\mathsf{SAT}}(x,y) = T$ without access to a SAT oracle? The idea is to "guess" the answer of every SAT query, and prove the necessary information to verify this answer. Suppose that $M$ queries $q \stackrel?\in \mathsf{SAT}$. If $q \in \mathsf{SAT}$ then we can provide a witness for it, namely a satisfying assignment. If $q \notin \mathsf{SAT}$ then we know that every assignment does not satisfy $q$.
Accordingly, we construct a machine $M'(x,y',z')$ in the following way. The witness $y'$ consists of the original witness $y$, together with the following information: the number of SAT queries performed by $M$; for each SAT query $q_i$, the answer $b_i$; for each positive answer, the corresponding satisfying assignment $a_i$. The "cowitness" $z'$ consists of an assignment $a_i$ for each negative answer to a SAT query.
The machine $M'$ acts simulates $M$. Whenever $M$ makes a SAT query $q_i$, it determines the answer from $y'$. If $b_i = T$, it verifies that $a_i$ is a satisfying assignment for $q_i$. If $b_i = F$, it verifies that $a_i$ is not a satisfying assignment for $q_i$. The new machine $M'$ accepts if all verifications
succeed, and additionally $M$ accepts.
This shows that $L \in \Sigma_2$, completing the proof of your statement.


How to prove finding two paths that are at least k edges apart is NP-hard?

You can reduce from 3SAT.

The graph has two parts. One part is the "variable" part. For each of the variables $v_1,\ldots,v_n$ there are two three vertices $v_i^+,v_i^-,v_i$, and this part consists of the following edges, for $i \in [n]$:

$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$

Here $v_0$ is a new vertex, identified with $s_1$, and $v_n$ is identified with $t_1$.

The second part is the "clause" part. For each of the clauses $C_1,\ldots,C_m$ there four vertices $w_j^1,w_j^2,w_j^3,w_j$, connected much as before, with $s_2$ and $t_2$.

We connect $v_i^b$ with $w_j^r$ via a path of length $k$ (for some large enough constant $k$) if the literal $v_i^b$ (either $v_i$ or $\overline{v_i}$, according to $b$) is the opposite of $j$'th literal in $C_j$.

Also, we take all the mindpoints of these paths, and connect all of them (making them into a clique).

We can think of an $(s_1,t_1)$-path as a truth assignment, and of an $(s_2,t_2)$-path as identifying a satisfied literal in each clause. The minimal distance is more than $k$ if this is indeed the case, and only $k$ otherwise.

You also need to verify that there is no point for the paths to cross between the parts. If only one of the paths crosses, then the two paths will be close together (at some constant distance, which for large enough $k$ will be smaller than $k$) immediately after the crossing. If both cross, then the midpoint clique will ensure that they are at distance at most 1.


The logic behind one's complement addition

A binary number in one's complement is represented by $\bar{N} = (2^{n} - 1) - N$.
So when you subtract N from M you get:
$$
S = M - N = M + \bar{N} = M + (2^{n} - 1 - N) = (M - N) + 2^{n} - 1
$$
And when you do the so called end-around carry operation you effectively add $-2^{n}+1$ to the intermediate result because you take away the MSB and add 1. So you get:
$$SUM = S -2^{n}+1= (M - N) + 2^{n} - 1 - 2^{n}+ 1 = M - N$$
This is correct again.

In two's complement ($2^{n} - N$) you have:
$$S = -M + N = \bar{M} + N = (2^{n} - M) + N = 2^{n} - (N - M)$$
Discarding the MSB does $- 2^{n}$
 and gives you:
$$SUM = S -2^{n} = 2^{n} - (N - M) - 2^{n} = N - M$$

Done you are.


$Q_1:$ I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

max-heapify can be described as a recursive function. There is no particular prevention from a recursive function running in logarithmic time. For max-heapify, the recurrence is $T(n) \le T(2n/3) + \Theta(1)$ (here $2n/3$ is the worst case when the leaves is exactly half full; where $n$ is the size of the subtree rooted at the node under max-heapify). You can solve it by Master Theorem.

Another way of looking at max-heapify is to unfold the recursions: it "floats down" a value through a path of the subtree, whose length is $\sim \Theta(\lg n)$.

  $Q_2:$ To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

The answer is simple: We don't run max-heapify on a min-heap. Use min-heapify for min-heap instead.


Judging by your description and comments, you might be helped the best by an exact description on how reductions can be used to prove NP-completeness:

A problem is NP-complete iff it is in NP and it is NP-hard. This means that any proof of NP-completeness has two parts: a proof that the problem lies in NP and a proof that it is NP-hard.

For the first part, you have to show that YES-instances can be verified in polynomial time using some suitable certificate. Alternatively, you can show the problem can be solved in polynomial time by a non-deterministic Turing machine, but this is not usually done as mistakes are easily made.

In your case, this comes down to proving that for every graph with a $n/2$-clique, you can find some proof that there is indeed such a clique, such that, armed with such a proof, you can check in polynomial time that there is indeed such a clique.

For the second part, you have to show that the problem is NP-hard. This is in nearly all cases shown by proving that your problem is at least as hard as some other NP-hard problem. If HALF-CLIQUE is as least as hard as CLIQUE, it must also be NP-hard.

You do this by proving a reduction FROM CLIQUE, TO HALF-CLIQUE. You 'reduce' the problem, making it 'easier'. You say "Solving CLIQUE is hard, but I have proven that you only need to solve HALF-CLIQUE to solve CLIQUE". (many people, even experts, occasionally say this the wrong way around :))

There are different types of reductions: the reduction that is most commonly used is the one where you map instances of in this case CLIQUE to instances of HALF-CLIQUE whose size is at most polynomially larger, in polynomial time. This means that if we can solve HALF-CLIQUE, then we can also solve CLIQUE by chaining the algorithm and the reduction.

In other words, we must show that we can solve CLIQUE if we can solve HALF-CLIQUE. We do this by showing that for every instance for CLIQUE, we can design an instance of HALF-CLIQUE such that the instance of CLIQUE is a 'yes' instance iff the instance of HALF-CLIQUE is a 'yes' instance.

The proof therefore starts like this: given a graph $G=(V, E)$, I can create some graph $H=(V', E')$ such that $G$ contains a $k$-clique iff $H$ contains a $n/2$-clique. I'll leave this part to you (this is the part that requires creativity, the part that is about the specific problem at hand).


Algorithm / data structure to filter documents by number of missing words

Use a locality sensitive hash, like MinHash or SimHash.

You could also sort the set of words, extract shingles, and hash them using MinHash or something similar.


What is the relation between a programming language and the language of its input?

There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language.

Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^* = \{\epsilon,1,11,111,\ldots\}$.

Still, program $1^n$ will accept a language $L_n$ which is completely unrelated to $1^*$. Indeed, by Turing completeness, for any r.e. language $A$ there is some $n$ such that $A=L_n$.

The crucial aspect to consider here is the semantics of the programming language,
the way we map each program $1^n$ to its behavior, and ultimately to the set of accepted words $L_n$. Even if $1^*$ is a very simple language, the semantics can still make it Turing powerful, so that $L_n$ can be any r.e. language.


How to interpret these asymptotic runtime bounds for discrete logarithm algorithms?

The confusion is that in the expression for $L(\alpha)$, $n$ is size of the field, whereas in $n^{O(\log n)}$, $n$ is the size of the input. The correct comparison is between $L(\alpha) = \exp O((\log n)^\alpha (\log\log n)^{1-\alpha})$ and $(\log n)^{O(\log\log n)} = \exp O((\log\log n)^2)$, which is indeed much smaller.

Note that your suggestion to plot $L(\alpha)$ for $\alpha = 1/4 + O(1)$ and $\alpha = 1/4 + O(n)$ doesn't make much sense; you should think of $\alpha$ as a constant. It could make sense to consider $\alpha = 1/4 + o(1)$ (or $\alpha = 1/4 + \epsilon$, where $\epsilon$ is understood to be "small"), though it's not clear how exactly you'd plot it. Indeed, there is no reason to plot, and a plot wouldn't make too much sense without knowing the hidden big O constant. In practice you just do experiments.


Show Language is not context free without pumping lemma

Your approach doesn't work. We don't know how a putative push-down automaton for the language works. What you show is that a particular PDA doesn't work, but perhaps another one does.


Updating an AVL Tree Based On Balance Factors

I will answer the second question.

  Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Yes, actually that's the whole idea behind the avl tree. All balance factors are always in range [-1, 1], so you need only two extra bits per node to store it.

After insertion you simply climb up the tree and update balance factors:

decrease if the left sub-tree became higher,
increase if the right sub-tree became higher,
retrace the tree if the balance factor becomes -2 or 2 (this can be achieved by local rotations on the tree),
if balance factor becomes 0, then the tree became balanced and no further work is required.

For more details check wikipedia page.

If you need more mathematical analysis on how the balance factors change after local rotations, check my question/answer here.


Floating point precision from rearranging equation

First of all, the different numbers of digits are misleading. The two numbers store the same amount of precision; Python is just leaving off final zeroes.

However, there is a loss of precision here, and it comes down to the intermediate results.

Floating-point values aren't infinitely precise, and the larger their absolute value, the fewer places they can store after the decimal point. (Hence the name "floating point": one way to think of floating point numbers is that they're a fixed number of digits long, but you can move the decimal point back and forth to represent both really big and really small values.)

When you compute 8.8888888888**2, you're effectively using more of the available bits to store things before the decimal point. So there are fewer left over to store things after the decimal point. It gets less precise.

When you instead compute 8.8888888888 - 9.9999999999, you're not using those extra bits before the decimal point, so they can all be devoted to the part after the decimal point.

(Note: this is an intuitive explanation, not a technical one. The essence is correct, but the details are somewhat handwaved. If you want more technical details, look into how an IEEE float is stored.)


Proof of commonality of acceptors in majorities

Let $A,B,C$ be the first, second and third majorities. If there are $M$ players, we can think of $A,B,C$ as subsets of $[M] = \{1,\ldots,M\}$ satisfying $|A|,|B|,|C|>M/2$.

If $A,B$ were disjoint then $|A \cup B| = |A| + |B| > M$, which contradicts $A \cup B \subseteq [M]$; that's why two majorities always have an acceptor in common.

If $C$ intersects $A \cap B$ then the third majority includes an acceptor that saw both previous proposals, so suppose that $C$ is disjoint from $A \cap B$. Define
$$ A' = A \setminus (A \cap B), \;\;\; B' = B \setminus (A \cap B) \;\;\; U = [M] \setminus (A \cap B). $$
In order to show that the third majority includes two acceptors that saw one of the previous proposals each, we need to show that $C$ intersects both $A'$ and $B'$. If $C$ didn't intersect $A'$ then $|C \cup A'| = |C| + |A'| > M - |A\cap B|$, which contradicts $C \cup A' \subseteq U$ since $|U| = M - |A\cap B|$; so $C$ must intersect $A'$. Similarly, $C$ must intersect $B'$.


Here is the encode-decode method that L. Garde suggests (in cubical Agda):

{-# OPTIONS --cubical --safe --postfix-projections #-}

module Hmm where

open import Cubical.Core.Everything

open import Cubical.Foundations.Prelude
open import Cubical.Foundations.Isomorphism

open import Cubical.Data.Empty
open import Cubical.Data.Unit

data ℕ₂ : Type₀ where
  0₂ 1₂ : ℕ₂

Code : ℕ₂ → ℕ₂ → Type₀
Code 0₂ 0₂ = Unit
Code 1₂ 1₂ = Unit
Code m  n  = ⊥

Crefl : ∀{m} → Code m m
Crefl {0₂} = tt
Crefl {1₂} = tt

decode : ∀ m n → Code m n → m ≡ n
decode 0₂ 0₂ c = refl
decode 1₂ 1₂ c = refl

encode : ∀ m n → m ≡ n → Code m n
encode m n p = transport (λ i → Code m (p i)) Crefl

decode-encode : ∀ m n p → decode m n (encode m n p) ≡ p
decode-encode m n p
  = J (λ z q → decode m z (encode m z q) ≡ q) (lemma m) p
  where
  lemma : ∀ m → decode m m (encode m m refl) ≡ refl
  lemma 0₂ = refl
  lemma 1₂ = refl

encode-decode : ∀ m n c → encode m n (decode m n c) ≡ c
encode-decode 0₂ 0₂ c = refl
encode-decode 1₂ 1₂ c = refl

Cprop : ∀ m n → isProp (Code m n)
Cprop 0₂ 0₂ = isPropUnit
Cprop 1₂ 1₂ = isPropUnit

ℕ₂set : isSet ℕ₂
ℕ₂set m n = transport (λ i → isProp (p i)) (Cprop m n)
  where
  p : Code m n ≡ (m ≡ n)
  p = isoToPath (iso (decode m n) (encode m n)
                   (decode-encode m n) (encode-decode m n))


Even this might be too basic for teenager, I nicely shows how to abstract problems, and is applicable for kids :

I highly recommend all CS people to take a look at: Computer Science Unplugged , just to see how CS can look different :).

For young CS minded people I recommend to develop intuition by solving programming tasks from problem solving contests, like programming contests: ACM ICPC, Olympiads in Informatics etc.

It's nice way to go into "Practical Algorithmic" , which gives you best from both worlds: programming and algorithms. Thanks to that you will be prepared to go in future in both directions: CS oriented industry (Google, Yahoo etc), and University CS.

Nice places to start:

Sphere On-line Judge - you can sort problems from easiest to hardest and try to solve them
http://www.topcoder.com/ - There are many contests for HS, you can find there similarly minded people to you.


Fastest square root method with exact integer result?

You do not need an exact method, anything with error less than 1 is OK. Say you want to compute $\lfloor \sqrt{x} \rfloor$. This is the largest integer $y$ such that $y^2 \leq x$. Say you have an algorithm $\mathcal{A}$ which on input $x$ outputs $z = \mathcal{A}(x)$  such that $|z - \sqrt{x}| < 1$. You can just:

Compute $z = \mathcal{A}(x)$
Let $z_0 = \lfloor z \rfloor$
Let $S = \{z_0 - 1, z_0, z_0 + 1\}$
Output  $y = \max\{y \in S: y^2 \leq x\}$ (in words: output the largest integer among $z_0 - 1$, $z_0$, $z_0 + 1$ whose square is at most $x$).

You can also verify you have the correct number by checking that $(y+1)^2 > x$.

Correctness follows from the fact that if $|z - \sqrt{x}| < 1$, then $|\lfloor z \rfloor - \lfloor \sqrt{x} \rfloor| \leq 1$.

I think Newton's method with a small number of iterations is the best thing you can do. Since you only need error smaller than 1, I believe a few iterations will indeed suffice. Doing extra three integer multiplications and comparisons at the end cannot slow you down so much.


Is the language of all TMs *not* accepting a given string, Enumerable?

The classic technique of dovetailing can be used to show the complement of $L$, $\{\langle M\rangle : M\text{ is a TM that accept }010\}$ is recursively enumerable. Check this answer for details.

Since $L$ is not decidable as shown by Rice's theorem, $L$ cannot be recursively enumerable.

Exercise. Show that $\{\langle M\rangle : M\text{ is a TM that accept } 010\text{ and }101\}$ is not in RE.


How to prove LastToken problem is NP-complete

Here is a reduction from the Hamiltonian path. Given a graph $G=(V,E)$. Add a vertex $v_0$ to the graph and connect it to all vertices in the graph. Set $t(v_0)=2$. Set $t(u) = 1$ for all $u \neq v_0$.

Claim. The previous reduction is correct. Try to prove it formally as an exercise.

Edit. Here is a brief proof of correctness. We have to prove that the created instance is a yes-instance of your problem, if and only if the given instance is a yes-instance of the Hamiltonian path problem. First, let $G$ be a yes instance of the Hamiltonian path. Let $v_1, \dots v_n$ be a Hamiltonian cycle in the graph. Now we describe a winning strategy for the last-token, where in the step $i$ we take two tokens from the vertex $v_{i-1}$ and add one to the vertex $v_{i}$. It is easy to prove by induction, that in step $i+1$ all vertices $v_0, \dots v_{i-1}$ have no tokens in them, the vertex $v_i$ has two and all vertices $v_{i+1}, \dots v_n$ have exactly one token. In the $n-th$ step we take the two tokens left in $c_n$ and put one token in $v_0$ and we are done. Note that $v_i$ has always a common edge with $v_{i+1}$ since the are consecutive in a Hamiltonian path.

On the other hand, assuming the reduced instance is a yes-instance, we prove that the given graph is Hamiltonian. Since all but one vertex have exactly one token. We have only one choice for the first vertex. In each step we take two tokens from a vertex and add a token to another one. It is easy to prove inductively that in each step all but at most one vertex have at most one token in them. One vertex can have two tokens wich is the only choice for the next step. Using this claim, it is also easy to prove that to vertex can be chosen twice. Hence, if we were able to choose $n+1$ vertices, we must have a permutation of the $n$ vertices with $v_0$ starting in $v_0$ and this permutation must be a Hamiltonian path since we always have an edge between two consecutive choices in the game.


How to Identify which instructions are represented by this microcode

Microcode instruction sets typically have more fields than ordinary instruction sets.

Sometimes this is called wide word, as a very long instruction can offer access to multiple hardware components in the same cycle for many operations to be performed in parallel.

In simpler microcoded systems, instead of being wide in the extreme, the numerous (smaller) fields offer access to simple operations (though still in parallel), like read from memory, write, transfer one register to another, etc..

We also generally won't see overlapping fields in microcoded instruction sets, like we do with normal instruction sets.   Look at MIPS for example, which has half a dozen different instruction forms, like J-type and R-type where the fields overlap and the hardware decides how the fields are to be interpreted based on the instruction type.

In microcode, you just use the fields you need in each microcoded instruction, instead of choosing a different instruction type.  This keeps the micro-machine simpler, at an expense of either needing a wider microcoded instruction set, or having fewer micromachine features, like fewer micromachine registers and/or hardware units (like adders).

Because of the large number of instruction fields in each microcoded instruction, we can expect multiple operations per instruction.

In your example, I think we can assume the following are all encoded in a single instruction:

MAR = PC       // transfer PC to address bus
PC = PC + 1    // increment PC register
IR = MBR       // transfer data bus to IR register
Assert MR      // assert memory read

And it looks like the "put addr 7000 into MAR, Assert MAR" is a programming comment associated with this instruction.

N.S. Matloff
 has a description of a 32-bit microcoded instruction set that looks roughly like what you're showing.  You can see the large number of fields, and also that by comparison to a normal instruction set.  There are fields of the instruction for branching, fields for alu operation, register source & target, memory access, etc..  These fields exist in every instruction; there are no overlapping fields as there is only one instruction type.


Path in a graph with a given xor of weights of edges

Arbitrary paths

If you want to know whether there exists a not-necessarily-simple path from $a$ to $b$ with weight $x$, here is a one-sided test:

Compute a cycle basis for the graph, $c_1,\dots,c_k$; this can be done in polynomial time.  Let $p$ denote any simple path from $a$ to $b$.  Let $W(p)$ denote its weight and $W(c_i)$ the weight of the cycle $c_i$.  Then there exists a path of weight $x$ only if $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$ (with all operations taken over $\mathbb{F}_2$).  This condition can be tested in polynomial time.

Why does this work?  If there exists a path from $a$ to $b$, then it can be written as the xor (symmetric difference) of $p$ and some subset of $c_1,\dots,c_k$.  Thus, its weight is given by $W(p)$ xored with the selected $W(c_i)$ values.

However, the converse doesn't necessarily hold.  If $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$, there is no guarantee that there exists a path from $a$ to $b$.  (The linear combination of $W(c_1),\dots,W(c_k)$ might correspond to a set of cycles that form a disconnected graph, and doesn't provide any way to form a path from $a$ to $b$.)

I don't know whether there is a polynomial-time algorithm or not.

Simple paths

If you want to require the path to be a simple path, then the problem is NP-complete, by reduction from Hamiltonian path.

Let $G$ denote your graph.  Suppose it has $n$ vertices, with vertices numbered from $1$ to $n$.  Modify it to replace each vertex $v$ with two copies $v_0$ and $v_1$, and add an edge between $v_0$ and $v_1$.  For each edge $(u,v)$ in the original graph $G$, we'll introduce edges $(u_1,v_0)$ and $(v_1,u_0)$ in the new graph, with weight zero ($0^n$).  Each the edge $(v_0,v_1)$ will have a weight from $\mathbb{F}_2^n$ that has the $v$th bit set and all other bits clear (i.e., its weight is $0^{v-1} 1 0^{n-v}$).  Let $x$ denote a weight with all bits set (i.e., $1^n$).

Now there exists a simple path from $a_0$ to $b_1$ of weight $x$ in the new graph if and only if there exists a Hamiltonian path from $a$ to $b$ in the original graph.  Therefore, any algorithm for your problem with paths restricted to simple paths immediately yields an algorithm for the Hamiltonian path problem, which is known to be NP-complete.


I don't know that there is any "standard" or "best" approach, as the technique that is appropriate will depend on the setting.  However, I recommend you start by looking at the algorithms used by rsync and the Remote Differential Compression scheme.  More generally, look at techniques for delta compression.


Using pumping lemma to show a language is not context free(Complicated)

Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and

$i_1,...,i_{2m}=0$
$j_1,...,j_{2n}=0$
$k_1,...,k_{o}=0$

$w = a\; b^{2(p+2)}\; d\; e^{2(p+1)}\; g\; h^{p} $

Then apply pumping lemma (it should be easier ;-).

If you want to "reduce" $L$ to $L' = \left\{0^i1^j2^k|1\le \:i<j<k\right\}$ then you must use closure properties, in particular CFLs are:

closed under homomorphism
closed under reverse homomorphism
closed under reversal

The homomorphism that you can use is: $H(a) = H(c) = H(d) = H(f) = H(g) = H(q) = \epsilon, H(b) = \bar{2}, H(e) = \bar{1}, H(h) = \bar{0}$

Applying $H$ to the language gives $H(L) = \{ \bar{2}^{2m} \bar{1}^{2n} \bar{0}^{o} \mid m > n > o > 0\}$

Then you can use a reverse homomorphism $\varphi(2)=\bar{2}\bar{2}, \varphi(1)=\bar{1}\bar{1}, \varphi(0) = \bar{0}$ and you get:

$\varphi^{-1}( H(L)) = \{ 2^m 1^n 0^o \mid m>n>o>0 \}$

and finally apply closure under reversal:

$(\varphi^{-1}( H(L)))^R = \{ 0^o 1^n 2^m \mid 0<o<n<m \} = L'$

If $L$ is CF then by closure properties $(\varphi^{-1}( h(L)))^R = L'$ should be CF, which is not the case.


Number of probes in a successful search in open address hashing

You are almost right about "5 probes". It will take, in fact, 6 linear probes to find an empty slot if the probe starts at index 0 of a table with slots 0 through 4 occupied (and slot 5 available). They are 5 failing probes and 1 successful probe at last.
However, you are, apparently, skipping the meaning of the word "expected". That word here means "on average" basically.

While the number of probes can be as big as 4 sometimes, it can be as low as 1 many times as well. So it is not surprising the expected number of probes can be as low as 2.
To be exact and rigorous, the phrase "expected number" as in "the expected number of probes" and "the maximum expected number of probes" has a specific meaning defined in mathematical terms.

The expected value of a discrete random variable $X$ is $E[X]=\sum_xx\cdot \text{pr}\{X=x\}$, where $\text{pr}\{X=x\}$ is the probability of $X$ taking value $x$.

"The expected number of probes" is the shorthand for "the expected value of the discrete random variable that stands for the number of probes." You can understand it simply as "the average number of probes".
I would recommend you read sections in the textbook you are reading that introduce or review related concepts. Or section 3, Discrete random variables in Appendix C of the book CLRS.


Term for members of a class that are not inherited

Just a member variable. If you want to specify that it is not inherited, I suppose you could call it 'noninherited member variable'. Wiktionary lists this as a term in computing.


If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

For 9x9 Sudoku, no.  It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.


Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?

This is explained in Wikipedia. Given $n,m$, the false positive probability is
$$
\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k.
$$
This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation
$$
\left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k,
$$
which is good if $m$ is large. We can optimize the latter expression using calculus, and the result is some expression which is very close to $(m/n) \ln 2$. This is a calculation that I leave to you.


Why should I use Huffman enoding if it makes my data longer?

I cannot see the benefit of Huffman coding in XML. First, the coding dictionary of each symbol has to be known on the receiving end, i.e.

<dictionary>0111....</dictionary>

Second, the Huffman coded data should be represented as 8-bit data to be space efficient. For example, your Huffman code for 2TR,07N becomes &xECD1;&x50;. However, 8-bit data is incompatible to XML because a lot of symbols are reserved for tags "<>" or attributes ":=".

If you are free to use any compression technique, I would suggest gzipping your data and then encoding the 8-bit data as base64. In this case, the string
 (264 characters without comma)

2TR,07N,2TS,082,084,2TT,2TU,2TV,2TW,2TX,2TY,2TZ,2U0,2U1,2U2,2U3,2U4,081,083,2U5,2U6,2U7,2U8,2U9,2UA,2UB,2UC,2UD,2UE,2UF,2UG,2UH,2UI,012,014,015,016,2UJ,2UK,2UL,2UM,2UN,2UO,2UP,2UQ,2UR,2US,2UT,2UU,2UV,2UW,2UX,2UY,2UZ,2V0,2V1,2V2,2V3,2V4,2V5,2V6,2V7,2V8,2V9,2VA,2VB,2VC,2VD,2VE,2VF,2VG,2VH,2VI,2VJ,2VK,2VL,2VM,2VN,2VO,2VP,2VQ,2VR,2VS,2VT,2VU,2VV,2VW,2VX

will be encoded as (232 characters)

H4sIACSf+1YAAxXPS1ZCMRBF0b5jSeMlgmDTDyAKfuDVFZ3/QNg0zlrVqcrOmE9tWn22MZ/btB5a
mGeVol9d9Kf/NmpS19C9Fna6bvNSD1pprUc96VkvetVGW+30pn2bune7O32p2/67PnTQUXz1pW/9
6KSzOIuzOIuzOIuzOMMZznCGLf4VvrgfvvCFL3zhC1/4whe+8IUve/GEJzzhCU94whOe8IQnPOEJ
T3hyubsCdDvGCWABAAA=

It is worth noting that gzip has Huffman coding in design, and the base64 encoding is a common practice for embedding PNG images in HTML.

References:

https://stackoverflow.com/questions/1091945/what-characters-do-i-need-to-escape-in-xml-documents
https://stackoverflow.com/questions/7849067/how-can-i-convert-a-string-into-a-gzip-base64-string


determine if a machine prints a certain string in less time than it takes to run the machine itself?

Your question is somewhat unclear, but here is something you can prove using the time hierarchy theorem. We will use the convention that a Turing machine computing some function prints the result at the end, and prints nothing except that. Suppose $T$ is a machine that accepts the code of a machine $P$ running in time $O(n^\alpha)$ and an input $x$, and returns the output of $P(x)$ in time $O(n^\beta)$ for $1 \leq \beta < \alpha$. Using $T$, we can evaluate the function computed by $P$ in time $O(n^\beta)$, so $\mathrm{Time}(n^\alpha) \subseteq \mathrm{Time}(n^\beta)$, which contradicts the time hierarchy theorem.


4-digit 5's complement of a negative number

Let me demystify $b$'s complement.

Let $b \geq 2$ be an integer. Given a $d$-digit integer $x$ is base $b$, we want to find a $d$-digit integer $y$ such that $y \equiv -x \pmod{b^d}$. Why is this useful? Suppose that $z$ is also a $d$-digit integer, and assume that $z-x \geq 0$. Then $z-x \equiv z+y \pmod{b^d}$, and so if we add $z$ and $y$ and ignore the carry, we will get $z-x$ to achieve subtraction.

How do we find $y$, the $b$'s complement of $x$? We take $y =k\times b^d-x= b^d-x = (b^d-1-x)+1$ (with $k\in \mathbb{Z}$, let $k = 1$). Now the representation of $b^d-1$ in base $b$ consists of $d$ digits of $b-1$, so $b^d-1-x$ is obtained by inverting all the digits of $x$ (subtracting them from $b-1$). This is $b$'s complement: the $b$'s complement $y$ of $x$ is obtained by inverting all digits and adding 1.


Whether $\mathsf{HALT}_{M_0}$ is decidable or not depends on $M_0$. For example, if $M_0$ always halts, the $\mathsf{HALT}_{M_0}$ is trivially decidable, whereas if $M_0$ interprets its input as a Turing machine $M$ which it runs on the empty input, then $\mathsf{HALT}_{M_0} = \mathsf{HALT}_\epsilon$ is undecidable (see below).

The language $\mathsf{HALT}_{w_0}$ is always undecidable, as a simple diagonalization shows. Suppose that $M$ could solve $\mathsf{HALT}_{w_0}$. Using the recursion theorem, one can construct a machine $M'$ which acts as follows:

Run $M$ on $M'$. If $M$ returns YES, go into an infinite loop, otherwise halt.

Notably, $M'$ doesn't depend on its input. Considering what happens when it is run on $w_0$, we reach a contradiction just as in the standard proof of undecidability of the halting problem.


Is Half - Palindrome subset of a context-free language context-free?

Let $L=\{a^n b^n c^m d d c^k b^k a^m\}$, then $L$ is context-free. I claim
$L'=\{a^n b^n c^n d\}$ which is not context-free.

Suppose $x\in L'$. Then $x$ must be of the form $a^i b^j c^k d$. Then $x x^R = a^i b^j c^k d d c^k b^j a^i \in L$, which means that $i=j=k$. Conversely, it's clear that $\{a^n b^n c^n d\} \subseteq L'$.


$NL^2 = NDSPACE(\log^2n)$ is closed under complement

The Immerman–Szelepcsényi theorem states that $\mathsf{NSPACE}(s(n))$ is closed under complementation whenever $s(n) \geq \log n$.


Periodic Pattern recognition In a Sales Log

These are the steps you need to follow.

Model

You need to pick a model that you think explains your data. It can be very simple (e.g. linear regression) or very complex (e.g. a four-layer neural network). You want to pick as simple a model as possible!

Example: Assume sales follow $s(x) = a + b\sin(cx)$.
Train

Using one part of the data, you determine which parameters of the model fit your data best. The method of training depends on your model of choice.

Example: You fit the parameterized sine against the first half of your data with least-squares and find $(a,b,c) = (3,77, 13)$ is "best".
Validate

Inspect how well the model explains the rest of the data. You will have to decide in step 1 how you quantify quality here, and what your acceptance criteria are.

Separately, if that makes sense in your domain, apply the model entirely different data sets that should follow the same model if your hypotheses are correct. Does it predict anything there? What does the answer say about your model and/or your assumptions?

Example: Inspecting the squared error between $3 + 77\sin(13x)$ and the second half of the timeline data, you notice it is far too large.
Iterate

Unless the predictive quality of your model is good, go back to step 1. Sometimes, more training data can be the answer, too; note how that weakens your result, though.


Relation and difference between information retrieval and information extraction?

Information retrieval is based on a query - you specify what information you need and it is returned in human understandable form.

Information extraction is about structuring unstructured information - given some sources all of the (relevant) information is structured in a form that will be easy for processing. This will not necessary be in human understandable form - it can be only for use of computer programs.

Some sources:

Information Extraction vs Information Retrieval
From  Information Retrieval to Information Extraction
Information    Extraction Stanford PPT
Introduction to Information Retrieval(link to place in the book with definition)


Prove the equivalence between a CFG and a Context free language

Since this is a very simple "linear" grammar, its language can be determined by looking at the possible derivations.

Clearly a successful derivation has to start with $S\to a^2Tb$, then repeats $k$ times the production $T\to a^3Tb^2$ and closes with $T\to \epsilon$. That will give strings of the form $a^{2+3k}b^{1+2k}$ with $k\ge 0$. (1)

Then we need to establish that these are exactly the strings of the form $a^ib^j$ with $2i=3j+1$. (2)

One direction is easy, strings of the form (1) satisfy (2) -- you solved that yourself -- by observing that
$2(2+3k) = 3(1+2k)+1$.

Your proof for the other direction sounds good, but it is not clear to me how one argues that the induction has step size $5$ (other than by trial and error).

The following would work. Start with (2) for natural numbers $i,j$.

This implies $3j+1$ is even (and non-negative).

Or, $3j$ is odd, so $j$ is odd, which means it is of the form $j=2k+1$ for $k\ge 0$.

Then $2i=6k+4$, or $i=3k+2$, and we are done.

This argument seems rather ad hoc. Note the similarity between this exercise and linear algebra. There are two different representations for a line in 2D: using vectors or equations. Here these are:

$\{ (2,1)+ k\cdot(3,2) \mid k\in \mathbb R \}$
$\{ (x,y) \mid 2x-3y=1 \}$

Unfortunately, I do not think linear algebra tricks directly work, as we here must restrict ourselves to integers and not the real numbers.


(I assume by "error propagation" you mean what I call "error back-propagation.")

On page 231 of Neural Networks (by Haykin), he states that back propagation always converges, although the rate can be (in his words) "excruciatingly slow."

I think what you are asking though is not whether the algorithm will always converge, but whether it will always converge to the optimal answer. And unfortunately, it won't. Even in simple cases like yours, it's entirely possible that there are local minima which are not global minima.

Dealing with local extrema is a hugely important topic in optimization, and you can find a plethora of advice on how to deal with it. One of the most common is what it sounds like you're doing: random restarts (i.e. just run the algorithm multiple times, each starting from a random place).

To figure out if there's a bug in your code, I would print out the error term and verify that it decreases at each iteration. If so, then you're probably just hitting a local minima.


Can we prove that a time machine is impossible using the Halting Problem?

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

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

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


Given a string and a CFG, what characters can follow the string (in the sentential forms of the CFG)?

I'll describe an algorithm that works. It's running time shouldn't be too bad. You can precompute quite a bit of this as well.

I'll assume that $a$ does not contain nonterminals (though it's probably easy to adapt to that case) and that you don't know $x$, $y$ or the derivation of $a$. I'll also assume your grammar doesn't contain productions that are never used in any derivation ($A \rightarrow A$ for example).

The main issue really is to parse $a$, as you want to know what kind of states you end up in, so you know what can follow $a$. This is not so easy as you don't know $x$.

We use an adaptation of Earley's algorithm. You'll want to understand that algorithm first. Our algorithm works in almost the same way, except our initialization and completion steps are different.

For the initialization, we seed our first set with an Earley item for every occurrence of $a_1$ (the first character in $a$) in any production of your grammar. We set the back pointer of this item to -1, an invalid value. This is important in our modified completion. Essentially, the -1 means 'I have no idea where this production was started'.

Now, we perform the Earley algorithm separately for every possible such initial Earley item. We can't simply do all of them at the same time, as the parses may interfere with each other. I can't easily see a faster method than backtracking here.

For the completion step, we only have to make a modification to handle -1 back pointers. As we've completed a production whose origin we don't know, we are in trouble. However, the method used to compute $LALR(1)$ lookahead sets by Pennello and DeRemer saves us: what we need here is exactly the $LALR(1)$ lookahead sets. Every item in these lookahead sets has a corresponding position in the grammar, which in turn corresponds to a possible continuation of the completed production.

Unfortunately, I don't really see any other choice than to backtrack once again here. For every position in the lookahead set, you perform the completion step with this position, and continue the parse from there. You do this separately for every parse. Note that if your grammar is $LALR(1)$, your lookahead will uniquely determine which position you have to go to, so you don't have to backtrack.

You continue the above algorithm one character beyond $a$, where you consider this extra, virtual character to be the 'any character', which immediately gives you the 'follow' set you are looking for - any time the scanner phase finds something for this final set, you can add this character to your answer set.

Edit: I think I've found the method that removes most of the overhead introduced by the backtracking. We associate with every Earley item a set of identifiers, which are strings, as we will need to use prefixes of these identifiers. On initialization, we add all initial items to the Earley set, and associate a unique identifier with every set.

On the scanner and predictor steps, identifiers are carried over to new items. Earley items in the same Earley set that only differ in their identifiers are merged together by merging their identifiers together. Note that we can perform scanner and predictor steps on these new items with identifiers, without having to perform this step for every identifier separately.

The completer considers the identifiers separately, and only completes an item if the corresponding item in the earlier itemset has an identifier that is a prefix of the identifier. For every possible completion (so for every item in the $LALR(1)$ lookahead set), we append a unique character to the identifiers of the completed items.

Essentially, we do the backtracking using these identifiers, so that we don't do double work in the scanner and predictor steps.


Context free grammar transformation to Normal Form

If you are trying to convert the grammer into Chomsky Normal Form, consider applying this algorithm that can create a new normal grammer from an existing non-normal one.


How many possible prime implicants are there in total for a 4-variable Karnough-map?

Hint: $81 = 3^4$. So each variable can appear in a prime implicant in three different forms. Can you figure out which?


Increasing the speed of memory typically involves increasing the size of the bit cell. For example increasing the capacitor size in a DRAM (which using one transistor and one capacitor to store a bit) allows faster reading of the bit but obviously also reduces the number of bit cells that can be fit onto a chip. (Similarly, SRAM is less dense but faster than DRAM.)

From an economic perspective, since speed is generally valued, techniques to increase speed are allowed spend more effort (i.e., cost) in research, design, and manufacture to increase speed.

Aside from the cost factor (users seeking higher capacity will seek lower cost per bit), higher capacity memories are generally slower from a combination of lesser integration and greater distance between a bit cell and the consumer of the data. Greater integration (on the same chip, in the same package, on the same board, in the same system/enclosure) not only reduces physical communication overhead (crossing physical boundaries has overhead) but also interface overhead as less integrated interfaces are typically more generic and less optimized for one specific use.

Indexing overhead is an additional factor making larger memories slower. Hardware effectively traverses a binary tree to select the desired data. (This factor is typically minor, but it seemed worth mentioning.)

Another significant tradeoff in memory system design is access granularity/randomness. Larger access granules and less random access correlate with increased density/lower cost per bit. This is also a result of economic and physical factors.


Find pth percentile of a stream of numbers

I'm afraid that it is not possible to solve this problem with above conditions. Sooner or later, while reading next element from stream, you will run out of memory and will have to throw away one of buffered elements. But without having any constraints on further elements in stream, it is always possible to construct such sequence of further elements in stream, so that thrown out element is the searched one.

A practical commercial-grade solution exists, though it produces approximate result:

Allocate memory for as many numbers as you can afford
Use reservoir sampling atop of allocated memory to sample numbers from stream
When end of stream is reached, search for percentile among samples

To get exact solution, you need to either know number of elements in advance, or to have enough memory, or to have knowledge of stream properties (e.g. stream is monotonic). Keywords are "running median" and "n-th order statistics".


Sieve of Eratosthenes vs. Sieve of Sundaram

Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes.  In this evaluation, it is important to note that these intense considerations are only necessary for ranges of primes in the order of a hundreds of millions or more:  A simple trial division algorithm can be sufficient for a range of up to about a million and just about any properly optimized sieve can sieve to a billion in a few seconds to tens of seconds in just about any language that is not interpreted (compiled or Just-In-Time - JIT - compiled to native code).  It is large ranges of a billion an up where things get interesting in that the amount of memory used becomes a consideration such that it may be a requirement to implement page segmentation so as to be able to efficiently use the available memory.

First, note that there are three considerations on what makes a particular sieve fast, as follows:

The number of operations and how these operations increase for increasing ranges for a particular sieve, which latter evaluation is what is indicated by the big-O value for asymptotic execution complexity for large ranges.
The complexity of each individual culling operation as in machine cycles per operation which usually isn't considered in given big-O functions as per point 1.
The ability to add page segmentation without impacting excessively on the above two requirements, which segmentation is necessary to reduce memory requirements for large ranges so the sieve can be run at all, to achieve better cache associativity which otherwise will have a (large) negative impact on point 2 above.

Many mistakenly think that the best big-O performance is the best algorithm, but that is an error in analysis:  An algorithm may have the best big-O performance as in (say) O(N) for sieving (where N is the sieving range) but require either many more operations or such complex operations that the execution time for each operation is so high that the total time to execute to a given range may be much higher than for an algorithm with less operations/complexity such that it can never catch up to an algorithm with worse big-O performance for practical achievable sieving ranges; thus, it is usually not the best or only consideration for comparison and is more useful for predicting the performance of a given algorithm with increasing range as compared to itself.

The main three contenders are usually the following with the given big-O performance characterizations following:

The Sieve of Eratosthenes (SoE) - O(N log(log (N)))
The Sieve of Sundaram (SoS) - O(N log(N))
The Sieve of Atkin (SoA) - O(N) (i've added this one as it is usually considered...)

Let's consider these in order:

First, it is pointless to implement the SoE without including the very simple "odds-only" optimization that reduces the number of operations by a factor of about two and a half to about the same number of culling operations as the sieving range.  However, there is no reason to stop there, and with a little added complexity in using the maximally wheel factorized "combo sieve" as per the Wikipedia article, one can reduce this to about a quarter of the sieving range for ranges of about a billion to about a third of the sieving range for sieving ranges of about a trillion.  Thus, with maximum wheel factorization the number of culling operations aren't much more than the best of the other algorithms.  The majority of the inner culling loop(s) in which the SoE spends most of its time can be reduced to a very simple native code single clock cycle read/modify/write instruction with maximum optimization techniques so that even when averaged across supporting code and parts of the code that can't use this optimization, the average is still only two to three CPU clock cycles per culling cycle for ranges of trillions.  While it's true that operations get gradually a little slower on the average for larger ranges, they increase relatively slower than the practical application of the other algorithms.
The unmodified SoS algorithm can never approach the performance of other sieves due to not specifying the proper limits for the i and j variables, which can easily be limited so that the culling function i + j + 2ij never exceeds one half of the culling range value as larger values exceed the sieve buffer range.  However, the SoS still has many more operations than the "odds-only" SoE as it culls by the factors of all odd values rather than only the prime factors as for the SoE, which is why it has the O(N (log N)) performance rather than O(N ((log (log N))) performance; this makes a significant difference in the number of culling operations for culling ranges of a billion and above, and while the number of operations can be reduced by such techniques as pre-culling for small values of factor, this optimization (and more) can also be applied to the SoE.  Now, it could be improved by using a recursive loop so that it uses a secondary source of primes to generate the i values and letting the j values start from i up to maximum, and then observing that every increment from i + j + 2ij to i + (j + 1) + 2i(j + 1) is just i + j + 2ij + (1 + 2i) or just the value of the sieving base prime/factor, but that is exactly the algorithm for the "odds-only" SoE.  Once we've optimized the SoS into the SoE, we can apply the same further optimizations as it now identical.  So the SoS can not be considered as a competitor as in its simple form it is much less efficient and in its maximally optimized form it is the SoE.
The SoA is by definition a wheel factorized sieve by the prime factors of 2, 3, and 5.  The SoA once (and perhaps still does) enjoy quite a bit of Internet hype due to it's very good big-O performance of O(N).  However, while it does perform according to that relation with a constant about 0.2517 times N number of culls starting at a very low N value, all is not so rosy as believed:  It doesn't match that combined performance for any reasonably large range requiring page segmentation where primes squares-free spans get huge as compared to the page segment range and the complexity of the continuously increasing culling span means that the true combined big-O performance is much worse than that of the fully wheel optimized Sieve of Eratosthenes while the code complexity in implementing it even this efficiently is worse than the maximally wheel factorized SoE.  Much of the confusion comes about due to the reference page segmented implementation of the SoE by Atkin and Berstein, which, while reasonably fast in sieving to a billion, did not prove (even close) its claim of linear asymptotic big-O complexity with increasing range as it is very slow for larger ranges, and only beat the reference SoE to which it is compared for a range of a billion by artificially limiting the level of wheel factorization of that implementation.  As to the culling speed, due to the increased complexity of the span increasing with every successive operation, typical speed is about twice as slow as for the SoE in CPU cycles per operation, so it would have to have half the number of operations as the maximally wheel factorized SoE, which it never does within practical ranges.

In conclusion, for large sieving ranges using page segmentation, the Page Segmented SoE is a clear winner with the number of cull operations ranging only up to about 0.35 to very large ranges of 1e16 or more and the number of machine cycles when efficiently compiled to native machine code as little as under two CPU clock cycles per operation for small ranges under a billion and only increasing to the order of ten CPU cycles per operation for very large ranges (of about 1e19) in some common implementations such as primesieve, which can also be multi-threaded for even faster execution times.  Even when compiled in Just-In-Time (JIT) environments such as the Java Virtual Machine (JVM), Microsoft's DotNet, or even JavaScript engines as are builtin to modern browsers, the performance is still only about ten CPU cycles per operation with the number of operations the same.  In contrast, the unmodified SoS is many times slower and when fully optimized just becomes the SoE with its only feature over the SoE that it doesn't need the secondary primes feed for a page segmented version and thus the code optimized to the same extent is somewhat simpler, and the SoA never comes anywhere close to the number of CPU clock cycles per cull operation at any point as  for larger culling ranges such that the reduced number of culling operations is never enough lower to make up for this discrepancy nor for the increased complexity of implementation.


Difference between the Magnitude and the Phase Spectrum of the Fourier Transform?

Fourier Transform changes basis from time (spatial data) to frequency. To encode frequency we need amplitude (magnitude) to know how strong is signal at given frequency and phase to know when sine started - in what moment of its phase we are now.

Example: take input signal $5\sin(x + \pi)$, here phase is $\pi$ and magnitude is $5$.


What do you mean by real? You can define as many logic gates as you want and build them. However, in a boolean logic with 2 inputs, there are 16 different combination of outputs. On the other hand, it proven that $\{AND,NOT\}$, $\{OR,NOT\}$, $\{NAND\}$ and $\{NOR\}$ are functionally complete (which means we can build all other combination from 16 outputs with only using gates in those sets ).

However, you may build a new gate directly with a technology (let say MOSFET) and use another name. You can still build that gates using one of the comprehensive gate set.


Two counterexamples are:

$(\lambda x. b x (b c)) c$ and $(\lambda x. x x) (b c)$ (Plotkin).
$(\lambda x. a (b x)) (c d)$ and $a ((\lambda y. b (c y)) d)$ (Van Oostrom).

The counterexample detailed below is given in The Lambda Calculus: Its Syntax and Semantics by H.P. Barenredgt, revised edition (1984), exercise 3.5.11 (vii). It is attributed to Plotkin (no precise reference). I give an incomplete proof which is adapted from a proof by Vincent van Oostrom of a different counterexample, in Take Five: an Easy Expansion Exercise (1996) [PDF].

The basis of the proof is the standardization theorem, which allows us to consider only beta expansions of a certain form. Intuitively speaking, a standard reduction is a reduction that makes all of its contractions from left to right. More precisely, a reduction is non-standard iff there is a step $M_i$ whose redex is a residual of a redex to the left of the redex of a previous step $M_j$; “left” and “right” for a redex are defined by the position of the $\lambda$ that is eliminated when the redex is contracted.
The standardization theorem states that there if $M \rightarrow_\beta^* N$ then there is a standard reduction from $M$ to $N$.

Let $L = (\lambda x. b x (b c)) c$ and $R = (\lambda x. x x) (b c)$. Both terms beta-reduce to $b c (b c)$ in one step.

Suppose that there is a common ancestor $A$ such that $L \leftarrow_\beta^* A \rightarrow_\beta^* R$. Thanks to the standardization theorem, we can assume that both reductions are standard. Without loss of generality, suppose that $A$ is the first step where these reductions differ. Of these two reductions, let $\sigma$ be the one where the redex of the first step is to the left of the other, and write $A = C_1[(\lambda z. M) N]$ where $C_1$ is the context of this contraction and $(\lambda z. M) N$ is the redex. Let $\tau$ be the other reduction.

Since $\tau$ is standard and its first step is to the right of the hole in $C_1$, it cannot contract at $C_1$ nor to the left of it. Therefore the final term of $\tau$ is of the form $C_2[(\lambda z. M') N']$ where the parts of $C_1$ and $C_2$ to the left of their holes are identical, $M \rightarrow_\beta^* M'$ and $N \rightarrow_\beta^* N'$. Since $\sigma$ starts by reducing at $C_1$ and never reduces further left, its final term must be of the form $C_3[S]$ where the part of $C_3$ to the left of its hole is identical to the left part of $C_1$ and $C_2$, and $M[z \leftarrow N] \rightarrow_\beta^* S$.

Observe that each of $L$ and $R$ contains a single lambda which is to the left of the application operator at the top level. Since $\tau$ preserves the lambda of $\lambda z. M$, this lambda is the one in whichever of $L$ or $R$ is the final term of $\tau$, and in that term the argument of the application is obtained by reducing $N$. The redex is at the toplevel, meaning that $C_1 = C_2 = C_3 = []$.

If $\tau$ ends in $R$, then $M \rightarrow_\beta^* z z$, $N \rightarrow_\beta^* b c$ and $M[z \leftarrow N] \rightarrow_\beta^* (\lambda x. b x (b c)) c$. If $N$ has a descendant in $L$ then this descendant must also reduce to $b c$ which is the normal form of $N$. In particular, no descendant of $N$ can be a lambda, so $\sigma$ cannot contract a subterm of the form $\check{N} P$ where $\check{N}$ is a descendant of $N$. Since the only subterm of $L$ that reduces to $b c$ is $b c$, the sole possible descendant of $N$ in $L$ is the sole occurrence of $b c$ itself.
If $\tau$ ends in $L$, then $M \rightarrow_\beta^* b z (b c)$, $N \rightarrow_\beta^* c$, and $M[z \leftarrow N] \rightarrow_\beta^* (\lambda x. x x) (b c)$. If $N$ has a descendant in $R$ then this descendant must also reduce to $c$ by confluence.

At this point, the conclusion should follow easily according to van Oostrom, but I'm missing something: I don't see how tracing the descendants of $N$ gives any information about $M$. Apologies for the incomplete post, I'll think about it overnight.


Is the set of all context-free languages contained in the set of all languages that have a w-grammar?

The class of languages accepted by this kind of grammar is known as linear languages (the definition on Wikipedia is slightly different, but equivalent). According to Wikipedia, the language of all balanced parentheses (generated by $S \to SS \mid (S) \mid \epsilon$) is context-free but not linear.


How does RAID-5 algorithm locate the right device?

Extracted from: HERE

// Assume all indexes are zero-based.
// Algorithm = Left-Asym

ChunkIndex = LogicalSector / SectorsPerChunk
StripeIndex = ChunkIndex / (DiskCount - 1)

ParityDisk = (DiskCount - 1) - ((StripeIndex / ParityDelay) % DiskCount)

DataDisk = (LogicalSector % (SectorsPerChunk * (DiskCount - 1))) / SectorsPerChunk
If ParityDisk <= DataDisk:
    DataDisk = DataDisk + 1

PhysicalSector = (LogicalSector / SectorsPerChunk) * (DiskCount - 1)
PhysicalSector = PhysicalSector * SectorsPerChunk
PhysicalSector = PhysicalSector + (LogicalSector % SectorsPerChunk)


Under what conditions is K-means clustering transformation-invariant?

The answer depends on your K-means algorithm, but what follows should work for standard algorithms.

You will get the same result if your transformation $T$ satisfies two conditions:

It preserves distances: $d(z,w) = d(T(z),T(w))$, where $d$ is your metric, say $d(z,w) = \|z-w\|$.
It preserves averages: if $\sum_i p_i z_i$ is a convex combination that $T(\sum_i p_i z_i) = \sum_i p_i T(z_i)$.

You can check this by going over the algorithm, showing that it always makes the same choices.