Is there an algorithm that provably exists although we don't know what it is?

The simplest case I know of an algorithm that exists, though it is not
known which algorithm, concerns finite state automata.

The quotient $L_1/L_2$ of a language $L_1$ by a language $L_2$ is
defined as $L_1/L_2=\{x \mid \exists y\in L_2 \text{ such that } xy\in L_1\}$.

It is easily proved that regular set are closed under quotient by an
arbitrary set.  In other words, if $L_1$ is regular and $L_2$ is arbitrary (not necessarily regular), then $L_1/L_2$ is regular, too.

The proof is quite simple. Let $M=(Q,\Sigma,\delta,q_0,F)$ be a FSA
accepting the regular set $R$, where $Q$ and $F$ are respectively the
set of states and the set of accepting states, and let $L$ be an
arbitrary language. Let $F'=\{q\in Q\mid \exists y\in L \;\;\delta(q,y)\in
F\}$ be the set of states from which a final state can be reached by
accepting a string from $L$.

The automaton $M'=(Q,\Sigma,\delta,q_0,F')$, which differs from $M$
only in its set $F'$ of final states recognizes precisely $R/L$.  (Or see  Hopcroft-Ullman 1979, page 62 for a proof of this fact.)

However, when the set $L$ is not decidable, there may be no algorithm
to decide which states have the property that defines $F'$. So, while
we know that the set $F'$ is a subset of $Q$, we have no algorithm to
determine which subset. Consequently, while we know that $R$ is
accepted by one of $2^{|Q|}$ possible FSA, we do not know which it is.
Though I must confess we know to a large extent what it looks like.

This is an example of what is sometimes called an almost constructive
proof, that is a proof that one of a finite number of answers is the
right one.

I suppose an extension of that could be a proof that one of an
enumerable set of answers is the right one. But I do not know any. Nor
do I know a purely non-constructive proof that some problem is
decidable, for example using only contradiction.


Find a truth assignment of 2SAT that has the most number of true variables?

Your problem is known as Weighted-2-satisfiability, and is known to be NP-complete. The easiest way to see that is by reduction from Vertex Cover (exercise).

Note that the link above is about whether there is a satisfying assignment having at most $k$ true variables. This is equivalent to your problem (exercise).


Solve PARTITION-INTO-THREE-SETS in pseudo-polynomial time

Yes, there is a pseudo-polynomial algorithm for this problem.

Here is a wrong algorithm. Can you spot the biggest error?

Let $K=\sum_{i=1}^n{a_i}$. If $K$ is not divisible by 3, return none.

Run the pseudo-polynomial algorithm with $\lfloor K/2\rfloor$ replaced by $K/3$ everywhere. Adapting the algorithm so that it tracks the set of numbers whose sum is a given number. If that run of that algorithm return false, return none. If yes, remove the set of numbers from $a_1, a_2, \cdots, a_n$, we reduce the problem to find a subset of the remaining numbers whose sum is $K/3$, or half of the sum of remaining numbers, which is, of course, the partition problem again and which can be solved in pseudo-polynomial time.

Let us see how to construct a correct algorithm.

In the pseudo-polynomial algorithm for partition into two disjoint subsets, the goal is to compute function $p$ such that $p(i, j)$ is True if a subset of $\{x_1, \cdots, x_j \}$ sums to $i$ and False otherwise.

Now for partition into three disjoint subsets we have two variable parts, the first subset and the second subset (the third subset is the remaining integers), our goal is to compute function $q$ such that $q(h,i,j)$ is True if there are two disjoint subsets of $\{x_1, \cdots, x_j \}$ such that one of them has sum $h$ and the other has sum $i$, where $0\le h\le K/3, 0\le i\le K/3$. We have the following recurrence relation, ignoring a few corner cases because of the out-of-bound situations that are easy to figure out.

$q(h, i, j)$ is True if either of the following is true.

$q(h, i, j − 1)$
$q(h, i − x_j, j − 1)$
$q(h-x_j, i, j − 1)$

$q(h, i, j)$ is False otherwise.

I will leave the rest for readers to figure out.

Exercise 1. Write the correct algorithm roughly or fully in pseudocode or in your favorite programming language. Adapt it so that it will track the subsets in order to return the wanted three disjoint subsets.

Exercise 2. Show the time-complexity of the correct algorithm is $O(nK^2)$.

Exercise 3. Generalize to PARTITION-INTO-M-SETS for any given integer $M\ge2$.


What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?

As $\log(n) \times \log(n) = \log^2(n)$, you can say $\log(n) \times \log(n) = O(\log^2(n))$.Moreover, as $\lim_{n\to\infty}\frac{\log(n)}{\log^2(n)} = 0$, you can't write $\log(n) \times \log(n) = O(\log(n))$, but you can write $\log(n) \times \log(n) = \omega(\log(n))$.


What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

To get the sequence $T = \{4,7\}$ from $S = \{4,2,7,2\}$, you can take the entire set S as a minipart and remove $2$ from it. Therefore, there is just one minipart.

To get the sequence $T = \{4,7\}$ from $S = \{4,7,1,4,1,7,1\}$, you can take three minimarts as follows:

$P1 = \{4\}$
$P2 = \{7\}$
$P3 = \{1,4,1,7,1\}$

Now, remove $4$ from $P1$, remove $7$ from $P2$, and remove $1$ from $P3$. You will get the sequence $T = \{4,7\}$.


Ambiguous grammar? Could the grammar be parsed by SLR parser?

Your grammar indeed is ambiguous as it currently is, but not because the follow sets of two nonterminals have common elements. The ambiguity I see is that both re2 -> re1 -> expr -> term -> factor -> num -> ε and re2 -> re1 -> expr -> term -> factor -> id -> ε derive the empty word. If you require that num and id are both nonempty, then your grammar is SLR(1) (unless you do weird things to make num and id nonempty).

As an example where your 'follow test' does not work is the following:

S -> A c
S -> B c
A -> a
B -> b

The follow sets of A and B both contain c, but the grammar is SLR(1).

Unfortunately, the only three options I know to test whether a grammar is SLR(1) all have downsides: generating the table and doing the polynomial time test both take quite some time for an exam, and the third method, visual inspection of the grammar, is not very accurate. Finally, 'quickly' writing down the LR(0) automaton (by omitting the items in the states of the automaton) is possible but requires a lot of practice and is still somewhat inaccurate.


Numerical example of theoretical diff file size using Kullback Leibler?

I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL)

That's not quite right.  I suspect you've taken an imprecise, non-technical, handwavy statement from Wikipedia and interpreted too much into it.  They're trying to summarize some underlying theory in an informal way, but such summaries are inevitably incomplete.  Instead, you'd be better off reading and understanding the underlying theory.

There is a sense in which that statement is correct if we make certain assumptions -- e.g., that the source is memoryless (each character is independent of all past ones, with no history), and that we interpret it in an asymptotic, average-case kind of way -- but for many real-world sources of  data, those assumptions don't apply.


What is the computational complexity of k bit subset sum problem?

I'm assuming that when $k=1$, the $k$th bit is the LSB.

If $b = 0$ then the answer is always positive, since you can take the sum of the empty subset.

If $b = 1$ and one of the numbers has its $k$th bit equal to $1$ then the answer is positive, so we can assume that all $k$th bits are equal to $0$. Reduce all numbers modulo $2^k$. Since originally the $k$th bits were $0$, all numbers are less than $2^{k-1}$. If the sum of all numbers is less than $2^{k-1}$, then clearly the answer is negative. If the sum of all numbers is at least $2^{k-1}$, arrange them in some arbitrary order $x_1,x_2,\ldots$, and sum them one by one until reaching the first sum $s_i = x_1 + \cdots + x_i$ which is at least $2^{k-1}$. Since $s_{i-1} < 2^{k-1}$ and $x_i < 2^{k-1}$, we see that $s_i < 2^k$. Thus the $k$th bit of $s_i$ is $1$. Hence the answer is positive.

Summarizing, here is our algorithm:

If $b = 0$, answer True.
If $b = 1$ and there exists a number whose $k$th bit is $1$, answer True.
If $b = 1$ and all $k$th bits are $0$, reduce the input modulo $2^k$, and answer True if the sum of all reduced numbers is at least $2^{k-1}$.


It is a general feature of reasonable total programming languages that they do not have self-interpreters, but interpreters for reasonable programming languages are Turing-computable. So, a concrete example of a total computable function which is not definable in a total programming language is an interpreter for that programming language.

See Definition 2.1, Theorem 2.2, and Corollary 2.3 of this note. It proves that a self-interpreter for Gödel's T is not definable in Gödel's T. You can use the exact same proof for MLTT.

It is generally well known that a confluent terminating normalization system such as that of MLTT leads to a Turing-computable normalization procedure.


Language involving irrational number is not a CFL

According to Parikh's theorem, if $L$ were context-free then the set $M = \{(a,b) : a \leq \gamma b \}$ would be semilinear, that is, it would be the union of finitely many sets of the form $S = u_0 + \mathbb{N} u_1 + \cdots + \mathbb{N} u_\ell$, for some $u_i = (a_i,b_i)$.

Obviously $u_0 \in M$, and moreover $u_i \in M$ for each $i > 0$, since otherwise $u_0 + N u_i \notin M$ for large enough $N$. Therefore $g(S) := \max(a_0/b_0,\ldots,a_\ell/b_\ell) < \gamma$ (since $g(S)$ is rational). This means that every $(a,b) \in S$ satisfies $a/b \leq g(S)$.

Now suppose that $M$ is the union of $S^{(1)},\ldots,S^{(m)}$, and define $g = \max(g(S^{(1)}),\ldots,g(S^{(m)})) < \gamma$. The foregoing shows that every $(a,b)$ in the union satisfies $a/b \leq g < \gamma$, and we obtain a contradiction, since $\sup \{ a/b : (a,b) \in M \} = \gamma$.

When $\gamma$ is rational, the proof fails, and indeed $M$ is semilinear:
$$
\{ (a,b) : a \leq \tfrac{s}{t} b \} = \bigcup_{a=0}^{s-1} (a,\lceil \tfrac{t}{s} a \rceil) + \mathbb{N} (s,t) + \mathbb{N} (0,1).
$$
Indeed, by construction, any pair $(a,b)$ in the right-hand side satisfies $a \leq \tfrac{s}{t} b$ (since $s = \tfrac{s}{t} t$). Conversely, suppose that $a \leq \frac{s}{t} b$. While $a \geq s$ and $b \geq t$, subtract $(s,t)$ from $(a,b)$. Eventually $a < s$ (since $b < t$ implies $a \leq \frac{s}{t}b < s$). Since $a \leq \frac{s}{t} b$, necessarily $b \geq \lceil \tfrac{t}{s} a \rceil$. Hence we can subtract $(0,1)$ from $(a,b)$ until we reach $(a,\lceil \tfrac{t}{s} a \rceil)$.


Rotation matrix between two objects - alignment

You probably want to find a homography that maps object A to object B.  I suggest reading about image rectification/alignment/registration.  A homography is a linear function of the form

