Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?

Let $A = \langle a_1, \dots, a_n \rangle$ be the input array.
I will only consider the case $n \ge 3$, otherwise the problem is trivial.

The key property is that the order relation between all but one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$), and "less than" if $A$ is some circular shift of a decreasing array. Examining the first and last elements suffices to determine if the shift is trivial or not.

In practice you can determine the type of $A$ in constant time, as follows:

Look the majority value $x$ among $\textrm{sign}(a_1-a_n)$, $\textrm{sign}(a_2-a_1)$, and $\textrm{sign}(a_3-a_2)$.
If $x = +1$ then $A$ is some circular shift of an increasing array. If $\textrm{sign}(a_1-a_n)=-1$, $A$ is of type "ascending", otherwise it is of type "ascending rotated".
If $x = -1$ then $A$ is some circular shift of a decreasing array. If $\textrm{sign}(a_1-a_n)=1$, $A$ is of type "descending", otherwise it is of type "descending rotated".

As for returning the maximum, I will only discuss the case in which $A$ is a circular shift of an increasing array (the complementary case is handled similarly). Notice that, if the maximum element is in some position $a_j$, then all $a_1, \dots, a_j$ are larger than or equal to $a_1$, while all ements $a_{j+1}, \dots, a_n$ are smaller than $a_1$. This allows you to binary search for the last element that is larger than or equal to $a_1$, i.e., $a_j$.


Prove the existence of a proposition logical formula so that following conditions are fulfilled

The formula $\psi$ is called an interpolant and the method of finding such an interpolant is called Craig interpolation. On the Wikipedia article you can find more information about it, including a proof that interpolants always exist in propositional logic.


Your algorithm makes $\lfloor \log n  \rfloor+ 1$ comparisons for an array of length $n$, which is at most $2 \log n$, which is $O(\log n)$.  Hence, $\lfloor \log n  \rfloor+ 1 = O(\log n)$.

In more detail, recall that the big-O notation subsumes constant factors. A function $f(n)$ is said to be $O(\log n)$ if there exist positive constants $c$ and $n_0$ such that $f(n) \le c \log n$ for all $n \ge n_0$.  In our case, we want to prove $\lfloor \log n \rfloor +1 = O(\log n)$.  To prove the existence of positive constants $c$ and $n_0$ satisfying the desired condition, observe that $\lfloor \log n  \rfloor+ 1 \le \log n + \log n = 2 \log n$, for all $n \ge 2$.  So we can take $c = 2$ and $n_0 = 2$.


If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

You are correct, without further information we can only say that $A\cap B$ is recognizable.

A simple example would be to let $B$ be any recognizable (but not decidable) language - the Halting Problem for example, if you want to be melodramatic, and let $A = \Sigma^{\ast}$. Then $A \cap B = B$, so clearly can't be decidable.

It is of course possible that the intersection happens to be decidable, (for example if $A \cap B = \emptyset$ is a trivial example), but this may not be true in general.


Making random sources uniformly distributed

Consider this: get two elements $x_0$ and $x_1$ from $S$. If $x_0x_1$ is $aa$ or $bb$ then discard them and repeat. Otherwise return $0$ for $ab$ and $1$ for $ba$, events that occur with the same probability $p_ap_b$.

This will use $2n$ elements from $S$, $n$ the number of performed steps. The probability of stopping at each step is $p=1-2p_ap_b$. The expected value of $2n$ is therefore $$2p\sum_{n=1}^∞{n(1-p)^{n-1}}=\frac{2p}{(1-(1-p))^2}=\frac{1}{p_ap_b}\enspace.$$


Why do we distinguish between term abstraction and type abstraction in System F?

Well there should be a distinction between types and terms somehow. If we had a "plus 10" function it wouldn't make any sense to apply it to a type. What is a type plus 10? So we need some kind of type system that differentiates between types and terms. This much is unavoidable. I suspect that this is the brunt of your issue.

But lets try and consolidate things a bit.

$$
\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(term abstraction)} \\
        &|~t~u && \text{(application)} \\
        &|~\lambda \alpha : Type. t && \text{(type abstraction)}\\
\end{align}
$$

where Type is a new keyword. Then applications can be type checked to ensure that only terms that have types of the form $\forall a. t$ can have types applied to them and that terms of the form $\lambda x : Type. t$ have type $\forall x. t$

This is however just a rebranding of System-F! All I have done is unified the syntax a bit. This does manage to consolidate application but you might then ask what happens when we say "Type is a Type too!" so that we can have only one kind of abstraction as well. So you might try and define things like this

$$
\begin{align}
A, B ::=&~\alpha && \text{(type variable)} \\
       &|~A \rightarrow B && \text{(function type)} \\
       &|~\forall \alpha. B && \text{(universal quantification)}\\
       &|~Type && \text{(type of types)} \\
\end{align}
$$

and then try something like this for terms

$$
\begin{align}
t, u ::=&~x && \text{(variable)} \\
        &|~\lambda x : A. t && \text{(abstraction)} \\
        &|~t~u && \text{(application)} \\
\end{align}
$$

Now I have introduced some terms I didn't want to! like $\lambda x : Type \to Type. t$. We don't even have the proper machinery to use something like that! So it doesn't seem like we can consolidate much further than our first attempt lest we introduce functions on types which would take us outside of system F! Infact the above move takes us outside of system-$F\omega$ as well! Consider the term $\lambda x : \forall a. a \to Type. t$. That's a dependent type!

If we morph the system into something closer to dependent types we eventually can drop the distinction if we are very carful. Such a system would not be System-F however and thus the distinction is needed as long as we are in System-F.


What's wrong with my beta reduction of pred c_0 on Church numerals?

$$ \mathrm{pred}\, c_0 \to \lambda s. \lambda z. c_0 \underline{(\lambda g. \lambda h. h (g s))} \; \underline{(\lambda u.z)}(\lambda v.v) $$

Nope, that's not a redex.

You have a term of the form $c_0 M N P$. That's $c_0 M N$ applied to $P$. It could be parenthesised as $((c_0 M) N) P$. This is how lambda calculus encodes functions with multiple arguments: by applying the function to one argument, and then applying the result to the next argument, and so on. Since this construction is very common, parentheses are omitted: function application associates to the left.

Once you expand the abbreviations, there is only one redex in $\mathrm{pred}\,c_o$, which is $(\lambda n. []) c_0$. This is very intuitive: $\mathrm{pred}$ is a function that takes a numeral as an argument, and the first thing you to to kick off the calculation is to apply the function to the numeral.


Context-Free Languages where every rule produces at most one non-terminal

A grammar where every production has at most a single non-terminal is called a linear grammar. If the non-terminal is rightmost in all productions, it is a right linear grammar; if the non-terminal is leftmost in all productions, it is a left linear grammar. Left and right linear grammars produce regular languages (and every regular language can be described by a right and a left linear grammar), but unrestricted linear grammars produce a proper superset of regular languages ($a^nb^n$ is linear), are not necessarily deterministic (the set of palindromes is linear), and are a proper subset of context free languages (the Dyck language [Note 1] has no linear grammar. The Dyck language has a deterministic grammar, so linear languages are not a superset of deterministic languages, either.)
It is not decidable whether a CFG has a linear grammar, a result proven by Sheila Greibach in 1966 (http://dl.acm.org/citation.cfm?doid=321356.321365)

Notes

The Dyck language is the set of all strings of square brackets where the brackets are balanced, given by the deterministic CFG:

$$S \to \epsilon \mid \mathbb{[}\; S\; \mathbb{]} \; S$$


Simulating DFA operations on non-regular languages with finite final state set

Your question is missing quite a few definition, but here is my interpretation.

  A language $L \subseteq \Sigma^*$ is finite-regular if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Note that if the minimal DFA for a language has $m$ accepting states, then every DFA for the language has at least $m$ accepting states (this follows from Myhill–Nerode theory). Therefore we obtain an equivalent definition if we replace "some DFA" with "the minimal DFA".

Using the product construction, you can easily show that the class of finite-regular languages is closed under union and intersection, and more generally under monotone set operations.


Question about Circuit-SAT NP-Complete Proof

You're right.  All that matters is that the reduction runs in polynomial time.  (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.)
Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1.  If the circuit has polynomial size, this modification takes polynomial time, since you're only modifying at most polynomially much stuff.


Note the sentence "The pipelined processor uses operand forwarding from the PO stage to the OF stage". That means if a result is written at cycle n, the same result can be read as an operand at the same cycle n. This happens twice in your instruction sequence. If you ignore this, your count will be too high by two.


1) This is the worst case in regards to all the possible recurrences and their respective sub-problem sizes.

Let's take some small sample $n$'s for a tree of height $3$. This is to show how the varying worst-case sub-tree size ranges from 1/2 to 2/3.

$$
\begin{align}
n &\quad \text{bottom half-full?} & \text{size of worst case sub-tree} \\
8 &\quad no & 4/8 \\
9 &\quad no & 5/9 \\
10 &\quad no & 6/10 \\
11 &\quad yes & 7/11 \\
12 &\quad no & 7/12 \\
13 &\quad no & 7/13 \\
14 &\quad no & 7/14 \\
15 &\quad no & 7/15 \\
\end{align}
$$

We deal in worst case scenarios when defining running times. This is why we must look for the worst case sub-problem (sub-tree) to define the recurrence relation. Clearly with varying $n$ values, the recurrence would vary, so we must take the worst of them. This is clearly the result of the deepest level being half-full, resulting in the upper bound recurrence:

$$T(n) \leq T\left(\frac{2n}{3}\right) + \Theta(1)$$

Alternatively if we were looking for a lower bound, we should look for the best case of all those worst case sub problems. We could then achieve:

$$T(n) \geq T\left(\frac{n}{2}\right) + \Theta(1)$$

2) The heap with the bottom level half full will always have the worse running time no matter how trivial the difference is. Minor differences like the one you described are not important. We're not comparing for one instance, time complexity is used to compare on a larger scale. On a large scale you can see the size of the sub problem ranges from n/2 to 2n/3.


Does White never lose in Chess if Chess is solved?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed).

Now it's obvious that White has a strategy to never lose. Because if every move except a pass leads to a loss, then White can pass, and we know that whatever move Black does will lead to a loss for black.

In real chess, nobody knows. And nobody knows if there is a forced win for either white or black either. It is also reasonably likely that there is a time and space limited algorithm that can force a draw.

