Could we design a Turing machine that output every bit of $\pi$ one after another correctly with limited tape length?

If by "limited tape length", you mean having a finite amount of memory, then the answer is "no".  With a finite amount of memory, the Turing machine as a whole can be modeled as a finite state machine.  A finite state machine that doesn't terminate must eventually repeat a state and thus fall into a loop. Therefore, the output of any such machine must correspond to the binary expansion of a rational number. The binary expansion of any irrational number whatsoever will require an unbounded amount of state.


NP-complete decision problems - how close can we come to a solution?

You made a crucial change to the question.  I've updated my answer to respond to the new question; I'll keep my original answer below for posterity as well.

To answer the latest iteration of the question: If the problem you really want to solve is a decision problem, and you've shown that it is NP-complete, then you might be in a tough spot.  Here are some candidate next steps:

Look for heuristics.  This means algorithms that work on some problem instances, but not all.  Basically, you're hoping that you only come across problem instances that are easy, not any of the worst-case problem instances.

SAT solvers are an example of this approach.  They solve a NP-complete decision problem ("does SAT formula $\varphi$ have a satisfying assignment?") using heuristics that happen to work well on many of the formulas we run into in real life, but their worst-case running time remains exponential.  Integer linear programming is another example of this.

One very powerful kind of heuristic is to formulate your problem as an instance of SAT, ILP, constraint satisfaction programming, or something like that; and then apply an off-the-shelf SAT/ILP/CSP solver to solve it.
Look for a fixed-parameter tractable algorithm.  Sometimes the complexity of a problem can be characterized by multiple parameters, and occasionally one can find an algorithm that is polynomial in one of the parameters, even if it is exponential in the length of the input (and thus is not a polynomial-time algorithm).

An example would be the knapsack problem, which takes as input an integer $W$ (the capacity of the knapsack) and some other inputs describing the items you can select from.  The knapsack problem is NP-hard.  However, there is a standard dynamic programming algorithm whose running time is $O(nW)$.  This algorithm is exponential in the length of the input (because $W$ is specified in binary, so the value of $W$ is exponential in the length of the input), and thus this does not qualify as a polynomial-time algorithm.  However, if $W$ is not too large -- as will often be the case in many practical settings -- this algorithm is efficient enough nonetheless.
Start looking at algorithms whose running time is exponential, or at least super-polynomial.  Sometimes the running time can be optimized so that the exponential running time is (just barely) tolerable.
Change the problem.  Start looking for way which you can "cheat", i.e., change the assumptions or the information given to you to make the computational problem easier.
Give up.  Accept that this is one problem you probably won't be able to solve.

These are standard strategies for coping with NP-completeness.  Many textbooks mention these options.

No, randomization alone is not going to take a NP-complete problem and make it easy to solve in polynomial time.  Everyone knows that proving $P\ne NP$ is a famous hard problem, and that most complexity theorists expect that $P \ne NP$ but just don't know how to prove it; similarly, most complexity theorists expect that $BPP \ne NP$, but they just don't know how to prove it.  Proving that $BPP \ne NP$ looks even harder than proving that $P \ne NP$.  That's why it is the $P \ne NP$ problem that is famous, not the $BPP \ne NP$ problem; if we can't prove that $P \ne NP$, we have no hope of proving that $BPP \ne NP$.