$$q = Ap+b,$$

where $A$ is a matrix, $b$ is a translation vector, $p$ is a point from object $A$, and $q$ is the corresponding point from object $B$.

If you have four points from object A and the corresponding four points in B, you can solve uniquely for a homography that maps each of those A-points to the corresponding B-point (using linear algebra).  There are standard methods for finding that homography in the computer vision literature, based on solving a system of linear equations.  For instance, OpenCV has a method that will do that for you.

More generally, if your points have some small amount of error in them, it can be more effective to take more than four points and then find the best-fit homography.  For instance, you could take five points, or six points, or 10 points, and find the best-fit homography that maps those 10 points from object A (as close as possible) to the corresponding 10 points from object B.  This becomes a least-squares fit problem, where you want to minimize the sum of the squared distances between (homography applied to point from object A) and (location of corresponding point in object B).  There are ways to find that best-fit homography using a least-squares fit.

There's lots more one can say about the subject -- it has been studied extensively in the image processing and computer vision literature. See https://en.wikipedia.org/wiki/Point_set_registration for a starting point.


One of the simplest ways to avoid TOCTTOU issues is for your system calls to perform the check at time of use (within the system call) instead of trusting a prior check. If you can gracefully fail a check upon use, the caller can instead rely upon exception handling to avoid a check race or a vulnerability. This methodology will help with both long-running and short-running scenarios.

To further assist with short-running scenarios, you could implement transactions for your security-related system calls. Of course, this would require being architected in early on, and would influence the design of the system call APIs, but it would provide concurrent consistency across the system.


An algorithm to find the closest match between 2 arrays of RGB pixel tuples

You can't satisfy both goals.  Suppose $A=[10,20,30]$ and $B=[10,20,30]$; then you presumably want the modified $B$ to be $[10,20,30]$.  Now suppose $A=[10,20,30]$ and $B=[10,30,20]$; then you presumably want the modified $B$ to be $[10,20,30]$.  The original A and the modified B are the same in both cases, so there is no way to tell from them what the original $B$ was (both remain a possibility).


"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

Charles Dodgson -- who wrote those words under the name of Lewis Carroll -- was a brilliant mathematician with a taste for whimsy, all of which provide an interesting undercurrent to works such as Through the Looking Glass. Humpty's creed could have been taken directly from Dodgson's textbook on Symbolic Logic:

[Authors of other textbooks on logic]… speak of the Copula of a Proposition “with bated breath”, almost as if it were a living, conscious Entity, capable of declaring for itself what it chose to mean, and that we, poor human creatures, had nothing to do but to ascertain what was its sovereign will and pleasure, and submit to it.
In opposition to this view, I maintain that any writer of a book is fully authorised in attaching any meaning he likes to any word or phrase he intends to use. If I find an author saying, at the beginning of his book, “Let it be understood that by the word ‘black’ I shall always mean ‘white’, and that by the word ‘white’ I shall always mean ‘black’,” I meekly accept his ruling, however injudicious I may think it. (Dodgson18??, p. 166)

This is particularly true in computer science, in which most papers seem to be about 75% definitions, loosely interconnected with proofs. The definitions need to be repeated in every paper because there are often conflicting uses of the same phrases in the literature. This often creates a kind of cognitive dissonance for learners, who have been schooled in a model of teaching which presents definitions as received truth:

To be more accurate, we might say that what eludes the
students is the distinction between a dictionary definition as
a description of pre-existing objects and a mathematical
definition as the chosen basis for deduction, one which
serves to determine the nature of the objects. (AS2002, p. 33, emphasis added).

The distinction is important. Definitions are a way to organise one's understanding of the world, and the liberty to choose categories appropriately is an important part of mathematical thinking. So Dodgson's advice and Simon & Alcock's observation, both directed at teachers of mathematics, seem to me to continue to be relevant.
On that basis, I assert that Alex Aiken has every right to define "handle" as he sees fit. Perhaps he has a good reason to use this particular definition, which will be revealed later. Or perhaps not, because we all make mistakes, even famous presenters of popular courses. The test will come later, when the definition proves to be useful (or not). Because definitions (in the mathematical sense) are neither right nor wrong; they are simply useful or not.
However, like Dodgson, I too reserve the right to think that a definition may be injudicious, and it seems to me that Aiken's definition of handle as being the entire input up to the point of reduction is not as useful as the normal definition of handle as a production which could be reduced at a given point of input. (As the authors of the Dragon book point out, although they often talk about handles as though they were a subsequence of the stack, they actually define the handle to be the production itself.)
Both definitions involve the necessary fact that a handle is rooted in a moment in the parse. The fact that the right-hand side of a production happens to match the top of the stack does not necessarily make that production into a handle; it is only a handle because the reduced stack could appear in a rightmost derivation.
Aiken later talks about the handle as something which can be reduced, which implies that it is not simply the stack at the point of the reduction, as his definition appears to say, but the stack at the point of the reduction with a marker indicating what reduction will take place. If it were just the stack, an ambiguous grammar would have a single handle, which obscures the concept of ambiguity. I prefer to say that a grammar is ambiguous if there could be more than one handle at a point in the parse.
I have no doubt that Aiken, Aho&al, and, less importantly, I have the same concept of what a handle is for. And the essential point of that concept is that a reduction (or right-hand side) is a handle for the entire parser stack, not just a reduction whose right-hand side happens to match the top of the stack.
This would all be a minor point if it were not for the quiz Aiken inserts into the course immediately following his definition, which asks the student to focus on the definition rather than the use (in the sense highlighted by Alcock & Simpson).
[AS2002] Alcock, L. and Simpson, A. P. (2002) 'Definitions : dealing with categories mathematically'. In For the learning of mathematics, vol. 22 No. 2, pp. 28-34.
[Dodgson1896] Dodgson, Charles Ludwig (published under the name Lewis Carroll) (1896), 'Symbolic Logic', 2nd edition.


How would a neural network deal with an arbitrary length output?