White starts with an advantage - 1/2 tempo. (Why one half tempo? After e3-e5 e4 White has lost one tempo, and White and Black have effectively swapped sides). We may suspect that with perfect game any advantage would tend to increase. But you need a considerably better position than your opponent in order to win and might not be able to ever get that.


Temporal logic - mixing AF and AG in CTL formula

Does it mean that: 1. or 2. or 3.?

Your second interpretation is correct: $\varphi_1 \rightarrow AG(\varphi_2)$ is a CTL state formula, and to check whether it is satisfied by a state $s$, the path formula $G(\varphi_2)$ is evaluated relatively to the paths starting in s.

Therefore, a state $s$ satisfies your formula $AF(\varphi_1 \rightarrow AG(\varphi_2))$ iff all paths starting at $s$ eventually reach a state $s'$, such that if $\varphi_1$ holds in $s'$, then all paths starting at $s'$ satisfy that all states on this path satisfy $\varphi_2$.

  If 2, will the G start at the current or at the next iteration?

G starts at the current state/iteration. A path satisfies $G\varphi$ iff all states on this path satisfy $\varphi$, including the current state.

  For example if φ1=p , φ2=q, are both A and B in the language, or just A?

I am not sure what you mean by the "language" of a CTL formula. For LTL it makes sense to define the language of a formula, containing the words / label sequences that satisfy the formula. CTL does not reason about linear sequences, but about branching time, so usually for a CTL formula we are interested in the labeled transition systems whose initial states satisfy the formula (alternatively, you can unroll the transition systems and use CTL formulas to reason about languages of  infinite, finitely-branching, labeled trees). I assume you meant "language" in this sense, i.e. A and B are meant as sketches of transitions systems or their unrolling, with the left-most state as the initial state.

Then A and B both satisfy the formula: Both have an initial state that is not labeled with $\varphi_1 = p$. Hence both initial states satisfy the CTL state formula $\varphi_1 \rightarrow AG(\varphi_2)$. Therefore, it is true that all paths starting from their initial states eventually (in this case immediately) reach a state that satisfies $\varphi_1 \rightarrow AG(\varphi_2)$. Thus, the initial states satisfy $AF(\varphi_1 \rightarrow AG(\varphi_2))$.

References: Baier, Christel, and Joost-Pieter Katoen. Principles of model checking. MIT press, 2008.


Will a vertex present in the set of vertices present in each basis cycle be present in all the cycles?

Consider the following graph:

Let $S$ be the set containing the cycles formed by i) the red and black edges, and ii) the blue and black edges. $S$ is a cycle basis in which every cycle contains vertex $x$, yet the cycle formed by the red and blue edges does not contain $x$.

Edit: it is also not true that the existence of a vertex $x$ that lies in all cycles of a cycle basis implies that $x$ belongs to all cycles of the graph. See the following counterexample:

The $3$ cycles that can be formed by taking an edge $e$ of color $c$ for $c \in \{ \mbox{red, green, blue}\}$ along with the two black edges incident to the endpoints of $e$ form a basis $S$. Vertex $x$ belongs to all the cycles in $S$ but it does not belong to the cycle formed by the red, green, and blue edges.


Particularly Tricky Recurrence Relation (Master's Theorem)

Since n refers to "the length in bits of x", you should translate n with the binary log of x, and (n-2) with the binary log of x/4.

Hope it helps.


which error is it - a semantic error or a link error?

We can reproduce your error using this C++ code:

intmain() {
    return 0;
}

The following error is returned during compile time:

error: ISO C++ forbids declaration of ‘intmain’ with no type [-fpermissive]

Every function in C/C++ has to have a type. In this sense, it's a type error, which falls in the category of (static) semantic errors. On the other hand, your error is caused by a typo. This sort of error is considered a lexical error, which falls under syntax errors.

There is a lot of discussion whether certain errors are syntactical or static semantic. My opinion is this case is that the error is lexical, considering the cause.


Choosing nonzero entries from an array so no pair in same row or column

The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation matrices (0/1 matrices which contain precisely one 1 in each row and column). This immediately implies your result.

If you don't want to assume this theorem, you can use Hall's theorem directly. Given your table $A$, define a bipartite graph by having $n$ row-vertices, $n$ column-vertices, and connecting row $i$ and column $j$ if the $(i,j)$th entry is non-zero. Your goal is to find a perfect matching in the graph.

According to Hall's theorem, the graph contains a perfect matching if for all subsets $S$ of row vertices, the number of neighbors of $S$ is at least $|S|$. That is, given a set $S$ of rows, we need to show that the set
$$T = \{ j : A_{ij} \neq 0 \text{ for some $i \in S$}\}$$
contains at least $|S|$ columns. Indeed, the sum of the entries in the rows in $S$ is exactly $|S|$, and the sum of the entries in the columns in $T$ is exactly $|T|$. Therefore the sum of entries in $S \times T$ is at most $|T|$. However, by definition this sum must equal $|S|$ (since all other entries in the rows in $S$ are zero), and so $|S| \leq |T|$, which is what we wanted.

This argument shows that you can use standard algorithms for finding maximum matchings in bipartite graphs to actually find your $n$ entries.

We are now at an excellent position to prove the Birkhoff–von Neumann theorem. The proof is by induction on the number of non-zero entries. The argument above shows that there are at least $n$ non-zero entries, and in that case it's not hard to see that the matrix must be a permutation matrix, completing the base case.

Now consider an arbitrary doubly stochastic $A$ with more than $n$ non-zero entries, and find a matching $(i,\pi(i))$ in $A$. This matching corresponds to sum permutation matrix $P$. Define $\alpha = \min_i A(i,\pi(i)) > 0$. The matrix $B = \frac{A - \alpha P}{1 - \alpha}$ is also doubly stochastic (since subtracting $\alpha P$ removes exactly $\alpha$ from each row and column), with at least one more zero entry. By induction, $B$ is a convex combination $\sum_t \beta_t P_t$ of permutation matrices. Hence so is $A$: $$A = \alpha P + (1-\alpha) \sum_t \beta_t P_t.$$

The Birkhoff–von Neumann theorem can be stated in many different ways. It states that the set of doubly stochastic matrices is the convex hull of the permutation matrices. It also states (with some more work) that the vertices in the polytope of doubly stochastic matrices are the permutation matrices.


Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

The purpose of the "search direction" is that we want to move closer to a minimum of $f(x)$.  The gradient tells us the direction of steepest descent (as in gradient descent).

The reason we do the line search is to figure out how far to travel in that direction.  The gradient tells us the direction; but it doesn't tell us how far to go in that direction.

The product $\alpha_k \mathbf{p}_k$ is an ordinary product of a scalar and a vector; i.e., component-wise product.  You probably need to study a bit of linear algebra and multivariate calculus to get familiar with this sort of thing -- that's a vitally important foundation.

Step 5 is the heart of BFGS.  A full Newton method would calculate the Hessian (matrix of second partial derivatives) at each point; i.e., it would re-calculate the Hessian in step 5.  BFGS doesn't re-calculate it from scratch, as re-calculating it is expensive.  Instead, it tries to make an estimate/guess of how the Hessian has changed.  That's what step 5 is doing.  This estimate is less accurate than simply recomputing the full Hessian matrix, but it's faster.

You're not going to be able to understand what's going on in BFGS from Wikipedia.  Wikipedia's description is not very good, and there is no explanation of where the method came from.  Look for a better, more detailed explanation that explains where these steps came from, the intuition of what's going on, and how these particular formulas were derived.  Wikipedia is a great resource, but it's not a very good source for learning BFGS.


For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

Assuming the Unique Games Conjecture, your problem is solved for MAX-CUT in Ryan O'Donnell and Yi Wu, An optimal SDP algorithm for Max-Cut,
and equally optimal Long Code tests, who determined the gap curve for this problem.

I am not aware of any such work for MAX-2SAT, but Per Austrin has essentially determined the optimal approximation ratio (again, assuming the Unique Games Conjecture) in his paper Balanced MAX 2-SAT might not be the hardest.

In celebrated work, Prasad Raghavendra has essentially determined the optimal approximation ratio for any constraint-satisfaction problem, again assuming the Unique Games Conjecture.


Proof on lower bound of search in unsorted array with information theory?

Here is an informal proof, which you can try to formalize.

Suppose that we’re looking for 1 in an array of length $n$ of 0s and 1s. We consider the following distribution: each element is 1 with probability $1/n$. (You can also try your luck with the uniform distribution over all arrays with a single 1.)

Given the transcript of the algorithm, you can either recover the position of a 1, or deduce that the array consists only of 0s. Since typically there are only few 1s, the entropy of the answer should be $\Theta(\log n)$.

On the other hand, each position you query only gives you $h(1/n) = \Theta(\log n/n)$ information. Hence you need to query $\Omega(n)$ bits.


Determine if there's a $P_3$ as an induced subgraph in a graph $G$

Without loss of generality, we can assume that the graph is connected and contains at least three vertices. If the graph is a clique, it doesn't contain an induced $P_3$. What happens if it is not a clique?


Find all pairs of strings in a set with Levenshtein distance < d

There's a "trick" you can use that might potentially speed up your algorithm a little: shingling.  No guarantees that it'll necessarily help in your particular case, though.

Lemma. If the edit distance between two words $w,x$ is $\le 4$, and the two words both have length 20, then there exists some 4-gram that is common to both words (i.e., some $u$ of length 4 that is a substring of both $w$ and $x$).

This lemma then suggests the algorithmic trick.  Build a table with $4^4$ buckets, one bucket for each possible $4$-gram.  Given a word $w$, extract all of its 4-grams (there will be 17 of them) and insert it into those 17 buckets.  Do this for each word.

Now, if there is a pair of words at edit distance $\le 4$, then there must be some bucket that contains both words.  So, for each bucket, we search the set of words within that bucket for a pair of words at edit distance $\le 4$.  Use whatever algorithm you like for that task.  I would suggest trying BK-trees or metric trees.

Will this trick help?  The only way to know for sure is to try it.  But here's the intuition.  We'll have 256 buckets.  Each word will get mapped into 17 buckets.  Thus, heuristically, we expect each bucket to have $n'=17n/256$ words in it.  If we have an algorithm that can search for pairs of words at edit distance $\le 4$ among a set of words in $T(n)$ time, then applying that directly to the original set of words takes $T(n)$ time.  In contrast, after applying this trick, we apply it once to each bucket.  Now if $256 T(17n/256)$ is smaller than $T(n)$, this trick might yield improvements in running time.  My prediction is that it'll yield improvements for $\Theta(n^2)$-runtime algorithms, but not for $O(n \lg n)$ or $O(n)$ time algorithms.

This trick can be combined with any algorithm for looking for a pair of words with edit distance $\le 4$ in a set of $n$ words.

The "trick" can be improved further.  Define a "slate" of the word $w$ to be a pair $(i,u)$ where $i$ is a position ($1 \le i \le 17$) and $u$ is the 4-gram that occurs at position $i$ within $w$.  From each word you get 17 slates.  Now we get a refined lemma:

Lemma.  If the edit distance between two words $w,x$ of length 20 is $\le 4$, then there exists a slate $(i,u)$ of $w$ and a slate $(j,v)$ of $x$ such that $u=v$ and $|i \le j| \le 2$.

(It might be possible to improve the latter condition to $|i \le j| \le 1$, but I haven't tried to check.)

We'll do the same thing as before, but identifying each bucket with a slate.  We get $20 \times 256$ different buckets.  Now, for each word $w$, extract its 17 slates and store the word in the corresponding 17 buckets.  Let $B_{i,u}$ denote the set of words in the bucket for the slate $(i,u)$.  Finally, for each slate $(i,u)$, we check whether there exists a word $w \in B_{i-2,u} \cup B_{i-1,u} \cup B_{i,u} \cup B_{i+1,u} \cup B_{i+2,u}$ that is within edit distance $\le 4$ of some word in $B_{i,u}$.

Heuristically, we expect each bucket to have $n'=17n/(20 \times 256) \approx 0.0033 n$ words in it.  We expect the running time for each bucket to be something like $5 T(n')$, and we need to do that $20 \times 256$ times, for a total running time of $25600 T(0.0033n)$.

Is this better than the prior trick?  The only way to know for sure is to try it.  My prediction is that this'll be better for $\Theta(n^2)$-runtime algorithms, but worse for $O(n \lg n)$ or $O(n)$ time algorithms.

Finally, I don't think you have the running time of your scheme right.  I believe the Levenshtein transducer automata approach will have running time $\Omega(n^2)$ in your setting, as several folks have outlined in the comment thread under your question.


Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$

$\sum_{i=1}^k 2^i=\Theta(2^k)$ and you have $k\approx\log n$, so the sum is $\Theta(2^{\log n})=\Theta(n)$.


The picture I always visualize for this is the one featured on here on the Wikipedia page for NP-Completeness. The definition of NP-Hard is that it is the set of problems to which all NP problems can be reduced in polynomial time, so, for example, the bounded halting problem - does a Turing Machine $M$ halt within $k$ steps, is strictly not in NP, because there is no way to check in polynomial time whether a Turing Machine halts in $k$ steps. However, all problems can be converted to the bounded halting problem very easily, simply by building a Turing Machine which ostensibly solves the problem and asking whether it halts in some appropriate amount of time.

This answers your first question: not all NP-Hard problems are in NP or can be reduced to them. As for the second: Some NP-Hard problems can be converted to one another. For example, the EXP-TIME class, which can be though of as the next class beyond P, has EXP-TIME-Complete problems just like NP has NP-Complete problems, and there are classes even beyond that, indefinitely.


What are system clock and CPU clock; and what are their functions?

The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The CPU clock has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the system clock and multiplies it by a number, which is either fixed or unlocked (in that case the user can change the multiplier in order to over- or underclock the CPU).


The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

I'm assuming that there is a (non-uniformly) random function $h\colon [n] \to [m]$, and $n_j$ is the number of preimages of $j$.

Notice that $\binom{n_j}{2} = \sum_{1 \leq a < b \leq n} 1_{h(a) = h(b) = j}$. We have
$$
\mathbb{E}\left[\binom{n_j}{2}\right] = \frac{1}{2} \sum_{a \neq b} \Pr[h(a) = h(b) = j] = \frac{1}{2} \sum_{a=1}^n \sum_{b \neq a} \Pr[h(a) = h(b) = j] \leq \frac{n-1}{2m} \sum_{a=1}^n \Pr[h(a) = j].
$$
Summing this over $j$, we get
$$
\sum_{j=1}^m \mathbb{E}\left[\binom{n_j}{2}\right] \leq \frac{n-1}{2m} \sum_{a=1}^n \sum_{j=1}^m \Pr[h(a) = j] = \frac{n(n-1)}{2m} = \frac{1}{m} \binom{n}{2}.
$$


How to generate all $n$-bit numbers with certain bits fixed?

Practically speaking, here is one thing you could try:

Make a list $A[1],\ldots,A[m]$ of powers of two corresponding to free bits.
Generate a list of all XORs of elements from $A[i]$ (in the correct order), XORed to a mask consisting of the fixed bits.

If you don't care about the order, then an efficient way to generate the list is using a Gray code. Otherwise, you could use a recursive procedure.


I don't know if there is a correct or recommended usage of Unicode codepoints for the LTL operators, but the mapping we used in LaTeX was the following:

□ (U+25A1) => \Box
◇ (U+25C7) => \Diamond
○ (U+25CB) => \medcirc (from txfonts/pxfonts)


What's the formal definition of Big-O notation for functions of more than one variable?

There are many possible definitions; see e.g. Rutanen et al. [1].

Generally speaking, if you define your $O$ over domain $X$, you will need an order relation $\leq$ on $X$. The definition then reads:

$\qquad O(g) = \{ f : X \to \mathbb{R}_{\geq 0} \mid \exists\,x_0 \in X, c \in \mathbb{R}_{>0}.\ \forall\,x\in X.\\
\qquad\qquad\qquad x_0 \leq x \implies f(x) \leq c \cdot g(x) \}.$

So if $X = \mathbb{N}^k$ you can use lexicographic order, element-wise $\leq$, ...

Beware that the properties your $O$ has depend on both the definition and the the order you choose. The outcome may not be as expected.

A general definition of the O-notation for algorithm analysis by K. Rutanen et al. (2015)


I think that what is going on here is this.

In most operating systems, including Windows, there are lots of data structures inside the kernel that the kernel "shares" between all the processes running on the machine.  In early versions of Win32 (starting maybe with Windows 95?) there are some kernel data structures, specifically those having to do with the graphics device interface (GDI)) that are shared by all the processes that are using the same desktop.  In early versions of the OS there was only one desktop, so only one session, so these data structures were just shared like all the others.  In the Server versions of Windows each remote login gets a "terminal" which, I think, is sort of a virtual desktop.  So now they needed to "virtualize" those GDI data structures inside the kernel that weren't previously virtualized.  I think that a "session" is that set of virtualized GDI datastructures.  They are shared by all processes running on the same "terminal", and each "terminal" has its own version of the data structures.