Incidentally, many complexity theorists expect that $P = BPP$, but proving that is way beyond our current knowledge.  That said, for all practical engineering purposes, you can assume that $P = BPP$.  (Complexity theorists, close your eyes here.  I'm about to use some engineering reasoning that works well enough for all engineering purposes, but will drive theorists crazy.)   If you have an efficient randomized algorithm that solves some natural real-world problem, I bet I can build a deterministic algorithm that will almost surely solve the problem, too; I won't be able to give you a proof of that fact, but I'll gladly take that bet even at \$100 to \$1 odds in your favor.  How can I be so confident?  Because if we take your randomized algorithm and, instead of feeding it truly random bits, feed it bits from the output of a cryptographic-strength pseudorandom generator, then there's no way your randomized algorithm is going to be able to tell the difference.  After all, if it could, it would have found a way to break the crypto.  If you find a way to break the crypto, there are people who will pay you a whole lot more than \$100 for the secret.  That's part of the reason why many people expect that $P = BPP$ (or some moral equivalent) is probably true.

Your original question said you wanted to find an approximate solution to a NP-complete problem, and asked what performance is possible.  Here was my answer to that question:

It depends on the problem.  Some NP-hard optimization problems have good approximation algorithms; others don't.  There's lots written in textbooks (and in Wikipedia) on approximation algorithms for NP-hard problems; this is a standard topic in undergraduate algorithms.  See, e.g., https://en.wikipedia.org/wiki/Approximation_algorithm and https://en.wikipedia.org/wiki/Polynomial_time_approximation_scheme, but make sure to read textbooks too.

BPP is not a relevant concept here.  The question of whether $NP \subseteq BPP$ would be relevant if you were looking for a randomized algorithm that produces an exact solution to the NP-complete problem.  But that's not what you're looking for.  You're looking for a randomized algorithm that produces an approximate solution to the problem.  Looking for an approximate solution is a different problem than looking for an exact solution.  If there were a polytime randomized algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $NP \subseteq BPP$.  Similarly, if there were a polytime deterministic algorithm to find an approximate solution, that wouldn't imply that there's a polytime algorithm to find an exact solution, and it wouldn't imply that $P=NP$.

Similarly, $PP$ is not very relevant here.

If you really want to relate this to complexity classes, the relevant complexity class is $APX$ (see, e.g., https://en.wikipedia.org/wiki/APX).

Incidentally, many approximation algorithms are deterministic algorithms.  Randomization is occasionally helpful but often not needed.


Context free grammar problem for number of a's is twice the number of b's

Let $c(w)=2\#_b(w)-\#_a(w)$. Your language is exactly $\{w\mid c(w)=0\}$.
Now consider a string $w$ with $c(w)=0$ and $|w|\ge 2$. If we can split $w$ into three parts: $w=pms$ such that $c(p)$ and $c(pm)$ have different signs, i.e., $c(p)c(pm)<0$, then there are two cases:

$c(p)>0$ and $c(pm)<0$. Note each time we append a character to string $x$, $c(x)$ is either increased by 2 or decreased by 1, so we can always split $m$ into two parts $m_1m_2$ such that $c(pm_1)=0$.

$c(p)<0$ and $c(pm)>0$. In this case  we can always split $m$ into two parts $m_1m_2$ such that either $c(pm_1)=0$, or $c(pm_1)=-1$ and $m_2$ begins with $b$.

As a result, either $w=w_1w_2$ where $c(w_1)=c(w_2)=0$, or $w=w_1bw_2$ where $c(w_1)=c(w_2)=-1$.
If $w$ cannot be split into such three parts, then $w$ must be either $bw_1aa$ or $aaw_1b$ where $c(w_1)=0$.
So, if we let $S_-$  generate the language of strings where $2\#_b-\#_a=-1$, then we have the following grammar
\begin{align}
S&\rightarrow SS\mid S_-bS_-\mid bSaa\mid aaSb\mid\epsilon\\
S_-&\rightarrow aS\mid SS_-
\end{align}


Decide whether the Language is regular {a^i b^j c^k|i ≥ 0, j ≥ 0, k ≥ 0}

You're using the lemma completely wrong. It states that

If language $L$ is regular, then there is $p$ such that for every string $s$ in $L$ where $|s|>p$ there is a decomposition $xyz$ with $|y|>0$ and $|xy|\le p$ for which $xy^i z \in L$ for all $i \ge 0$.

When you want to use it to prove language not to be regualr, you use contrapositive implication (making $\neg B \implies \neg A$ from $A \implies B$ ).

You get if for every $p$ there is a string $s$ with $|s| > p$ where for every decomposition $xyz$ with $|y|>0$ and $|xy| \le p$ there is a $i \ge 0$ such that $xy^i z \notin L$ then $L$ is not regular.

Now for your actual question, what you seemed to be doing is trying to prove the first implication, which would tell you nothing. It's important to note that the lemma is implication not equivalence, thus proving that a language has the pumping property does not mean it is regular. Conversely you cannot prove such languages to not be regular by pumping lemma.

If you wanted to prove that the language is not regular, you would need to make a string $s$ longer than $p$ for every $p$ from the language $L$ (for example by taking string $a^p b$ or $a^{p+1}$ or similar strings) and then you would have to make sure that there is an $i$ for all of the decompositions $xyz$ such that $xy^i z \notin L$. You can find many examples both on this site and on the Internet, but it is impossible here because the language is in fact regular.

To take your example more closely, if you wanted to prove the language to not be regular with the pumping lemma, your first mistake was chosing $p$, because you need to prove the statement for every $p$.


Is GAP NP-hard with at most two balls per bins?

You can reduce numerical 3-dimensional matching (N3DM) to your problem.

Given an instance of N3DM $X\times Y\times Z$ with the bound $b$, say $X=\{x_1,\ldots,x_k\},Y=\{y_1,\ldots,y_k\},Z=\{z_1,\ldots,z_k\}$, you can construct $k$ bins with capacities $b-x_1+M+M^2,\ldots,b-x_k+M+M^2$, and $2k$ balls with sizes $y_1+M,\ldots,y_k+M, z_1+M^2,\ldots,z_k+M^2$, where $M$ is a very large number. Now there is a valid solution to the N3DM instance if and only if you can pack all the $2k$ balls.


grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

There is a linear space deterministic algorithm for deciding whether a given propositional formula is tautological. The algorithm goes over all truth assignments and verifies that the formula evaluates to TRUE under all of them.

Regarding monadic predicate logic, Lewis (journal version) determined that the nondeterministic time complexity is $2^{\Theta(n/\log n)}$, but I'm not sure if the nondeterministic space complexity is known. Perhaps you could sift through the papers citing Lewis.


Encoding (binary) trees using lambda calculus

I'll choose to encode binary trees with data in the internal nodes.
Intuitively, a tree is either empty leaf, or a triple (data,left subtree,right subtree).

The corresponding Church encoding is:

$$
\begin{array}{l}
{\sf Empty} = \lambda e b. e
\\
{\sf Branch}\ x\ l\ r = \lambda e b. b x (l e b) (r e b)
\end{array}
$$

For instance, ${\sf Branch}\ 1\ {\sf Empty}\ ({\sf Branch}\ 2\ {\sf Empty}\ {\sf Empty})$ is an encoded tree. You can easily reduce it to a normal form, if wanted, resulting in $\lambda e b. b \ 1\ e\ (b\ 2\ e\ e)$.

Indeed, the normal form of a tree obtained from the above "constructors" will always start with $\lambda e b.$ and then proceed with the tree where the variable $b$ denotes a "branch" and variable $e$ denotes the empty tree.

To use an encoded tree, you can simply apply it as in $t\ E\ B$, providing two suitable terms $E,B$. This will compute a so-called "fold" of the tree, using constant $E$ and ternary function $B$ over the tree $t$.

For instance, $t\ 0\ (\lambda x l r. x+l+r)$ will result in the sum of all the numbers in the tree $t$, assuming $t$ only contains numbers as data.

It takes a while to convince oneself that this encoding indeed lets us do "whatever we want" with the tree, i.e. run any algorithm over a tree. For primitive recursive algorithms, we can use the encoding itself, directly. For more general algorithms, we can use a fixed point combinator on top of that.

This encoding can be generalized to all the algebraic data types defined through (positive) recursion. Moreover, the encoding can be typed in System F.
It is really general.

If you are familiar with some typed functional languages (such as Ocaml or Haskell), I'd recommend you try to implement a "fold" function on trees (with data in the nodes, or in the leaves), or on other algebraic data types. It's a nice exercise which I believe can help a lot in understanding the encoding in its generality.


The base case works because, if the array contains only 2 elements, it compares them and return the biggest.
Starting from this assumption, the recursive call to the function maxNumber compare the maxnumber of the precedent call to the next element in the array.
when the list has been read all the way to the end, the algorithm will return the max number of the whole list.


Here is the idea of the proof. Throughout, we assume that $p \geq q$.

Let $p^{(t)},q^{(t)}$ be the values of $p,q$ after $t$ iterations, so that $p^{(0)}=p$ and $q^{(0)}=q$.

Let $F_m$ be the $m$th Fibonacci number, which satisfies $F_m = \Theta(\varphi^m)$, where $\varphi = \frac{1+\sqrt{5}}{2} > 1$. Suppose that $p \leq F_m$. If $q \leq F_{m-1}$ then $p^{(1)} = q \leq F_{m-1}$. If $q \geq F_{m-1}$ then $q^{(1)} = p \bmod q \leq F_{m-2}$, and so $p^{(2)} = q^{(1)} \leq F_{m-2}$.

This argument shows that if $p \leq F_m$ then after at most (roughly) $m$ steps, the algorithm will terminate (since we cannot have $p \leq F_0 = 0$). Since $F_m$ grows exponentially, it's not hard to check that $p \leq F_{O(n)}$, where $n$ is now the length of $p$ in bits. Therefore the algorithm terminates in $O(n)$ steps.

If you want a bound depending on $\min(p,q)$ rather than on $\max(p,q)$, simply notice that $p^{(1)} = q$, and run the above analysis on $p^{(1)}$.


Closure property of recursively enumerable language

Basically, "R.e. sets are closed under intersection means that for any two r.e. sets $A \cap B$ is again r.e, but when we say that r.e. are not closed under some set-theoretic operation it means there are at least one pair of r.e sets which results in not-r.e. set under that operation no matter it is set-theoretic difference or complement. In other words,

R.e. sets are closed under a set theoretic operation $\star$ means that for any pair $A$ and $B$, $A\star B$ is r.e.
R.e. sets are NOT closed under a set theoretic operation $\star$ means that NOT for all pair $A$ and $B$, $A\star B$ is r.e. In simple words, there may be sets $A$ and $B$ such that $A\star B$ is r.e., and there exist other sets $C$ and $D$ such that $C \star D$ is not r.e.

For example, the set $N - 2N$ (the set of all odd positive integers is r.e (even recursive), but the set $N - A_{TM}$ is clearly not r.e. ($A_{TM}$ denotes the set of Halting problem).


Is "super-exponential" a precise definition of algorithmic complexity?

"Super-exponential" just means more than exponential, so a function is super-exponential if it grows faster than any exponential function. More formally, this means that it is $\omega(c^n)$ for every constant $c$, i.e., if $\lim_{n\to\infty} f(n)/c^n=\infty$ for all constants $c$.
Conversely, a function is "sub-exponential" if it is $o(c^n)$ for every constant $c>1$, i.e., $\lim_{n\to\infty} f(n)/c^n=0$ for all constants $c>1$.
Asymptotically, the $n$th Catalan number is $\Theta(4^n\, n^{-3/2})$.  This is $o(4^n)$, so the Catalan numbers are not super-exponential; it is $\omega(2^n)$, so they're not subexponential either. The Catalan numbers are just exponential.
An exception to the above definitions is that, in some contexts, functions of the form $b^{n^k}$ for constants $b,k>1$ are considered to be exponential, even though
$$
\lim_{n\to\infty}\frac{b^{n^k}}{c^n}=\lim_{n\to\infty}b^{n^k-n\log_b c}=\infty\,.$$
For example, the complexity class EXP is defined as the class of languages decided by Turing machines running in time $O(2^{n^k})$ for any $k$. Thanks to Yuval Filmus for pointing this out.


Binary heap removal peculiar potential function analysis

Amortized analysis relies on $\sum_{i=1}^n \overline{C_i} = \sum_{i=1}^n C_i+\phi_n-\phi_0$ being an upper bound for $\sum_{i=1}^n C_i$. This requires $\phi_n$ to be at least as large as $\phi_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.


Reference for counting the number of paths in a DAG

This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details.
It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs by extending the value set to $\mathbb{N} \cup \infty$ and adding a suitable $a^*$ operator.


Solving the recurrence $T(n)=T(n−1)/T(n−2)$


Maximum number of multiples of an array element preceding it

Hint: note that if there are duplicates, we are basically only interested in the last occurrence of each value. Now if you maintain an array $C$ of size $\max_i A[i]$ such that at the $i$-th iteration of your algorithm $C_k=|\{j\le i, A_j=k\}|$, how can you compute the number of multiples of $A[i]$ to the left of $i$ so that the overall complexity is not too high?


Hint: Take a new variable $x$ and add it to all clauses. This shows that HALF-SAT' is NP-hard, where HALF-SAT' differs from HALF-SAT by strengthening "at least half" to "more than half". HALF-SAT is similar.

The $P$-closure of HALF-SAT' (and HALF-SAT) forms the complexity class $PP$.


If we have a set of size $n$, you can represent an element of the set using $\lceil \lg n \rceil$ bits.  You say that there are 2598960 possible 5-card hands.  That means that a 5-card hand can be represented using just $\lceil \lg 2598960 \rceil = 22$ bits.  22 bits is significantly shorter than 30 bits.

How does the representation work?  There are various options, with different tradeoffs.  I list two below.

Hard-coded dictionary

In this case, the number of possible 5-card hands is small enough that you could just have a hard-coded dictionary that lists all 2598960 hands, and you represent a hand by its index in the dictionary (represented in binary).

In other words, the dictionary can be a sorted list of hands.  Each hand is the 5-tuple of the cards in the hand, in sorted order.  You can look up a hand in the dictionary using binary search and find its corresponding index; and given an index, you can find the correspond hand.  Or, you could store the dictionary as a hashmap that maps from the hand to its index.  The index is an integer between 0 and 2598959, so it can be represented using 23 bits.

This approach will work and be very simple to program, but it is wasteful in space (size of the program executable).

Ranking/unranking

Alternatively, if you care, there are better methods.  See, e.g., any of the following references:

https://en.wikipedia.org/wiki/Combinatorial_number_system
East Side, West Side.  Lecture notes, Herbert S. Wilf, August 14, 1999.  Sections 3.7-3.8.
https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/
https://stackoverflow.com/q/3143142/781723

The general topic is known as "ranking (and unranking) of combinations".  These are a little more complex to implement and understand, but avoid the need to include a hard-coded dictionary in the program.


Justifying a claim in the proof of the master theorem

Suppose that $f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants $N,C>0$ such that $f(n) \leq Cn^{\log_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log_b a - \epsilon}$ over all positive integers $n < N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq \max(M,C) n^{\log_b a - \epsilon}$ holds for all integer $n \geq 1$. Therefore
$$
g(n) = \sum_{j=0}^{\log_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} = O\left( \sum_{j=0}^{\log_b n-1} a^j (n/b^j)^{\log_b a - \epsilon} \right).
$$


Does Bellman–Ford algorithm can handle zero-weight cycles?

Yes.  Bellman-Ford can handle graphs with zero-weight cycles; they aren't a problem.

Intuitively, negative-weight cycles are problematic because they can make the notion of "shortest path" ill-defined: there is no shortest path.  For instance, suppose we have a cycle from A to A with weight -5, and an edge from A to B with weight 10.  Then there is no shortest path from A to B.  There's a path with length 10 (go straight there), a path with length 5 (traverse the cycle once, then go there), a path with length 0 (traverse the cycle twice, then go there), a path with length -5, a path with length -10, and so on.

Zero-weight cycles don't cause this problem.


I suggest you slightly modify your program, as follows:

int i, j, k, t = 0;
for (i = 0; i <= n - 1; i++)
  for (j = i + 1; j <= n - 1; j++)
    for (k = j + 1; k <= n - 1; k++)
      t++;

Now run this program for various values of $n$ and print the corresponding values of $t$, which is your runtime $T(n)$. Make a guess at the growth rate of $T(n)$ based on this. Try to prove your guess.

Another idea is to try to understand what happens when you have only one loop, then two nested loops, and then all three nested loops. The first case in particular is pretty easy.


Check if intersection of several 2D half-planes is empty

Your problem can be solved in linear time.

This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question).

In your case $m=2$ therefore the resulting time complexity is $O(n)$.


Minimize the maximum Hamming weight of basis vectors spanning a binary subspace

This is background, rather than a complete solution of your specific question.

What you're looking at are called linear anticodes in the literature, while Ahlswede uses the term "diameter" for the maximum distance of a code. Like normal codes, there are some bounds on maximum size, given length and distance.

The problem may also be stated in terms of the minimum number of coordinates where two codewords agree. If the alphabet is nonbinary, it gets much more complicated, and [1] has an upper bound for that case, but also discusses the result from [2] which is the following:

Given a binary anticode with diameter (maximum distance) $n-t$ over the binary alphabet (which need not be linear), letting $N_2(n,t)$ be the maximum cardinality of such a code we have
$$N_2(n,t)=\left\{
\begin{array}{lrr}
\sum_{i=0}^{(n-t)/2} \binom{n}{i},&\quad& if~n-t~is~even,\\
 & & \\
2 \sum_{i=0}^{(n-t-1)/2} \binom{n-1}{i},&\quad& if~n-t~is~odd.
\end{array}
\right.
$$

See the reference [1] for details. Apparently the binary diametric theorem above was proved by Kleitman in [2]. This bound applies to all anticodes and would apply to your linear anticode as well.

Farrell had an earlier article on anticodes which considered linear anticodes obtained by deleting columns from a simplex code, which may also be of interest, it shouldn't be hard to locate the reference.

[1] Ahlswede and Khachtarian, The Diametric Theorem in Hamming
Spaces:Optimal Anticodes, Adv. Appl. Math:20, 429:449 1998.

[2] D. J. Kleitman, On a combinatorial conjecture of Erdos, J. Combin. Theory, Volume 1, pp.209-214, 1966.


Bayesian networks encode a factorization of the joint probability distribution of a set of variables. Specifically, each variable is conditionally independent of all its non-descendants given its parents.

The joint probability distribution can be written as:

$P(X) = \prod_i P(X_i|Pa(X_i))$

where Pa(X) are the parents of X in the network.

You should be able to find the answer to your question by computing this quantity for your specific network and CPTs.


Does a turing machine halt with input left on tape?

When a Turing machine enters an accepting state, it immediately stops running and accepts whatever the original input string was (regardless of the state of the tape). So given the input aabb, the Turing machine will read the two as and enter the accepting state $q_2$, at which point it will halt and accept aabb.

In this case it doesn't matter that there's no transition for reading a b from $q_2$ because we've already accepted (though you are correct in general that whenever we're running a Turing machine and we arrive at a state with no transition defined for the character we're reading, we implicitly go to a dead state and reject).


Find vertices of a convex polytope, defined by intersecting half-spaces

Your problem is a special case of enumerating the vertices of a convex polytope, and there is an efficient (polynomial-delay) recursive algorithm for your special case, which I will describe next.

If $a_1+\dots+a_d > 1$, then there is no solution, and you can terminate.  If $a_1+\dots+a_d=1$, there is a single solution $(a_1,\dots,a_d)$, so output it and terminate.  Otherwise, I'll assume $a_1+\dots+a_d < 1$, so you use the following:

For each index $i$ such that $a_i<b_i$:

Let $c_i = 1-a_1-\dots-a_{i-1}-a_{i+1}-\dots-a_d$.
If $c_i \le b_i$, output $(a_1,\dots,a_{i-1},c_i,a_{i+1},\dots,a_d)$; it is a vertex of the original polytope.
Otherwise, replace $a_i \le x_i \le b_i$ with $b_i \le x_i \le b_i$ (i.e., replace $a_i$ with $b_i$) and recurse to output the vertices of the resulting polytope.

To help others find this by search: it's the intersection of the unit simplex (points of L1 norm exactly one) and an axis-aligned box.

In general, if the polytope is defined by an intersection $m$ half-spaces, then a vertex is defined by choosing a combination of $d$ out of the $n$ of the corresponding hyper-planes; if their intersection is a single point, and it is in the polytope, then it is a vertex.  This gives an exponential-time algorithm for enumerating all vertices for a general polytope.  There are other algorithms for the general case, but that's beyond the scope of this answer.


Let $f(n)=6n^2 + 12n$

The $O$ notation for $f(n)$ can be derived from the following simplification rules:

If $f(n)$ is a sum of several terms, we keep only the one with largest growth rate.
If $f(n)$ is a product of several factors, any constant is omitted.

From rule 1, $f(n)$ is a sum of two terms, the one with largest growth rate is the one with the largest exponent as a function of $n$, that is: $6n^2$

From rule 2, $6$ is a constant in $6n^2$ because it does not depend on $n$, so it is omitted.

Then: $f(n)$ is $O(n^2)$


Algorithm Time complexity analysis for algorithm having two different time complexities

No, you can't determine the asymptotic worst-case running time from these two graphs.

First, plotting empirical running times is not a reliable way to determine worst-case running time: How to fool the plot inspection heuristic?.  So, the approach of graphing performance on some testcases isn't a reliable way to get a "big-O" running time.

Second, knowing just these two graphs isn't enough to uniquely determine how it depends as a function of both $N,M$.  There are multiple possibilities for functions $f(N,M)$ that are consistent with both of these graphs.  For example, a two-variable function $f(N,M)$ is not uniquely determined by the one-variable functions $f(100,M)$ and $f(N,100)$.

Third, I strongly suspect that those two graphs don't tell the whole story.  For instance, you show us only a single graph for when $N$ is held constant and $M$ is varied.  But I suspect the shape of the graph (or the slope of the line) might depend on exactly which constant value of $N$ you choose: a very large value of $N$ might lead to a different graph than a small value of $N$.  This further highlights that we don't have enough information to uniquely infer the running time.

So what should you do?  Rather than plotting running times and treating the algorithm as a black box, it's probably to start by looking at the algorithm itself.  Look at the pseudocode of the algorithm and analyze its worst-case running time using standard techniques.  See, e.g., Is there a system behind the magic of algorithm analysis? and How to come up with the runtime of algorithms?.  This allows mathematically rigorous analysis that is provably correct and that can analyze the running time for all combinations of $N,M$.


Why ambiguous grammars are allowed for operator precedence parser?

An operator precedence parser usually has no ambiguity at all. However, the evaluation order is not determined by the parse tree, but by the operator precedences and associativities.

As a practical example, the Swift language doesn't define operator precedence or associativity in the language. It doesn't even define operators, except that the scanner knows which sequences of letters could be operators. The actual operators and precedence / associativity are define by the programmer, or as part of the standard library. As a result, a+b*c>d/e produces a parse tree that just consists of the five operands and four potential operators. The parse is unique, but doesn't tell how the expression should be evaluated.

The next phase checks that all the four potential operators are indeed operators. Then the priorities and associativity of the operators, as defined by the programmer or standard library, are examined. * and / have highest priority, + has lower, and > has even lower priority. If you had a-b-c, then the two operators have the same precedence, and both are left-associative, so the order is also clear. If you had two or more consecutive operators with same priority and different associativity, or with no associativity, that would be an error.

You couldn't define a grammar to handle operators, because their precedence and associativity are not even known when you start compiling.


Is there a standard way to define a formal language transformer?

Without knowing what kind of transformation you compute, it's unlikely that there's a useful word. Assuming that any two inputs are processed independently of each other, you're looking at (computable) function(al)s from $A^* \to B^*$ with two alphabets $A$ and $B$.

Here are some specific kinds of transformations:

string homomorphisms,
finite-state transduction, or
the transducer equivalent(s) of any automaton model.


If $w \in (L^R)^*$, then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^R$. Hence $w_1^R,\ldots,w_\ell^R \in L$, and so $w_\ell^R \ldots w_1^R \in L^*$. This shows that $w = (w_\ell^R \ldots w_1^R)^R \in (L^*)^R$.
Similarly, if $w \in (L^*)^R$ then $w = x^R$ for $x \in L^*$. Since $x \in L^*$, $x = x_1 \ldots x_\ell$ for some $x_1,\ldots,x_\ell \in L$. Then $x_1^R,\ldots,x_\ell^R \in L^R$, and so $w = (x_1 \ldots x_\ell)^R = x_\ell^R \ldots x_1^R \in (L^R)^*$.


You can do a lot better than a total delay of 36. In fact you can get a total delay of half that. The idea is to recursively adjust the delays from bottom up.

In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8.

At the start, the component delays, reading from the left are:

  8, 11, 8, 12, 5, 5, 7, 10

In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.

After the first adjustments, the component delays are now

  11, 11, 12, 12, 5, 5, 10, 10

Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.

After the second adjustments the delays are

  12, 12, 12, 12, 10, 10, 10, 10

Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync.

So finally, the component delays are

  12, 12, 12, 12, 12, 12, 12, 12

We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.

It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.


Suppose that $T(n) = aT(n/b) + n^{\log_b a}$ and $T(1) = 1$. Now consider some $n$ which is a power of $b$, say $n = b^k$. The formula gives
$$
\begin{align*}
T(n) &= aT(n/b) + n^{\log_b a} \\ &=
a^2T(n/b^2) + a(n/b)^{\log_b a} + n^{\log_b a} \\ &=
a^3T(n/b^3) + a^2(n/b^2)^{\log_b a} + a(n/b)^{\log_b a} + n^{\log_b a} \\ &=
\cdots \\ &=
a^kT(n/b^k) + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &=
a^k + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a} \\ &=
a^k(n/b^k)^{\log_b a} + a^{k-1}(n/b^{k-1})^{\log_b a} + \cdots + n^{\log_b a}.
\end{align*}
$$
There are $k+1 = \log_b n + 1$ terms in the final formula. Miraculously, all of them are equal to $n^{\log_b a}$! (Work that out on your own.)


What is meant by "uneven spacing" on number line when dealing with floating point numbers in computers?

Let's look at a single-precision floating point number (as specified by IEEE 754). It is made up of 32 bits. Therefore, there are exactly $2^{32}$ floating point numbers that dots the number line.

What does it mean when we say that the floating point numbers are "unevenly" distributed on the number line? It means that they are not uniformly distributed. But why?

Well, let's consider the case where these numbers are distributed uniformly on the number line. Then there's some constant finite gap between successive numbers, $\Delta$. Since there are $2^{32}$ points on this line, then these uniformly distributed numbers span an interval of $\Delta \times 2^{32}$ width.

How big is $2^{32}$? Well, it's about 4 billion. Do you see the problem with uniformly distributed representations of numbers? If you want to even be able to represent the number $\pm 2$ billion in your uniform system, then you need to make sure that both $-2 \times 10^9$ and $2 \times 10^9$ are within your representable interval. Therefore, we need $\Delta \times 2^{32} \ge 4 \times 10^9$, so that we must space our numbers around $\Delta \approx 1$ apart. But if $\Delta \approx 1$, how are you going to represent both $1$ and $0.5$ precisely? Their difference is smaller than the gap!

Herein lies the rationale for having non-uniformly distributed representations such as floating point numbers. Uniformly distributed representations (or fixed-point numbers) cannot represent both big numbers and small numbers in a "good-enough" manner.


Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?

It is not currently known whether or not a polynomial algorithm exists to solve these systems of nonlinear equations because, as the reduction provided shows, if such a thing were to exist, it would show that $NP = P$ which remains yet unknown.


timed automata - advance only in certain states

So, after looking deeper into the subject I found the solution. Posting in case somebody else needs an answer and is unfamiliar with the subject.

What I was looking for is called a Stopwatch Automaton (SWA) and allows the time to stop or advance (by specifying the derivative of a clock c' = {0, 1}).
Reference: The Impressive Power of Stopwatches. Franck Cassez, Kim Larsen
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.669&rep=rep1&type=pdf

Further I discovered that Hourglass automata also allow time to stop, but additionally also to reverse: c' = {-1, 0, 1}.
They however require the specification of a maximum clock value after which "all the sand passed through the hourglass" and the clock does not advance further.
Reference: Hourglass Automata.
Yuki Osada, Tim French, Mark Reynolds, Harry Smallbone
https://arxiv.org/abs/1408.5965


TM that finds the middle of an input string in O(n) time

With a two tape TM it is not difficult:

Move to the right on the input tape. Every second step write something to the secondary tape. Once you reach a blank on the input tape (i.e. the end of the input), start moving to the left on the input tape. Each step delete a symbol from the secondary tape. You have reached the middle if the second tape is empty.


Just simply use the inequality $1 + \Theta(1/n) \geq 1$ in the denominator. You will get the required answer.


The Law of Excluded Miracle in the language of guarded commands

The answer I can provide is I was reusing the definition of weakest precondition from the IMP language, but in fact I need a stronger definition. This definition looks as follows:

definition "wp c Q s ≡ (∃t. (c,s) ⇒ t) ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

It is taking care of non-determinism. When one evaluates:

lemma excluded_miracle: "wp c (λ t. False) = (λ s. False)"

One realizes that the statement is simply saying that the program either terminates, or does not terminate. Therefore, the import point now is to see whether my proposed definition is correct or can be improved in any way.


Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?

If it was not for multiples the problem would be Set Cover.
With multiples, a natural name would be Multiset Cover though I cannot say I have encountered this name before.

Obviously, Multiset Cover has Set Cover as a special case.
Hence (the decision variant of) it is NP-hard and you will not find a truly efficient algorithm.
On the other hand, Multiset Cover can be seen as a special case of integer linear programming in the same way that cover problems generally can.


Prove the languages |L| = 2 and |L| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

If I can show that $A_{TM}$ is mapping reducible to $L_{=2}$, ...

That is a nice idea. Given $\langle M, w \rangle$, can you construct a TM $M_1$ that accepts only one word, the word $w$ if and only if $M$ accepts $w$?

Then, can you change $M_1$ so that it accepts another word that is different from $w$?

You can also show that $A_{TM}$ is mapping reducible to $L_{\not=2}$ by creating a TM $M_3$ which accepts 2 words if $M$ does not accepts $w$ and 3 words otherwise.


Can we always transform a set of lines to a function?

The short answer is yes. The longer answer is no.

The short answer is yes: that's a fundamental computation operation and it's pretty much the definition of a function. The equivalence between

def f(x):
    do something with x
f(foo)

and

do something with foo

is in fact the definition of a function, or more precisely of function application. This is so fundamental that it's the basis of the lambda calculus. In the lambda calculus, there are just three syntactic constructs:

variables ($x$, $y$, …);
applying a function to an argument ($F X$ where $F$ is a function and $X$ is the argument);
lambda abstraction $\lambda x. M$ where $x$ is the parameter name and $M$ is the function body.

The lambda calculus gets its name from that $\lambda$ notation, and it's where Python got lambda. In the lambda calculus, there is a single computation rule, called beta conversion (beta reduction when done from left to right, beta expansion from right to left):
$$ (\lambda x. M) N \equiv M[x \leftarrow N] $$
where $M[x \leftarrow N]$ means to replace $x$ by $N$ in $M$. (Details omitted because it would take a book chapter or two.) That single rule is enough to express all possible computations, in the sense that the lambda calculus is Turing-complete.

Beta conversion can be done in any language that has something that can reasonably called a function. But you need to take care of the details, and there are some language features that require additional effort or make it impossible in certain cases. Pretty much any language that isn't purely functional has restrictions on when beta expansion is correct.

In any language, the lines that you move to the new function must form a syntactic block. For example, if you have lines that are part of a multi-line construct like

while condition():
    instruction1()
    instruction2()

then you can move the loop out as a whole, but you can't move out while condition(): instruction1() and keep instruction2() in place.

One superficial but easily understood feature where beta conversion changes the behavior is introspection features. For example, if the language exposes a way to identify the current function or the function call stack trace, such as traceback.extract_stack() in Python, beta conversion changes that trace. If you put a call to traceback.extract_stack in a new auxiliary function, it's going to return something different. To make a beta-expansion that preserves the behavior, you'd need to modify calls to traceback.extract_stack to remove the new function from the trace. Note that this includes calls that may be deeply nested (if a function called inside the moved code calls a function that calls a function that … that calls traceback.extract_stack), so doing a fully behavior-preserving beta expansion turns into a global program transformation.

Another introspection feature of Python that breaks beta conversion is that it exposes local variables through locals(): locals()['x'] evaluates to the same value as x. If the code that you move calls locals(), you also need to pass the variables accessed through locals() as arguments to the new function and return their new values. So it isn't a purely syntactic transformation anymore.

A more interesting interaction is with flow control features. If the instructions that you put in the new function have self-contained flow, meaning that they're executed by starting at the top and either finishing at the bottom or raising an exception, then beta expansion or beta conversion doesn't change anything. It's ok if the code has loops and function calls inside it. But if the block of code that you move contains a non-local exit, i.e.  an instruction that makes the execution jump outside that block of code such as return or break, you can't just move it. Likewise if the block contains a jump target (in imperative languages that have goto). It's possible to get around this with a local transformation: make the auxiliary function take one more argument which indicates the entry point (if there's a way to jump into the middle of the code), and one more return value which indicates where to exit to (if there's a way to jump out to a place other than the end of the code block). For example:

def outer_function(x):
    if x == 1: return 2       #
    else: x = x - 1           #
    return x

If you want to extract the two lines marked with # on the right into a function, you need to remember whether to return the 2 or continue on to return x.

def new_auxiliary_function(x):
    if x == 1: return "RETURN", 2
    else: x = x - 1
    return "FALLTHROUGH", x
def new_outer_function(x):
    tmp = new_auxiliary_function(x)          #
    if tmp[0] == "RETURN": return tmp[1]     #
    x = tmp[1]                               #
    return x

Your transformation also changes exactly when variables are modified. This can become an issue due to aliasing. Aliasing is not normally an issue in Python since there's no way for a variable to designate another variable, as opposed to designating the same object as another variable. I wouldn't swear that it's never an issue, but I can't think of a way to do it. So instead I'll give an example in C, where aliasing is common due to pointers.

int x = 3;
int *p = &x;
*p = 2;                    //
printf("%d\n", x);         //

This code prints 2, since the pointer p points to x and the line *p = 2 therefore sets x to 2. Now let's create an auxiliary function for the part marked with //. Since C can't create compound values on the fly, we need to define a structure type for the return values, but that's just a cosmetic change compared with Python.

typedef struct {
    int x;
    int *p;
} values;
values new_function(int x, int *p) {
    *p = 2;
    printf("%d\n", x);
}
…

int x = 3;
int *p = &x;
values tmp = new_function(x, p);
x = tmp.x;
p = tmp.p;

The line *p = 2 in new_function sets the outer variable x to 2, since that's where p points to. It does not change the variable x that is inside new_function. Therefore this program prints 3.

When a compiler performs a beta reduction, it's called inlining. This is a common optimization, which typically makes the program run faster at the expense of larger code size. Compilers much more rarely do beta expansions. It's a worthwhile optimization when the same block of code (or more generally similar-enough blocks) appears more than once and code size is more important than execution speed, but it's difficult to detect worthwhile cases. Both transformations have limitations as to exactly when they're correct.


The first line should read
$$
\Pr_{x,y \sim D}[h(x) \neq y].
$$
(This is assuming that the classifier is deterministic.)

We can sample $x,y \sim D$ in two steps: first sample $x \sim D'$, and then sample $y \sim C_x$, where $C_x$ is a distribution depending on $x$.

The second line expresses the idea
$$
\operatorname*{\mathbb{E}}_{x \sim D'} \Pr_{y \sim C_x}[y \neq h(x)]
$$
in an elaborate way.

Both of these are the same, and equal to
$$
\operatorname*{\mathbb{E}}_{x \sim D'} \operatorname*{\mathbb{E}}_{y \sim C_x} 1_{h(x) \neq y}.
$$


Solving unusual recurrence with two variables

In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$.
Assume that $0<C<n$. Show that
$$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
for $0\leq k\leq n-C$ and $n\leq 2C$. It looks like this is the formula that you mentioned in the question, except that the binomial coefficient should have the same amount that is being subtracted from the first entry of $T$.
Apply it for $k=n-C$.
We get $$T(n,0)=\sum_{i=0}^{n-C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{n-C}\binom{n-C}{i}=2^{n-C}$$
If $n>2C$ the formula that we get is
$$T(n,0)=\sum_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
Putting $k=n-C$ we get
$$T(n,0)=\sum_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{C}\binom{n-C}{i}\in O(n^C)$$
since it is a polynomial of degree $C$.

We didn't need it this time, but a technique that could be useful to work with recurrences is generating functions.


Intersection of context free with regular languages

If $L$ is context-free then there is a PDA $\mathscr{P}$ that accepts it. If $M$ is regular then there is a DFA $\mathscr{F}$ that accepts it. The intersection language consists of the words that are recognized by $\mathscr{P}$ and $\mathscr{F}$.

Any word that is in the intersection is accepted by $\mathscr{F}$, but not all words that are accepted by $\mathscr{F}$ are in the intersection: only those that are also accepted by $\mathscr{P}$.

The cross product proof consists of constructing an automaton $\mathscr{P} \otimes \mathscr{F}$ which contains the mechanics of both $\mathscr{P}$ and $\mathscr{F}$, and which accepts only words for which both sides accept. The cross-product automaton is a PDA (and therefore the recognized language is context-free) — intuitively, because the cross product with an $n$-state DFA consists of taking $n$ copies of $\mathscr{P}$ and adding $(q,a,[q])$ arrows between matching states in $\mathscr{P}$ where the DFA has $a$ arrows. The result is not a finite automaton in general (not even a non-deterministic one) because the $\mathscr{P}$ part relies on the stack and this reliance does not go away in $\mathscr{P} \otimes \mathscr{F}$ in general.

A trivial example is that $\mathscr{A}^*$ is regular, and if $L$ is context-free but not regular then $L \cap \mathscr{A}^* = L$ is context-free but not regular.


The following is an easy to understand approach to tree pruning. It's easy to see why it's correct.

Let's start with ordinary minimax evaluation. If you are trying to evaluate position $p$ when it's the minimizing player's turn, you return $\min\{\operatorname{eval}(p',\text{max}) \mid p'\text{ successor of }p\}$.

To do tree pruning you change what $\operatorname{eval}(p',\text{max})$ does. Instead of returning a single value, it streams messages to you. Messages like "my final value will be at greater than 3", "my value will be greater than 20", "my value is 23". If the minimizer already got a message saying that one successor $p'$ has has value $5$, and it gets a message from $\text{eval}(p'',\text{max})$ saying that its value will be at least $10$ then the minimizer will close the channel with $\text{eval}(p'',\text{max})$.

It's easy to translate this into code and it's clear that it's functionally identical to minimax.

But it's not quite the algorithm presented on Wikipedia under alpha beta pruning.


if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$

Suppose $L$ is an NP-hard problem in coNP, and let $M$ be any problem in NP. Since $L$ is NP-hard, there is a polytime reduction $f$ such that $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$: given an input $x$, compute $f(x)$ and apply the coNP algorithm for $L$. This shows that $M$ is in coNP. In other words, NP is a subset of coNP. The same argument also shows the reverse inclusion, and so NP equals coNP.

The key idea is to avoid Cook reductions, for the reasons you mention.


How to express complexity of two functions considering it is the same in big O notation

Big O notation is oblivious to this difference. This is one of its downsides.
One reason we use big O notation in the first place is that the exact running time depends on the system used to run the algorithms. It is meaningless to say that a given algorithm takes X instructions, since X depends on the CPU, the compiler, and so on. However, in some cases we can find a proxy for the running time which is meaningful to look at.
The prototypical example is the number of comparisons in a comparison-based sorting algorithm. In many cases, number of comparisons is a good proxy for the overall running time, and this is a "dimensionless" quantity which is meaningful to compare across algorithms.
Another option is to implement your algorithms as efficiently as possible, and then compare their running time empirically. In a practical paper, this is a very reasonable thing to do.
In your particular case, you can just say that algorithm B invokes algorithm A three times, and consequently is three times slower. This is not reflected in big O notation, but is quite precise and meaningful.


Here some ideas:

Put the numbers in an array and repeat it. This allows to view the problem in a different light. Now you just have to compute a bunch of range maximum queries. RMQ is a well studied topic, and there are countless efficient solutions:

Sqrt-Decomposition: $O(N)$ preprocessing, $O(\sqrt{N})$ per query.
Segment Tree: $O(N)$ preprocessing, $O(\log N)$ per query.
Sparse-Tables: $O(N \log N)$ preprocessing, $O(1)$ per query
Farach-Colton and Bender: $O(N)$ preprocessing, $O(1)$ per query
and many more

Most of them are of a more general nature, e.g. they allow modifying the array. And some (like Farach-Colton and Bender) are not very pleasant to implement. This is probably way too much for your application.

So here I want to present a very simple and short data structure, which is still capable to compute the maxima in optimal $O(n)$ time: the Max-Queue.

A Max-Queue is a queue, that functions like a normal queue (you can insert values at one end and remove values at the other), and also can compute the maximal value in $O(1)$ time. CP-algorithms.com describes a few possible implementations of min-queues, which are just the dual data structure. I'll
use method 2 here:

The queue internally keeps track of how many items we have pushed and popped already, and stores the elements as pairs (value, push_index). E.g. pushing the elements [1, 6, 2, 4, 3] leads to the queue: [(1,0), (6,1), (2,2), (4,3), (3,4)]. And one thing more. It will do this in such a way, so that we only store elements in a monotone decreasing way, so that it stores the maximum at the beginning, and so that after popping the maximum the next maximum is still at the beginning. This would give us the queue structure: [(6,1), (4,3), (3,4)]. This allows looking at the maximum in $O(1)$ time (just look at the first element), inserting in amortized $O(1)$ time (you need to delete all elements from the back that are smaller than the new value), and popping in $O(1)$.

A Min-Queue implementation can be found under the link above. Each method consists of only 1-4 lines of code.

With the Max-Queue we can find all desired maxima in $O(n)$ time.
We insert the first $n/2$ numbers in the queue, and print the maximum. The pop a value, insert the next one, and print the maximum. Repeat until you printed $n$ values.


What are string matching algorithms used in text editors like Atom and sublime

Since Emacs is the superior editor, you can take a look in the source code yourself:  search.c
Emacs uses the Boyer–Moore string-search algorithm, so that's probably what you should prefer too.


How do real numbers like Pi, golden ratio, etc fit into type theory

If by "non-terminating real number" you mean to say that the digit expansion of the number is an infinite sequence, then that is not saying much, because every real number is "non-terminating" in this sense, even the real number 42, for its digit expansion is
$$41.999999999999999999999999999999....$$
In any case, nobody suggests that the digits must somehow be computed all at once, although that is a common misconception that arises in the study of computability of reals. We just need a method which computes any digit we desire – but we never desire all the digits at once.
A sequence of digits is a function $f : \mathbb{N} \to \mathbb{N}$, and such functions can be perfectly managed by type theory. In fact, the correct way to represent a real number by a sequence is to use positive and negative digits, or else you can't compute certain operations (such as $+$). So in reality, in type theory or in any other setting a real number may be represented by a sequence of digits $f : \mathbb{N} \to \{-9, -8, \ldots, 8, 9\}$. Even better but equivalent is the representation by which a real number is represented by a map $g : \mathbb{N} \to \mathbb{Q}$ satisfying the condition $\forall m, n \in \mathbb{N} \,.\, |g(m) - g(n)| < 2^{-\min(m,n)-1}$. Such a map represents the number $\lim_n g(n)$.
All of the above can be stated in type theory:
$$
\Sigma (g : \mathbb{N} \to \mathbb{Q}) \,
\Pi (m, n : \mathbb{N}) \;
\mathrm{Id}_\mathbb{Q}(1, \max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1))
$$
The inner $\mathrm{Id}$-type says
$$\max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1) = 1$$
which is just a fancy way of stating
$$|g(m) - g(n)| \cdot 2^{1 + \min(m, n)} \leq 1.$$


Easy to state open problems in computability theory

One famous open question about the poset $(D, \leq_T)$ of Turing degrees is whether it has any non-trivial automorphisms. That is, does there exist a non-identity bijection $f\colon D \to D$ such that $a \leq_T b $ if and only if $f(a) \leq_T f(b)$?.


Is this concatenation of two FA done right?

You can think of the concatenation of the languages defined by the two automata as the language of the automaton that can be obtained by connecting all final states of the first (in the example, just $x_1$) with the starting state of the second ($y_1$), by an empty transition, and then making them non-final.

A transition table can then be used to convert the NFA just generated into a DFA, which is what you did.

In this case, $r_1r_2$ is indeed equivalent to $r_2$, and this is completely normal. A transition graph represents a transition function, which is part of an automaton. If you minimize $TG_3$, what you get is exactly $FA_2$, which confirms the equivalence.


What is the type signature of a Turing Machine?

Usually, Turing machines are presented using set theory rather than type theory.

There might be many ways to represent a TM in type theory, each one with its advantages and disadvantages. I would not represent it as a function $\{0,1\}^* \to\{0,1\}^*$ since the function implemented by a TM is a partial function, because the TM might fail to terminate, while in type theory functions are total.

If we wanted to follow the set theoretic definition, we might define a TM as a dependent tuple. This tuple would include:

$\Sigma:\sf Type$ a type representing the tape "alphabet"
$Q:\sf Type$ a type representing the states
$b:\Sigma$ the blank symbol
$q_0 : Q$ the initial state
$\delta : Q \to \Sigma \to (Q \times \Sigma \times 3)$ for the transition function (assuming a deterministic TM) where $3=1+1+1$ represents the directions
$F : Q \to 2$ with $2=1+1$ the halting states

Technically, this would be a huge dependent sum such as

$$
\sum_{\Sigma\sf Type}
\sum_{Q:\sf Type}
  \Sigma \times Q \times (Q\to \Sigma \to(Q\times \Sigma\times 3))\times(Q\to 2)
$$

The above would be a possible representation of a TM. (I'm unsure it would be a very good one, especially if we work without functional extensionality, but I'll neglect that.)

In a similar way one could define the type of the configurations of a TM ${\sf Conf}\ T$ and a step function $step: {\sf Conf}\ T \to 1 + {\sf Conf}\ T$
(the $1+$ is to report "no next step" when the TM halts).

One could even define a function to run $n$ steps, or a predicate for "the TM $T$ on input $x$ halts with output $y$".

$$
\begin{array}{l}
{\sf runTM} :
\prod_{T:TM} {\sf Conf}\ T \to \mathbb N \to 1+{\sf Conf}\ T
\\
{\sf semanticsTM} :
\prod_{T:TM} (\pi_{\Sigma} T)^* \to (\pi_{\Sigma} T)^* \to \sf Type
\end{array}
$$


Reducing a graph without changing its chromatic number

The general idea of taking a problem instance and reducing it to a smaller one that gives the same answer is called kernelization. It's widely used in parameterized complexity theory and not just for colourings.


Each len_ = lps[len - 1] decreases $lps$ by at least 1, thus, it can only happen for lps[i - 1] + 1 - lps[i] times, since you initialize lps[i] as lps[i - 1] + 1. Therefore, the maximum number of times len_ = lps[len - 1] can happen is $\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$. As you know, $lps$ can increase by at most $n$ in total, therefore, it can decrease by at most $n$ in total, since $lps$ can never be negative, or equivalently, for each $+1$ $lps$ gets, it can get at most one $-1$. thus $\displaystyle \sum_{i=1}^n (lps[i - 1] + 1) - lps[i]$ will be $O(n)$.
I hope my answer was helpful.


Showing resolution algorithm for 2SAT is polynomial time

In the case of 2SAT, resolving two clauses does not increase their width (the width of a clause is the number of literals appearing in it). This is not the case for 3SAT, where resolution could increase the width. For example, if we resolve $a \lor b \lor c$ and $\lnot a \lor d \lor e$, both of width 3, we get the clause $b \lor c \lor d \lor e$ of width 4.
When running resolution on an instance of 2SAT on $n$ variables, we necessarily get stuck after at most $4n^2 + 2n + 1$ steps, since this is the total number of clauses that we could encounter. This shows that resolution runs in polynomial time on 2SAT.
Showing that resolution does not run in polynomial time on 3SAT is much more involved, among else since resolution is not really an algorithm but rather a proof system. Perhaps the simplest proof can be found in Ben-Sasson and Wigderson's classic paper Short proofs are narrow – Resolution made simple.


Represent there are infinitely many in FOL

The existing answers provide examples of contexts where "there are infinitely many" can be expressed. However, there is an important sense in which "there are infinitely many" cannot be expressed in a first-order way without some additional context restrictions:

Specifically, fix your favorite first-order language $\Sigma$. Then it's a consequence of the compactness theorem that there is no $\Sigma$-sentence $\varphi$ which is true in exactly the infinite $\Sigma$-structures:

If there were, then $\neg\varphi$ would hold in exactly the finite $\Sigma$-structures.
Then the $\Sigma$-theory $\{\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j): n\in\mathbb{N}\}\cup\{\neg\varphi\}$ would be consistent (since any finite fragment holds of any sufficiently large $\Sigma$-structure), so by compactness has a (presumably non-unique) model $\mathcal{M}$.
But $\mathcal{M}$ must be infinite, since any structure satisfying $\exists x_1...x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j)$ has at least $n$ many elements. By assumption on $\varphi$, this means $\mathcal{M}\not\models\neg\varphi$, and we have a contradiction.

Phrased most relevantly to your question, what we've shown is that even the sentence "There are infinitely many $x$ satisfying $x=x$" is not expressible in first-order logic.

On the other hand, when we restrict attention to specific structures we often have a better situation:

There are many natural structures over which the quantifier "there are infinitely many $x$ such that" is expressible. For example, in $(\mathbb{N}; +,\times,<)$, we may write "there are infinitely many $z$ such that $\varphi(z)$" as "$\forall x\exists y(x<y\wedge \varphi(y))$."

The other two answers fall into this category: they exhibit structures over which "there are infinitely many" is a first-order definable generalized quantifier.


Non-regular language whose prefix language is regular

One approach to think of examples or counterexamples is to looking for the simplest examples or starting from some known situations.

What are some typical examples of non-regular languages? A typical example is the language of palindromes. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. That is, its prefix language is a regular language.

The question has been answered.

However, as pointed out by Bader Abu Radi, the above example breaks down with unary alphabet, when the language of palindromes is the set of all words.

What are some typical examples of non-regular languages over unary alphabet, say $\{a\}$?

Let us try $\{a^{n^2}\mid n\ge0\}$ or $\{a^{2^n}\mid n\ge0\}$ or just any non-regular language you can think of. Since it is non-regular, its words can be arbitrarily long. That means its prefix language contains all words, $\epsilon, a, a^2, \cdots$. That is, its prefix language is regular.

Readers may enjoy the following two exercises.

Exercise 1 (easy). Show that an example over unary alphabet can be considered as an example over any larger alphabet.

Exercise 2. A language is prefix-closed if it is own prefix language. Give an example of non-regular prefix-closed language that does not contain a regular infinite language.


As said in the comment by Yuval, an SLR parse table with no conflicts (or parsing deterministic finite automaton) for a particular grammar implies that the grammar is unambiguous.

In fact, that is true for most if not all popular parsing methods.

LL(k)
LR(k)
SLR(k)
LALR(k)

Here is the sketch of a proof for all parsing methods. A parse table or a parsing finite automaton specifies an algorithm to produce all leftmost derivations (or rightmost derivations) of the input sentence. If there is no conflict in the parse table or the finite automaton is deterministic, only one derivation can be generated. That means the grammar is unambiguous.

Note for a given sentence, there is only one leftmost derivation is equivalent to there is only one rightmost derivation.


Tight asymptotic bound for recursive algorithm

Suppose that $n = 2^k$. Then
$$ T(n) = T(2^k) = T(2^{k-1}) + 1 = T(2^{k-2}) + 2 = \cdots = T(2^0) + k = k + 1. $$
So $T(n) = \log_2 n + 1$ in that case. In the general case you would get something similar, $T(n) = \lfloor \log_2 n + 1\rfloor$.


This is not the answer, but you may consider it as hints to find it
yourself.

Why do you write 4.95=5 without any explanation. Is that your idea of
perfect solution? Apparently your first solution never accesses the
disk. Your second solution is essentially the same as the first,
presented more abstractedly (hence a bit better in my opinion, but the reasonning may not be explicited enough for what seems to be your level of proficiency), but it
ignores the disk access as much as the first soution.

That may not always be true, but you should always worry at least a
little bit where you are ignoring part of the data of your problem.
You should convince yourself that the data you ignore is

either redundant with the data you use. This means that it is
actually a consequence of the data you are using, and can thus be
taken into acount implicitly through the data you are using;
or irrelevant to the problem. In this case you should preferably
have some argument as to why it is irrelevant. This argument may not
be required in your answer (though it may not hurt to give it), but
you probably at least sketch it for yourself to convince yourself
that you are right in ignoring the corresponding data.
Irrelevance can also include the fact that the corresponding data is negligible in the context of your problem. But that usually demands some argument to convince the reader that it is indeed the case.

Does the data you ignore correspond to such a case?


Smallest set of features that would make relational algebra Turing complete

You need just two things: new values and recursion/while.

New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.

Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.

SQL with CTE RECURSIVE is Turing Complete (without stored procedures).

See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.


Can exactly one of NP and co-NP be equal to P?

No, because $\mathsf{P}$ is closed to complement this cant be, and we even know that $\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$.

Let us assume that $\mathsf{P}=\mathsf{NP}$, and let $L \in \mathsf{co\text{-}NP}$, thus $L^c \in \mathsf{NP}$. We assumed $\mathsf{P}=\mathsf{NP}$, and therefore there exists a TM $M$ s.t. $L(M)=L^c$. If we take the "complement" of $M$, that is a machine $M'$ which is identical to $M$ except its accept and reject states are reversed, we get that $L(M')=(L^c)^c=L$, and thus $L$ is in $\mathsf{NP}$.

This shows that, under the assumption that $\mathsf{P}=\mathsf{NP}$, we get $(\mathsf{P}=)\mathsf{NP}=\mathsf{co\text{-}NP}$ and thus $\mathsf{P}=\mathsf{co\text{-}NP}$.


tl;dr: 25 times the clock frequency and two transfers per clock cycle equals 50 times the data rate.
First of all, let's forget about the terms IDE and EIDE. They were never specified in any standard or reference, and they were used in widely different manners by different people.
Some people use the term IDE (Integrated Drive Electronics) for any interface where the drive controller is integrated into the drive hardware, i.e. they use the term IDE to refer to any ATA, SATA, SCSI, SAS, IEEE1394, USB, or Thunderbolt drive. Some use it to refer to ATA-1 and the proprietary predecessors only, some use to refer to all ATA versions. Some people use the term EIDE to exclusively refer to ATA-2, some use it to refer to ATA-2 and ATA-3, some to any standard starting with ATA-2, excluding SATA, and some to any standard starting with ATA-2 including SATA.
So, let's stick to just official ATA versions, and let's call the proprietary versions before ATA-1 pre-ATA.
(Almost) every new ATA version has introduced new transfer modes, starting with the very simple PIO 0 transfer mode of pre-ATA. Each transfer mode has its own maximum transfer rate and cycle time.
Looking at Wikipedia, those were:

pre-ATA:

PIO 0 [3.3 MB∕s | 660 ns]

ATA-1: adds

PIO 1 [5.1 MB∕s | 383 ns]
PIO 2 [8.3 MB∕s | 240 ns]
Single-word DMA 0 [2.1 MB∕s | 960 ns]
Single-word DMA 1 [4.2 MB∕s | 480 ns]
Single-word DMA 2 [8.3 MB∕s | 240 ns]
Multi-word DMA 0 [4.2 MB∕s | 480 ns]

ATA-2: adds

PIO 3 [11.1 MB∕s | 180 ns]
PIO 4 [16.7 MB∕s | 120 ns]
Multi-word DMA 1 [13.3 MB∕s | 150 ns]
Multi-word DMA 2 [16.7 MB∕s | 120 ns]

ATA-3: drops all Single-word DMA modes
ATA/ATAPI-4: adds

Ultra-DMA 0 [16.7 MB∕s | 240 ns ÷ 2]
Ultra-DMA 1 [25.0 MB∕s | 160 ns ÷ 2]
Ultra-DMA 2 [33.3 MB∕s | 120 ns ÷ 2]

ATA/ATAPI-5: adds

Ultra-DMA 3 [44.4 MB∕s | 90 ns ÷ 2]
Ultra-DMA 4 [66.7 MB∕s | 60 ns ÷ 2]

ATA/ATAPI-6: adds

Ultra DMA 5 [100 MB∕s | 40 ns ÷ 2]

ATA/ATAPI-7: adds

Ultra DMA 6 [133 MB∕s | 30 ns ÷ 2]

Note that the Ultra DMA 4, 5, and 6 transfer modes required 80-wire ribbon cables instead of the older 40-wire ribbon cables. The 80-wire ribbon cables still had 40 connectors with the same pinout and semantics as the older cables, every other wire was a ground wire that was intended to provide physical separation as well as reduce capacitative coupling between the signal wires.
Also note that the Ultra DMA modes have two transfers per clock cycle, hence Ultra DMA 0 has the same maximum transfer rate as PIO 4 at half the clock speed.
Also, later versions introduced independent device timing, which allowed the host adapter to talk to each of the two devices on the bus with a different timing, whereas before that, it had to use the timing of the slower of the two devices.
Other than improvements to the transfer mode, there were also improvements to the command set that improved performance especially with multiple drives per bus. Originally, commands were completely serialized. The host adapter was only allowed to send a new command once the previous command was finished. ATA/ATAPI-4 introduced overlapped commands and queued commands as optional extensions to the ATA Command Set (ACS).
Overlapped commands allow the host adapter to send overlapping commands to both Device 0 and Device 1 on the bus, i.e. it allows the host adapter to parallelize communication with the two devices. Queued commands allow the host adapter to place multiple commands in a queue on the device, thus allowing the device to schedule the commands in a way that makes most sense for the device.
E.g. imagine, there is a WRITE command to write A into block 23, another WRITE command to write B into block 23 and a READ command for block 23, the drive could just throw away the first WRITE command, have the READ command immediately return B without even moving the read head, and only execute the second WRITE command.
However, neither overlapped nor queued commands were actually widely implemented because they caused a large load on the host CPU due to the way they were designed for backwards-compatibility with the ISA bus (from which the original pre-ATA bus was derived in 1986 and even the very latest version of Ultra DMA 6 in 2005 still had to be compatible with). Placing this large load on the host CPU meant that in most cases, while raw drive performance might have slightly increased depending on workload, the overall system performance didn't improve.
So, performance improvements were mostly made by improving the transfer mode, mainly by increasing the clock frequency (from 1.67 MHz in pre-ATA all the way up to 41.67 MHz in Ultra DMA 7), and later making two transfers per clock cycle (Ultra DMA). The command set added (optional) features for performance improvements as well, but those features were widely ignored.
Using DMA transfer as opposed to Polling I/O also helped, especially reducing load on the host CPU.


Can we understand SVM without knowledge of Machine Learning

I don't think there is anything that should stop you. A couple of tips to set you on the right path:

The basic principles of Machine Learning are very simple. They are often formalized in a way that makes it look very complicated, but this is only necessary if you want to get into the details of why things work. The general framework of what makes a classifier or what makes a clustering algorithm is very simple. Make sure you understand things on that level, before you dig into the details.
The title question (can SVMs be understood without ML knowledge) is slightly non-sensical. Understanding the basic ideas of ML is a minor investment and understanding SMVs takes much longer. There's no reason not to get a basic idea of what machine learning is before you dig into SVMs.
Make sure you have a good intuitive undertanding of the following principles and distinctions: features and instances, clustering and classification, supervised and unsupervised learning. After that, SVMs are just one particular way of solving a particular problem.
If you understand what a classifier is, you can start using SVMs without knowing anything about how they work or what they do. This may not give you the best result, but it's a good way to start learning by doing.

I can't really give you any references to start reading, since most of what's out there is far to formal for the level you'd want to start with. I recommend browsing around. If something is easy to read, then continue on, if it's too full of math, try something else first.


Loop invariance insertion sort algorithm

Python arrays have 0-based indexing, like in C, and unlike Fortran, which uses 1-based indexing. You can check Wikipedia for information about other languages.
A python array $A$ of length $n$ consists of the elements $A[0],\ldots,A[n-1]$. The python function range(n) goes over the indices $0,\ldots,n-1$, and your range(1,n) goes over the indices $1,\ldots,n-1$.
In insertion sort, we go over all prefixes of the array inductively, and make sure that they are sorted. If $A[0],\ldots,A[j-1]$ is already sorted, in order to make $A[0],\ldots,A[j]$ sorted, we just need to more the current $A[j]$ into its proper location. Since $A[0]$ is automatically sorted, we only need to go over $j=1,j=2,\ldots,j=n-1$, at which point the entire array $A[0],\ldots,A[n-1]$ is sorted. This is why the loop goes over range(1,n).
Is your implementation correct? Practically speaking, the best way to find out is to test it on many inputs. While such a test cannot verify that the algorithm is correct, and could miss some corner cases, it is also likely to catch off-by-one errors, especially in a language like python with bounds checking. Since insertion sort is such a simple algorithm, you are likely to catch any implementation errors by sorting small random arrays.


Black-box combinatorial optimization problem over permutations

In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force.  If f has no structure, no properties, no regularities, and is just totally random, then it is easy to see that any algorithm has to compute f on all $N!$ possible permutations to find the minimum.

In practice it is common to deal with functions f that do have some degree of structure.  For instance, if x,x' are similar (for some notion of similarity), then f(x),f(x') might have a good chance of being similar.  In those cases you can use techniques like local search.  But if you don't have that property, then you can't use local search, and you may be back to a situation where you cannot do any better than brute force.