You just add more neurons. You're right that it's often not useful (if you only get 5 bits of information in, it's hard to put 10 bits of information out), but if you want to (e.g. because your output format is less dense), go ahead.

As a trivial example, if you wanted to create an ANN to convert characters to graphemes (as represented on an 8x8 grid of on/off pixels) you could have 26 input neurons and 64 output neurons. Connect each input neuron to the output neurons which would be turned on if that character is being displayed; then the output neurons' function is just logical OR.

The standard learning algorithms like gradient descent should work fine no matter the size of the output layer.

EDIT: I guess your question is: "how do you handle unknown input and output lengths?" Any Turing machine can be simulated by a recurrent neural network, so you will never run into a "halting problem" (if I understand what you mean by that phrase).

It's very rare that you can't bound the size of the output as a function of the input size. So you just have some metalearning procedure which generates the network for you on the fly.

One common idea is that of "template" models. I'm not familiar with text-to-speech, but I guess you would make an assumption like "no phoneme spans more than 6 characters". So you build your network with 6 inputs, and just repeat it for as long as the word is. You need some rule like "each network gives the pronunciation of the middle two characters" to handle overlaps, as well as some special handling for the beginning and end of words too.


The graphs that you get are known as unit disk graphs. There is a vast literature about algorithms on unit disk graphs. Since you are asking about shortest paths, check out this article by Cabello and Jejcic. Of course all of this will not take into account that the graphs are generated by some random process.

For further references consult the wikipedia page or the Cabello and Jejcic paper.


Detection stability is about consistency of detection, in this case rare events are classified independent of small changes. One might think of detector having smooth function when it is stable and chaos-like, heavily discontinous when it is not.

Detection stability in the case of rare events (rare attacks) is about consistency and fluctuation. The lack of stability means that similar events, that differ marginaly will not be detected, becase the techniques are very prone to fluctuations - that is a very bad property, malicious query with e.g. $99\%$ classification when changed slightly might drop below detection threshold. Another outcome is that slight changes to the rest of population will influence rare queries.


Is there a universal learning rate for NeuralNetworks?

There is no universal learning rate. It depends on your problem space (Are you solving a problem with many local minima or just one? Does your problem’s solution vary dramatically based on a slight change to your input or does the solution gradually shift?, etc.), and it depends on your network architecture (number of layers, number of hidden layers. Do you have a feedback loop etc).

Character recognition is relatively easy for example so you could try a faster learning rate. I once tried to teach a neural network to understand a simple computer machine code, and after a month of training with a dozen computers, it always came close but never solved the problem 100% correctly. No choice of learning rate worked to get me to the solution.

Once I broke down the problem space into a few subcomponents, the entire set of neural networks were trained in under an hour. I used the same choice of training rate in both cases (see below). A good example of how the rate of convergence changes based on the problem being trained.

What I found works best is to start with a fast learning rate to quickly find local minima, but then reduce the rate with each successive training, down to some limit.

All that to say that there is no universal learning rate, and that it worked best for me to reduce it as the training proceeds.


It is conjectured that $\mathsf{P} \neq \mathsf{NC}$, and so no $\mathsf{P}$-complete problem has polylogarithmic parallel algorithms. This in no way contradicts the existence of a linear time and space algorithm for DFS.


$A\bigoplus B$ can be empty (and thus definitely not $NP$-complete) if we pick $A$ and $B$ carefully. For instance, if all strings in $A$ have even length and all strings in $B$ have odd length then $A\bigoplus B$ is empty.

It is fairly easy to modify any $NP$-complete language $L$ to have either only even (resp., odd) strings: let $L'$ be the language consisting of strings formed by prepending $1$ to any odd (resp., even) length string from $L$ and prepending $01$ to any even (resp., odd) length string from $L$.

Note that we can easily recover the original language $L$ from $L'$ by noting that any string that was originally of odd length starts with a $1$ (and thus we must drop the first character), and any string that was originally of even length starts with $01$ (and thus we must drop the first two characters).


Dynamic Programming Travel Planning Problem

Hint: For each $0 \leq i \leq n$ and $0 \leq t \leq i$, calculate the optimal route between city $0$ and city $i$ using $t$ plane rides and $i-t$ train rides.


First of all, I assume that $C_1^4 \equiv O \iff (X_2 \lor A)$ in accordance to $F_1$. Second, note that 3CF as defined in the exercise is equivalent to 3CNF. In the following, I will denote with $\phi_X$ the subformula of the given formula $F$ which has been assigned new variable $X$ by the construction. For example, $\phi_A=(\lnot P \land S)$ and $\phi_O = F_1$.
$\renewcommand{\models}{\mathop{|\!\!\!=}}\newcommand{\rmodels}{\mathop{=\!\!\!|}} \newcommand{\semeq}{\models\!\rmodels}$

Satisfaction equivalence

  I don't see why $X_1$ is satisfiable

$X_1$ is a single variable and thus trivially satisfiable (by setting it to $1$). The $C_1^i$ essentially take apart $F_1$ operator by operator, introducing new variables that have to evaluate to the same truth values as their respective subformulae. Using $\{O\}$ as clause of $C_1$ guarantees the statement, essentially (as "$O \semeq F_1$", given $C_1$).

Proof

Assume $F_1$ is satisfiable and let $\psi$ be a satisfying valuation of the variables. Construct $\psi'$ by extending $\psi$ with $\psi'(X) = \psi(\phi_{X})$ for $X \in \{X_1,X_2,A,O\}$. As a consequence, $\psi'$ satisfies all $C_i^1$. Because $\psi(F_1)=1$ by assumption, we have chosen $\psi'(O)=1$. Therefore, $\psi'(C_1)=1$.

Conversely, assume $C_1$ is satisfiable and let $\psi$ a satisfying valuation. Clearly, $\psi(O)=1$ and $\psi(C_1^4)=1$. Therefore, $\psi(\psi_O)=1$. Because $\psi_O=F_1$, we are done -- $\psi$ satisfies $F_1$. In order to be rigorous, we would have to iterate this argument top-down, following the structure of $F_1$, to unfold $X_2$ and then $X_1$ (in the general case, we would need a structural induction here).

Size restriction

The constraining formulae all have the same form and are small (three literals, two operators). You can transform those into equivalent 3CF formulae locally, i.e. ignoring the others. This conversion always yields formulae with at most 24 literals, that is at most 8 clauses. This can be shown by dull calculation.

Details

The general form of a contraining formula is $A \iff (A \circ B)$ for $\circ$ some logical operator. Let us transform it into 3CF using laws and rules of boolean algebra.

$\qquad \begin{align}
  C^i &\equiv X \iff (A \circ B) \\
      &\semeq\ [X \land (A \circ B)] \lor [\lnot X \land \lnot(A \circ B)] \\
      &\semeq\ [\lnot X \lor (A \circ B)] \land [ X \lor \lnot(A \circ B)]
\end{align}$

Now, for $\circ = \land$, we use both distributive and associative law resp. De Morgan's rule:

$\qquad \begin{align}
  C^i &\semeq\ [\lnot X \lor (A \land B)] \land [ X \lor \lnot(A \land B)] \\
      &\semeq\ [\lnot X \lor A] \land [\lnot X \lor B] \land [ X \lor \lnot A \lor \lnot B]
\end{align}$

This has three clauses (after padding with redundant literals, nine literals). For $\circ \in \{\lor, \to\}$¹ this works exactly the same way. You can proceed similarly for other choices of $\circ$, such as $\oplus$ or $\iff$, depending on which operators are allowed in your setting.

Generalisation

This is just a matter of writing down what the example does in general terms. Let $F$ an arbitrary propositional formula, w.l.o.g. without "negation chains"². Now do the following.

$\quad$ Let $i=0$.
$\quad$ Until $F$ is a literal, do
$\qquad$  Increase $i$ by one.
$\qquad$  Pick a subformula of $F$ of the form $L_1 \circ L_2 = \phi$ with $L_1,L_2$ literals.
$\qquad$  Let $C^i \equiv X_i \iff (L_1 \circ L_2)$.
$\qquad$  Replace $\phi$ with $X_i$ in $F$.
$\quad$ For all $j=1,\dots,i$, convert $C^j$ into 3CF by finite case distinction.
$\quad$ Return $[F \lor F \lor F] \land \bigwedge_{j=1}^{i} C^j$.

Note that $F = X_i$ after the loop. For intuition and implementation purposes, think of a formula as a tree: operators are inner nodes, leaves are literals. Above algorithm iteratively contracts subtrees of height two into leaves, collecting the $C^j$ as "mapping" from new variable to the removed subtree along the way.

Remember $A \to B \semeq \lnot A \lor B$.
We can always use $\lnot \lnot A \semeq A$.


How to solve for recurrence with substitution or other methods?

Use the Akra-Bazzi theorem. Let $p$ be the solution to $2\cdot(1/3)^p + (1/2)\cdot(2/3)^p= 1$, namely $p = 1$. Compute
$$ S(n) = \int_1^n \frac{x^2}{x^{p+1}} \, dx = n-1= \Theta(n). $$
Then $T(n) = \Theta(x^p S(n)) = \Theta(n^2)$.


Kripke Models - evaluating the meaning of $\Box\Box p$

This is an unfortunate use of the word “reachable”, in that Kripke structures are graphs but “reachable” in a Kripke structure is not the same thing as “reachable” in a graph.  Let us avoid this confusion by saying that a state $y$ is a successor of state $x$ if there is a (directed) edge $(x,y)$ in the structure.

Now, the semantics of modal logic says that $\Box\varphi$ is true at state $x$ if, and only if, $\varphi$ is true at every successor of $x$. Informally, $\Box\varphi$ means, “$\varphi$ is true everywhere I can get to from here in one step.” So, to understand the meaning of $\Box\Box p$, just substitute $\Box p$ for $\varphi$:

$\Box p$ is true at every successor
$p$ is true at every successor of every successor.

In other words, $p$ is true everywhere I can get in two steps.  Note that this is not, in general, the same thing as $\Box p$, which means that $p$ is true after one step. Indeed, one can show that $(\Box \varphi)\rightarrow (\Box\Box\varphi)$ is a tautology in a particular Kripke frame if, and only if, the successor relation is transitive.

Note that, without assuming transitivity, basic modal logic with only $\Box$ and $\Diamond$ has no way of expressing “$\varphi$ is true everywhere that can be reached from here, in any number of steps” (i.e., the usual graph-theoretic meaning of “reachable”).


I'll just expand one of the attacks mentioned in D.W.'s comment; this attack seems the most relevant to your question, but other attacks may exist according to the parameters you actually use.

Ideally, an encryption can be viewed as a permutation $\pi_i$ (determined by $e_i$), that maps $\{0,\ldots,n-1\}$ to itself. If you don't know the two permutations and you don't know the messages $m_i$, there is no way to tell if you used the permutation $\pi_1$ or $\pi_2$ by only seeing a small number of (image only) samples.

Under certain assumptions, RSA is a good encryption. This means you cannot decrypt a codeword $c$ and find $m$ such that $m^e=c \mod n$, even if you know $e$. Of course, information-theoretically, knowing $e$ gives you all the information you need to find $m$ from $c$–it fully specifies the permutation. But for a computationally-bounded Eve, we assume this is impossible.

However, if $n_1 \ne n_2$, Eve gets a certain advantage in distinguishing ecryptions in the two settings. By definition, $c_1 \in \{0,\ldots, n_1-1\}$ while $c_2 \in \{0, \ldots, n_2-1\}$. So if $n_1$ is very different from $n_2$ (say, $n_2>n_1$), and Eve is lucky to see $c_i \in \{n_1, \ldots, n_2-1\}$, she knows that this message was encrypted using $(e_2,n_2)$. Assuming RSA is close to a random permutation, then this has probability of about $1/(n_2-n_1)$ per sample.


How could an SMT solver be implemented as simple as possible?

What happens next is that we invoke a SMT solver to try to check whether the formula

$$x+y < 20 \quad \land \quad  x > 10 \quad \land \quad y > 10$$

is satisfiable.  The solver tries to find values for $x,y$ that make this formula true.  If it finds such a value, then it knows the assume(false) statement is reachable. (I am guessing you meant to write assert(false), not assume(false).)  If the formula is not satisfiable, then that statement is not reachable.

So basically you are asking: how do SMT solvers work?  That is too broad for this site, but there are lots of places that explain how SAT solvers and SMT solvers work.  I would suggest doing some research; you will find many explanations.  You could start with the DPLL algorithm for SAT.

There is little point in implementing your own solver.  Your solver will probably perform far worse than existing tools.  There has been a lot of research into building effective solvers, and the techniques required are non-trivial.  Instead, I'd recommend you simply use an existing solver, such as Z3.

If you just want to implement one for fun, the most straightforward approach is probably to bit-blast to SAT: treat each bit of (the binary representation of) $x,y$ as a boolean variable, then write down a boolean formula (on those boolean variables) that expresses the requirement that $x+y<20$.  How can you do that?  Write a boolean circuit that computes $x+y$ and compares the sum to 20, then convert that circuit from CircuitSAT to SAT.  Finally, invoke an off-the-shelf SAT solver to check satisfiability of this boolean formula.  You'll need to do some research to understand each of these steps, but there's a lot written on how to do that.


Algorithm for determining if there is exactly one Eulerian path

Do you know an algorithm for finding Eulerian paths?
Fleury's algorithm begins at one of the endpoints and draws out the eulerian path one edge at a time, then imagine removing that edge from the graph. The only trick to the algorithm is that it never chooses an edge that will disconnect the graph. Only with that condition, it is guaranteed to never get stuck in tracing out an eulerian path.
So, as long as that choice of edge is unique at every step, the eulerian path will be unique. If ever there are two choices that can be made which are valid (i.e. they each would not disconnect the graph) then you have multiple eulerian paths.


Can a probabilistic Turing Machine compute an uncomputable number?

Consider the following reasonable definition for a Turing machine computing an irrational number in $[0,1]$.

  A Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, it outputs the first $n$ digits (after the decimal) of the binary representation of $r$.

One can think of many extensions of this definition for probabilistic Turing machines. Here is a very permissive one.

  A probabilistic Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, (1) it outputs the first $n$ digits of $r$ with probability $p$; (2) it outputs any other string with probability less than $p$; (3) it never halts with probability less than $p$.

Under this definition, it is not immediately clear whether everything that you can compute is indeed computable (under the sense of the first definition).

However, there are some modifications that do allow us to conclude that the resulting number is computable, for example:

We can insist that the machine always halt.
We can insist that $p > 1/2$.

Other modifications are not necessarily enough. For example, does it help if we assume that the non-halting probability tend to $0$ with $n$?

Summarizing, it might depend on the model.


How do you prove that this TM decides a language that is undecidable?

Hint: The exact definition of $A$ is not important; you just need $A \neq \Sigma^*$. When is $L(R) \neq A$? (look at the third line!)


Primitive Recursion equipped with an evaluator function

A paper of Sylvain Schmitz, Complexity hierarchies beyond elementary, seems to tackle a similar question. While not necessarily defining your exact class (I haven't read the paper), it discusses classes of function between primitive recursive and recursive (as well as between elementary and primitive recursive).


Necessity to define co-NP in the first place?

We don't define problems to be NP-complete. We define classes of problems, define the concept of completeness for those classes, and then prove that problems are complete, because they have the properties that define completeness.

Analogously, we don't define 13 to be prime; rather, we define the property of being prime and then prove that 13 has that property.


Graph searching: Breadth-first vs. depth-first

I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely:

  That heavily depends on the structure of the search tree and the number and location of solutions.
   If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might rootle around forever, but BFS could be faster. If the tree is very wide, a BFS might need too much more memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

  But these are just rules of thumb; you'll probably need to experiment.

Rafał Dowgird also remarks:

  Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.


Characterize an OS as multiprogrammed OS

Sorry That is not a complete answer but i hope it can help you .

"One of the most important aspects of operating systems is the ability
to multiprogram. A single program cannot, in general, keep either the CPU
or the I/O devices busy at all times. Single users frequently have multiple
programs running. Multiprogramming increases CPU utilization by organizing
jobs (code and data) so that the CPU always has one to execute.
The idea is as follows: The operating system keeps several jobs in memory
simultaneously (Figure 1.9). Since, in general, main memory is too small to
accommodate all jobs, the jobs are kept initially on the disk in the job pool.
This pool consists of all processes residing on disk awaiting allocation of main
memory.
The set of jobs in memory can be a subset of the jobs kept in the job
pool. The operating system picks and begins to execute one of the jobs in
memory.Eventually, the job may have to wait for some task, such as an I/O
operation, to complete. In a non-multiprogrammed system, the CPU would sit
idle. In a multiprogrammed system, the operating system simply switches to,
and executes, another job. When that job needs to wait, the CPU switches to
another job, and so on. Eventually, the first job finishes waiting and gets the
CPU back. As long as at least one job needs to execute, the CPU is never idle.
This idea is common in other life situations. A lawyer does not work for
only one client at a time, for example. While one case is waiting to go to trial
or have papers typed, the lawyer can work on another case. If he has enough
clients, the lawyer will never be idle for lack of work. (Idle lawyers tend to
become politicians, so there is a certain social value in keeping lawyers busy.) Multiprogrammed systems provide an environment in which the various
system resources (for example, CPU, memory, and peripheral devices) are
utilized effectively, but they do not provide for user interaction with the
computer system. Time sharing (or multitasking) is a logical extension of
multiprogramming. In time-sharing systems, the CPU executes multiple jobs
by switching among them, but the switches occur so frequently that the users
can interact with each program while it is running."

"Time sharing and multiprogramming require that several jobs be kept
simultaneously in memory. If several jobs are ready to be brought into memory,
and if there is not enough room for all of them, then the system must choose
among them. Making this decision involves job scheduling."

'Having several programs in memory at
the same time requires some form of memory management'

Operating System Concepts Essentials -Abraham Silberschatz -second edition [2013] section [1.4]


Why do we need Gibbs sampling (and MCMC)?

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time.

Further, sampling from a Markov chain allows you to sample without having to construct the probability distribution explicitly or even the state space, explicitly. For example, how do you propose to randomly sample matchings in a graph by your method, even uniformly? You'd need to first construct the set of all matchings (of which there can be exponentially many), then select one. And note that constructing the set of matchings implies being able to count them, which is #P-hard, so very unlikely to be doable efficiently. With a Gibbs sampler, you just run a Markov chain for polynomially many steps and you have yourself a matching chosen uniformly at random.


Can the unbounded knapsack problem be described as a matrix exponentiation?

For the Fibonacci sequence, the recurrence relation is linear.  That's why it can be represented as a matrix representation, i.e., using linear algebra.  If the recurrence relation isn't linear, you can't do something like that.

So, no, you can't always do that.


Recursively edit 2-D array using backtracking

The following algorithm would be my first attempt.

Initialize a 2D array $A$ with given characters, 'C', 'W' or 'R'.
Loop $m+n-2$ times.

In each loop, iterate over all cells of $A$. For each cell, check whether it is 'C'. If yes, change all of it neighbors that are 'W' to 'C'. Otherwise, do nothing.

Here is an illustration of the step 2 on the example given in the question, where after 3 loops the situation will not change any more although we have specified 5+5-2=8 loops. Looping $m+n-2$ times guarantees that all contaminated elements will be found although the situation should become stable earlier in general. (In fact, the number of times needed is the longest Manhattan distance from a water cell that will be contaminated to the nearest cell that is contaminated initially.) $m+n-2$ is chosen here just for its simplicity.

WWWRW     CWWRW     CCWRW     CCCRW              CCCRW
CRRRR     CRRRR     CRRRR     CRRRR              CRRRR
RWWRW ->  RWWRW  -> RWWRW  -> RWWRW  -> (stable) RWWRW
WWWRR     WWWRR     WWWRR     WWWRR              WWWRR
WRRWC     WRRCC     WRRCC     WRRCC              WRRCC

Once the above simple and sound algorithm has been working well, we can consider a couple of improvements.

Once we have checked a cell with value 'C', we will mark it as 'V' after we have changed its neighbors. In each loop, we will ignore cells with value 'V'.
We can use a queue to list the cells to be checked. Cells that are changed to 'C' will be appended to the queue. Once the queue is empty, the algorithm stops.

  I know I have to solve this using via backtracking and recursion.

Not necessarily.

The technique used in the above algorithm is looping simply. Or nested loops to advance the frontier of contaminants. You can imagine the contaminants are spreading to their immediate neighbors uniformly by one tick of time. Ticks of time correspond to the outer loop while all contaminant correspond to the inner loop.


How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$?

Let's consider an $\mathsf{NP}$-complete like $SAT$: given a formula $\varphi$, is there a turht assignment $\tau$ such that $\tau \vDash \varphi$?
By assumption $\mathsf{NP} \subseteq \mathsf{P/\log}$ we know that $SAT \in \mathsf{P/\log}$. We will show that $SAT \in  \mathsf{P}$ which will imply $\mathsf{NP} \subseteq \mathsf{P}$.

Notations
Let us denote a partial truth assignment as a function from the set of variables to $\mathbb{B}_\bot = \{1,0,\bot\}$ where $\bot$ means the corresponding variable is not determined. We will denote the empty assignment where all variables are left undetermined as $[]$ and the assignment that sets only the value of the variable $x$ to $b$ as $[x\mapsto b]$.
Let $FV(\varphi)$ denote the set of free variables in $\varphi$.
Let us also denote the formula resulting from pluging in the values from a partial truth assignment $\sigma$ into a formula $\varphi$ as $\varphi\sigma$.

Witness Search Problem: $SATSearch$
Consider the witness search problem $SATSearch$: given a formula $\varphi$, find a truth assignment $\tau$ s.t. $\tau \vDash \varphi$ if there is one, otherwise return $None$.
It is easy to see that if the witness search problem can be solved in deterministic polynomial-time then $SAT$ is in $\mathsf{P}$: we just run $SATSearch$ on $\varphi$ and $\sigma = \emptyset$ and we accept iff the answer is not $None$.
Also note that if $SAT \in \mathsf{P/\log}$, then so is $SATSearch$: consider the following polynomial time algorithm for $SATSearch$ that uses $SAT$ as a black box:
$\tau = []$
if not $SAT(\varphi\tau)$ return $None$
for $x \in FV(\varphi)$

if $SAT(\varphi(\tau \cup [x \mapsto 0]))$ then $\tau = \tau \cup [x \mapsto 0]$
else $\tau = \tau \cup [x \mapsto 1]$

return $\tau$
More generally the claim holds for any class which is closed under Cook reductions.

By our assumption $SATSearch\in \mathsf{P/\log}$. Let $M$ be an TM with polynomial running time and advice of length $l(n)=O(\log n)$ where $n$ is the size of the input formula $\varphi$. We show that $SATSearch$ can be solved in deterministic polynomial time.
for all c of length $l(|\varphi|)$

$\tau = M(\varphi,c)$
if $\tau \vDash \varphi$ then return $\tau$

return $None$
If $\varphi$ is satisfiable, then at least for the right advice $M$ will return a witness and we can verify it. If the formula is not satisfiable, no $\tau$ can satisfy $\varphi$ so we will return $None$.
The running-time of the algorithm is polynomial and it uses no advice. So $SATSearch$ can be solved in deterministic polynomial time with no advice.
Therefore we can conclude that $\mathsf{NP}=\mathsf{P}$ if $\mathsf{NP}\subseteq \mathsf{P/\log}$.


To elaborate on gallais' clarifications, a type theory with impredicative Prop, and dependent types, can be seen as some subsystem of the calculus of constructions, typically close to Church's type theory. The relationship between Church's type theory and the CoC is not that simple, but has been explored, notably by Geuvers excellent article.

For most purposes, though, the systems can be seen as equivalent. Then indeed, you can get by with very little, in particular if you're not interested in classical logic, then the only thing you really need is an axiom of infinity: it's not provable in CoC that any types have more than 1 element! But with just an axiom expressing that some type is infinite, say a natural numbers type with the induction principle and the axiom $0\neq 1$, you can get pretty far: most of undergraduate mathematics can be formalized in this system (sort of, it's tough to do some things without the excluded middle).

Without impredicative Prop, you need a bit more work. As noted in the comments, an extensional system (a system with functional extensionality in the equality relation) can get by with just $\Sigma$ and $\Pi$-types, $\mathrm{Bool}$, the empty and unit types $\bot$ and $\top$, and W-types. In the intensional setting that's not possible: you need many more inductives. Note that to build useful W-types, you need to be able to build types by elimination over $\mathrm{Bool}$ like so:

$$ \mathrm{if}\ b\ \mathrm{then}\ \top\ \mathrm{else}\ \bot  $$

To do meta-mathematics you'll probably need at least one universe (say, to build a model of Heyting Arithmetic).

All this seems like a lot, and it's tempting to look for a simpler system which doesn't have the crazy impredicativity of CoC, but is still relatively easy to write down in a few rules. One recent attempt to do so is the $\Pi\Sigma$ system described by Altenkirch et al. It's not entirely satisfying, since the positivity checking required for consistency isn't a part of the system "as is". The meta-theory still needs to be fleshed out as well.

A useful overview is the article Is ZF a hack? by Freek Wiedijk, which actually compares the hard numbers on all these systems (number of rules and axioms).


Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm

The running time of adding a vertex to the independent set $S$ is $O(1)$ if you use an appropriate set data structure, such as a linked list, an array, or a dictionary. Also, deleting a vertex $v$ from $G$ (once you have identified the vertex) takes time proportional to the number of neighbours, which, in this case, is bounded above by a constant ($4$), so it also takes $O(1)$ time.

The running time of your greedy algorithm will, therefore, be dominated by the costs of the maximum-weight vertex computations. I can think of three ways to implement this operation:

Naive approach - $O(|V|)$: identifying the maximum-weight vertex of a graph takes linear time in the number of vertices if you explore all of them.
Priority queue - $O(log \: |V|)$ : since you are doing repeated maximum computations, it makes sense to use a priority queue, which allows you to extract the maximum element in logarithmic time.
Sorted array - $O(1)$ : the maximum-weight vertex of a graph can be identified in constant time if you sort the vertices by weight beforehand.

The number of times that the algorithm computes the maximum-weight vertex is equal to the number of iterations, which is $O(|V|)$. Therefore, the naive approach takes $O(|V|^2)$ time and the priority queue based solution takes $O(|V| \: log \: |V|)$ time. In the sorting-based solution, each iteration takes $O(1)$ time; however, the overall running time is not $O(|V|)$, but, rather, $O(|V| \: log \: |V|)$ because the running time is dominated by the sorting operation.


Quicksort Algorithm with Pivot element as Median

It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.


Prove that for a general data structure - operations Extract_min() and Insert(x) cost $\Omega(\log n)$?

I don't think your proof is valid, because it only considers trees, and a certain type of trees at that. If there were an algorithm with a smaller lower bound for what you describe, we'd have a sorting algorithm faster than $\Omega(n \log n)$ no matter which of the two operations is $\log n$. So the problem reduces to proving that sorting cannot be faster than $\Omega(n \log n)$, which is a classical proof that you can find online.


Determining whether the output of an algorithm is constant

It's not decidable. Given any program $P$, you can write a program $Q$ running in time (say) $O(n^2)$, which on input $n$ simulates $n$ steps of $P$, and returns 1 if $P$ halted. Then $P$ doesn't halt if and only if $Q$ always outputs 0.

This shows that your problem is $\Pi_1$-hard (since the halting problem is $\Sigma_1$-hard). It is also clearly in $\Pi_1$, and so it is $\Pi_1$-complete. (For the definition of $\Pi_1$, check out the arithmetical hierarchy on Wikipedia.)


Finding minimum spanning tree of a special form graph

That recursive algorithm is wrong, although it was an interesting attempt to improve established algorithms on specialized graphs.

Here is a counterexample with $n=3$.

The graph above was drawn at https://graphonline.ru/en

All edges weigh 2 except that the rightmost two edges, $(v0,v3)$ and $(v2,v3)$ weigh 1. The recursive algorithm will pick only one edge from the rightmost two edges while an MST must include both of them.

By the way, I cannot understand clearly the description of the algorithm in the case of $n=1$ and in the case of $n=2$. Fortunately (or unfortunately), that does not affect this answer since the counterexample depends only on the "else" branch of the algorithm, which is described clearly.


Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

There's a solution in pseudo-polynimial $O(nk)$. First, you can safely delete every node of the graph with weight bigger than $k$.  For each node $v$ keep an array $A[v]$ of size $k$, where $A[v][i]$ says how many children $u$ of $v$ have paths that start in $u$ (a node $u$ is the start of a path $u_1, \ldots, u_m$ if $u = u_1$ and $u_{i+1}$ is a child of $u_i$ for all $i$) and whose weight is exactly $i$.  Also, let $w$ be the function that maps nodes to their weights.

Your graph is a bunch of trees, and you can process each of them individually. For a given tree, choose an arbitrary node as the root, and do dynamic programming in the following way to fill up $A$. For any node $v$ we have that

$$
A[v][i] = \sum_{u \text { is a child of } v} \big[ A[u][i - w(u)]  \geq 0\big]
$$

If for some $v$ it holds that $A[v][k-w(v)] \geq 1$ we are done. This corresponds to the case where there is a path that starts in $v$ and has weight $k$. It could be however, that the path of weight $k$ we are looking for does not start in $v$, but it rather has $v$ as its closest node to the root. In order to detect this, we can process the tree from bottom to top. We denote the parent of a node $u$ as $p(u)$. For each node $u$, if there is some $j$ such that $1 \leq j \leq w(u)$ and $A[u][j-w(u)]$, then we know there is a path of weight $j$ that starts in $u$. We call this path $\pi_1$. So we only need to check whether there is a path $\pi_2 \neq \pi_1$ of weight $k-j-w(p(u))$ that starts from a child of $p(u)$. This corresponds to check the value of $A[p(u)][k-j-w(p(u))]$. Note that it could happen that $w(\pi_1) = w(\pi_2)$, in which case we would need to check whether $A[p(u)][k-j-w(p(u))] \geq 2$.

Thanks to @j_random_hacker for the suggestions on how to improve the algorithm.


Number of vertices and edges lies on the boundary of bounded cells in line arrangement

Consider 3 additional lines such that their arrangement consists of a single bounded (triangular) cell $C$ and $F \subset C$. Then every edge of $F$ belongs to a zone (using a terminology from your textbook) of at least one of the 3 added lines. And all 3 zones of 3 added lines contain at most $30n$ edges according to Zone Theorem. So $F$ has no more than $30n$ edges which is $O(n)$.


What is the common terminology to refer to the nth ancestor of a tree root?

Commonly used phrases include,

"vertex at height $h$",
"vertex at depth $d$",
"vertex at distance $d$ from the root".

"Subtree $n$" doesn't make any sense, except as the $n$th element in some enumeration of subtrees.

By the way, I'd avoid using $n$ for anything other than the number of vertices in the graph.  That bit of notation is so standard in graph theory that it's confusing for the reader to have $n$ mean anything else.


Number of computations for multiplication

It should be "10 superscript{n/2}" meaning $10^{n/2}$. For example, if $n=4$, then "6#2" would represent $6\cdot10^2=600$. All he's doing is shifting a decimal number to the left.


If executing each instruction took a single clock-cycle, then your confusion would have been understandable, as a higher clock frequency would imply shorter cycle time, hence, more instructions per unit time.
However, the reality is quite different. Modern CPUs are usually pipelined, meaning that a single instruction takes multiple number or core-clocks, and that multiple instructions are executed simultaneously at the same time (each occupies different parts of the CPU pipeline). Complex instructions, such as calling a function or "jumping" to a different part of the code interfere with this pipeline and cause the CPU to temporarily halt its execution until the offensive instruction completes (known as a pipeline stall).
The picture is even more complex. Recent processors have multiple pipelines running on the same "core" (say, one clock advances pipeline 1 while the next clock advances pipeline 2). Of course, sometimes the program running on one pipeline affects (stalls) the progress of the other pipeline. This is "multithreading". Other approaches to make the CPU perform better are superscalar processing and other paralleling approaches.
As you can figure out, the number of instruction a CPU performs at any time unit is very complex to compute or even estimate, and is affected by the clock frequency, but also by the architecture of the CPU as well as by the program itself (e.g., how many "jumps" instructions it contains, or how well it parallelizes). All of these together determine the "speed" of the CPU, which is measured in the (average) number of instructions it can perform in a second, known as IPS. As said, the clock frequency is only one factor to the IPS, but in modern CPUs the specific architecture (rather than small differences in their clock frequency) dominates the IPS.


How to solve this recurrence involving binomial coefficients?

Let us guess that $A(n,k) = \alpha \binom{n}{k} + \beta$. The recurrence reads
$$
\alpha \binom{n}{k} + \beta = \alpha \binom{n-1}{k} + \beta + \alpha \binom{n-1}{k-1} + \beta + c,
$$
from which we deduce $\beta = -c$. The base cases are
$$
\alpha \binom{n}{n} - c = \alpha \binom{n}{0} - c = 1,
$$
From which we deduce $\alpha = c+1$. All in all, the solution is
$$
A(n,k) = (c+1) \binom{n}{k} - c.
$$


Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines

I figured it out. Turns out the solution is deceptively simple, but in the details it is somewhat different than proofs I have seen for other greedy algorithms. We basically show that any output besides the one the greedy algorithm returns can be improved further.

To do this, consider two jobs with sizes $s_j$ and $s_i$ such that $s_j > s_i$. Furthermore, consider two machines with constants $p_l, p_k$ such that $p_l > p_k$. We show that the best way of assigning $s_j, s_i$ to $p_l, p_k$ is to assign $s_j$ (the larger job) to $p_k$ (the faster machine) and $s_i$ (the smaller job) to $p_l$ (the slower machine). Since there are only two possible assignments, in other words we want to show $$s_j \cdot p_k + s_i \cdot p_l \le s_j \cdot p_l + s_i \cdot p_k$$

To do so we set $s_i = x, s_j = x+a, p_k = y, p_l = y + b$ for some $x,y,a,b \ge 0$. So equivalently we want to show $$(x+a)\cdot y + x \cdot (y + b) \le (x + a)(y + b) + xy$$

This can be seen simply by simplifying. Thus we have shown that for two jobs and two machines, cost is minimized by assigning the larger job to the faster machine and the smaller job to the slower machine.

It quickly follows that the greedy algorithm is optimal because for any other output, there will be a pair of assignments that don't satisfy the "larger job to faster machine, smaller job to slower machine" rule. And thus by switching the assignments of this pair, we lower the total cost.


How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

Let $\mathcal{C}(n,m)$ denote the set of sequences you are interested in, namely non-decreasing sequences of length $n$ consisting of integers from $\{0,\ldots,m\}$, and let $C(n,m) = |\mathcal C(n,m)|$ be the number of such sequences. It is not hard to verify the following recursion:
$$
\begin{align*}
&C(0,m) = 1, \\
&C(n,m) = \sum_{k=0}^m C(n-1,k) \text{ for } n > 0.
\end{align*}
$$
In fact, it is not hard to check that
$$ C(n,m) = \binom{n+m}{m}. $$
But the recursion allows us to rank and unrank sequences. More explicitly, we will now describe a bijection $r_{n,m}$ from $\mathcal C(n,m)$ to $[0,C(n,m))$ (i.e., $\{0,\ldots,C(n,m)-1\}$). The bijection is defined recursively as follows (below, $\lambda$ is the empty sequence):
$$
\begin{align*}
&r_{0,m}(\lambda) = 0, \\
&r_{n,m}(\sigma_1,\ldots,\sigma_n) = \sum_{k < \sigma_n} C(n-1,k) + r_{n-1,\sigma_n}(\sigma_1,\ldots,\sigma_{n-1}).
\end{align*}
$$
This doesn't order the sequences in the order you listed, though one can easily adapt it to your order (by considering the first rather than last element). We can also describe the inverse bijection explicitly:
$$
\begin{align*}
&r^{-1}_{0,m}(0) = \lambda, \\
&r^{-1}_{n,m}(r) = r^{-1}_{n-1,k}\left(r - \sum_{\ell<k} C(n-1,\ell)\right),k, \\ &\qquad \text{ where $k$ is defined by } \sum_{\ell < k} C(n-1,\ell) \leq r < \sum_{\ell \leq k} C(n-1,\ell).
\end{align*}
$$

Finally, if all you want is to list the sequences in order, say the order in your post, then you can use the following simple "counter" algorithm. Start with the all-zero sequence $\sigma_1 = \cdots = \sigma_n = 0$. At each step, find the maximal $i$ such that $\sigma_i < m$ (if $\sigma_1 = \cdots = \sigma_n = m$, we are done). Increase $\sigma_i$, and set all numbers following it to its new value. This will enumerate all sequences in lexicographic order, in amortized time $O(1)$ per sequence.


number of subsegments that contain A[i] as the minimum

You haven't stated what a subsegment is, but I assume that you mean a "contiguous subsequence", that is, $A[s],A[s+1],\ldots,A[t]$. Also, I'm assuming that $A[i]$ is still a minimum if there are other equal values (you can easily adapt the algorithm for the other option).

Let $\ell \leq i$ be the smallest index such that $A[s] \leq A[i]$ for all $\ell \leq s \leq i$, and let $r \geq i$ be the largest index such that $A[r] \leq A[i]$ for all $i \leq s \leq r$. Then $A[i]$ is a minimum of $A[s],\ldots,A[t]$ iff $\ell \leq s$ and $t \leq r$. Thus there are $i-\ell+1$ options for $s$, namely $\ell,\ell+1,\ldots,i$, and similarly $r-i+1$ options for $t$, for a total of $(i-\ell+1)(r-i+1)$.

You can easily find $\ell,r$ in linear time by scanning left of and right of $i$ (respectively), so this algorithm runs in linear time.


Yes, you can define $T'(n) = 2 T'(\frac{n}{2}) + \Theta(n \log n)$, notice that $T(n) \le T'(n)$, and use the master theorem on $T'$ to obtain an upper bound of $O(n \log^2 n)$ to $T$.

Since for $n \ge 2$, $\frac{2+\log n}{1+\log n} \le \frac{3}{2}$ you can get a better upper bound by comparing $T$ to
$$T'' = \begin{cases}\frac{3}{2}T''(\frac{n}{2}) + \Theta(n \log n) & \text{if $n\ge2$} \\ \Theta(1) & \text{otherwise}\end{cases}.$$ Applying the master theorem on $T''$ yields and upper bound of $O(n \log n)$ for $T$.


Thomas write rula andview serializability

Timestamp ordering ensures conflict serializability

proof :

Assume that in precedence graph of schedule, we have edge $T_i \rightarrow T_j$.

Now, When $T_j$ puts it's request for this conflicting operation it will be continue only if $\text{timestamp}(T_i) < \text{timestamp}(T_j)$.

Now, for schedule to be non conflict serializable there must exist a cycle in precedence graph of that schedule and let say that cycle is $T_i, T_{i+1}, ...., T_i$.

Now, note that that cycle can't exist because existence of cycle implies $\text{timestamp}(T_i) < \text{timestamp}(T_i)$. (As timestamp are unique.)

So, we conclude that there can't be any such cycle which in turn implies that timestamp ordering protocol allows only conflict serializable schedules.


Abstract machine that can recognize repetition

There is a generalization of NFAs in which the transitions are labeled with regular expressions. (They are equivalent to NFAs and DFAs.) You can represent "twice the same letter" by $\sum_{\sigma \in \Sigma} \sigma^2$. Of course, such expressions are not standard, but if you want a succinct representation, this is one.


Relationshop between Theta and little-o (Big-O notation)

To expand slightly on Karolis's comment, you can get a counterexample by taking for any strictly positive function $f$ and, for any constant $\delta>0$, the function $(1+\delta)f(x)$.  $(1+\delta)f(x)\in \Theta(f(x))$ but $(1+\delta)f(x)\notin (1+o(1))f(x)$ since, for $\epsilon<\delta$, it is not true that $(1+\delta)f(x)\leq (1+\epsilon)f(x)$.


How can I reduce the time of this program

A very nice question.

Here is the brief idea of a more efficient algorithm. The central idea is how to fill one package and close it with minimal unfilled capacity left. That is a standard knapsack problem that can done efficiently with dynamic programming.

However, now we have two packages available, each might have different initial capacities available, as you have pointed out.

What to do? Then do two knapsack problems at the same time!

Right after you have closed one package, you have two packages, one with $a_1$ available capacity and the other with $a_2$ available capacity. We have two knapsack problems here: how to fill the one with $a_1$ capacity as much as possible without bursting the other one and how to fill the one with $a_2$ capacity as much as possible without bursting the other one. Solve them separately. Compare the result to find which one get less free capacity left. Choose that package and its maximal filling found just now and close it. Fill the other one with the items that should have been used before closing the previous one. Repeat the process.

(Further update might come to clarify the above explanation. But this should get you going.)


Let us consider a generic optimization problem:

Maximize $f(x)$ subject to the constraint $x \in \mathcal{D}$.

The corresponding decision version is

Given $\mathcal{D}$ and $T$, is there $x \in \mathcal{D}$ such that $f(x) \geq T$?

In most cases, the range of $f(x)$ is at most exponential in the description length of $\mathcal{D}$, and so the optimization problem reduces to the decision version via binary search. For example, if $0 \leq f(x) \leq n$, then we first ask whether there is a solution with $f(x) \geq n/2$; depending on the answer, we ask whether there is a solution with $f(x) \geq n/4$ (if the answer was negative) or with $f(x) \geq 3n/4$ (if the answer was positive); and so on.
Conversely, if we can solve the optimization problem then we can easily answer the decision problem, and so the two are essentially equivalent.


How are threads implemented in different OSs?

Threads and processes are execution contexts.  They mostly differ only by the amount of shared state (memory, signal handlers, file descriptors,...) with the other execution contexts (processes share little with other processes; threads share a lot with the other threads in the same process).

Most OS keep the two things separated, and thus know about several kinds of execution context.

Linux kernel on the other hand has just one kind of execution context, which is able to share or not things with other. If you want a process, set it up so that it share little, it you want threads, set them up so that they share what they need. You can set things up so that they behave in a way unsuitable for the process/thread terminology.

The POSIX API commonly used when programming for Linux knows only about processes and threads and thus most programs don't really care about what is an implementation detail for them in the way responsibilities are divided between kernel and user space. Older implementations of threads leaked some the implementation details (ps showing threads, thread id and process id mixing up, ...) and didn't provide exact POSIX semantic in some cases (signal delivery was problematic IIRC).


Why every rational langage is the image of a local automaton

(1) Indeed. Every regular [=rational] language is the morphic image of a local [=2-testable] language.

This is seen as follows. A finite state automaton can be "encoded" by a 2-testable language by using the transitions as letters. So we consider symbols $(p,a,q)$. The corresponding language is 2-testable: basically test whether the transitions are consecutive which is clear from letter pairs: $(p,a,\underline q)(\underline q,b,r)$. We find the original language by applying a coding: $(p,a,q)$ maps to $a$.

(2) No. Local languages are not closed under codings. $(ab)^*$ is a local language. Initial letter $a$, final letter $b$, two letter substrings $ab, ba$. The image $(aa)^*$ is not local. There is no way to distinguish odd length strings from even length strings by just looking at substrings.


What is the fastest way to input all of 30 million human "go" move into the computer that haven't digitized?

Your bottleneck when doing this will be to gather up all the not yet digitized moves, validate them somehow, and digitize them. Once that is done, reading in the data will be a snap.


I believe the question is asking you to implement the queue so that every time you perform a queue operation (enqueue or dequeue) your implementation does O(1) total operations on the stacks used to implement this. For example, an implementation that performed at most 137 total pushes and pops per time that the client calls enqueue or dequeue would satisfy this requirement, but an implementation that requires, say, $n$ stack operations per enqueue would not meet this requirement.


These combinations of items are sometimes called itemsets.  There are algorithms for finding itemsets that are especially common in a database; see association rule learning.

In general there is no efficient algorithm for producing such a table, as the size of the table can be exponentially large in the size of the input.  Consequently any algorithm will take exponential time on at least some inputs (i.e., will be extremely slow on at least some inputs).  You might want to consider what you plan to do with the table and whether there's a way to achieve your ultimate goal, without building the table explicitly; that might turn out to be a better approach.


Is there an Algorithm that can code itself?

While there are no program synthesizers that can synthesize themselves in their entirety, plenty of synthesizers can synthesize pieces of themselves. Rohit Singh, for instance, has a project using the Sketch synthesizer to optimize many logical solvers, including that of Sketch itself.


How many segmentations are possible for a string length N?

There are n-1 points where you can break the string. Each is independent of the others. Therefore there are $2^{n-1}$ possibilities to break the string.


Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer?

Let $T$ be a tree, and let $T'$ be the tree formed from $T$ by removing all leaves (vertices of degree 1). Assume that $T$ contains at least three vertices, so that $T'$ is not empty. This implies that every leaf $f \in T$ has a (unique) neighbor $p(f) \in T$ which is not a leaf.

For $v \in T$, denote by $h_v(T)$ the height of $T$ when rooted at $v$.
I claim that the following hold:

  For every vertex $v \in T'$, $$ h_v(T) = h_v(T') + 1. $$
  For every leaf $f \in T \setminus T'$, $$ h_f(T) = h_{p(f)}(T) + 1. $$

For the first claim, consider $T$ rooted at a non-leaf $v$. The height of $T$ is the length of the maximal root-to-leaf path. Every such path gets shortened by one in $T'$, implying that $h_v(T) = h_v(T') + 1$.

For the second claim, let $x$ be a leaf farthest away from $p(f)$. We can assuming that $x \neq f$ since $p(f)$ has at least two neighbors, and $f$ is at minimal distance from $p(f)$. Clearly $d(f,x) = d(p(f),x) + 1$, and so $h_f(T) \geq h_{p(f)}(T) + 1$. The other direction follows from the triangle inequality, which implies that $d(f,y) \leq d(p(f),y) + 1$ for all nodes $y$.

The algorithm. If $T$ contains one or two vertices, then clearly all vertices are centers (roots of minimum height trees). Otherwise, by the second claim, no leaf can be a center, and so by the first claim, the centers of $T$ are the same as the centers of $T'$. This suggests the following algorithm for computing the centers of $T$:

  While $T$ contains at least three vertices, remove all leaves of $T$.
  Once $T$ contains one or two vertices, return all vertices of $T$.

The correctness of the algorithm follows the reasoning stated above.


Why is O(n log n) the best runtime there is?

Your confusion seems to stem from several misconceptions. I'll try to address some.

There are several ways an algorithm can be "best". Which is applicable depends on the context and on what you want to say.

An algorithm is provably the best one, period. (Hint: impossible)
An algorithm is the best we know. (Best in what metric?)
An algorithm is provably optimal. (W.r.t. what metric? What about others? Proven under which assumptions?)
An algorithm is probably asymptotically optimal. (W.r.t. what metric? What about others? Proven under which assumptions? What about the constant factor? What about small inputs?)

And probably more. Note that all these need an addition: "for problem P". Every algorithm solves some specific problem, and it does usually not make sense to compare algorithms for different problems.

Now, in the case of Mergesort, here are two facts.

Mergesort takes $O(n \log n)$ operations to sort $n$ elements in the worst case.
Sorting $n$ pairwise distinct elements (from an unknown range) by comparing
element in a pairwise fashion requires $\Omega(n \log n)$ comparisons.

Hence, Mergesort is an asymptotically worst-case-optimal algorithm for sorting pairwise distinct numbers whose range is unknown (or huge), among all comparison-based sorting algorithms.

However:

On average (again, model assumptions apply), Quicksort is faster Mergesort.
For some input classes, there are linear-time sorting algorithms.
On small inputs, even Insertion Sort is faster.

As you see, Mergesort is "best" in a certain sense, but not universally.

Regarding your specific question in the end, proving an $\Omega(n)$ lower bound for general sorting is easy.
Try to imagine an algorithm that does not even look at every input element.
Can it sort the input?


Sort array of 5 integers with a max of 7 compares

There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between.

The first comparison is easy: you have to compare two keys, and since you don't know anything about them, all choices are equally good. So let's say you compare $a$ and $b$, and find that $a \leq b$. You now have $2^6 = 64$ possible answers left, and $60$ possible permutations remaining (since we have eliminated half of them).

Next, we can either compare $c$ and $d$, or we can compare $c$ to one of the keys we used in the first comparison. If we compare $c$ and $d$, and learn that $c \leq d$, then we have $32$ remaining answers and $30$ possible permutations. On the other hand, if we compare $c$ with $a$, and we discover that $a \leq c$, we have $40$ possible permutations remaining, because we have eliminated $1/3$ of the possible permutations (those with $c \leq a \leq b$). We only have $32$ possible remaining answers, so we're out of luck.

So now we know that we have to compare the first and second keys, and the third and fourth keys. We can assume that we have $a\leq b$ and $c \leq d$. If we compare $e$ to any of these four keys, by the same argument we used in the previous step, we might only eliminate $1/3$ of the permutations remaining, and we're out of luck. So we have to compare two of the keys $a,b,c,d$. Taking into account symmetry, we have two choices, compare $a$ and $c$ or compare $a$ and $d$. A similar counting argument shows we must compare $a$ and $c$. We can assume without loss of generality that $a \leq c$, and now we have $a \leq b$ and $a \leq c \leq d$.

Since you asked for a hint, I won't go through the rest of the argument. You have four comparisons left. Use them wisely.


How do I compute the huge numbers which occur in el gamal decryption?

Two techniques will be of use here and in many similar problems. To find $(1/a)^b\pmod n$,

First, compute $1/a = a^{-1}\pmod n$. In your example, compute $62^{-1}\pmod{71}$, namely, the modular inverse of $62\pmod{71}$. That happens to be $63$.
Then use repeated squaring to find $(1/62)^{62}\equiv63^{62}\pmod{71}$, which will be 8. This relies on the fact that $a^{62} = a^{32+16+8+4+2}=(a^{32})(a^{16})(a^{8})(a^{4})(a^{2})$ where, reading from the right, each value is the square of the preceding one, meaning that you can find $a^{62}$ using 9 modular multiplications, rather than 61.


Confusion related to this algorithm about finding the orientation given 3 points

The orientation of three points in the plane is classically done with a determinant. In the linked article the approach is done on a polygon thus they use a 3x3 determinant. For only three points, i.e., a triangle, a 2x2 determinat is sufficient.

Let $p_1=(x_1,y_1), p_2=(x_2,y_2)$, and $p_3=(x_3,y_3)$ be three points in the plane. Then we compute the orientation vectors at $p_1$, that is $p_{1,2}=p_2-p_1$ and $p_{1,3}=p_3-p_1$. Now we use the determinant to find the orientation: $$\mathrm{det}\begin{bmatrix}x_2-x_1&y_2-y_1\\x_3-x_1&y_3-y_1\end{bmatrix}=(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1).$$

If the result is smaller than zero then $(p_1,p_2,p_3)$ are in counter-clockwise order, if larger than zero in clockwise order, and if zero then they are collinear.


How to detect Farkas or MPEG4 FDP points on image with a face?

In the simplified special case where each image $x$ has a single correct labelling $k=\kappa(x)$, this becomes just a regression problem: you want to find a function $q$ that minimizes the risk

$$\mathbb{E}[||q(X)-\kappa(X)||^2],$$

where $X$ is a random variable distributed according to some distribution on faces.  One way to solve this is to build up a training set of pairs $(x_i,k_i)$ where $x_i$ is a face and $k_i$ is its label, and then minimize the empirical risk

$$\sum_i ||q(x_i)-k_i||^2.$$

This then becomes an optimization problem: find parameters for $q$ that minimize the empirical risk.  You could use any of a number of different methods for regression, based on what structure you think $q$ might have.  For instance, you could use a convolutional neural network.

Your problem is a more general version of this, where we want to minimize the risk

$$\mathbb{E}[\ell(X,q(X))],$$

where

$$\ell(x,y) = \int p(k|x) ||y-k||^2 dk.$$

I will assume you have an efficient way to compute $\ell(x,y)$ for any particular $x,y$ (whether by integrating analytically using some expression for $p(k|x)$, or by sampling many $k$ from the distribution $p(k|x)$ and taking the average value of $||y-k||^2$).  If this is the case, one approach is again to build a training set of faces $x_i$, each with a known distribution $p(k|x_i)$, and then minimize the empirical risk

$$\sum_i \ell(x_i,q(x_i)).$$

This is just an optimization problem, where you try to find parameters for $q$ that minimize the empirical risk.  Assuming you have an efficient way to compute $\ell(\cdot,\cdot)$, you can proceed as before and use any standard method for regression (e.g., a convolutional neural network).


Longest-path in a graph, where the path should be 'straight'

Idea 1: Short paths are straight paths

In Euclidean space, a straight path is usually a short path.

So I would compute shortest paths between every pair of points in the graph.  This can be done in $O(|V|^3)$ time with the Floyd-Warshall algorithm, which is suitable for dense graphs, or $O((|E|+|V|)|V|\log|V|)$ time by running Dijkstra's algorithm starting from each vertex in turn, which is faster for sparse graphs.

You can then evaluate each vertex pair according to whatever "straightness" criteria you like -- e.g. average/maximum angle formed or maximum perpendicular distance, balancing these against the length of the path somehow -- and choose the overall maximum.

For a quick heuristic, you could randomly subsample the points and solve the smaller subproblem.  Repeat this several times to build a list of candidate (source, sink) pairs, then run Dijkstra on each candidate in the full graph to pick the overall winner.

Idea 2: Partition edges by angle

The above should work well if it's OK for the line to be quite jagged at a small scale.  But if smoothness at a small scale is important, another approach comes to mind: Partition the edges into angle buckets (e.g. all edges making an angle of 0-5 degrees with the horizontal, all edges making an angle of 6-10 degrees, etc., for 360/5 = 72 buckets overall).  For each bucket, solve a separate subproblem that contains all vertices, but only the edges in that particular bucket.  Every path in such a graph necessarily contains only edges that have very similar directions.  (If you choose sufficiently fine buckets, you might find that the graph fragments into many small, line-like components, which will speed things up greatly as they can be solved independently.)

In fact it's not necessary to partition the edges; it's probably desirable to have some bucket overlap, so that an edge typically appears in more than one subproblem.


NP-complete proof from Dasgupta problem on Kite

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way: for each node $v_i$ add a tail of $k$ new nodes.

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Added nodes cannot introduce new cliques on G′, so $G$ contains exactly the same cliques of $G'$.


Find all polygons from a set that overlap a given polygon (convex case)

Suppose all the polygons $S_1,\dots,S_n,P_1,\dots,P_n$ are given in advance.  Then I can propose an algorithm that might often be efficient in practice (though it can degenerate to quadratic-time behavior if you get a sufficiently nasty configuration of polygons).

In particular, the polygon $P_i$ overlaps with some $S_j$ if and only if:

(1) some line segment of the perimeter of $P_i$ crosses some line segment of the perimeter of $S_j$; or,

(2) some vertex of $P_i$ is inside $S_j$, or some vertex of $S_j$ is inside $P_i$.

So, it suffices to check both conditions separately.

Crossings between perimeters

You can check find all crossings between the perimeters of the polygons as follows.  Decompose the perimeter of each polygon $P_i$ into a collection of line segments.  Do the same for each $S_j$.  Then, use the Bentley-Ottmann algorithm (or some other similar algorithm) to find all crossings between these line segments.  This will tell you, for each $P_i$, whether its perimeter crosses any of the $S_j$ perimeters.  If it does, then you know that $P_i$ has an overlap with some $S_j$.

The running time will be $O((n+k) \log n)$, where $k$ is the number of crossing between these line segments.  In practice, you can hope that $k$ won't be too large (it probably often will be fairly small, unless you get really unlucky with how the polygons are arranged).

Vertex inside a polygon

So we have a bunch of polygons, and a bunch of points.  I suggest using the Bentley-Ottman sweepline algorithm on the line segments corresponding to the perimeters of the polygons.  In addition to an "event" happening at each two intersection between two line segments and at each endpoint of each line segment, create another event at the location of each point.  In addition to a binary search tree storing the locations of the line segments that intersect the sweepline, also use an interval tree to store an interval for each polygon that intersects the sweepline (namely, the range of $y$-coordinate values where the sweepline intersects that polygon).  Now, when you hit an event corresponding to a point, you can check which intervals in the segment tree contain that point, i.e., which polygons contain that point, using a stabbing query.

By using self-balancing trees, you can arrange that each step of this algorithm can be done in $O(\log n)$ time.  Thus, the total running time will again be $O((n+k)\log n)$.

Online queries?

The above describes how to solve your problem in "batch mode", where all polygons are given in advance.  What if only $S_1,\dots,S_n$ are given in advance and the $P_i$'s are provided one at a time, and we have to check for overlap in an online fashion?  I don't know how to handle that.

I might be able to get you started on an idea for half of it, but I don't see how to flesh it out into a full algorithm.  For part of it, I think it might be possible to do something for that case as well, using partially persistent data structures.

Apply the sweepline algorithms above to the polygons $S_1,\dots,S_n$, and store all copies of the binary tree and interval tree at each event.  Naively, this would require $\Omega(n^2)$ space (since there are $\Omega(n)$ events and each tree is $\Theta(n)$ in size), which is horrible.  Fortunately, each tree differs from the previous tree by only $O(1)$ modifications.  Therefore, we can use a persistent data structure to store all of the trees, using standard path copying techniques, and in that way we'll be able to store all of the trees in $O((n+k) \log n)$ space.  Moreover, if we keep an array of all of the roots of these trees, then given any x-coordinate, we'll be able to look up the appropriate tree for that x-coordinate in $O(\log (n+k))$ time using binary search.

Given a polygon $P_i$, we'll first look up each vertex of $P_i$ in this data structure to see if it is contained in any of the $S_j$'s.  This can be done by taking each vertex, looking up the Bentley-Ottman trees for the x-coordinate of that vertex, and looking up the y-coordinate of that vertex in the interval tree to see if any of the $S_j$s contain it.

Next, we need to go through each line segment in the perimeter of $P_i$ and check whether it intersects any of the line segments of the $S_j$'s.  However, I don't know how to do this in a way that supports online queries for the $P_i$'s.  So, that's the part you'd need to find a way to fill in.


Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

The authors give the answer:

  The error is that we have not proved the exact form of the inductive hypothesis, that is, that $T(n) \leq cn$.

Granted, that is hard to understand if you are not used to do inductions (right), because they do not do the induction explicitly/rigorously. In short: you need to have one constant $c$ for all $n$, but this (un)proof constructs many (one per $n$).

In long, remember what $T(n) \in O(n)$ means:

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \exists n_0 \in \mathbb{N}.\, \forall n \geq n_0.\, T(n) \leq cn$

or, equivalently,

$\qquad \displaystyle \exists c \in \mathbb{N}.\, \forall n \in \mathbb{N} T(n) \leq cn$.

The second form works better for an induction as you know the anchor. So you need one constant $c$ that provides an upper bound for all $n$.

Let's inspect what the induction does:

Induction anchor: The anchor of $T$ is not explicitly given, but it's constant, so we find a suitable $c$.
Induction hypothesis: There is some $c$ so that $T(k) \leq cn$ for all $k\leq n$, for some arbitrary but fixed  $n$.
Inductive step: as shown in the question, construct $d > c$ so that $T(n+1) \leq dn$.

So, in effect, we construct a new constant for every $n$. That does not fit the definition of $O$ at all! And, worse, it is completely meaningless: every function can be "bounded" by any other function if you can adjust the factor with $n$.

Regarding the induction proof, $c$ has to be part of the claim (and it is, hidden in the $O$), that is bound "outside" of the induction. Then, the same $c$ shows up in anchor, hypothesis and step. See the last part of this answer for an example.


Avoiding the trivial certificate in complexity class NP

The point that you're missing is that the deterministic algorithm is given an input to the NP problem and string and it has to say either "That string is a valid certificate for the input" or "That string is not a valid certificate for the input." For example, for compositeness, the verifier would have to be able to accept "Six is composite because it is two times three" and reject "Five is composite because it is two times three." This can be done easily, by checking the arithmetic and checking that the claim isn't something like "$p$ is prime because it is $p$ times one."

If the certificate is just one bit, the only way the verifier could check that a string is a valid certificate would be to ignore the certificate and solve the problem.  Using compositeness again, the verifier's input would be just "Six is composite because, well, I promise it is" and "Five is composite because, well, I promise it is." The verifier can't just "believe" that the string is a valid certificate.


I've never seen this data structure before.  However, it doesn't seem like a good choice for storing a set of words, for most purposes.  I see three significant disadvantages:

Performance. Looking up a word in this data structure can potentially be quite slow.  In particular, when looking up a word of length $n$, checking whether it contains a particular letter involves looking at all $n$ characters of the word.  Therefore, traversing the entire tree (all 26 levels) might require reading the entire word 26 times.  In contrast, a trie reads each character of the word only once, so might be about 26x times faster.  Same for a hashtable.
Space usage. This might take a lot of space.  I am assuming you won't construct a node unless it is needed (i.e., if it has only one child, you'll omit the node).  With that optimization, the depth of the tree is at most 26 if you're using words with letters a-z.  If you are storing strings in Unicode, the depth of the tree might be enormous, and in the worst case this might devolve to a data structure where the depth of the tree is proportional to the number of words in the set, and then the space usage is bad and the time for a lookup is very bad (linear in the size of the set).  Without that optimization, the number of the nodes in the tree can be as large as $2^{26}$ for letters a-z, or enormous for Unicode strings.
Incomplete. This isn't a complete data structure.  It cannot distinguish between two words with the same set of letters, e.g., between words that are permutations of each other (anagrams).  Therefore, you'll need another data structure for storing the second-level sets (your circle shapes).  If we had a good data structure for that purpose, why wouldn't we use it for all the words, and skip your data structure?  Conversely, if you use a poor data structure for that, then your data structure inherits the limitations of that data structure: for instance, if you store all the words in the circle in a linked list, then lookups will be slow as they might need to traverse the entire list.