The reason this matters in the DataCollider paper you referenced is that they are using data breakpoints, which are set on virtual addresses rather than physical addresses.  But race detection (in the kernel) really makes more sense from the physical address perspective.  For most kernel data structures there is a one-to-one mapping from virtual addresses to physical addresses.  You set a data-breakpoint on a particular virtual address and when it "fires" you know that the physical address corresponding to that virtual address is still the same.  All processes, from all users, from all "terminals" are really sharing those data structures, and if there is a race, there is a race.

The problem, for DataCollider is that in "session memory" this one-to-one mapping doesn't hold.  In the case of session memory the virtual addresses are the same for every process, but the physical address that virtual address is mapped to is different when the kernel is working on behalf of processes from different terminals.  So when the data breakpoint fires you need to do some extra bookkeeping to figure out whether the virtual address is pointing to the same physical address that you intended when you set the breakpoint.


If you're at a state $q$ reading $\alpha$ and there is no outgoing edge labeled $\alpha$, then there is way to extend the computation path. In view of that, the only valid computation path upon reading $abba$ is $q_0,q_0,q_0,q_0,q_0$; in fact, the same is true for any word ending in $a$, whose computation paths are of the form $q_0,\ldots,q_0$. Words ending in $b$ have the additional computation path $q_0,\ldots,q_0,q_1$, and words ending in $bb$ have the additional computation path $q_0,\ldots,q_0,q_1,q_2$, making three in total.


Why Does The Division Alorithim Need [Register Size] + 1 Iterations

"Why is that?"

Because divisor <<= 4 means original_divisor * (2**4), where I use original_divisor to denote the value of divisor when you began computing div(dividend, divisor).

Every time you do divisor >>= 1, you divide that divisor by 2. So you will get original_divisor * (2**3), original_divisor * (2**2), original_divisor * (2**1), original_divisor * (2**0).

Notice there are 5 of them, corresponding to original_divisor times $2^4, 2^3, 2^2, 2^1, 2^0$ respectively or 16,8,4,2,1 respectively. You should have noticed how 4 is changed to 5 by now. There are 4 possible shifts to the left, by 4 bits, by 3 bits, by 2 bits and by 1 bit. There is also a non-shift, or shift by 0 bit.

What you have experienced is the most famous/infamous error in computer programming, off-by-one error or off-by-one errors. I must have made this error hundreds if not thousands of times.

Just in case you have not heard of the most famous joke in computer programming, here it is. "There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors." Or a shorter version, "There are two kinds of errors, off by one errors".


Efficient algorithm to find number of sequences in string

You cant create an algoithm to do this in the worst case. Even if we read right to left and if we assume we can do some level of jumping (e.g if we see an f we can jump 6 spaces left) we still have to, in the worst case (the string of a's), read over the entire string. This can never be done in $o(n)$ time. The right to left with skipping will run in $O(m)$ time where $m$ is the number of increasing subsequences, and $m$ is $O(n)$.


Average number of collisions before successful insertion into hash table

1 / (1 - alpha) is about right, if you ignore that for the second slot the chance is (m - 1 - n) / (m - 1) and so on. But when that difference becomes relevant, you should have increased the size of your hash table :-)

What also will happen if you visit consecutive slots on collisions is that once your table is reasonably full then you might have large ranges of occupied slots, which could very much change the situation. Say you have 1,000,000 slots and 999,500 used entries: It's quite likely that the 500,000 slots from 0 to 499,999 are all used.

But all this depends on having a good hash function. Your hash function needs to rarely map different items to the same hash code. And if your hash table visits consecutive slots for collisions, then your hash function mustn't map similar items to consecutive hash codes. Otherwise the average number of slots might be a lot larger.