There are other approaches in other situations: e.g., if we know the symbolic expression for f, we might be able to use a SAT solver, especially if that symbolic expression is not too large.  But again this requires f to have some structure and not be totally arbitrary.

There are no silver bullets.  You need to know something about f to have a hope of doing anything.


How can a probability distribution across classical states be computed for the measurement of a Quantum State represented by a Complex Vector?

The quantum state is a vector $v$ of unit norm. The probability of measuring outcome $x$ is $\|v_x\|^2$, the squared magnitude of the corresponding coefficient in the vector. Since $v$ has unit norm, these probabilities add up to $1$.


Usually, a random pivot is selected and moved to the first location.
After swapping -13 and 22, your pointers should be on 7 and 34.

7 and 34 are correctly placed.
Also 7 and 34 are adjacent, so time has come to put the pivot in its correct place.

array looks like this

15, -7, -13, 7, 34, 22, 19

So now you know that all elements after 34 are greater than 15.
So swap the first element before 34 with the pivot.

So array looks like

7, -7, -13, 15, 34, 22, 19

Now all on left of 15 are lesser than 15 and all on right of 15 are greater than 15


What is OUTER UNION and why is it partially compatible

There are two flavors of outer union: with and without NULLs. Google search readily exibits an example for NULLs version. The cleaner version of relational algebra desn't allow NULLs, and outer union is defined via De Morgan's law:

$ X \bigcup Y = \overline {\overline X \Join \overline Y} $

Date&Darwen call this operation $\blacktriangleleft OR \blacktriangleright$.

Given

R = [A B]
     1 2
     3 4

and

S = [B C]
     4 5
     6 7

both outer join variants agree that the result projected to common column B should be {2,4,6}. This is what is called inner union -- alternative way of generalizing standard relational algebra union operator. Now the problem is finding values of attributes A and C. Next, we match the values of the "middle column" with attributes A and C trying to leverage information in the relations R and S. In case of value B=2 we don't have matching value of C. Likewise, for B=6 we don't have matching value of A. Therefore, D&D $\blacktriangleleft OR \blacktriangleright$ operator fills the blanks in

[A B C]
 1 2
 3 4 5
   6 7

with all the values from corresponding domain, while the NULL version just blurts NULLs.


Randomized agorithm for selecting a $m$-subset out of a $n$-set

There are actually only two random steps in this case:

Start with $\{1,2,3\}$.
With probability $3/4$, replace a random element with $4$.
With probability $3/5$, replace a random element with $5$.

You get $\{1,2,3\}$ if you don't insert $4$ or $5$, which happens with probability $$\left(1-\frac{3}{4}\right)\left(1-\frac{3}{5}\right) = \frac{1}{4} \cdot \frac{2}{5} = \frac{1}{10}.$$