The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols

That section is not talking about parsing. The algorithms referred to are algorithms for converting between CFGs and PDAs of different types. The question is, as usual, "what is the computational complexity of the algorithm", and the response is, as usual, expresseded in terms of the size of the input -- to the algorithm.

The input to an algorithm which converts a PDA to a CFG is the PDA, and the size of the input -- the metric stick for the algorithm's complexity -- is the size of the *PDA". That's what the authors intend n to be.

How does one measure the size of a PDA? Simple: you write the PDA out as a string in some PDA definition language, and count symbols in the description. That's a completely fair procedure, because in order to call the conversion algorithm on the PDA, it's necessary to give the converter an input which represents the PDA.

Given that definition, the claims are not at all surprising. Every state and every alphabet symbol must be present at least once in the PDA description, so the size if that description is an upper bound. Similarly, it is possible that most of the description of the PDA is the description of a single rule, which could push almost n symbols.


Length of shortest codeword in Huffman encoding

Consider the distribution $\Pr[a]=0.34,\Pr[b]=\Pr[c]=\Pr[d]=0.22$.

Huffman's algorithm will first merge (say) $c$ and $d$ to create the symbol $cd$ with probability $0.44$. It will then merge $a$ and $b$ to create the symbol $ab$ with probability $0.56$. Finally, it will merge the remaining symbols.