On the other hand, the cost of visiting a few or a dozen used slots is usually very low to the cost of computing a hash code, if the hash table stores hash codes. It gets really expensive when you have a collision not in slot numbers, but in hash codes. That's when you actually have to compare values. So the most important thing would be a good hash function.

Added: Assume that you have a hash table with 1,000,000 slots, and that 999,500 slots are used. Which is obviously a much higher load factor than a hash table should ever be allowed to have. If the used slots were perfectly random, then inserting a new element would require visiting 2,000 slots on average.

But if you had a range of 500,000 consecutive used slots (which would be quite likely if inserting always visited the next available slot), and you inserted the next item: There would be a 50% chance that the next item gets inserted into that range, visiting from 500,000 to 0 slots, or 250,000 on average. And a 50% chance that the next item gets inserted into the other range which has 0.1% empty slots, or 1,000 on average. So the total average is 125,500 slots visited.


Herlihy's result, indeed the whole paper, is about wait-free synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined informally at the beginning of the introduction, and defined formally in the automata model in §2.3.

Dekker's algorithm is not wait-free. The busy-wait loop to enter the critical section is a wait in the sense of Herlihy. It's possible to have P0 set its wants_to_enter flag, then P1 sets its own, then P0 sees that P1 wants to enter and one of the processes busy-waits (depending on the turn value).

Think of wait-free as “must work even with a hostile scheduler”, i.e. with a scheduler that always switches between processes at the most inconvenient time. Dekker's algorithm requires a scheduler that's at least weakly fair, i.e. guaranteeing that if a process is schedulable then it's eventually scheduled (as opposed to being locked in an order of execution that causes a livelock, such as never exiting the busy-wait loop). Wait-free algorithms complete in finite time with any scheduler that doesn't completely lock up the system if there's work to do (no fairness requirement).

Busy-wait loops require the scheduler to be preemptive (otherwise the loop runs forever). In practice a busy-wait loop would be written with a yield call, and even non-preemptive schedulers try to avoid immediately re-scheduling a process that just yielded. But even with a preemptive scheduler, busy-wait is generally bad: if nothing else it uses up CPU time and electricity. A case where Dekker's algorithm doesn't work at all is if the two processed have different priorities and the scheduler never schedules the process that would enter the loop because the busy-waiting process has a higher priority.

A naive solution to avoid waiting is to put in a time delay. It isn't a good solution because in practice it means an additional useless delay when there is contention on the mutex, and in theory the delay isn't enough since the scheduler could take that long to make its decision and so end up scheduling the busy-wait loop only anyway. A good solution avoid busy-wait altogether is to add a primitive that lets a process block until some shared variable is modified; with such a primitive, I think it's easy to achieve an infinite consensus number.

It is instructive to contrast Dekker's algorithm with a wait-free consensus solution, such as the one Herlihy gives for two processes (fig. 7).

prefer[P] := input
if RMW(r,f) = v
  then return prefer[P]
  else return prefer[Q]
end if

RMW is a primitive operation with a consensus number of at least 2, for example test-and-set. There's no busy-wait in the consensus protocol itself: both processes run pretty much instantly, without ever waiting for the other one. In a real scenario, the processes that doesn't acquire the mutex may well wait for it; but the process that does acquire the lock isn't stopped, and in practical terms that means at least an expected performance gain both when there is contention and when there isn't.


The idea is to define a new function $S(m)$ by $S(m) = T(2^m)$. Then by definition we have $S(m/2) = T(2^{m/2}) = T(\sqrt{2^m})$.


Determine saving moves for a checked king

Well, you could try to directly use the geometry the attacking piece and possible defenders to see if an intersection is available. This would be faster.
But there is a lot of cases to be taken into consideration : multiple checks, pinned defenders, half-pinned defenders, en passant rules... It's much easier to code that wrong, so be careful, and prepare lots of test cases to compare to the "simple" version, to check that you're not mixing things up.
Computing "long" lists of legal moves isn't hard for a computer, there's less than 200 anyway. What's hard in chess computer programs is the exponential search tree  and deciding when to stop recursing and evaluate.


As Emil said, That is the number of milliseconds since the Unix epoch (1 Jan 1970 midnight UTC).


What does it mean to be "independent of machine model"?

The class $\mathsf{P}$ is usually defined as the class of decision problems solvable in polynomial time by (one-tape) Turing machines. However, you get the same class if you replace "one-tape Turing machines" by "multi-tape Turing machines", "RAM machines", "machines running C natively", and many other machines. That's what is meant by the class being independent of the machine model.

Other classes, such as $\mathsf{TIME}(n)$, are very much dependent on the machine model: there are (I think) languages which can be computed in linear time on a two-tape Turing machine but not on a one-tape Turing machine.

The reason we are happy that $\mathsf{P}$ is machine-independent is that it makes $\mathsf{P}$ a very natural class. You don't have to ask yourself whether the correct model is Turing machines with one tape, two tapes, or more: all definitions result in the same class. The same cannot be said about $\mathsf{TIME}(n)$, for example.


Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?

As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$.
This is somehow a basic reduction that can be done by standard tricks, so it would be a nice exercise to solve it alone. Here is a hint.
Hint: you can simplify things by fixing one of the machines $K_1$ or $K_2$ to be a constant machine that recognizes some fixed language. Then, think how to define the other machine depending on the reduction's input $\langle M, w\rangle$.


How pictures and videos are usually loaded in Memory?

Just having malicious instructions loaded into memory is not a problem in itself.  Instructions (code) is just binary, so it might be stored in the data segment.

Where it becomes a problem is if something causes that code to be executed.  It's not clear why a video player would jump to data inside an image.  If it had a security vulnerability, that could happen, but if it has a vulnerability, almost by definition bad things could happen, so that's not really saying much.


In contrast to popular thought, the description of a language doesn't have to be of the exact form
$$
L = \{a^i b^j c^k \mid \text{conditions on $i,j,k$}\}.
$$
A language is a set, and you can describe it in exactly the same variety of ways as you describe sets. For example, we can write
$$
L = \{a,b\}^* \setminus \{a^nb^n \mid n \geq 0\}.
$$
In your case, as rici mentions in the comments, you might as well just take a union with $\{abc\}$ to account for the additional case.


The first thing to note specifically for integer arrays is that quicksort might not be the best choice for sorting depending on the possible range of values.  A counting sort may be more appropriate, for example.

In the general case (i.e. not specific to integers), Martinez and Roura analyzed this problem for both quicksort and (single order statistic) quickselect. See "Optimal Sampling Strategies in Quicksort and Quickselect" SIAM Journal on Computing http://dx.doi.org/10.1137/S0097539700382108

The short answer is that the optimal strategy is to pick as the pivot element the median of a sample of elements, with the sample size roughly proportional to the square root of the number of elements in the array to be sorted, unless swapping is extraordinarily expensive.  Specifically for simple types (e.g. integers), swapping is not expected to be expensive; it may be less costly than comparison via a function call, as in qsort.

That strategy also changes the worst-case (adversarial input) performance from quadratic to polynomial with an exponent of 1.5; see also McGeoch and Tygar "Optimal Sampling Strategies for Quicksort" Random Structures and Algorithms http://dx.doi.org/10.1002/rsa.3240070403

Instead of using the exact median of the samples, a lower-cost option is to approximate the median with a pseudomedian. One which can be scaled with sample size and which provides an increasingly accurate estimate of the median as sample size increases is the remedian as described by Rousseeuw and Bassett in "The Remedian: A Robust Averaging Method for Large Data Sets" Journal of the American Statistical Association http://amstat.tandfonline.com/doi/pdf/10.1080/01621459.1990.10475311   See also Battiato et al. "An Efficient Algorithm for the Approximate Median Selection Problem"  in Proceedings of the 4th Italian Conference on Algorithms and Complexity http://dl.acm.org/citation.cfm?id=648257.753042 (it's the same remedian, "rediscovered" by the authors about a decade after Rousseeuw and Bassett).

For an even deeper dive (especially regarding the importance of quality of sampling as well as quantity), see https://github.com/brucelilly/quickselect/blob/master/lib/libmedian/doc/pub/generic/paper.pdf or the video at https://www.youtube.com/watch?v=iWmAf4RMMiM  There you'll also find a way to get the adversarial performance to remain linearithmic (as opposed to going polynomial) without deterioration in non-adversarial input performance.

You say

  If we invest more effort in finding a good pivot (e.g., take the median of k random samples), we might make more comparisons, but swap less elements.

What typically happens (for uniformly distributed random input) is that a better (i.e. closer to the true median) pivot results in fewer overall comparisons during sorting but more swaps.  With a pivot close to the median every time, the number of comparisons to sort (ignoring comparisons for pivot selection) is $N \log _ 2 N$ and the number of swaps (if efficiently arranged) is 1/4 $ N \log _ 2 N$.  On the other hand, a randomly selected pivot element leads to 1.386 $N \log _ 2 N$ comparisons but only 1/6 $N \log _ 2 N$ swaps (more than 8 times as many comparisons as swaps).  The two are related; a reduction in the number of swaps implies a lopsided partition (about 78.9%/21.1% for 1/6 $N \log _ 2 N$ swaps) and that leads to an overall increase in the number of comparisons because the problem size is reduced by less than half.  The key to minimizing comparisons is using an efficient pseudomedian, one which provides a good estimate of the median with much fewer comparisons than the ~2N which are expected to find the exact median.  The remedian with base 3 computed on a sample of size $\sqrt {N}$ costs about 1.5 $\sqrt{N}$ comparisons, which is much less than 2N for reasonable N.


Optimal algorithm for finding all ngrams from a pre-defined set in a text

What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes.

Be aware that they give worst-case runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive nature. Therefore, you should benchmark the respective algorithms with data similar to which you expect to get.


Assignment to make formula unsatisfiable

Your problem is the canonical $\Sigma_2^P$-complete problem:
$$
\exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}).
$$
As such, it is thought to be more difficult than SAT (which is $\Sigma_1^P$). Solving it with a few SAT-oracle calls is akin to solving SAT itself efficiently (the P vs. NP question), though it could be that $\Sigma_2^P = \Sigma_1^P$ while $P \neq NP$, so in some sense there is more hope for your problem than for SAT itself.


Are all undecidable/uncomputable problems reducible to the Halting problem?

No. As I recall a practical example can be made out of a function inequivalence statement. More abstractly, there is something called Turing-degree in undecidability and infinite levels of "hardness".  Each level has it's own Halting Problem strictly harder than those at every level lower.  Check out the first section of this Scott Aaronson lecture and what he calls a "Super Halting Problem".