You get $\{3,4,5\}$ in two cases:

You replace $1$ with $4$ and then $2$ with $5$.
You replace $2$ with $4$ and then $1$ with $5$.

The probability that you replace a specific element with $4$ is $(3/4)(1/3)=1/4$, and the probability that you replace a specific element with $5$ is $(3/5)(1/3)=1/5$. In total, the probability that we get $\{3,4,5\}$ is

$$ \frac{1}{4}\cdot \frac{1}{5} + \frac{1}{4}\cdot \frac{1}{5} = \frac{1}{10}. $$

So both probabilities are the same.


Efficient algorithm for sorting objects by key that values are range from 0 to 100

Let $A[0 \dots, n-1]$ be the elements to be sorted.
A possible strategy that requires $O(n)$ time and $O(1)$ additional memory is:

count, for each possible key $k$, the number of elements in $A$ with key $k$, in $O(n)$ time;
for each $k$ compute the intervals of indices of $A$ in which elements with key $k$ must lie (in $O(1)$ time);
Scan the input array a place each element in the correct interval. This can be done by swapping the considered element with any element that was already in that interval, taking care to not swap that element back.

A possible implementation is the following:

Initialize an array $C[0, \dots, 100]$. Initially all entries of $C$ are $0$.
For each $i=0, \dots, n-1$: increment $C[k]$ where $k$ is the key of $A[i]$.
For $k=0, \dots, 101$, let $P[k]=\sum_{j=0}^{k-1} C[j]$; At this point we know that an element with key $k$ needs to end up in some $A[i]$ with $P[k] \le i < P[k+1]$. Notice that, for $k>0$, $P[k] = P[k-1] + C[k-1]$.
Let $i=0$.
While $i<n$:

Let $k$ be the key of $A[i]$.
If $i \not\in [P[k], P[k+1])$

Decrement $C[k]$
Swap $A[i]$ with $A[P[k]+C[k]]$

Else

Increment $i$


Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states

Let the automaton have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$, and suppose that $|Q| = n$. Denote the language that it accepts by $L$.
Suppose that $xy^iz \in L$ for $i = 0,\ldots,n-1$. Denote $p_i = \delta(q_0,xy^i)$. We consider two cases:

The states $p_0,\ldots,p_{n-1}$ are all different. In this case, $Q = \{p_0,\ldots,p_{n-1}\}$, and so $\delta(q,z) \in F$ for all $q \in Q$, implying that $\delta(q_0,xy^iz) \in F$ for all $i$, and so $xy^iz \in L$ for all $i$.
For some $j < k$, we have $p_j = p_k$. It follows that the sequence $p_i$ is eventually periodic, and so again $xy^iz \in L$ for all $i$.


Algorithm for type conversion / signature matching

I would suggest first solving the all-pairs shortest distance problem on the graph $T$ (or at least the single source version for each $p_i$ as the source) using standard approaches. Then, for each function signature $F_j=f_1,\dots,f_n$, compute $\sum_{i=1}^nd(p_i,f_i)$, where $d(p,f)$ is the distance between $p$ and $f$ (which can be infinite if $f$ is not reachable from $p$), then take the function that achieves the minimum. You should be able to do this in $O(|V|^3+nm)$ if you have $n$ parameters and $m$ functions.