All codewords thus have length 2.

You can check that the same example works up to $\Pr[a] = 0.4$ (we need $\Pr[a] \leq 2\Pr[b] = (2/3)(1-\Pr[a])$). What if $\Pr[a] > 0.4$? Consider the time at which Huffman's algorithm merges $a$ with some symbol $X$ (which may be composed of several original symbols). If $a$ and $X$ are the only symbols, then $a$ will be encoded using a symbol of length 1. Otherwise, there is some other symbol $Y$ of probability at least $\max(\Pr[a],\Pr[X]) > 0.4$. We see that $a,X,Y$ must be the only remaining symbols, and furthermore $\Pr[a] > \Pr[X]$ (otherwise there would 3 symbols whose probability exceeds 0.4).

Suppose that $Y$ was obtained by merging two other symbols $Z,W$. At that point, since $X$ itself or one of its constituents wasn't merged, we must have $\Pr[X] \geq \max(\Pr[Z],\Pr[W]) \geq \Pr[Y]/2$. But $\Pr[Y] > 0.4$ and so $\Pr[X] > 0.2$, and so the probabilities sum up to more than 1. This contradiction shows that $Y$ is an original symbol, and so in this case there is a codeword of length 1.

Concluding, the threshold for guaranteeing a codeword of length 1 is 0.4.