Understanding constraint formula concept in Java

First, not all of the constraint formulas work with types, some of them work with expressions, or other objects. For example, what would be the set for the formula ‹1+1 → Integer›?

Second, a formula might contain zero, one (at either position) or two inference variables (denoted by Greek letters). What would be the set for ‹String → Object›, ‹α → Object›, ‹String → α›, or ‹α → β›?

Third, I think you should think about constraint formulas as predicates, not as sets. For example, the formula ‹String <: Object› is satisfied, while ‹Object <: String› isn't.

And when you have a constraint formula with inference variables, you can start talking about sets of types (or sets of pairs of types for formulas with two variables) that satisfy the formula.

This means that I think that the closest you can get to your equation would be something like:

{α | ‹α <: T› } = {α | (α belongs to M) and (α is a subtype of T) }

(Though the second part is unnecessarily verbose, "α is a subtype of T" already implies "α belongs to M".)


Finding partition with maximum number of edges between sets

If your question really is "is there an algorithm", the answer is obviously yes: just try every possible partition and choose the one maximizing the number of edges with endpoints in different parts.

Otherwise, it's unlikely that there is a polynomial-time algorithm. Indeed, this problem is known as maximum cut and it is well-known to be NP-hard.


Where is the mistake in this apparently-O(n lg n) multiplication algorithm?

Your algorithm is very similar to Schönhage–Strassen. In the FFT step, there are large numbers involved - as you mention, their size can be up to $O(\log n)$. Arithmetic on them doesn't come for free. You need to apply the construction recursively, and you'll lose something.


Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

The Q is not clear enough for me, an in-order traversal will get u "n2" as the predecessor of "n1" so  what is exactly required???

Regarding ur prepositions:

-P1:         if n1 has 2 children, or just a left child, then n2 is the rightmost leaf of n1's left child

So  Proposition 1 is  correct

-P2:
-As stated above, if n1 only child is a left child, n2  have atmost only left child.
(meaning not just at most 1, but it must be left)

-if n1 has only a right child, then reverse the argument; i.e., n2 is the node n1 is her left child of a right child (search upward for a node smaller than n1.. its parent if it is a right child does not make a difference if its parent has another left child or not, parent of parent,....)

For the bold case inside the brackets, ur second proposition is wrong.

I'll try to find an example picture, u may search any data structure text book for a complete tree to exhaust all different cases by ur self

Check the example in the second pic in this Q (My mobile is subject to a Denial of Service attack that prevents attaching it here again)

Ambiguity with the Top View of a binary tree

It is clear that 10 precedes 11, 11 has one right child while 10 has two


Given a low resolution video, is it possible to create a higher resolution image

It heavily depends on the setting, accuracy and goal, but shortly, yes, even considering practical application.

Theoretically of course it is possible, with various (or used together) techniques like sharpening, noise removal, scene reconstruction, frames merging, geometry reconstruction or even motion blur removal. The last one works by solving optic equation and could be used with success if you treat consecutive frames as one speeding object, applying frames as artificial motion blur, for example Practical Layered Reconstruction for Defocus and Motion Blur.
The most straightforward technique would use shifted grids (frames) and after applying constraints from "big pixels" and how they round at the discrete domain the result is in the "reconstruction domain" - all pixels represent ranges of possible chrominance / luminance. The accuracy increases with the number of frames used. Here are two problems: the additional processing is needed to estimate the repative position of frames (which in the case of static camera gets easier - the equivalent of motion capture of smart objects) and the number of frames. If these came from different cameras (angles, coordinates, intrisinc camera setting) the scene reconstruction with possibly light oblivious merge (the light condition may vary, it must be equalized).

As stated earlier it depends, the plate recognition is easier, it reduces to contours extraction of low resolution data / blurred setting or image reconstruction discarding colours (which are known and not interesting), with some degree of certainty - the numbers under noise should be matched with patterns.

For the face recognition it gets harder due to unknown pattern, possibly 3D reconstruction from frames, which are low resolution, and hopefully with full colour after processing. This is a part of active research, because many powerful algorithms yield grayscale images.

Generating perceptualy clearer images is quite established field, heavily dominated by SSIM derivative techniques (the theoretical-empirical model for images compression, that could be fed with "reconstruction domain" image and return the most plaussible one), but reconstruction beyond doubt is harder task.

Here are some good to read articles about it:
Super resolution algorithm

An Algorithm for Repairing Low-Quality Video Enhancement Techniques Based on Trained Filter

Video Superresolution Reconstruction Using Iterative Back Projection with Critical-Point Filters Based Image Matching

VIDEO SUPER RESOLUTION RECONSTRUCTION FROM LOW RESOLUTION IMAGES USING SPLINE INTERPOLATION


Does a shift operation distribute over XOR

Shift is right-distributive over XOR, and over many other operations as well (AND, OR, addition, min, max)

As for why, informally for the bitwise operations I'd explain it as: bitwise operations are like pointwise operations (if you view a number as a function from bit index to the bit at that index), translating (or permuting, etc) the positions distributes over doing the operation. Eg if we have two numbers $f$ and $g$ as such functions, then $(f ⊕ g)(k) = f(k) ⊕ g(k)$ so $(f ⊕ g)(k + j) = f(k + j) ⊕ g(k + j)$, here $f(k + j)$ is just $f$ shifted by $j$ so this showed that it didn't matter whether the shift is done after the XOR or on both of its operands. In general this applies to any remapping of the coordinates, ie $(f ⊕ g)(r(k)) = f(r(k)) ⊕ g(r(k))$ where $r$ is any function from $\mathbb{N}$ to $\mathbb{N}$.

As pointed out in the comments, this also relies on the operator to map two zeroes to an other zero, ie $0 ⊕ 0 = 0$.

Or simpler but less general, using string notation, let's say we have two number $a$ and $b$ and let their XOR be $c$, then $a0^k ⊕ b0^k = c0^k$ and $(a⊕b)0^k = c0^k$ (by substitution).


Does inserting and immediately removing a node change a red-black tree?

It's not obvious that there is a "correct" answer to this question, as there are multiple insertion/deletion algorithms for red-black trees. Tarjan explicitly explains this in his book Data Structures and Network Algorithms, where he demonstrates (in section 4.2) update algorithms that require $O(1)$ rotations and references algorithms that require $\Omega(\lg n)$ rotations.

This is also mentioned in Hize's "A Simple Implementation Technique for
Priority Search Queues" and Driscoll et al.'s "Making Data Structures Persistent"


Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text

$\dagger\dagger$ Theorem 22.7 concludes that exactly one of the three conditions listed is satisfied. The inequalities listed in (4) show that the intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ intersect. Therefore, the first condition of the theorem is not the one being satisfied. In the other two conditions one of these two intervals is inside the other. Now, because the inequality $d[u]<d[v]$ is strict, it can't be that $[d[u],f[u]]$ is inside $[d[v],f[v]]$. So, the third condition in the theorem is the only one that can be satisfied.
$\dagger$ This is also using theorem 22.7 or its corollary. The inequality $d[u]<d[v]$ is part of the assumption, that by time $d[u]$ the vertex $v$ is still white. The inequality $f[w]\leq f[u]$ comes from Corollary 22.8, since $w$ is a descendant of $u$. The inequality $d[v]<f[w]$ is due to $(w,v)$ being an edge. Because all neighbors of $w$ must be discovered before we consider it finished. Now, the claim that the proof should end here is jumping to the conclusion of the theorem without justification. It hasn't been justified that DFS will actually use $(w,v)$ to discover $v$.
Example 1: For example, consider the graph with vertices $1,2,3,4$ and (directed) edges $(1,2),(1,4),(2,3),(4,3)$ and we start at $1$ doing DFS. Assume that we already discovered $1$ and $2$.
At this point the vertex $v=3$ is is a white path from $u=w=2$. Just one edge $(2,3)$. DFS will discover $3$ and make it a descendant of $2$. There is no way to change that, since Theorem 22.9 proves it. But imagine that at this point we stop obeying DFS and go to discover $4$ and from $4$ go and discover $3$. Then $3$ wouldn't be a descendant of $2$. It would only be a descendant of $4$ and $1$. Theorem 22.9 proves that DFS wouldn't do that.
Example 2: This is to illustrate the question in the comments. Consider the graph with vertices $1,2,3,4$ and edges $(1,2),(1,4),(2,3),(2,4),(3,4)$. Assume that we have discovered already $1$ and $2$, in that order. The vertex $v=4$ is in a white path from $u=w=2$. However, the edge $(2,4)$ doesn't necessarily need to be used by DFS. If the neighbors of a vertex are considered in the order according to the labels that we gave them in this example, then from $2$ DFS will discover $3$ and from $3$ it will discover $4$. Then $3$ becomes finished, then $2$ becomes finished, and $1$ becomes finished, in that order.
While theorem 22.9 doesn't ensure that either $(2,4)$ or $(3,4)$ will be used, since that depends on the other in which neighbors are explored, note that it does ensure that the edge $(1,4)$ will not be used (under the assumptions of the example that $1$ was discovered and $2$ just got discovered). In fact, Theorem 22.9 implies that $4$ will be a descendant of $2$.


Which is better ? Iterations or Recursions?

A straightforward answer would be "iteration", since recursion consumes stack memory and imposes computational overhead for calling functions.

However, in practice both implementations can be equivalent at machine code level due to compiler optimizations (such as tail call optimization). In general, you shouldn't really be concerned about these matters unless you have strong reasons to believe they are relevant in your particular case.

As a rule of thumb, you should concentrate on clarity and efficiency of your algorithm, and use constructions that look natural for the logic of your method. This recommendation is repeated virtually in all books on the subject, so please follow it.

P.S. You should also consider that certain algorithms require you to store certain local values on each iteration. Recursion gives you this capability "for free", so you should also consider that iterative procedures may need additional data structures comparing to their recursive equivalents.


The algorithm yields optimal ternary codes

We can’t prove that, but we can disprove it. The given algorithm is not always optimal. In step 2, three nodes may not be available, so there is more than one way to build the tree. That can’t happen in the binary case.

Consider a min heap containing four characters, whose frequencies are 0.4, 0.3, 0.2, and 0.1. The given algorithm yields the tree on the left, with mean length 1.6. The optimal tree is shown on the right, mean length 1.3.

@PeterShor’s comment above indicates that a correct algorithm is known, but I haven’t seen it.


Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge

Ok, here is a simple proof I came up by myself. I was apparently going the wrong way in trying to prove the exercise.

Proof. Suppose edge $e$ is a cut-edge. Study graph $G-e$. For any $v \in G-e$ other then $e$ endpoints $x, y$, the vertex degree $d(v) = k$, and $d(x)=d(y)=k-1$.

Now, since graph $G$ is bipartite, graph $G-e$ remains bipartite. Also, because $e$ is a cut-edge, $G-e$ is composed of 2 components $H_1, H_2$, which are also both bipartite, and each contains exactly one of $x, y$. Assume WLG that $H_1$ has vertex $x$, that $H_1$ has vertex bipartition $X_1, Y_1$ and that $x \in X_1$.

Clearly, in subgraph $H_1$, we have

$S_1 = \sum_{v\in X_1 }d(v) = k(|X_1|-1) + k-1$ and $S_2 = \sum_{v\in Y_1 }d(v) = k(|Y_1|)$, and $S_1$ can't be equal $S_2$ unless $k=1$. However, it must be the case that $S_1 = S_2$ in a bipartite graph. Thus, our initial assumption that $e$ is a cut-edge was wrong. Therefore, $G$ has no cut-edge. $\Box$


Correctness of splitting an undirected tree into a forest of trees with even number of children

I got my "Aha! Gotcha" moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.

The set of edges that can be cut is a "static property", the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be "even" if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees.

So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.


The Hadamard gate might be your first encounter with superposition creation. When you say you can relate the usefulness of the Pauli $X$ gate (a.k.a. NOT) to its classical counterpart – well, Hadamard is exactly where you leave the realm of classical analogue, then. It is useful for exactly the same reason, however, namely that it is often used to form a universal set of gates (like clasical AND with NOT and fan-out, or NOR with fan-out alone).

While a single $H$ gate is somewhat directly useful in random number generation (as Yuval Filmus said), its true power shows when appearing in more instances or in combination with other gates. When you have $n$ qubits initialized in $|0\rangle$, for example, and apply one $H$ to each of them in any order, what you get is
$$(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) \otimes \ldots \otimes (|0\rangle + |1\rangle) / 2^{n/2}$$
which can be expanded to
$$1/2^{n/2} \cdot (|00\ldots00\rangle + |00\ldots01\rangle + |00\ldots11\rangle + \ldots + |11\ldots11\rangle)$$
Voilà, we can now evaluate functions on $2^n$ different inputs in parallel! This is, for example, the first step in Grover's algorithm.

Another popular use is a Hadamard on one qubit followed by a CNOT controlled with the qubit you just put into a superposition. See:
$$CNOT \big(2^{-1/2}(|0\rangle+|1\rangle)\otimes|0\rangle \big) = 2^{-1/2} CNOT(|00\rangle + |10\rangle) = 2^{-1/2} (|00\rangle + |11\rangle)$$
That's a Bell state which is a cornerstone of various quantum key distribution protocols, measurement-based computation, quantum teleportation and many more applications. You can also use a CNOT repeatedly on more zero-initialized target qubits (with the same control) to create
$$2^{-1/2} (|00\ldots00\rangle + |11\ldots11\rangle)$$
which is known as the GHZ state, also immensely useful.

Last but not least, it's a quite useful basis transform that is self-reversible. So another Hadamard gate undoes, in a sense, what a previous application did ($H^2 = I$). You can experiment around what happens if you use it to "sandwich" other operations, for example put one on the target qubit of a CNOT gate and another after it. Or on both of the qubits (for a total of 4 Hadamards). Try it yourself and you'll certainly learn a lot about Quantum computation!

Re "what is the Hadamard gate doing geometrically to a vector": read up on the Bloch sphere, you'll going to hear about it everywhere. In this representation, a Hadamard gate does a 180° rotation about a certain slanted axis. The Pauli gates (NOT being one out of three) also do 180° rotations but only about $x$ or $y$ or $z$. Because such geometrical operations are quite restricted, these gates alone can't really do much. (Indeed, if you restrict yourself to those and a CNOT in your quantum computer, you just build a very expensive and uneffective classical device.) Rotating about something tilted is important, and one more ingredient you usually need is also rotating by a smaller fraction of the angle, like 45° (like in the Phase shift gate).


Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

You can always write a grammar without $\lambda$, unless the language itself includes $\lambda$. In that case, you will need the single production $S\to\lambda$ (where $S$ is the start symbol).
There's a simple algorithm for removing $\lambda$ from grammars. First, figure out which non-terminals might produce $\lambda$. (These non-terminals are called "nullable non-terminals".) Then, for each nullable non-terminal and for each production in which it occurs, add a new production which is the same but without the non-terminal. (If the non-terminal appears more than once in the same production, do this for each occurrence of the non-terminal.) Keep doing this until no more additions are possible. Then remove all of the productions with empty right-hand sides, except the empty production for the start symbol (if there is one).
Applying this algorithm to your example, we first find that $Y$ and $Z$ are nullable, while $S$ and $X$ are not. So then we need to add additional productions:

From $X\to a Z b$, add $X\to a b$.
From $Y\to c Y d$, add $Y\to c d$.
From $S\to X Y$, add $S\to X$.

That gives us:
$$S\to X Y, S\to X\\
X\to a Z b,
X\to a b \\
Z\to X,
Z\to \lambda \\
Y\to c Y d,
Y\to c d,
Y\to \lambda
$$
We then delete the two empty productions, leaving:
$$S\to X Y, S\to X\\
X\to a Z b,
X\to a b \\
Z\to X \\
Y\to c Y d,
Y\to c d
$$
At this point, we might note that $Z$ is totally redundant. We can simplify the grammar by just substituting its right-hand side in the only place where it is used:
$$S\to X Y, S\to X\\
X\to a X b,
X\to a b \\
Y\to c Y d,
Y\to c d
$$


Possibility to prove that a function in big-theta is in big-O and little-o

Yes, it looks like that you missed something obvious.

A stronger claim: If $f(n) = \Theta (g(n))$ and $g(n) = o(h(n))$ then $f(n) = o(h(n))$.

Sketch of a proof: $f$ is bounded both above and below (up to a constant factor) by $g$ asymptotically, which is informally understood as $f$ and $g$ are the same asymptotically. $g$ is dominated by $h$ asymptotically. Hence $f$ is dominated by $h$ asymptotically.

(Sure, the above sketch is no more than rephrasing the claim in English. Well, that is how you (or at least I) would like to understand and reason about the situation)

Here is a detailed proof.

$f(n) = \Theta (g(n))$ implies that $c_1g(n) \le f(n) \le c_2 g(n)$ for some $c_1\gt0,\,c_2\gt0,\,k_1$ and any $n \gt k_1$.

$g(n) = o(h(n))$ implies that $|g(n)| < c_3 h(n) $ for some $c_3\gt0,\,k_2$ and any $n \gt k_2$.

Let $k_3=\max(k_1,k_2),\, c_4=\max(c_1,c_2)c_3\gt0$. Then for any $n\gt k_3$,
$$\begin{align}
|f(n)|&\le \max(|c_1g(n)|, |c_2g(n)|)\\
      &\lt\max(c_1c_3h(n),c_2c_3h(n))\\
      &=\max(c_1,c_2)c_3h(n)\\
      &=c_4h(n)
\end{align}$$
Note the first inequality above is guaranteed by the fact that $f(n)$ is bounded between $c_1g(n)$ and $c_2g(n)$ since $n>k_1$.

Finally, note that $f(n)=o(h(n))$ implies $f(n)=O(h(n))$.

P.S. There is some typo in your question. For example, "$c_1, c_2\in\mathbb{N}$" should be "some $c_1,\,c_2\in\Bbb{R}^+$" or "some $c_1>0,\,c_2>0$". If you let $f(n)=n, g(n)=2n$, then there is no natural number $c_1$ such that $c_1g(n)\le f(n)$ for even one positive $n$.


Is automaton not practical in real coding?

While solving common programming tasks it's usually not helpful to think of an automaton. But there are still many cases where they are applied:

writing small parsers (e.g. parse an integer/float); in order to not forget edge cases drawing an automaton is really helpful; for more complicated parsers grammars are usually a better tool
state machines  are often encountered in game programming (e.g. to manage which animation is currently executing; e.g. press the UP key switches the animation state machine in walking up mode; or to manage game states like if are you currently in-game or in the main menu)
important (string) algos such as the KMP string matching algorithm use an automaton in the background but it's usually represented as a table and quite hard to wrap your mind around

Automatons are models that are theoretically useful to prove properties of language classes. To make proves as simple as possible their definition is also kept simple.
In day to day code you usually stitch together powerful high level data structures to solve your problems and don't think on the low level of e.g. a Turing Machine that would manipulate input on the bit level but rather in terms of higher data types such as ints and lists.
P.S. Automatons are very useful for designing circuits, since circuits work on the bit level and you usually try to minimize the components used it's useful to note down which states your circuit needs and how it should transition between them given some small binary input.


Finding maximal cardinal independent set given oracle

Let $O(G)$ be an oracle that returns the maximum cardinality of an independent set in $G$; you can implement it given your oracle using binary search.

Pick an arbitrary vertex $v$, and form a graph $G'$ by removing $v$ and all its neighbors. If $O(G') < O(G) - 1$ is false, then $v$ doesn't participate in a maximum cardinality independent set, and we try more vertices until we find a vertex that does. If $O(G') = O(G) - 1$, then we put $v$ aside, and continue in the same way with $G'$.

Taking all vertices put aside, we obtain a maximum cardinality independent set of $G$.


Prove that any subtree in a red-black tree has at least $2^{bh(x)} -1$ internal nodes

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


How to show that cross entropy is minimized?

You are calculating the so-called binary cross-entropy. Let $f(\cdot)$ be a sigmoid function. The binary cross-entropy between $y$ and $f(t)$ is

$$    F(t,y) = H(y,f(t)) = -y\log f(t) - (1-y)\log(1-f(t)). $$

When you compute the partial derivative of $F(t,y)$ with respect to $t$, you get:

$$    \frac{\partial F(t,y)}{\partial t} = f(t) - y $$

You reach the minimum when $f(t)=y$. In case of multiple variables, let:

$$    F(\vec{t},\vec{y}) = \frac{1}{n}\sum_{i=1}^n F(t_i,y_i) $$

so