Not Exactly. The microcode is a layer "below" the ISA and the Hardware-level functionality. That is, when you write some machine code like MOV or ADD or MUL (which are part of the ISA), the microcode translates it into multiple simpler activities (e.g., "move info from A register to B register. ADD this registers. Load from the Memory. etc.). These simple activities eventually perform the instruction you coded.

For instance, think of the MUL instruction that can be micro-coded as multiple add and subtract, like in done in elementary school.


In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

Note that the statement you want prove is equivalent to showing that the shaded triangles in figure 33.4b are non-empty, or more precisely (for the left triangle) that there exists a vertical line $x$ with x-coordinate strictly less1 than $p$ such that the triangle enclosed by segments $a,b$ and line $x$ does not contain a point of any other segment.

To show this, take a vertical line $x'$ to the left of $p$ that intersects both $a$ and $b$. The triangle enclosed by segments $a, b$ and line $x'$ may contain or intersect with a number of other segments. Of those segments, consider the segment with the rightmost point of intersection with the triangle, call this point $q$. Note that $p\neq q$, since the assumption was made that no three input segments intersect at a single point. Since $q$ lies in the triangle, its x-coordinate $q.x$ is strictly less than $p.x$. Now take a line $x$ with an x-coordinate in the open interval $(q.x,p.x)$, then no other segments intersect with the triangle enclosed by $a,b,x$.

Note that this proof also shows that line $x$ can be taken arbitrarily close to the right endpoint of some segment, which are the lines that the algorithm considers.

Although this proof fails when a third segment intersects at $p$, you can still show that for any intersection point $p$, there exists a pair of segments $a,b$ that intersect at that point such that they are consecutive in the partial order, using similar ideas.

1: Depending on the definition of "consecutive", a line with x-coordinate equal to that of $p$ would do, but this is not useful for the algorithm.


Where I can find example how prove red black tree?

Here is the obvious thing to try:

Prove that if you apply the insertion algorithm twice on an empty tree, then the resulting red-black tree has a red node (this also follows from the invariants of red-black trees).
Prove that if a red-black tree has a red node and you insert an element using the insertion algorithm, then the result red-black tree has a red node.

I don't know if this scheme works, but it's the most immediate way to apply induction.


Your teacher is right. $\delta^*(q_0, w) \cap (Q - F) \neq \emptyset$ does not necessarily imply that $\delta^*(q_0, w) \cap F = \emptyset$. Question 5 says that you don't terminate in any of the accept states, question 6 says that you terminate in some non accepting states, but NFA can still terminate in some accepting state.


The question is asking how many units are flowing from $s$ to $t$ under the current flow.

The maximum flow problem asks for the maximal number of units that can flow from $s$ to $t$ under any flow.


Guess the number from its different base representations

Let's start with a simple algorithm. Go over all possible interpretations of the first string (using all possible bases). For each such interpretation, go over the remaining string, and check whether they equal the interpretation of the first string for one of the possible bases. If there are $m$ possible bases and $n$ digits in total, then the running time is $O(m^2 n)$, ignoring the cost of arithmetic.

We can improve this as follows. Suppose for simplicity that all strings are at least two digits long (if not, we know the value of the number, and can finish in $O(nm)$ time). Compute all possible interpretations for each string, put all of these $nm$ numbers together, and sort them. Check whether the sorted list contain $n$ identical elements. This algorithm takes $O(nm \log (nm))$ time.

Another improvement, with a slightly better running time, modifies the original approach using binary search. Go over all possible interpretations of the first string. For each such interpretation, go over the remaining string, and for each one, use binary search (on the base) to find whether they equal the interpretation of the first string for one of the possible bases. This algorithm runs in $O(nm \log m)$ time.


If it is ambiguous (as in this case), a well-written text should indicate what it means.  If it doesn't, you might have to guess.  Sometimes people are sloppy or imprecise, or rely on you to infer what they mean from context.  There's certainly no guarantee that people will use language the way you describe -- it's not a standard assumption you can make.

In a graph without weights on the edges, the situation is clear, and we will use "shortest path" to mean the path with the fewest edges, and use "distance" to mean the number of edges.  In such a graph, the notion of number of edges and sum of edge weights coincides (since we assume each edge has weight 1), so there's no distinction to draw.  Thus, in that situation, we'd use the two words similarly.

In a graph with weights (lengths) on the edges, the most common situation is probably to use "shortest" path to mean the path with the smallest sum of edge weights, and use "distance" to refer to the length (sum of edge weights) of the shortest path.  In other words, when there are weights (lengths) on the edges, the most common situation is that we never refer to anything involving the number of edges on the path.

But sometimes we have a graph with weights (lengths) on the edges, and we want to talk about two different distance metrics: the number of edges on the path, and the sum of the weights on the edges on the path.  Then it's anyone's guess what terminology people will use; I don't think there's any accepted standard.  In this situation, I think you have to hope that the writer defines their terms, or try to infer their meaning from context.


Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

Unfortunately your proof is not correct. The claim you want to prove or disprove is:

  The union of any undecidable language and any finite language is undecidable.

To do a proof by contradiction, you need to take the opposite:

  The union of some undecidable language and some finite language is decidable.

Note that the "any" (universal quantifier) turns into "some" (existential quantifier) when you apply the negation.

You showed that a contradiction follows from:

  The union of any undecidable language and any finite language is decidable.

But unfortunately, that only proves:

  The union of some undecidable language and some finite language is undecidable.

In other words, you can't just pick specific languages and show that their union is decidable: you need to show that your proof will work for any arbitrary $L_1$ and $L_2$ fitting the requirements.

I would suggest that you instead start with an arbitrary undecidable $L_1$ and finite $L_2$ and, from there, show that $L_1 \cup L_2$ is undecidable. Here's a hint to get you started: is $L_1 \setminus L_2$ decidable or not?


Check if a tree is formed by 3 subtrees with given number of nodes

Let's root the tree arbitrarily at node $r$. Now with a DFS, compute the size of each subtree rooted at each node $v$. Let $good(u,i)$ be true, if there is some subtree rooted at $v$ where $v$ lies in the subtree rooted at node $u$ such that the size of the subtree rooted at $v$ is exactly $i$. We will maintain this property for only three values of $i \in \{X,Y,Z\}$. This can be done in the same DFS itself (which is left as an exercise for you).

Since we have rooted the node at $r$, due to the DFS traversal from $r$, all nodes except $r$ have a parent which we will denote by $p(u)$ for a node $u$. Now let's compute the same function $good'(u,i)$ for the same 3 values of $i$ but instead for the subtree which is obtained after deleting the subtree rooted at node $u$. This value can be computed via a second DFS (which I also leave as an exercise for you).

  HINT: Read up on how to find the longest and second longest paths starting at some node in a unrooted tree for each node.

Now the answer to the question is "Yes" if $\exists\ u \in$ tree $T$ such that $good(u,i)$ is true and $good'(u,j)$ is true and $i \not= j$

Since we have only two DFS traversals, the time complexity is $\mathcal{O}(n)$
and a constant amount of memory per node implies $\mathcal{O}(n)$ memory as well.


This has come up on the Coq mailing list several times, but I never saw a conclusive answer. Coq isn't as general as it could be; the rules in (Coquand, 1990) and (Giménez, 1998) (and his PhD thesis) are more general and do not require strict positivity. Positivity enough is not enough, however, when you go outside Set; this example came up in several discussions:

Inductive Big : Type := B : ((B -> Prop) -> Prop) -> Big.

With plain data structures such as yours, the inductive type would not cause problems other than making the implementation more complex.

There is a general way to define types such as this defined as the fixpoint of a polynomial:
$$F = \epsilon + \delta\, (F \times F) + \omicron\, \mathrm{id} + F \circ F$$

Instead of attempting to define the function $\mathrm{exptree} : a \mapsto \mathrm{exptree}(a)$, define the family of types $\mathrm{exptree}, \mathrm{exptree} \circ \mathrm{exptree}, \mathrm{exptree} \circ \mathrm{exptree} \circ \mathrm{exptree}, \ldots$. This means adding an integer parameter to the type that encodes the number of self-compositions ($\mathrm{exptree}^0(a) = a$, $\mathrm{exptree}^1(a) = \mathrm{exptree}(a)$, $\mathrm{exptree}^2(a) = \mathrm{exptree}(\mathrm{exptree}(a))$, etc), and a supplementary injection constructor to turn $a$ into $\mathrm{exptree}^0(a) = a$.

Inductive et : nat -> Type -> Type :=
  | alpha : forall a, a -> et 0 a                      (*injection*)
  | omicron : forall n a, et n a -> et (S n) a         (**)
  | epsilon : forall (S n) a, et (S n) a
  | delta : forall n a, et (S n) a -> et (S n) a -> et (S n) a
  | iota : forall n a, et (S (S n)) a -> et (S n) a
.

You can proceed to define values and work on them. Coq will often be able to infer the exponent. Set Implicit Arguments would make these definitions prettier.

Definition exptree := et 1.
Definition et1 : exptree nat :=
  delta _ _ (omicron _ _ (alpha _ 42)) (epsilon _ _).
Definition et2 : exptree nat := iota _ _ (omicron _ _ et1).

You may prefer to decrease the argument by 1, so that exptree is et 0. This removes a lot of S n in the definition, which may make some proofs easier, but it requires splitting the initial case from the recurrence case in every constructor that takes an $a$ in an argument (instead of adding a single injection constructor for $a$). In this example, there's only a single constructor to split, so this should be a good choice.

Inductive et : nat -> Type -> Type :=
  | omicron_0 : forall a, a -> et 0 a
  | omicron_S : forall n a, et n a -> et (S n) a
  | epsilon : forall n a, et n a
  | delta : forall n a, et n a -> et n a -> et n a
  | iota : forall n a, et (S n) a -> et n a
.
Definition exptree := et 0.
Definition et1 : exptree nat :=
  delta _ _ (omicron_0 _ 42) (epsilon _ _).
Definition et2 : exptree nat :=
  (iota _ _ (omicron_S _ _ et1)).

I think this is the same principle proposed in a more general form by Ralph Mattes.

References

Thierry Coquand and
Christine Paulin. Inductively defined types. In Proceedings of COLOG'88, LNCS 417, 1990. [Springer] [Google]

Eduardo Giménez. Structural Recursive Definitions in Type Theory. In ICALP'98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 1998. [PDF]


Trouble understanding the master theorem, from Jeffrey Erickson's Notes

You can further simplify $n^{\log_b(k)}f(n)$.

We have $\frac{a}{k}f(\frac{n}{b}) = f(n)$. If $c = \log_b(n)$, we can apply this identity $c$ times to get $\left(\frac{a}{k}\right)^c f(1)$.

So $n^{\log_b(k)}f(n) = n^{\log_b(k)}\left(\frac{a}{k}\right)^c f(1) = k^{\log_b(n)}\left(\frac{a}{k}\right)^{\log_b(n)} f(1) = a^{\log_b(n)}f(1) = \Theta(n^{\log_b(a)})$


When can one use a $O(n)$ time sorting algorithm?

In the comparison model, where all you are allowed to do is to compare two elements, and without further assumptions, we can prove that no sorting algorithm can do better than $O(n\log n)$.

If you want to sort in $O(n)$, you need either a stronger model, or additional assumptions.

For example, if you can bound the range of the numbers you are sorting, you can use bucket-sort, which is $O(n)$ (time).

A different example is spaghetti-sort: if you can implement the $\max$ function over $n$ elements in $O(1)$, then you can sort in $O(n)$.

You see here that different assumptions can allow you to sort in $O(n)$. There is no characterization of exactly which assumptions allow it.


Is recomnder systems part of computer science?

The algorithmic part of the  recommendation systems is more closely related to the computer science, the theoretical part of recommendation systems is mostly combination of statistics and linear algebra, thus we can think of recommendation systems as the combination of statistics and computer science, and the data science is the field that one would actually call the combination of statistics and computer science.
Thus my take on to answer the question is that the data science is the field you are looking for.


Name for concept: each pair of sets is either nested or disjoint


Virtual Memory: "Page Table or Page Tables?"

Each process has a different page table (since each process has a different address space). Each processor (or core if you want to be specific) can only have one active page table at a time, but the processor switches which table is used when it switches between processes.

I am also simplifying here because there are more tables used for IOMMU and hardware assisted virtualization.


Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists?

No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.


How fundamental are matroids and greedoids in algorithm design?

It's difficult to answer the question "how often". But as with all "underlying structures" the benefit comes from recognizing that the underlying problem one is trying to solve has a matroid (or greedoid) structure. It's not just matroid problems. The matroid intersection problem has a specific model (bipartite matching).

Nick Harvey did his Ph.D thesis fairly recently on algorithms for matroid problems and also looked at submodular function optimization (which generalizes matroid problems). Reading the introduction and background to the thesis might be helpful.


linear time nash equilibirum aproximations for two player zero sum games

By choosing a different framework of thought that does not attempt to ensure a specific bound we can do well in practice using an algorithm called regret matching.. The paper introducing this is called "A Simple Adaptive Procedure Leading to Correlated Equilibrium" by Sergui Hart and Mas-Colell
.
Regret matching is ensured to almost certainly converge to a nash equilibrium for a zero sum gum. There does not seem to be a ton of literature on the convergence rate but in practice it seems that for small matrices it converges close to the equilibrium in a matter of thousands of iterations. Additionally there are many strategies for speeding up convergence that sacrifice guaranteed convergence such as shareholding, or incorporating negative regret along with some normalization procedure. Regret matching has the extreme benefit of being exceedingly simple as well.
Regret matching is the basis for counter-factual regret minimization which is the technique behind state of the art poker AIs.


UNDIRECTED HAMCYCLE to HAMPATH reduction

No. Since you are performing a many-one reduction, you have no capabilities beyond the model you are using for the reduction, in this case a poly-time Turing machine. Queries to the problem you are reducing to are only allowed if you are performing a Turing reduction, but that is a different notion and (strictly) more powerful than a many-one reduction (and is not what is used when establishing NP-completeness).

Of course, the line would be allowed if you managed to prove HAMPATH is solvable in polynomial time. I don't think you will be able to.


Analyze time series data to get min max over past period of time

The following paper provides a O(1) algorithm:

D. Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element, Nordic Journal of Computing, 13 (4), 2006 (https://arxiv.org/abs/cs/0610046).

An implementation of this algorithm is provided in the GNU Scientific Library (see https://www.gnu.org/software/gsl/doc/html/movstat.html).