Is Artificial General Intelligence possible with our current machine learning models?

The short answer is, we don't know! This is an open question in AI research.

We know how neurons transmit signals, and can simulate that in a straightforward way: that's how layered perceptron models work. If we had a way to measure all the connections in a human brain, and enough computing power (which would be a LOT of computing power), we could simulate it. Or we could just make a neural network with as many neurons and connections as a human brain has. There's no theoretical missing link, we're just orders and orders of magnitude away in scale.

But it's an unanswered question whether the human mind exists entirely within neurons or not. It's a philosophical question more than a computer science one, and comes down to monism versus dualism.

Those who believe there's no theoretical barrier to AGI (just a problem of scale) tend to call their belief the Strong Church-Turing Thesis, which claims that a universal Turing machine could simulate a human mind, given unbounded resources and time. Or, equivalently, that a human mind is a Turing machine, or that there's nothing a human mind can do that a computer cannot do given time and resources for it.


Runtime analysis of prime-set computation

The key is already shown in your link: each composite number is marked only once in this algorithm.

Consider a composite number $x=p_1^{\alpha_1} p_2^{\alpha_2}\cdots$ where $p_1<p_2<\cdots$ are primes and $\alpha_1,\alpha_2,\ldots$ are positive integers. In the iteration for $p_i$ ($i>1$), note $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ has been deleted from $L$ in the iteration for $p_1$ because $p_1^{\alpha_1} p_2^{\alpha_2}\cdots p_i^{\alpha_i-1}\cdots$ is a multiple of $p_1$, so $x$ will not be marked in the iteration for $p_i$. As a result, $x$ will be marked only once in the iteration for $p_1$.