$$    \frac{\partial F(\vec{t},\vec{y})}{\partial t_i} = \frac{f(t_i) - y_i}{n} $$

Now, if $t_i=\sum_j w_{ij}x_j+b_i$ is the activation, with the chain rule:

$$ \frac{\partial F(\vec{t},\vec{y})}{\partial w_{ij}}=\sum_k\frac{\partial F(\vec{t},\vec{y})}{\partial t_k}\cdot\frac{\partial t_k}{\partial w_{ij}}=\frac{1}{n}\cdot x_j\cdot[f(t_i) - y_i]$$


What is meant by a single-threaded kernel?

I will be adding to nir shahar's answer.
A single-threaded kernel is essentially a kernel that processes only one thread at a time. We can have multiple kernel threads, but only one can get executed at any given point in time. This can be achieved by some scheduling procedure on the kernel threads.
But is this the same thing as having only one kernel thread (and using the many-to-one model) as even multiple threads have to be executed sequentially?
NO! A blocking call made on a many-to-one model blocks all other processes mapped to that kernel thread. Having a one-to-one model will allow for other processes to run even if one process executes a blocking call.
This does come at a cost. The overheads of creating and managing multiple kernel threads are somewhat expensive, but it all depends on your usage.


There are two flaws in your idea.

First, compression ratio is not the right metric.  The right metric for evaluating your scheme is the transmission rate: how long does it take to send a $n$-bit message?  The answer is that your scheme fares very poorly under that metric: it takes $\Theta(2^n)$ units of time to send a $n$-bit message.  Therefore, your scheme has very poor performance, both theoretically and practically.

Transmission rate is the right metric for a scheme that sends data over a communication channel.  Compression ratio would be suitable for a compression scheme of the form $C:\{0,1\}^n \to \{0,1\}^*$, but crucially, this requires that the output of the compression scheme can be expressed in bits.  Your protocol doesn't have that property: the output is actually trits.

This leads me to the second flaw in your idea.  Your protocol requires a communication channel that has three states (i.e., can convey one of three symbols at any point in time): "1", "0", or "I have nothing to send right now".  In other words, you need a communication channel that can send trits (0, 1, or 2), not just bits (0 or 1).  But if we had a communication channel like that, we could already achieve higher transmission rate than your scheme.  So, you're not comparing to the right baseline.

For these reasons, your scheme does not beat any information-theoretic bound and does not contradict any theoretical barrier.  It also probably won't be effective or useful in practice.


Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?

It's so wired that again, I'm answering my own question... I have to admit I am not confident at all when confronted with constructive proof problems.

An encoding scheme for ${P}$ could be described graphically as follows: Suppose $T_A$, $T_B$ are 2 Huffman trees for ${P}_A$ and ${P}_B$ respectively. For each leaf $s_{Ai}$ in $T_A$ replace it with $T_B$, i.e.

Letting $|S_A| = q,|S_B| = q$, the average code word length of this coding scheme is
$$C = \frac{\sum l_{Ai}+l_{Bj}}{pq} = \frac{q\sum l_{Ai}+p\sum l_{Bj}}{pq} = \mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}\mathbb{P}_B)$$
where $l_{Ai}$, $l_{Bj}$ are the codeword length of $s_{Ai}$ and $s_{Bj}$ in the Huffman code corresponding to $T_A$, $T_B$. Therefore,
$$\mathrm{MinAveCodeLen}({P})\leq C\leq\mathrm{MinAveCodeLen}({P}_A)+\mathrm{MinAveCodeLen}({P}_B)$$


Constructing orthogonal latin square Parker/Knuth method

Find 10 transversals that don't intersect; these cover all the cells of the square.  Fill the transversal that starts with 0 will all 0's; fill the transversal that starts with 1 with all 1's, and so on.  In the example, the transversal that gives rise to the position of the 0's in the second square is 0349728615.

It seems to me that it would be clearer to use the row numbers, rather than the number stored in that row, to indicate the transversal, but of course, I've used Euler's notation above.


Existence of Real-Time Multiprocessor Schedule

Y. Cho and S. Sahni, Scheduling Independent tasks with due times on a uniform Processor System, Jr. of the ACM, 1980

Presents an algorithm to preemptively schedule n tasks(with due dates) on m uniform processors whenever a solution exists in $O(n\log{n} + mn)$ time.

Which is a stronger problem than I wanted to solve but still gives a polynomial algorithm, which answers my question.


The false sharing is happening in the totals memory block.

The smallest unit of cache is a cache line. On standard x86 and ARM systems, a cache line is 64 bytes. On some PowerPC archs, the cache line is 128 or even 256 bytes. Reading from main memory into the cache is done one cache line at a time, and cache invalidation is done one cache line at a time.

Imagine each element of totals is a uint8. 64 elements of totals fit in one cache line. Every time += is called, the 64 byte cache line containing totals[tid] is read from and written to. That means every core is constantly invalidating that cache line, and the ensuing coordination, “false sharing”, is costly and unnecessary.

You could fix this while maintaining similar code structure by

Padding each element of totals so that it takes up a whole cache line
If totals has enough elements, offsetting your access so that multiple threads tend not to manipulate the same cache line. Ex: index by (tid * 64) % n_elements


What values do $y_i$ in training data for binary classification problems attain?

If your prediction is $f(x) = \text{sign}(w^T x + b)$ then the 0-1 loss will simply be
$$
L_{\text{0-1}}(w) = \sum_{i=1}^n \mathbb{I}\{y_i \neq f(x_i)\},
$$
where $\mathbb{I}$ is the indicator function, i.e., $\mathbb{I}\{a\} = 1$ if $a$ is true and $0$ otherwise. If you were to minimize this directly using subgradient descent you would get the perceptron algorithm. A more common approach is to upperbound the 0-1 loss with some other function, like the hinge loss, log loss, squared loss, etc and minimize that.


Can a Turing machine decide the language $L_\emptyset$ of machines with empty language?

By marking, you probably mean reachability analysis - looking for a path from the initial state to an accepting state. Indeed, the language of a DFA is empty iff there is no such path.

Let's start with an example as to why this fails in TMs. Consider a TM that, in $q_0$, ignores it's input, but writes $a$ on it's tape, moves the head right and goes to state $q_1$, then in $q_1$ it again ignores the input, writes $a$, moves the head left and goes to $q_2$. In $q_2$, if it reads $a$, then it writes $a$, moves the head right and goes back to $q_1$.

That is, the machine just writes $a$ and alternates between two states ($q_1$ and $q_2$) and always has two adjacent $a$'s on the tape.

We now add a transition from $q_2$ that when reading $b$ goes to an accepting state and halts.

The language of this machine is empty. Indeed, the run always gets stuck in the $q_1-q_2$ loop, and will never get to the accepting state. Yet, there is a state-path to an accepting state. So what went wrong?

Well, intuitively, the ``state'' of a TM is not informative enough to describe the continuation of the run. In order to have all the information, you need the configuration of the TM, which includes the state, the position of the head, and the contents of the tape. If you find a configuration-path (which is called a run) to an accepting configuration, then indeed the language is non-empty, and it is an iff condition.

The problem with using reachability analysis on the configuration graph, is that it may be infinite. This is why deciding language emptiness is undecidable.

This is also why language non-emptiness is recognizable - you can perform a BFS on the infinite configuration graph. If there is a path to an accepting state, you will find it eventually. If there isn't, however, then you may get stuck in an infinite search.


Can element uniqueness be solved in deterministic linear time?

You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y.  This does not impose any restrictions of the ordering of X and Y.

Initially all bits are unset.
Iterate over X setting the corresponding bit.
Iterate over Y checking if the corresponding bit was set above.


What is the time complexity of text justification algo?

There are two problems, here. Your foo algorithm doesn't have $\Theta(n!)$ complexity and it isn't the proper tranlation of the dynamic programming system.

foo(0) makes calls with arguments $1, 2, \dots$. The call to foo(1) makes calls with arguments $2, 3, \dots$. So now we have two outstanding calls to each of foo(2), foo(3), .... Each call to foo(2) one more call for $3, 4, \dots$, so we now have four outstanding for each of those.  Thus, foo(i) gets called $2^{i-1}$ times.  The total number of calls is $\sum_{i=1}^n 2^{i-1}=2^i-1$.

But the main problems is that your foo isn't what the dynamic programming system does. The whole point of dynamic programming is to avoid making the same recursive call many, many times. To do this, you remember the results of the function in an array, precisely so you don't have to call the function again.  You can see this in the code fragment you posted: DP[j] isn't a function call, but an array look-up.


All constraints in a linear program are convex (if $x,y$ satisfy the constraints, then $tx+(1-t)y$ also does for all $0 \leq t \leq 1$). The constraint $|a|+b > 3$ is not convex, since $(4,0)$ and $(-4,0)$ are both solutions while $(0,0)$ is not. It is also not closed, which is another reason why you cannot use it in a linear program (change $>$ to $\geq$). The constrict $|a|+b \leq 3$, however, can be used, since it is equivalent to the pair of constraints $a+b \leq 3$ and $(-a)+b \leq 3$.

So absolute values can sometimes be expressed in the language of linear programming, but not always.


Why we can't have FPTAS for strong NP complete problems

If there were an FPTAS for some strongly NP-complete problems then you could use the FPTAS to solve them in polytime. Consider for example bin packing. If the solution is of order $V$, then the input size is of order $V$. Therefore a $1-1/V$-approximation can be achieved in polytime, and since the answer is an integer, such an approximation actually gives the optimal answer. I'll let you work out the details.


Find all disconnected directed (cyclic) subgraphs and transform them into stars

Probably you want to compute weakly connected components, a subgraph having a path between every two vertices in the underlying undirected graph. Computing the weakly connected components is easy: first transform the directed graph into undirected by removing "directions" of each edge and run DFS/BFS on that graph (by looping on vertices!). Alternatively, if you're interested in the strongly connected components then you should run one of the algorithms computing SCCs. This gives you components $C_1, \dots, C_n$.

Then you can do whatever you want to do on these components.


Improving heading measurements from low cost compass module

While 'major' improvements is subjective, you can certainly improve your system more than it is (at least as you have described). Based on your problem description, it sounds as if your measurements may be non linear (you will have to confirm this). If this is the case, then a linear filter, such as the Kalman Filter, won't work well at all.