In each iteration, traveling the list costs the same asymptotically as the marking process, because each element in the list corresponds to a number to be marked.

Hence the total time is equal to the time for marking asymptotically, which is $O(n)$.


Pumping Lemma for single character language

You interpret the lemma incorrectly. The lemma says that "there is $n$ such that any string $y \in L$, with $|y| \geq n$...". So the lemma does not provide a particular $n$, it only says "there is", not "for all".

If the language is finite then, the pumping length is greater than the longest string in the language. And hence the three conditions of the lemma fails for all strings in the language, meaning there is nothing to "pump". Nevertheless, the lemma holds. Just recall the implication rule $p \implies q$: if $p$ is false then it does not matter if $q$ is true or false, the whole implication is true.

In your example with a single string $a$ take $n$, the pumping length to be $2$. So there is no string of the length greater than or equal to $2$. But it does not mean that the lemma fails.

Update:: the following predicate formula expresses the Pumping lemma for regular languages $$[ L \text{ is regular }] \implies [\exists n\forall x[ \left((x \in L) \land (|x| \geq n) \right)
\implies
(\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]]$$

and this is antecedent (conclusion) part of the lemma:
$$\exists n \forall x[ \left((x \in L) \land (|x| \geq n) \right)
\implies
(\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| > 0 \land \forall m[m>0 \implies uv^mw \in L))]]$$