From here, you need to determine if these 'large periodic deviations and noise' are normally distributed or not. If they are, then you can try a non-linear filter such as the Unscented Kalman Filter (If the deviations are truly 'large', the unscented filter is preferable to the extended as it is more robust to higher levels of non-linearity). If your noise and 'periodic deviations' are not normally distributed, then you will have to consider non-parametric approaches such as the Particle Filter.

As far as sensor calibration, you could try more advanced techniques, but typically the sensor manufacturer will supply some form of calibration procedure. This procedure is typically recommended unless you are absolutely sure about a different strategy.


Floyd's Cycle detection algorithm | Determining the starting point of cycle

You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:

Distance travelled by slowPointer before meeting $= x+y$
Distance travelled by fastPointer before meeting $=(x + y + z) + y = x + 2y + z$
Since fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the meeting point. So by using simple speed, time and distance relation (slowPointer traveled half the distance):
\begin{align*}
2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\
2(x+y) &= x+2y+z\\
2x+2y &= x+2y+z\\
x &= z
\end{align*}
Hence by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover.
They will reach at the point where the loop starts in the linked list.


what is definition of algorithm in computer science?

An algorithm is, alas, an informal concept, which can not have a precise mathematical definition. One can still attempt at an informal definition, and argue that it conveys the right (informal) intuition.

Because of its informal nature, sometimes it's also easy to argue against a given definition, attacking the definition wording. For instance, I've read more than once that an algorithm is a "sequence of steps" which makes my eyebrows raise, since it suggests that any algorithm will always halt within those number of steps, no matter how large the input is. Once, I had a conversation with a physicist where I couldn't follow their argument, and it turned out they identified "halting algorithm" with "constant-time algorithm" since they believed the number of steps were fixed by the algorithm (hence independent from the input).

If I had to define an algorithm, very informally, I would say that it is an informal but unambiguous description that, to each input, it associates a finite sequence of elementary computation steps which can be used to obtain the desired output.

This is far from being perfect. For instance, what is a "elementary computation step"? Further, it does not express that the mapping form input to the sequence of steps must be effective -- otherwise we could associate to all halting TM encodings the steps print 1, and print 0 otherwise.

To fix these issues, I believe that we also need to convey the notion of computability in some way, which is however too much for that definition. One could refer to a specific formalism or programming language, but I'd want that definition to be computation-model-agnostic.

Indeed, one could say that an algorithm is an informal description of, say, a Java program, which is not as detailed as real code, yet is enough detailed that it could be turned into actual Java without needing to do further research, but only doing "coding". I would regard such a definition as quite inelegant, though.


Optimal substructure and dynamic programming for a variant of the rod cutting problem

Answer My Own Question:

Let $L$ be the length limit array.

Define $R(i, L)$ to be the maximum revenue obtainable by cutting up a rod of length $i$ with the length limit array $L$. The recursion is (consider the leftmost piece of length $j$; the base cases are not included):

$$R(i, L) = \max_{1 \le j \le i \land L_j \ge 1} \Big(p_j + R\big(i-j, L[j \mapsto L_j-1]\big)\Big),$$
where $L[j \mapsto L_j - 1]$ leaves other length limit than $L_j$ unchanged.


Proving that it is undecidable if a Turing machine accepts a language that is its own reverse

The decision problem

  Given Turing machine $M$, is $L(M) = (L(M))^R$?

is undecidable. This is a simple consequence of Rice's theorem.

The property (i.e. class of Turing-recognizable languages)

$$\mathcal{S}_{\mathrm{rev}} = \{ L \mid L \; \text{recognizable and } L = L^R \}$$

is non-trivial, since $\emptyset \in \mathcal{S}_{\mathrm{rev}}$ and $\{ ab \} \notin \mathcal{S}_{\mathrm{rev}}$.


It depends on what kinds of things you can store on the stack.

If each item on the stack is of unbounded size, you can simulate a two-counter machine, which is Turing-complete.  Therefore, in this case, you can achieve Turing-completeness with just the ability to access the top two items on the stack.

If items are bounded-size, restricting to access a bounded number of top-most items of the stack gives something equivalent in power to a PDA.  (For instance, suppose all you can do is access the top 5 items of the stack, and use that together with a finite control to transition to a new state of the finite control and either push/pop.  Then grouping the items into 5-tuples, we can build an equivalent machine where you only need to access the topmost item.  That machine is a PDA.)  Therefore, in this case, it's not Turing complete with access to any finite number of items at the top of the stack.


Is function `number of TM which terminates on an empty word` computable?

Is that proof correct?

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

This TM works as following:

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

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


How, in hardware, MIPS can access a word in the middle of an address

First of all, to short circuit your question, I must say that you can not ready from multiple memory locations at the same time in the MIPS architecture.

Second, your interpretation of the offset is wrong. You assumed the offset is a bit offset, while it's actually an offset in bytes. Meaning if you give the address 2 and offset 4, the memory location to be read from will be 6 (2+4).

Third, more details into the MIPS lw (load word) instruction. The syntax is as follow:
lw  \$d, off(\$r), where \$d is the destination register (where the word is loaded to), off is an immediate 32 bit constant and \$r is your base register. What happens is as follow:

The target ram address is calculated by adding off and the value in \$r.
The calculated address in loaded in the memory register
The control unit enabled the RAM to get the value at the address
The value is set to the \$d register

Fourth, something I haven't mentioned before, related to the addressing pattern of the ram. As you may know, the ram stores bytes, no actual words. What's the problem you may wonder? It's something called word alignment, and it's the reason why you couldn't load a word from address 6. A word is a 4 byte value, and for fast design purposes, when loading a word, the address has to be a multiple of 4. I won't go in the design details, but suffice to say that this permits greater memory transfer speed than allowing any address.

What this means is that when loading and storing words, you have to respect the word boundaries. If you try to read from a bad memory location i.e. not a multiple of 4, e.g. 6, you will have a memory exception; meaning you program likely crashes.

In practice, this mean that if you have to store tree words a,b and c, you could store them at address 0x01234560, 0x01234564 and 0x01234568.

EXTRA: why use an offset

So, in my last example, you might have noticed my words were close in memory, but i didn't start at 0x00000000. Actually, the first word starts at adress 0x01234560. Here's how you can take that into consideration with the lw syntax.

First, set the value of \$r to 0x01234560
Then, to load a, you write lw \$d, 0(\$r). The will load the value at 0+\$r, 0 + 0x01234560 = 0x01234560
Then, to load b, you write lw \$d, 4(\$r). The will load the value at 4+\$r, 4 + 0x01234560 = 0x01234564
Then, to load c, you write lw \$d, 8(\$r). The will load the value at 8+\$r, 8 + 0x01234560 = 0x01234568

I hope this completely answers your question. The only thing I haven't touched is why you'd end up at such complex memory locations. Short answer: it's due to the structure of the compiled program and the way it's loaded into memory. I suggest you look further into that before delving deeper into the world of computer electronics. A sound knowledge of the structure of a program will greatly help understand why the CPU and instruction set were made that way.


How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar?

We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at.

The second crucial idea is that we have to reverse the process: TMs take the word as input and convert it to $1$ or $0$, or they don't terminate. The grammar, however, has to generate the word. Luckily, grammars are inherently non-deterministic, so we can just let it "guess" where the accepting $1$ came from; all words that cause the TM to accept can be generated then.

Let $\cal{Q} = \{Q_0,\dots,Q_k\}$ the set of state-nonterminals; w.l.o.g. let $Q_0$ be the starting-state-nonterminal and $\cal{Q}_F \subseteq \cal{Q}$ the set of accepting-states-nonterminals. First, we need starting rules that generate all possible accepting configurations:

$\qquad \displaystyle S \to \#1Q_f\# \qquad$ for all $Q_f \in \cal{Q}_F$.

Similarly, we terminate when we "reach" the starting state in the correct position, namely on the first symbol:

$\qquad \#aQ_0 \to \#a \qquad$ for all $a \in \Sigma$.

Translating the actual state transitions is straight-forward:

$\qquad \begin{align}
  aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\
  aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\
  abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q')
\end{align}$

There are some technical kinks to iron out; for instance, you have to get rid of the boundary markers $\#$ at the end. That can be done by spawning two special nonterminals instead of terminating, swapping those to the ends and then removing the $\#$ along with them. Furthermore, more $\#$ have to be created on demand; that requires some hacking of the rules with $d=\#$.

Also, the construction becomes a bit more complicated if the TM uses non-input symbols. In that case, the termination rules may be wrong: if there are non-input symbols somewhere on the tape, we have not generated a proper word. This can be fixed similarly to removing $\#$: spawn a special non-terminal from $Q_0$ that is swapped to the right and only removed if all symbols are from $\Sigma$.


AdaBoost - why using such alpha function?

Recall that the final hypothesis after $T$ rounds is $h_T(x)=sign\left(\sum\limits_{i=1}^T \alpha_t h_t(x)\right)$, i.e. $\alpha_t$ is the weight of $h_t$ in $h_T$. If $\epsilon_t$ is high (near one) you want to answer the opposite of $h_t$, so you want $\alpha_t$ to be negative and very large in absolute value. If on the other hand $\epsilon_t$ is very low then you want $\alpha_t$ to be very large. The worst case is $\epsilon_t=\frac{1}{2}$, in which case $h_t$ is of no use to you.
The function $\log\frac{1-\epsilon_t}{\epsilon_t}$ satisfies those properties. This magnitude is known as log odds (where the probability considered is $p=1-\epsilon_t$, the success probability). Intuitively, the odds ratio tells you how often an event with probability $p$ occurs, in our case if e.g. $\epsilon_t=1/3$ then $\frac{1-\epsilon_t}{\epsilon_t}=2$, i.e. $h_t$ is expected to succeed with ratio $2:1$.


If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?

In order to estimate the lower bound on $k$, you use the estimate $1/(1+\epsilon) = 1-\epsilon+\Theta(\epsilon^2)$, which is true as $\epsilon\to0$ (which is certainly your case). Using this, we can analyze the denominator:
$$
\begin{align*}
\bar{p}-1+\frac{1}{4\bar{p}} &= \frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\frac{1}{1+2/p(n)} \\ &=
\frac{1}{p(n)}-\frac{1}{2}+\frac{1}{2}\left(1 - \frac{2}{p(n)} + \Theta\left(\frac{1}{p(n)^2}\right)\right) \\ &=
\Theta\left(\frac{1}{p(n)^2}\right).
\end{align*}
$$
Therefore the lower bound on $k$ is of order of magnitude $$\Theta(np(n)^2).$$