This premise of the antecedent $(x \in L) \land (|x| \geq n)$ is false since $|x|$ is less than $n$ (for each $x \in L$) and hence the whole antecedent is true.


Apparently, you want to rebalance the AVL tree.

You can either do a simple left rotation or a right-left rotation.

I prefer not to mention right-right rotation since that term is misleading and ambiguous.

You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look closely when you delete 1.


Is any superset of an undecidable set is uncountable?

All sets of words over a finite alphabet are countable. Stated differently, no set of words over a finite alphabet is uncountable.


How to calculate the maximum sum over all arrays?

You can solve this using dynamic programming. For each $1 \leq m \leq n$ and $1 \leq t_m \leq \ell_i$, calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. This solution takes time $O(\sum_{i=1}^{n-1} \ell_i \ell_{i+1}) = O(\ell^2/n)$, where $\ell = \sum_{i=1}^n \ell_i$.

We can significantly improve on this algorithm by noticing that the objective function depends on the $i$th array via $\pm (i-1) A_i[1] \pm i A_i[\ell_i]$. This means that the shift we choose must maximize one of the following four quantities:
$$
\begin{align*}
+(i-1)A_i[1] + iA_i[\ell_i], \;+(i-1)A_i[1] - iA_i[\ell_i], \\-(i-1)A_i[1] + iA_i[\ell_i], \;-(i-1)A_i[1] - iA_i[\ell_i].
\end{align*}
$$
This means that there are at most four values of $t_m$ that we need to consider (and at most two for $m \in \{1,n\}$). We can find these value in $O(\sum_{i=1}^{n-1} \ell_i) = O(\ell)$, and the dynamic programming part now takes only $O(n)$. In total, we obtain an $O(\ell)$ algorithm, that is, a linear time algorithm, which is asymptotically optimal.


Finding at least two paths of same length in a directed graph

Consider a graph $G$, we want to know if there are two different paths from $A$ to $B$ of the same length. What to do? Simple: code two paths in one. Define graph $G'$ with vertices $V \times V \times \{0,1\}$. You make a step in $G'$ by making two independent steps in $G$. The additional bit tells you whether the two paths have already split from each other.

Formally, there is an edge $(i,j,e) \to (i',j',e')$ in $G'$ iff $i \to i'$, $j \to j'$ in $G$ and $e'=e ∨ (i,i')≠(j,j')$.

The algorithm checks if there is a path $(A,A,0)$ to $(B,B,1)$ in $G'$, which is $O(V^4)$, or something like $O((V+E)^2)$.

If you agree this algorithm is correct then, as a consequence, the path in $G'$ is of length at most $2n^2$, therefore potential "path collisions" must occur latest at that length. You can get a $O(V^{\omega} \log V)$ algorithm from this observation, where $\omega$ is matrix multiplication complexity (ask if you need a spoiler...).

I strongly feel there is a $O(V+E)$ algorithm, which uses more of the structure of the problem.