Decidability of language containing strings of length equal to that of some substring of 1s in $\pi$?

You are confusing knowledge and truth. Something may be true without us knowing precisely why. An object may exist without us being able to construct it.

If you belive in classical logic, then it is true that the maximum length of consequtive 1's in the expansion of $\pi$ is either finite or infinite. In each case, there exists a decision procedure for your language. Therefore a decision procedure exists.

But we do not know which of the cases happens, and so we not not know a particular decision procedure, even though one exists. If you don't like this line of reasoning, then you should ask for a constructive proof of decidability of your language.


Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

The question shows several misconceptions. I'll try to clarify the key aspects.

If $L$ is recognizable but not decidable, then $L$ has to be infinite (otherwise, it is decidable). If a TM recognizes such $L$, it has to accept all the words in $L$ (by definition of "recognizes"), hence it must halt in infinitely many cases.

A TM halting on infinitely many cases does not imply that the recognized language is decidable. (I'm unsure about why you think this would be the case, it would make the halting problem decidable, for instance.)

There is no such a thing as an uncountable language, at least in a conventional setting where the alphabet is countable, and words have finite length. Hence, a TM can never halt on "uncountably many" words.


Every function is big $\Theta,\Omega,O$ of itself, so you can already put your result in big $\Theta,\Omega,O$ notation. Using $4^{\log_4 (2n^2)} = 2n^2 = \Theta(n^2)$, you can also write $T(n) = \Theta(n^2)$; I'll leave you the details.


Computing FOLLOW sets for LL(1) grammar. Stuck on question

$FOLLOW\ (Y) = FOLLOW\ (D)$

  $FOLLOW\ (Y) = FOLLOW\ (E)$

A general Rule of thumb is, for any grammar

S -> XAB
A -> BC
X -> Bt

$
Follow (B) = Follow (S)  $
(Since there isn't anything after B in Production-1)

$Follow (B) = First (C) $ (Since C follows B in Production-2 and is a non-terminal)

$Follow (B) = t $ (since it follows B in Production-3 and is a terminal)


What are the different types of databases?

Wikipedia has a list of database models: http://en.wikipedia.org/wiki/Database_model


How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?

A grammar has "Production rules:" rules about the new sequences of symbols that you can produce from old sequences. In the cases of context-free grammars, this the old sequence is always a single non-terminal symbol.

Sometimes people abbreviate "production rules" to "productions". Sometimes people abbreviate "production rules" to "rules".

The two are not synonymous: there are plenty of things which are rules but are not productions, and people may call a single use of a rule a production, or the rule itself a production. Generally, the hope is that it's clear from the context what is meant.


Why do we say that polynomial time is easy?

I don't think it is possible to argue strictly with only mathematical or theoretical terms. Very much does come down to heuristics.
Of course an algorithm with runtime $O(n^{1000})$ or something similarly ridiculous would not be "easy" and in most practical cases worse than an algorithm of modest exponential growth. Yet such algorithms just don't happen in practice. And if an algorithm initially has a quite high runtime, then more often than not it can be improved dramatically, which means that the problem is a lot less "difficult".
As an example, take the AKS algorithm (which tests whether a given number is prime). It started out as $O(n^{12})$ (if I recall correctly), being one of the polytime-algorithms with the greatest exponent. But it was improved to $O(n^{6+\epsilon})$ in a quite short time. And very fast probabilistic algorithms for the primality problem exist as well, which shows that proving primalty is a lot easier than, say, your favorite NP-complete problem (assuming $P\neq NP$).

Of course the above could all turn out to be completely wrong. Maybe there exists a polytime algorithm for every NP complete problem which does not have a "practical" exponent. Knuth advocates that scenario; you might want to read question 17 here.


Gas Station problem : Fixed path variation

The greedy strategy works in this case (fill up as much as you need to reach the next cheaper city, or fill up to K if no cheaper city is reachable with a full tank).

The proof is pretty much the same as most standard proofs for greedy algorithms: Among all optimal solutions, take the one that "agrees with the greedy strategy the longest" and show that this solution is in fact identical to the greedy one (to understand why this almost always works, you can read up on matroids and see how the standard proof is done in this case).

Informally, in this case :

Call GS your greedy strategy and let OPTS be an optimal strategy which agrees with GS for the longest time, starting from the beginning. Suppose GS and OPTS differ in strategy for the first time in city C:

If OPTS fuels up more than GS at this point, then that means that GS fueled up just enough to reach the next cheapest city C'. It is clear that OPTS will arrive in C' with more fuel than GS (more than 0). But GS can then fill its tank up to as much as OPTS (for cheaper than OPTS could have at any point between C and C'). We can thus construct an optimal strategy OPTS' which does what GS does up to C' and then copies OPTS. But OPTS' is optimal and "agrees with GS" for longer than OPTS, which is impossible by definition of OPTS. So it is impossible that OPTS fuels up more than GS in C.
If OPTS fuels up less than GS in C, then let C' be the next city where OPTS is gonna fuel up. C' can not be cheaper than C, otherwise GS would have filled up just enough to get there and OPTS would have had to fuel up at some point between C and C'. So C' is as least as expensive as C, and filling up in C would not have been worse for OPTS. We can once again construct a new strategy OPTS' which contradicts the definition of OPTS. So it is impossible that OPTS fuels up less than GS in C.

Putting both together, we see that there can not be a "first disagreement point" between GS and OPTS. Thus, GS = OPTS, and GS is an optimal strategy.


Generating a Context Free Grammar from a Language

Given $L=\{a^nb^mc^k | \ n=m \ \vee m \neq k \}$ you can see it as $L=L_1 \cup L_2$ where:

$L_1=\{a^nb^mc^k | \ n=m\}$
$L_2=\{a^nb^mc^k | \ m \neq k\}$

Then you define 2 Context free grammars $G_1$ and $G_2$ for the 2 languages and in order to express the OR condition your add the production rule

$S \rightarrow S_1\ | \ S_2$

where $S$ is the starting symbol for $G$, $S_1$ for $G_1$ and $S_2$ for $G_2$.

As suggested in the comments, $L_1$ and $L_2$ can be splitted in order to make it easier the design of the grammars.

$L_1=L_{1,1} \cdot L_{1,2}$ where:

$L_{1,1}=\{ a^nb^n | \ n \geq 0 \ \}$
$L_{1,2}=\{ c^k | \ k \geq 0\ \}$

$L_2=L_{2,1} \cdot (L_{2,2} \vee L_{2,3})$ where:

$L_{2,1}=\{a^n \ | \ n \geq 0\}$
$L_{2,2}=\{b^mc^k | \ m < k\}$
$L_{2,3}=\{b^mc^k | \ m > k\}$


Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step?

Your analysis is correct, and you can conclude that $O(n^{3/4} \log(n)) = O(n)$ immediately. By L'hopital's rule $\log(n) = o(n^c)$ for any fixed $c > 0$, and in particular for $c = 1/4$. Therefore $O(n^{3/4} \log(n)) = O(n^{3/4} n^{1/4}) = O(n)$.


How is the problem of sorting in contiguous runs called?

Gopan et al. seem to define a more general problem and call it array partitioning [1].

The goals of array partitioning are twofold.  First, we
would like to isolate in separate groups [...]
we partition an array so that each element whose index is equal to
the value of any of the vari ables in the set is placed in a group by
itself. [...]
[W]e partition each array $A \in Array$ by grouping together elements of $A$
for which all partitioning functions in $\Pi_A$ evaluate to the same values.

I have not dug into how their formal framework captures your problem and it may not even do so. Still, I think the general idea is close enough to use the word.
Come to think of it, Quicksort-style partitioning is related as well: you want to partition w.r.t. identify, in Quicksort we partition w.r.t. equivalence classes induced by some pivots.

A framework for numeric analysis of array operations by D. Gopan, T. Reps and M. Sagiv (2005) [preprint]


Yes, of course they exist, and they're useful both practically and theoretically.

Any time you write a computer program to solve some specific task that's hard-coded into the program (for example, to compute some value or find solutions to a specific set of equations you're interested in), that's an algorithm with no input.

If you want to prove undecidability of, e.g., the problem of determining whether a Turing machine halts for every input, the first step is to translate a program that uses its input to a program that doesn't use its input and always computes as if it received some specific input. That's another example of an algorithm without an input.


A Special Case of Multiple Choice Knapsack Problem: Is it NP-hard?

There is a dynamic programming solution.

Let $f(i, V)$ be the minimum weight to achieve value $V$ while only the first $i$ classes (i.e. $N_1,\ldots,N_i$) are considered, then according to the item to be chosen in $N_{i+1}$, we have

$$
f(i+1,V)=\min_{0\le j\le |N_i|}w_{ij}+f(i,V-j),
$$

where $w_{i0}$ is defined to be 0. Now you can compute $f(n,1),\ldots,f(n,\sum_{i=1}^n |N_i|)$ to get the first $j$ such that $f(n,j)\le W$, then this $j$ is an optimal value for your original problem.

This algorithm runs in
$$
O\left(\left(\sum_{i=1}^n |N_i|\right)^2\right).
$$

This is polytime because the input length is $\Theta\left(\sum_{i=1}^n |N_i|\right)$.


Do arbitrary/Byzantine failures include omission failures and timing failures?

Arbitrary failure means exactly what it says. It means that the failing process should be treated as if an opponent is choosing the process's behavior to try to break your system.

Other types of failure, such as omission failures and timing failures, are special cases of this. They are relevant because certain algorithms only guarantee correct results in all cases if, for example, it is assumed that a process may fail to respond to a message (omission failure) but cannot fail in other ways, such as by responding with incorrect data.


What is a min-max theorem in graph theory?

A min-max theorem is simply a theorem that says that the minimum value possible for one quantity is the maximum value possible for some other.
For example,

Max-flow min-cut says that the value of the biggest flow between two vertices in a weighted graph is equal to the value of the minimum cut that separates them.  Closely related, Menger's Theorem says that the maximum number of edge-disjoint paths between two vertex sets is equal to the size of the minimum cut that separates them.
Edmonds' Theorem says that the maximum number of edge-disjoint spanning arborescences is equal to the minimum value of something called $\varrho(X)$ over certain non-empty vertex sets.
The cops and robbers characterization of treewidth says that the minimum width over all tree decompositions is equal to the maximum number of cops that a robber can escape (er, plus or minus one, probably).


Using LP to prove the max matching - min cover theorem

Your proof is missing a crucial ingredient, namely that for bipartite graphs, your LPs have the same objective value as the corresponding IPs. This is not true in general (otherwise vertex cover would be in P). You can see a proof for maximum matching in lecture notes of Meena Mahajan, and a proof for both in lecture notes of A. A. Ahmadi.


converting for loop into mathematical notation

Is the sequence $(a_i)_{i<n}$, where $a_0=1$ and $a_{i+1}=\lceil 1,5\cdot a_i\rceil$, what you need?


Is it common in the literature to define regular languages and serialization languages as programming languages?

No. In formal language theory, a language is just a set of strings, and it has nothing to do with programming. Note also that the things that programming languages such as Perl call "regular expressions" are more powerful than the regular expressions used in computer science and can define some non-regular languages.


The obvious algorithm tries all subsets, i.e., is $O(2^n)$ if you have $n$ elements to select. And your algorithm does that (try with first element, try without first element).

Complexity is given by the recurrence:

$$T(n) = 2 T(n - 1), T(0) \text{ given}$$

(try two posibilities for first one, recurse on the $n - 1$ others for each).


Space complexity for storing integers in Python

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the space complexity is $O(\log N + \log M)$, where $N$ is the number of integers in input and $M$ is maximum value in input. However note that normally we don't measure space complexity in bits: if we did, then the space complexity of most linear time algorithms, like DFS and BFS would have an extra $O(\log n)$ factor.

In my opinion, there is no single right answer when talking about space complexities like this in an informal setting like job interview. However you should keep in mind that having a single right answer is not the goal of job interviews.


How to show that any computable function is bounded above by Busy Beaver Function?

I think a sketch of the proof could be as follows.

First prove BB(k) is uncomputable. Assume it is computable, then it means there is some machine with some number of states m that can compute this value. Show that there exist a larger machine with some number of states M that calls this function on BB(M) and outputs BB(M)+1 1s, and then halts. Therefore there is a contradiction since it outputed more 1s than predicted by BB(M). It's easy to see M = m + C for some constant.

Now regarding the growth.

Assume G(k+1) >= BB(k+1) - BB(k) is computable for k >= K0.

Now, if the above is true then there must exist a machine with m states that computes G(k).

And there must also exist a machine, with a larger number of states M, that guesses BB(K0) and then computes UBB(M) = sum(K0..M)G(k) + BB(k0) and output UBB(M)+1 1s.

So this machine outputs more 1s than our assumed computable upper bound.

Therefore G(k) can not be computed for any K0.


Algorithm to choose the best team of 6 Pokémon given a constraint

You could use A* to solve this problem.  A* is designed to optimally search through a state space to solve a problem based on trying to minimize a "cost."

The first thing I'd do is reframe the problem.  Instead of thinking in terms of time and DPS, use time and "damage" by multiplying them together.  I recommend this because that's the term you're trying to maximize.  It'll make it clearer.

Let's define a "state" in this A* algorithm as a team of 0-6 Pokemon, and their total damage.  State transitions consist of adding Pokemon to the team, updating the total damage.  Don't forget that this is a combination problem, not a permutation problem.  Team ABCDEF is the same as team FEDCBA.  The easy way to handle this is to sort by name when adding to the team. (And as a small optimization, if you care, 50 pokemon is small enough to fit into a 64-bit integer, so your teams could be defined by a datastructure as small as an int)

To fit this problem to A*, we have to define a goal function.  The goal function defines an "acceptable" solution, but saying nothing about whether its the best solution.  The goal function is a team of 6 Pokemon that has a total time greater than 300.  This will satisfy your constraint.

We can handle your goal of maximizing damage by using it as our "cost" metric.  A simple way to do this is to say the "cost" is equal to $-damage$, that is to say that it's always a negative number.  A* doesn't mind the final cost being negative.

The last thing you need for A* is the "heuristic underestimate."  You need an estimated cost for finishing out the team that is always an underestimate (a lower "cost" than the real answer, which means a higher damage than the real best answer).  This can easily be constructed by finding a "best damage team" using the remaining Pokemon, ignoring the time constraint.

Put those together, and A* will do the rest.  A* is "optimal," meaning that it is the most efficient algorithm you can come up with given the information provided.  Any more ideal algorithm will need to use more information than what we gave A* (i.e. more than just a cost function and a heuristic underestimate).


To check if a chain with $n$ links can be "folded" into a size at most $L$

The crux of the problem is to identify when we can extend a chain $t, s_1a_1, \cdots, s_ka_k$ to a longer chain?
Let $m$ be the length of that chain, i.e., $m= t +\sum_{i=1}^ks_ia_i$. If $m+a_{k+1}\in [0,L]$, then we can extend it with $+a_{k+1}$. If $m-a_{k+1}\in [0,L]$, then we can extend it with $-a_{k+1}$. Otherwise, the chain cannot be extended.
An approach by dynamic programming.
Create a $(n+1)$-row by $(L+1)$-column table $F$ (shorthand for foldable). All entries of $F$ are False initially. $F[k][j]$ will be true if there is a chain made from $a_1,\cdots, a_k$ with length $j$ and within space $L$.

Set $F[0][j]=\text{True}$ for all $j$, $0\le j\le L$. According to the analysis above, $F[k+1][j]$ is true in two cases.

$j-a_{k+1}\in [0,L]$ and $F[k][j-a_{k+1}]$ true.
$j+a_{k+1}\in [0,L]$ and $F[k][j+a_{k+1}]$ true.

In other words, we can fill all values at row $F[k+1]$ if we know all values at row $F[k]$.
If $F[n][j]$ becomes True in the end for any $j$, then we return yes. Otherwise, return no.
Explanation on 5, 1, 7, 2, 8
     0   1   2   3   4   5   6   7   8   9
t 0  T   T   T   T   T   T   T   T   T   T
5 1  T   T   T   T   T   T   T   T   T   T
1 2  T   T   T   T   T   T   T   T   T   T
7 3  T   T   T                   T   T   T
2 4  T       T   T   T   T   T   T       T
8 5  T                           T

The fourth row $F[3]$ corresponds to chains of the form $t$, $\pm5$, $\pm1$, $\pm7$. Their lengths can only be 0, 1, 2, 7, 8, 9. Now if you add $\pm2$ to them, you can get lengths
     2,  3, 4, 9, 10, 11 (for +2)
    -2, -1, 0, 5,  6, 7  (for -2)

So the possible lengths of chains of the form $t$, $\pm5$, $\pm1$, $\pm7$, $\pm2$ are 2, 3, 4, 9, 0, 5, 6, 7, which correspond to row $F[4]$.
How to find the smallest realizable $L$?

A binary search on integers in [a_1, 2M-1] should be a nice way to find the answer, where $M$ is the maximum value of $a_i$s. Binary search is feasible since, if $L$ is realizable, values larger than $L$ are realizable too.
Exercises
Exercise 1. (One minute or less) Show that the smallest realizable $L$ is at most $2M-1$, where $M$ is the largest of $a_i$s.

Exercise 2. Adjust the algorithm if $s_i\in\{-2,-1,1,2\}$ for all $i$ instead of $\{-1,1\}$.


Can you reduce every decidable language to a regular language?

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then:

if $x \in A$, the reduction outputs $y_{in}$
if $x\notin A$, the reduction outputs $y_{out}$

where $y_{in}$ and $y_{out}$ are constant words in $B$ and $\overline{B}$, respectively.


A blocking $s$-$t$ flow is a flow whose residual network (consisting of all edges not saturated by the flow) contains no $s$-$t$ path. Stated differently, a blocking flow is a flow which, for every $s$-$t$ path, saturates at least one edge. Equivalently, a blocking flow is a flow which, for every simple $s$-$t$ path, saturates at least one edge.

The blocking flow problem is to find a blocking flow in a flow network. Such a flow exists since a maximum flow is always a blocking flow (but not vice versa).

The concept of blocking flow is used in Dinitz's maximum flow algorithm.


Can we express the program to find last element of a list as a catamorphism?

I'm a bit old-fashioned so I'll let Erik Meijer do most of the talking here.

Let's look at the classical definition of a list-catamorphism. More commonly, we call these functionals "folds" over some operator, because you can visualize it as bamboo scroll being folded into each other. (Except in this analogy, when we fold one piece into the other, we're left with a single piece).

Given a list over type $\alpha$ to fold over, an operation $\otimes : \alpha \times \beta \to \beta$, and an initial value $b : \beta$, we can define the $(b, \otimes)$ induced catamorphism $h : \alpha \textrm{ list} \to \beta$ as
\begin{align*}
h([]) &= b \\
h(a :: l) &= a \otimes h(l)
\end{align*}

In Meijer's (in)famous notation, we'll say that $h = (\!|b, \otimes|\!)$. We can do this because every catamorphism is uniquely determined by such a pair, and every pair defines a catamorphism, so we have an equivalent representation.

So let's now see whether there's some pair $(\!|b, \otimes|\!)$ such that the induced catamorphism finds the last element of the list. First, let us define the last function. You'll immediately notice a problem:
\begin{align*}
\textrm{last}([]) &= \bot \\
\textrm{last}(a :: l) &= \dots
\end{align*}

last is a partial function! Catamorphisms are by definition total functions, so we immediately see that a straightforward translation is impossible.

However, if we're allowed to use isomorphic representations, then we can consider the Maybe/Optional/Point functor that designates a special $\bot$ point that can be treated as the least element of the partial order. Let's say that the pointed type $\beta_{\bot}$ is either $\textrm{Some } b : \beta_{\bot}$ or $\bot_{\beta}$. The question now is whether there is some $(\!|a_{\bot}, \oplus|\!) : \alpha \textrm{ list} \times \alpha_{\bot} \to \alpha_{\bot}$ that models the last function. Some equational reasoning will quickly give a derivation

If
$$
\textrm{last}' = (\!|a_{\bot}, \oplus|\!) : \alpha \textrm{ list} \times \alpha_{\bot} \to \alpha_{\bot}
$$
then $a_{\bot} : \alpha_{\bot}$ and $\oplus : \alpha \times \alpha_\bot \to \alpha_\bot$.
Expanding the definition of a catamorphism out, we have
\begin{align*}
\textrm{last}'~[] &= a_{\bot} \\
\textrm{last}'(a :: l) &= a \oplus (\textrm{last}' ~l)
\end{align*}
The true last function ought to satisfy the equations
\begin{align*}
\textrm{last} ~ [] &= \bot_{\alpha} \\
\textrm{last}(a :: l) &= \textrm{match } \textrm{last}~l \textrm{ with} \\
&~~~~~ \mid~ \bot \to \textrm{Some } a \\
&~~~~~ \mid~ \textrm{Some } a' \to \textrm{Some } a'
\end{align*}

Equating last' and last then gives
\begin{align*}
a_\bot &= \bot_{\alpha} \\
a \oplus a' &= \textrm{match } \textrm{last}~l \textrm{ with} \\
&~~~~~ \mid~ \bot \to \textrm{Some } a \\
&~~~~~ \mid~ \_ \to a'
\end{align*}

which uniquely defines the pointed last' function as a catamorphism. To get the partial last function, just compose it with the partial function $\textrm{get}_{\alpha_\bot} : \alpha_\bot \to \alpha$.

Now, this proposal of returning to partiality has an interesting structure:
$$
\textrm{last} = \textrm{get}_{\alpha_\bot} \circ (\!|\bot_{\alpha}, \oplus|\!)
$$

The astute reader may point out that this seems to be of a form that is amenable to the catamorphic fusion law. And you are right, it has the correct syntactic form. To quote Meijer again, the fusion law is the extensional (since it is (usually) not an intensional reduction rule) equality that
$$
f \circ (\!|a, \otimes |\!) = (\!|b, \oplus |\!) \Leftarrow b = f~a \wedge f~(x \otimes x') = x \oplus (f ~ x')
$$
Unfortunately, neither of these conditions hold. In particular, $\textrm{get}_{\alpha_\bot} \bot$ is not valid (since get is partial at $\bot$).


Do two strongly connected nodes constitute a cycle in directed graph?

Like most things, you should only care about definition if it makes sense and useful in your context.

And in the context of strongly connected component, a nice property we would like to say is that:

  Node $a$ and $b$ belongs to the same cycle if and only if $a$ and $b$ are strongly connected.

This nice statement only holds if you count $f\rightarrow g\rightarrow f$ as a cycle.
So, we would like to count this as a cycle when talking about strongly connected components.


You can approach this problem using Reinforcement Learning.

A classic book for this is Sutton and Barto:

The draft of the second edition is available for free:
https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

In order to make your problem Markovian, define each state as a vector of the last ten decisions. You actions will be 1 or 0.


how the instructions are stored in relocatable format on disk

A compiled entity (say, a library) has a sequence of instructions. Each instruction has a particular location in sequence. This location is a value which can be considered simply as an offset from a base address. Loader loads the library at a particular address in the virtual address space of process and this address becomes the base address for the library and subsequently each instruction's location added to this base address becomes the actual address of the instruction in virtual address space of process.


How does computer store non-repeating decimal very accurately?

It may be that sqr (sqrt (7)) is displayed as 7, but it isn't actually exactly equal to 7. That's something you need to check. What you see is not always what you get. It may be that sqr (sqrt (7)) is exactly 7, by "coincidence" (not really coincidence, more like "unpredictable with my limited knowledge").

Take any floating point number x, 1 ≤ x < 4. When the square root is calculated, you get another floating point number y, 1 ≤ y ≤ 2. There are fewer floating point numbers (about half as many) 1 ≤ y ≤ 2 as floating point numbers 1 ≤ x < 4. If you square two numbers y and y', that calculation doesn't know how y and y' were created. So there are about half as many floating point numbers sqr (sqrt (x)), 1 ≤ x ≤ 4, as original numbers in that interval. So for about half the numbers, sqr (sqrt (x)) ≠ x.

The other way round, calculating sqrt (sqr (x)), you can probably prove that the result must be equal to x if both operations are calculated with high quality. If the squaring operation produces a relative error epsilon, then the square root operation divides that relative error by two.

PS. Yuval checked that for x = 7, sqr (sqrt (x)) is not equal to x. If you checked all integers from 1 to 10,000 except those that are squares, I'd expect that sqr (sqrt (x)) equals x in about half the cases that you check.


In a set of sentences, how could I determine the fewest sentences that contains all characters?

This is an instance of set cover.  It is NP-hard, so there is no efficient algorithm to find the absolute optimal solution.  The problem has been studied and there are many techniques out there, which you can find by searching on set cover.
One approach is to use a heuristic to select a subset of strings that might be a little larger than absolutely necessary, but which can be found efficiently.  See, e.g., the greedy heuristic and others derived from it.
Another approach is to use a SAT solver or ILP solver to find the optimal solution.  This is not guaranteed to terminate within your lifetime; it might, or it might not.  Some solvers will let you run for a fixed amount of time and output the best solution found so far.


Regular Expression with at least one a, even number of b

Another way of seeing this which gives a factorized representation is to try to locate the first $a$. It appears after either an odd or an even number of $b$.

If it appears after an even number of $b$ then you only have to check that what follows also has an even number of $b$ which can be done with Yuval's expression $a^*(ba^*ba^*)^*$.

If the first $a$ comes after an odd number of $b$, then you also have to find another $b$ and then check that the rest contains an even number of $b$.

This could be translated as follows: $(bb)^*(a+ba^+b)a^*(ba^*ba^*)^*$. Again, you can replace $a^+$ by $aa^*$.


Lemma R of section 3.2 (The Art of Computer Programming)

In "The Art of Computer Programming" by Donald Knuth, the proof of lemma R starts with the assumption that $\lambda = p^e$ which means:
  $$\left({a^{p^e}-1\over a-1}\right)\equiv 0\pmod{p^e}$$
  The above condition leads to:
  $$a\equiv1\pmod{p^e}\tag 1$$

If you read more carefully, that condition does not lead to formula (1). It only leads to
$$a\equiv1\pmod{p}\tag{2 }$$
In the case of $p=2$, the above condition is $$a\equiv1\pmod{2}\tag{3 }$$
which falls short of $$a\equiv1\pmod{4}\tag{4 }$$
That is why Knuth has to exclude the case of $a\equiv3\pmod{4}$ before asserting the formula (4).

  What proves $a=qp^f+1$, where $p^f > 2$?

Formula (2) implies $a=qp^1+1$ for all $p>2$, where $p^1=p>2$ in.  Formula (4) implies $a=q4+1$ when $p = 2$, where $4=2^2>2$.


What is the graph with $8$ vertices and $12$ edges that has the most spanning trees?

It is not too hard to search for it using SageMath. The graph you are looking for seems to be the Wagner graph.

It takes a couple of minutes to run, you can check it yourself here.


Is {a^n (a+b)^n | n>0} a Deterministic CFL?

You needn't determine the end of "first part".

Note $L$ is exactly the set of strings satisfying the following three constraints:

Its length is even.
It only contains $a$ and $b$.
The first $b$ appears in its latter half.

Constraints 1 and 2 are easy to check. To check constraint 3, the DPDA can push a symbol to its stack each time it reads a character until the first $b$ appears (excluding), and then pop a symbol each time it reads a character. Constraint 3 is satisfied if and only if the initial stack symbol is never read during the popping process.


Atomic multicast is a generalisation of atomic broadcast. In atomic multicast, there are $M \geq 1$ groups of processes $\Gamma = \{ G_1, G_2, \dots, G_M \}$, where $G_i$ is a non-empty group. The groups are usually defined to be non-overlapping or disjoint, that is, groups do not have processes in common. A message $m$ can be sent to one or more groups. The destination groups of a message $m$ are usually defined to be the groups inside the set $m.dst$, that is, m will be delivered by all processes inside the groups which are inside the set $m.dst$. Atomic broadcast is a special case of atomic multicast, where there is only one group which contains all processes.

To be more precise, let us more formally define the atomic multicast (AM) problem. An AM is a reliable multicast, which also requires a "total order" property to be satisfied. Let us first defined a reliable multicast.

A reliable multicast (RM) is defined in terms of two primitive operations, often denoted by R-multicast(m, m.dst) and R-deliver, where $m.dst$ is the set of groups to which $m$ is multicast. R-multicast is used to reliably multicast, that is, to send message $m$ to the groups in $m.dst$, and R-deliver is used to reliably deliver the message $m$ once it has been received by those same groups.

These primitive operations, R-multicast and R-deliver, and, in general, any algorithm which implements RM must satisfy 3 properties:

Validity: If a correct process multicasts $m$, then all correct processes that belong to a group of $m.dst$ deliver $m$
Uniform Agreement: If a process delivers a message m, then all correct processes that belong to a group of $m.dst$ deliver $m$
Uniform Integrity: A process $p$ delivers a message $m$ at most once and only if the group of $p$ is in $m.dst$ and some process has previously multicast $m$.

In addition to these 3 properties, the atomic multicast problem also requires the following property to be satisfied

Local total order: If processes $p$ and $q$ both deliver messages $m$ and $m'$ and $m.dst = {m'}.dst$, then $p$ delivers $m$ before $m'$ if and only if $q$ delivers $m$ before $m'$.

In other words, if the destination groups of the messages $m$ and $m'$ are the same and there are two processes which deliver both $m$ and $m'$, then they must deliver these messages in the same order (or in "total order").

In reality, there are other "total order" properties: for example, there is the "global total order" property. An atomic multicast problem defined in terms of the "global total order" property is different than the atomic multicast problem defined in terms of the "local total order" property. See section 2.2 of the paper "Fault-tolerant Genuine Atomic Multicast" by Carole Delporte-Gallet and Hugues Fauconnier for more details.

I stated that an atomic multicast is a generalization of an atomic broadcast. However, an atomic broadcast can actually be used to implement an atomic multicast. More specifically, to do that, we can atomically broadcast the messages and then only the groups inside $m.dst$ would atomically deliver $m$. However, this would send $m$ to all groups in the system, even though they may not be in $m.dst$. In other words, if we implemented an atomic multicast using the modified version of the atomic broadcast algorithm just explained, all groups and processes in the system would be involved. This implementation would be as costly as the implementation of an atomic broadcast algorithm. We want to avoid this!

A genuine atomic multicast algorithm is an algorithm which solves the atomic multicast problem where only the sender of the message $m$ and the processes in destination groups ($m.dst$) are "concerned" by (or involved in) the atomic multicast of the message $m$.

Thus the adjective "genuine" is associated with the algorithms which solve the atomic multicast problem and not with the problem itself.


If you want an algorithm that is always correct you can not do better, precisely because you have to look at all the values at least once (except if you find a $0$ somewhere, then you can immediately return that).
Otherwise, suppose your run your algorithm $A$ some input $I=[a_1,a_2,\ldots,a_n]$, and it returns a value $v\neq 0$ without looking at all numbers in $I$. Say it didn't look at $a_k$. Then we could just as well set $a_k=0$ and $A$ wouldn't know about it (because it didn't look at $a_k$). Thus $A$ will be wrong on this (modified) input.
That is of course assuming that setting $a_k = 0$ doesn't contradict some assumption you have about the data (for example it being sorted).


Can parameters be contra- or covariant in Python?

Here are some general thoughts on how contra- and co-variance issues affect programming in dynamically typed languages.

Covariance: If B is a subtype of B' then functions A $\rightarrow$ B form a subtype of A $\rightarrow$ B'.

Contrvariance: If A is a subtype of A' then functions A' $\rightarrow$ B form a subtype of A $\rightarrow$ B.

For example, if Auto is a subtype of Vehicle, then the contravariance rule says that a function that takes a Vehicle argument can be regarded as a function taking an Auto argument (because the Auto can be regarded as a Vehicle).  However, a function taking an Auto argument cannot be treated as a function that takes a Vehicle argument.  If you do, then sooner or later, you might pass it a non-Auto argument, say a Bicycle, and you would get a run-time error.

Whether the language is statically typed or dynamically typed makes little difference to the logic you use to design programs.  If the language is statically typed, the type checker would complain about the design flaws in your program that show up as type-mismatches.  If it is dynamically typed, you are likely to get a run-time type error such as "message not understood".  That is if you are lucky.  If you are unlucky, the problem would go unnoticed during testing, and the program would crash in the hands of the end-user.


Solving recurrence relation with different rules for odd and even n

When $n$ is odd, the recurrence can be unrolled:
$$
T(n) = T(n-1) + n = 2T\left(\frac{n-1}{2}\right) + (n-1)^2 + n.
$$
In total, we always have
$$
T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2).
$$
Applying the master theorem, we conclude that $T(n) = \Theta(n^2)$.


Compute unknown matrices that minimize a sum

I've found the answer. You can solve such problems using scipy.optimize.root which includes  Levenberg-Marquardt (LM) algorithm.


Why is the total number of atoms in the observable universe often considered as an upper bound for computational feasibility?

Let us assume an explicit range of the number of atoms in the universe to make sure that we are talking about the same thing.  It is estimated that there are between $10^{78}$ to $10^{82}$ atoms in the known, observable universe. In other words, it is a number between ten quadrillion vigintillion and one-hundred thousand quadrillion vigintillion atoms.

Is the number of atoms in the universe large enough?

The common unit of computing performance is one floating point operation per second (FLOPS, flops or flop/s).

How much is the total computing capacity worldwide today? According to a popular estimate, "computing capacity worldwide was probably around 2 x $10^{20}$ – 1.5 x $10^{21}$ FLOPS, at around the end of 2015".
Extrapolating that by a generous 50% yearly growth rate, the total computing capacity worldwide today, around the end of 2018 is less than 6 x $10^{21}$ FLOPS.
Suppose you can run the total computing capacity worldwide today continuously for 100 billion years (which is much longer the life span of our universe as commonly estimated by physicists), you would have done a whopping 6 x $10^{21}$ (seconds) x 3.1536 x $10^{19}$ (Flop/s) $\approx$ 2 x $10^{41}$ FLOPs.
Suppose everyone of about 7.6 billion people on the earth is enjoying the same computing journey and there are another 100 billion planets like earth, we would have done a total of 2 x $10^{41}$ x 7.6 x $10^9$ x $10^{14}$ $\approx$ 1.5 x $10^{65}$ FLOPs.
However, that number is still much less than a billionth of the number of atoms in the universe! If each FLOP would count as 1, we need much more computing device and time to count the number of atoms in the universe!

Even given the impossibly optimistic yearly doubling of computing capacity worldwide, we would still need tens of years before our total computing ability to be anywhere near the number of the atoms in the universe.

Why choosing the number of atoms in the universe?

As Rick Decker indicated in his comment, that number is about the easiest way to say a big but fathomable number just about right to convey the message of practical un-computability. The vivid image of an immensely large universe filled with one of the smallest particles brings immediate understanding of an otherwise unfathomably big number to all walks of people.

Another nice huge number, Google, $10^{100}$, is sort of void of concrete meaning.

Further Topics

Which project is the largest computing project that has been completed or is going on?

Does FLOP capture all kinds of computing power? For example, quantum computing?

Why is the number of atoms is a really very small number compared to the number of combinations that we have to deal with routinely in many practical computations?


k-means clustered data: how to label newly incoming data

This is not answerable without knowing something about the data itself and where it comes from and what it means.  But it sounds like you're trying to do something awfully dubious.

It sounds like you're trying to come up with labels for free, with a purely automated method.  That usually doesn't work.  There's no free lunch.  You'll need to obtain labels from some ground-truth source of data (e.g., human labelling; retrospective analysis); no amount of pure algorithms can replace that.  See Efficiently labelling training data in machine learning.

Using distance computations might give you a plausible approximation, or it might work poorly.  It all depends on the meaning and distribution of the data.  There will be some datasets where it will work well enough, and others where it will work terribly.  There is no single answer, and no special algorithm that eliminates the need to obtain known-correct labels for your data.


LSTM : What should I do if I am always getting an output too close to one value?

The usual starting point is that if the score is above 0.5, classify it as ham, otherwise as spam.  If most emails are ham, then it makes sense that most emails give you a score above 0.5, so you have not said anything that indicates there is a problem.
This approach assumes that the proportion of ham vs spam in the training set is the same as the proportion at test time.
If that doesn't work, one standard approach is to choose a threshold, and everything with a score above the threshold is treated as ham, everything below as spam.  A standard way to set a threshold is, after you've trained the LSTM, choose the optimal threshold based on the training set (i.e., that maximizes the accuracy on the training set, etc.), or on a validation set.


If you insist that the alternatives in a conditional statement be blocks, then the dangling-else ambiguity vanishes.

The dangling else ambiguity is something like this, where the else could be attached to either if:

if (a > 3) if (b > 4) do_something else do_something_else

However, if the statements in the conditional must be surrounded by braces, that is a syntax error. You would have to write either:

if (a > 3) { if (b > 4) { do_something } else { do_something_else } }

or

if (a > 3) { if (b > 4) { do_something } } else { do_something_else }

and both of those are quite explicit about which if the else belongs to.

In effect, a braced statement list (or block, as you refer to it in the context of a while statement) is a matched_statement, and you could just add it to the set of possibilities for that non-terminal. But that's only necessary if you want the braces to be optional; if you're going to require them, then you can scrap all that matched- and unmatched- statement stuff, and just use block in your if statement, just as with your while statement.

In any case, the problem is

Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE

Since matched_statement -> command (rule 20), the RBRACE in rule 21 induces a shift-reduce conflict. Assuming a command has just been reduced, the parser has to decide whether rule 20 should be applied (a reduce), which is necessary if the input is the start of rule 22, or whether the RBRACE should just be shifted, necessary if the input is the start of rule 21. And it can't know that by just looking at the RBRACE, since that is the same in both rules.

However, as I said, it doesn't matter. You don't need two different non-terminals for a block, and just using block will avoid the problem.


Is regex with backreference still able to be implemented by finite automata?

No, it doesn't. With backreferences, it is trivial to write a regex that matches exactly the standard textbook example of a non-regular language, $\{ a^nb^n \mid n \in \mathbb{N} \}$. A finite number of states can only distinguish between finitely many different prefixes in $a^*$, so it won't do.


Can undecidability theorems be detected by a machine?

Humans have found undecidability theorems. There is no reason known why an artificial intelligence cannot be built that matches what humans can do intelligence wise (although what is currently fashionable seems to be just pattern matching on a massive scale, which is not going to get you very far), therefore there is no reason known why an artificial intelligence, that is a machine, cannot find undecidability theorems.


Is my regular expression and finite automata diagram for this state table correct?

Your automaton accepts all words of even length, whereas your regular expression accepts all words of positive length. The most common way to express the language of all words of even length as a regular expression is $(\Sigma\Sigma)^*$, where $\Sigma$ is a common shortcut for an arbitrary letter of the alphabet (in your case, $\Sigma$ stands for $a+b$).


what are read/write operations involved in main memory, cache and processor?

Read is the same as load, and write is the same as store. Modify is a combination of both.


Evaluation functions of Minimax algorithm

An example for Expectimax (root node is a Max node):

(image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore)

changing the evaluation function changes the action taken.

For Minimax, since $f_1(s_i) \ge f_1(s_j) \implies f_2(s_i) \ge f_2(s_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):


Yes, this is a known thing. It's called bidirectional search.  It will find shortest paths in unweighted graphs and, in graphs of where every vertex has degree $d$, it will visit at most $2d^{\ell/2}=2\sqrt{d^\ell}$ vertices (where $\ell$ is the length of the shortest path), whereas ordinary BFS could visit up to $d^\ell$ vertices.


Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why?

The IEEE 754 standard defines exactly how floating-point arithmetic is performed. For many interesting theorems, you will need to examine the exact definition. For some less interesting ones, like a+b = b+a or ab = ba, all you need to know that IEEE 754 always calculates the exact result, rounded in a deterministic way. For non-theorems, like (a+b)+c = a+(b+c), which is false, all you need is a counterexample which is usually easy to find.


GCD binary representation time complexity

Assuming x <= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I.

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 <= I <= sqrt (x) and x itself.


Finding the closest visible vertex among line segments

I only noticed after posting that my first answer does not directly address your
specific question. So now my answer is in two parts.

(1) As suggested by @HEKTO, to find the closest segment,
you could first compute the Voronoi diagram:
CGAL 2D Segment Voronoi Diagrams.
Then next you need to perform point location within the (non-rectilinear) cells of the diagram.
That is also discussed, using "the segment Voronoi diagram hierarchy, a data structure suitable for fast nearest neighbor queries..."

CGAL figure.

(2) You specifically ask for the closest segment endpoint, which is not necessarily an endpoint of the closest segment:

Point $x$ is closer to segments $1,2,3,4$ than to the closest endpoint $y$.

For this you might need to look at
"visibility constrained Voronoi diagrams":

  Aurenhammer, Franz, Bing Su, Y-F. Xu, and Binhai Zhu. "A note on visibility-constrained Voronoi diagrams." Discrete applied mathematics 174 (2014): 52-56.
  Elsevier link.

I haven't studied this paper enough to be certain it solves your problem.
And perhaps there is a way to efficiently move from the closest segment to
the closest segment endpoint.


Multithreaded access to a persistent linked list data structure

Such list is intended to be immutable - the shared nodes will never be written to. There is no problem with several threads reading from the same memory location.


What happens internally when you remove an object from a treemap

I think there are two cases here

Java Collections implementation :
 In this case Java uses red black tree to keep the tree balanced and to maintain the order. Thus if you are removing a node in such a tree it will adjust itself without breaking anything and will form a perfect BST even after removal. Red black trees are self balancing trees so it will also arrange itself to maintain log(n) height where n is the number of nodes. Thus for sure you will not lose any data here.
Your custom implementation :
In this case you have to do all the painful things which I have explained above. However you have an option to maintain the order or to rebalance the tree as per your requirements.


Is the "Bidirectional Dijkstra" algorithm optimal?

When we talk about the "bidirectional Dijkstra" algorithm, we actually mean a family of similar algorithms which are implementations of a more abstract idea. All of these algorithms are optimal (produce an optimal solution). Some algorithms may work only under some assumptions on the input, for example only in the unweighted case, which is what the doubtful posts seem to have in mind.

More generally, algorithms usually come with correctness proofs. These proofs show that under certain conditions, the algorithm has certain guarantees. If these conditions don't hold, that the guarantees don't necessarily hold. When using an algorithm, check that the conditions that you know hold indeed imply the guarantees that you are looking for.


If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

It will be regular.

   Let $M$ be the syntactic monoid of $L$ and consider the monoid $M^{\operatorname{op}} \times M$ (where $M^{\operatorname{op}}$ is $M$ with multiplication flipped).


if we have a list of $n$ numbers we need $\log n$ bits

No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general.

If the numbers are all distinct, then $\log n \ge k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the complexity of radix sort is $\Theta(n \, k)$ where $n$ is the number of elements to sort and $k$ is the number of bits in each element.

To say that the complexity of radix sort is $O(n)$ means taking a fixed bit size for the numbers. This implies that for large enough $n$, there will be many duplicate values.

There is a general theorem that an array or list sorting method that works by comparing two elements at a time cannot run faster than $\Theta(n \log n)$ in the worst case. Radix sort doesn't work by comparing elements, but the same proof method works. Radix sort is a decision process to determine which permutation to apply to the array; there are $n!$ permutations of the array, and radix sort takes binary decisions, i.e. it decides whether to swap two elements or not at each stage. After $m$ binary decisions, radix sort can decide between $2^m$ permutations. To reach the $n!$ possible permutations, it is necessary that $m \ge \log (n!) = \Theta(n \log n)$.

An assumption in the proof that I did not write out above is that the algorithm must work in the case when the elements are distinct. If it is known a priori that the elements are not all distinct, then the number of potential permutations is less than the full $n!$. When sorting $k$-bit numbers, it is only possible to have $n$ distinct elements when $n \le 2^k$; in that case, the complexity of radix sort is indeed $\Omega(n \log n)$. For larger values of $n$, there must be collisions, which explains how radix sort can have a complexity that's less than $\Theta(n \log n)$ when $n \gt 2^k$.


Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely,
$$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$
The last inequality is a bit of algebra I leave to you.


Why there must be a relationship between user threads and kernel threads?

This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program.

When threading first became popular, most operating systems were Multi-processing OS's, but not "multithreaded" in the sense that the operating system provide support for multiple user code streams sharing the same user address space and allowing these threads to be scheduled separately by the OS.   Threading was a concept not dealt with by the OS at all.  The OS knew processes, what the processes did with the user mode time they were given was their business.

With User mode threading, support for threads was provided by a programming library and the thread scheduler was a subroutine in the user program itself.  The operating system would schedule the process to run and the process would schedule the threads within it.  There were problems with this model because an event on one thread that caused the OS to block the process effectively blocked all threads within that process.  This model only allowed the threads to run on a single CPU at a time, limiting parallelism.  This is the many to one mapping model listed in the book.  The single Kernel thread is the user process that the kernel schedules.

With Kernel threads, the OS becomes aware of the threads as separate schedulable entities that share the same address space.  The OS can then allow each thread to compete for CPU time separately with other threads in the system.  This allows the OS to schedule multiple threads from the same process on multiple CPUs at the same time. It also allows it run threads from a process where one thread is blocked, but the others have computable work to do.  In this case each user thread has a backing Kernel thread that is a schedulable entity.

The MUST relationship they are talking about is that even if you are using User threads there is an underlying Kernel thread that the OS can schedule. There MUST be a schedulable entity even if it's at the process level. So your first comment is correct.


If two languages are decidable, can one be mapping reducible to the other?

That is false. Consider for example the alphabet $\Sigma = \{0,1\}$ and the two languages $A = \emptyset$ and $B = \Sigma^*$.
Clearly both $A$ and $B$ are decidable (by the trivial algorithms that always reject and always acccept, respectively) but it is false that $A \le_m B$.


All 4 conditions must be satisfied at the same time.

Hold and Wait
Non-preemption of resources
Mutual Exclusion
Circular wait

In case of single instance of resources:

Cycle in resource allocation graph represents deadlock.

In case of multiple instance of resources:

Cycle in RAG doesn't mean deadlock.
You must check in the same way as you did. Let me write clear steps.

We need to identify a process, in the cycle, which can execute without any dependency and execute that.
Release the resources held by process.
Next check the process which has all the resources to execute and execute completely and release the resources held by it.
Keep doing till all the processes are executed.
If you can't execute all the processes this way, then there is deadlock.

Hope that helps!


Define a function $a(x)$ by primitive recursion as follows: $a(0) = s(0)$ and $a(x+1) = 0$. In particular, this function satisfies $a(0) = 1$ and $a(1) = 0$. Now we can define $E(x)$ by primitive recursion: $E(0) = 0$ and $E(x+1) = a(E(x))$. You can prove that $E(x)$ works by induction (left to you).


Treat the matrix as a weighted graph and use your favourite least-weight path algorithm.

To transform the matrix into a graph, say that the cost of going along the edge from $a$ to $b$ is the cost of visiting $b$. You'll need to separately add the cost of visiting the first node to the cost of any path the algorithm comes up with.


The language of the grammar $G$ presented here is regular and its corresponding regular expression is
$$r = (a \mid b)^*aa(a \mid b)^*.$$
Now, convert the regular expression to a minimal finite automaton and use this question to convert the automaton to an unambiguous regular grammar, which is always possible.
In the end you can get something like this:

$$
\begin{align}
S &\rightarrow aA \mid bS \\
A &\rightarrow aB \mid bS \mid a \\
B &\rightarrow aB \mid bB \mid \epsilon
\end{align}
$$

Proof that $\mathscr{L}(r) = \mathscr{L}(G)$: (1) Let $s \in \mathscr{L}(r)$, hence $s = x aa y$, where strings $x,y$ consist of characters $x_i, y_j \in \Sigma, i = [1..m], j = [1..n], m = |x|, n = |y|$.
There is a derivation of $s$:
$$S \rightarrow x_1S \rightarrow x_1x_2S \rightarrow ... \rightarrow x_1...x_mS = xS \rightarrow xSy_n \rightarrow xSy_{n-1}y_n\rightarrow ... \rightarrow xSy_1...y_n = xSy \rightarrow xaay.$$
Thus $s = xaay \in \mathscr{L}(G)$ and $\mathscr{L}(r) \subseteq \mathscr{L}(G)$.

(2) Let $s \in \mathscr{L}(G)$. This means there exists some derivation
$$S \rightarrow \alpha_1 \rightarrow \alpha_2 \rightarrow ... \rightarrow \alpha_p = s.$$
Observe that the only way to make the non-terminal $S$ disappear is to use the rule $S \rightarrow aa$ and it must be the last step of the derivation:
$$S \rightarrow \alpha_1 \rightarrow ... \rightarrow \alpha_{p-1} = xSy \rightarrow \alpha_p = s = xaay,$$
where $x,y$ are some strings of terminals.
Thus $s = xaay \in \mathscr{L}(r)$ and $\mathscr{L}(G) \subseteq \mathscr{L}(r)$, resulting in $\mathscr{L}(G) = \mathscr{L}(r)$. Qed.


What is a weighted or probabilistic automaton?

The setting you suggest is not clear enough to determine what kind of an automaton you are looking for.

A short explanation regarding the types of automata:

A weighted automaton is typically an automaton with a weight function on the edges (or states). Then, a run is assigned a weight according to the weight it traverses. There are many different semantics for the value of a run. These include the maximum/minimum weight, the sum, a discounted sum, an average, etc. Finally, nondeterminism is resolved with some semantics. Typically max/min.

The important thing is that a weighted automaton defines a function $f:\Sigma^*\to \mathbb{R}$, instead of a Boolean language (which can be thought of as a function $g:\Sigma^*\to \{0,1\}$).

Probabilistic automata can be thought of as a sort of weighted automata, but a distinction is usually made (mainly because weighted automata are often defined over a tropical semi-ring). In probabilistic automata, the "weights" (probabilities) are multiplied along a run, and the sum of the (accepting) runs is taken.

If you elaborate or demonstrate the scenario you are thinking of, perhaps I can modify the answer to suggest an appropriate model.


How does paxos algorithm handle partial failures of accept messages?

The paper's specification for the phase 2(b) of the algorithm, which is how an acceptor responds to an accept message is the following:

  If an acceptor receives an accept request for a proposal numbered n,
  it accepts the proposal unless it has already responded to a prepare
  request having a number greater than n.

This means that acceptors are allowed to accept multiple proposals (even with different values) in a single instance of Paxos, as long as they have not responded to a prepare request with a number greater than the number of the accept message. As a result, even after the last row of the example, a proposer could bring the system to an agreement, by making some of the nodes accept a different value.

For example, the proposer could send a subsequent prepare(6) message to nodes 1,2,5,6, followed by an accept(6, B) that reaches everyone, thus reaching a majority and concluding the consensus. The important thing to note is that after this point, it's impossible to form a majority with a different value, because any potential majority quorum would contain at least one node returning (6, B) during the prepare phase.


Is there a data structure for efficiently searching a string that contains a given substring?

You could append all of the $n$ strings together, and add an arbitrary character '\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new string to yield time complexity $O(nl+k)$ which is more efficient than your suggested $O(nl+nk)$.

Actually, you could still iterate with KMP for $O(nl+k)$ time, beceause the $k$ component is preprocessing the pattern you are trying to find. This only has to be done once, regardless of the number of strings you are checking.


Is there a standard recently-used algorithm based on time and usage count?

This concept is indeed known in data structures as self-adjusting/-organizing lists. Possible strategies include

move the accessed element to the front,
maintain a sorted list by (potentially degrading) counts, and
move the accessed element one step towards the front.

Many more strategies are possible; which is most suitable depends a lot on the specific situation.


Does KMP Algorithm handle finding multiple matches in overlapping cases?

This most likely is dependent on the implementation. The failure function is used when the matching of "next" character fails, thus falling back to a prefix of the pattern which is the longest proper suffix up to that point.

Now when we find a match, we are at a accepting state. This accepting state has no need to look at the "next" character because it accepts no more characters thus it should automatically fail at the next character. This is easier to see in a String Matching DFA. Note that this comparison is valid because KMP is based on a string matching DFA.

We can create a DFA for "ABCABC" (dotted lines are failure functions):

The accepting state automatically fails on whatever input is next, but should pick back up at state 3. So if you implement the failures correctly, it should continue to find the overlapping occurrences.

If you look at the worked examples of the failure function you can see the last state (accepting state) has the length of the longest suffix which is also a proper prefix. This is what you should use to "auto-fail" back to after finding a match. I believe this is also captured in the pseudocode for KMP, where it sets m and i:

  ...
    if i = length(W) then
      return m (or store/use occurrence)
      let m = m + i - T[i], i = T[i] (preparing for search next occurrence)
  ...

The return here should be removed if you want to find more than one match.


Show that some context free languages must contain more that one non-terminal

Consider the language $L=\{a^mb^{m+n}a^n\ |\ m,n\ge 1\}$. From the assumption that there is a single-nonterminal CFG $G$ for $L$, we can derive constraints which eventually lead to a contradiction.

$G$ is given by the (singleton) set $\{S\}$ of nonterminals, set $\{a,b\}$ of terminals, and some number of rules $S\to w_i$ for $w_i\in\{a,b,S\}^*$. There are some obvious conditions:

There must be some $i$ such that $w_i$ contains $a$.
There must be some $j$ such that $w_j$ contains $b$.
There must be some $k$ with $w_k\in\{a,b\}^*$.

Note that some of $i,j,k$ might coincide, but this does not matter. Now suppose that there is some $l$ such that $w_l$ contains more than one $S$, i.e. $w_l=xSySz$ for some $x,y,z$. Then
$S\to xSySz\to xxSySzySz\to\dots\to xxw_jyw_izyw_jz$ which contains a $b\dots a\dots b$ subsequence, i.e. we get a word outside $L$ (once any  additional $S$ which might occur inside $x,y,z$ are replaced with $w_k$).

So the rules in $G$ really can only be of the forms $S\to u_iSv_i$ or $S\to w_i$ with $u_i,v_i,w_i\in\{a,b\}^*$. Since we can only use one of the latter form when building a word, and we may need arbitrarily many $b$, we get

For some $i$, either $u_i$ or $v_i$ contains a $b$. We will assume wlog that it is $v_i$; the $u_i$ case is symmetric.

Suppose that there is also a $j$ such that $v_j$ contains $a$; then $S\to u_iSv_i\to u_ju_iSv_iv_j\to u_iu_ju_iSv_iv_jv_i$, which again contains a $b\dots a\dots b$ subsequence and takes us out of $L$. Therefore

$v_i\in b^*$ for all $i$.

But the words in $L$ all end with an $a$, so

$v_i=\epsilon$ for all $i$.

But then $G$ is a regular grammar and cannot generate a non-regular language like $L$.


Agda: Which part does this type introduce universe inconsistency?

The term you're applying ¬_ to is large: it quantifies over all M : Set and therefore has type Set 1. So instead of ¬_ : Set -> Set you need ¬_ : Set 1 -> Set 1.

A more general solution it to make ¬_ level polymorphic as in the standard library: you will be able to use this definition of negation across the board no matter how large the thing you're negating is.


How to simulate systems' unavailability?

Fix some probability distribution for failures and failure duration and sample from there. Maybe a Poisson distribution for failures and a normal distribution for repair times would make sense. Compare the results from your sampling with the real data to see whether things match.


Upper bound on the covering radius of a code

You need to show that every vector is at distance at most $n-k$ from a codeword. The code is the collection of all vectors $x$ satisfying $Ax = 0$, where $A$ is an $(n-k) \times n$ matrix, which without loss of generality has the form $A = \begin{bmatrix} I_{n-k} & B \end{bmatrix}$ (use Gaussian elimination, possibly permuting coordinates to avoid zero columns). Let $v$ be a completely arbitrary vector, and suppose that $Av = s$. Extend $s$ to a vector of length $n$ by adding zeroes at the end. Then $A(s + v) = 0$, i.e., $v + s$ is a codeword, which is at distance at most $|s| \leq n-k$ from $v$.


Where/when did Stephen Kleene first define the Kleene closure/star?

Kleene's classic paper on finite automata and regular expressions is

  Kleene, Stephen C.: "Representation of Events in Nerve Nets and Finite Automata". In Shannon, Claude E.; McCarthy, John. Automata Studies, Princeton University Press. pp. 3–42., 1956.

There seems to be a scan or recreation of that version of the paper at: http://www.dlsi.ua.es/~mlf/nnafmc/papers/kleene56representation.pdf.

But, as pointed out by @HendrickJan, the work seems to have been done about 5 years earlier.  The article starts with a note that says that "the material ... is drawn from Project RAND Research Memorandum RM-704 (15 Dec 1951, 101 pages) ... used by permission of the RAND Corporation ... supported by the RAND Corporation during the summer of 1951."  A scan of the RAND research memorandum is available for free from the RAND website: http://www.rand.org/pubs/research_memoranda/RM704.html.

"Regular events" are defined in Section 7 of both papers.  (page 46 of the 1951 memorandum and page 23 of the 1956 paper).  Interestingly, Kleene defines $*$, the closure operator, as a binary operator, rather than a unary operator as we do today.  This enables Kleene to avoid dealing with empty strings.  $E*F$ means the same thing it does today: "0 or more instances of E followed by F" but there is no way to say $E^*$ and have it include the empty string.


traverse direct graph with multiplicative edges

The fact that the weights are multiplicative is essentially irrelevant – you can always take logs, add the logs, then exponentiate. However, looking for the shortest simple path (i.e., no repeated vertices, so you're not whizzing round negative cycles) is an NP-hard problem when there are negative-weight cycles, as explained by Danny Pflughoeft on CS Theory SE. Essentially, longest path in a graph where all weights are non-negative becomes shortest path if you negate all the edge weights, but Hamiltonian path reduces easily to longest path.

You're now allowed to complain that I'm a complexity theorist, since you asked for an algorithm and I said "There's no fast one" as if that was the complete answer.

Wait, now I'm allowed to complain. You tagged your question "shortest-path" but you're actually looking for longest paths. That's straight-up NP-hard. Just give every edge weight $2$ and the longest simple path has weight $2^n$ if, and only if, the graph has a Hamiltonian cycle.


What is tight NSPACE complexity of $ALT\text{-}SPACE(a(n),s(n))$?

It's open, at least for the inclusion
$ALTSPACE(\alpha(n),\log n)\subseteq NSPACE(f(n))$ with $\Omega(\log n)\leq f(n)\leq \alpha(n)^{o(1)}$. According to Chandra, Kozen, and Stockmeyer, we know
$$DTIME(n^k)\subseteq ALTSPACE(n^{2k},\log n)\subseteq \mathsf{P}.$$

Therefore if it is true, then $\mathsf{P}\neq \mathsf{NPSPACE}$ which is not known to be true. On the other hand, rejecting it will yield $\mathsf{P}\neq \mathsf{NL}$, which is also not known to hold.


Better algorithm for determining if a vertex is on any cycle in a graph

You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.

Then you can check whether one neighbour can reach another.

Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).

I let you work out the details.


Here is an abstract definition of the concepts NP-hard and NP-complete. If $A,B$ are two decision problems, say that $A \leq B$ if there is a polytime reduction from $A$ to $B$, that is, if there exists a polytime function $f$ such that $x \in A$ iff $f(x) \in B$. Then:
$$
\begin{align*}
&\mathsf{NP\text{-}hard} = \{ B : A \leq B \text{ for all } A \in \mathsf{NP} \}, \\
&\mathsf{NP\text{-}complete} = \mathsf{NP\text{-}hard} \cap \mathsf{NP}.
\end{align*}
$$

Here is a different example. Consider the universe of all subsets of $\mathbb{N}$, ordered under $A \leq B$ if $A \subseteq B$. Let $\mathsf{X}$ consist of all subsets of some fixed set $X$. Define $\mathsf{X\text{-}hard}$ and $\mathsf{X\text{-}complete}$ just as above. You can check that
$$
\begin{align*}
&\mathsf{X\text{-}hard} = \{ S : S \supseteq X \}, \\
&\mathsf{X\text{-}complete} = \{ X \}.
\end{align*}
$$
In a similar way, NP-hardness is a lower bound on the difficulty, whereas NP-completeness is both a lower bound and an upper bound. In contrast to the second example above, there are many NP-complete problems, all of them having the same level of difficulty (two problems $A,B$ have the same level of difficulty if $A \leq B \leq A$).

Finally, here is a concrete problem which is NP-hard but not NP-complete: the halting problem.

The halting problem is NP-hard. Let $A$ be any computable decision problem, say computed by a Turing machine $M$ which always halts. Let $M'$ be the Turing machine which simulates $M$, halts if $M$ accepts, and runs into an infinite loop if $M$ rejects. Define a polytime function $f$ by $f(x) = (\langle M' \rangle,x)$. Then $x \in A$ iff $M$ accepts $x$ iff $M'$ halts on $x$ iff $f(x) \in \mathsf{HALT}$.

The halting problem is not in NP. The halting problem is not computable, and in particular not in NP.


Some machine instruction sets include instructions for which 'small' constants are part of the instruction, either explicitly or implicitly.  E.g the set of 'add' instructions can include 'add immediate', where the value to be added fills out the rest of the instruction bits.  In that case, the operation does not need to fetch the constant value from a separate location - it 'comes for free' during the 'add' instruction fetch.  Not all constants can be handled in this manner, but a lot of the more common constants can.

Something similar has been done in certain interpreters.  For example, the Pascal P-CODE interpreter implemented each instruction op-code as one byte, but all 128 of the positive byte values were interpreted as immediate loads - e.g if the next op-code was the value 0x40 (the 'space' character), then the value 0x40 was pushed onto the expression stack.  The Java Virtual Machine derives (at least conceptually) from the P-CODE interpreter, and may do the same thing.


If the speed of electrical charge hasn't changed, how have computers become faster?

if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.

  With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

You get erroneous conclusions because your initial hypothesis is wrong: you think that CPU speed is equivalent to the speed of the electrons in the CPU.

In fact, the CPU is some synchronous digital logic. The limit for its speed is that the output of a logical equation shall be stable within one clock period. With the logic implemented with transistors, the limit is mainly linked to the time required to make transistors switch. By reducing their channel size, we are able to make them switch faster. This is the main reason for improvement in max frequency of CPUs for 50 years. Today, we also modify the shape of the transistors to increase their switching speed, but, as far as I know, only Intel, Global Foundries and TSMC are able to create FinFETs today.

Yet, there are some other ways to improve the maximum clock speed of a CPU: if you split your logical equation into several smaller ones, you can make each step faster, and have a higher clock speed. You also need more clock periods to perform the same action, but, using pipelining techniques, you can make the rate of instructions per second follow your clock rate.

Today, the speed of electrons has become a limit: at 10GHz, an electric signal can't be propagated on more than 3cm. This is roughly the size of current processors. To avoid this issue, you may have several independent synchronous domains in your chip, reducing the constraints on signal propagation. But this is only one limiting factor, amongst transistor switching speed, heat dissipation, EMC, and probably others (but I'm not in the silicon foundry industry).


Does the databus size matter for determining the range of the memory addresses?

On most general purpose CPUs since the '70s, addresses are byte addresses.
This includes 6800, 680X0, PowerPC, x86, ARM, MIPS, SPARC, SuperH, Z80, PA-RISC...

There are sometimes exceptions with DSPs that are not meant for processing bytes. (example : Analog Devices SHARC)
Some small embedded CPUs may also have different addressing, or separate address spaces for instructions (example : Microsemi PIC)
Some CPU support address spaces where data is aliased and expanded. For example mapping each bit at a different byte address (example : Some ARMs)

The actual width of the data bus is not directly related to the CPU internal architecture, wether it is a 8bits, 16bits or 32bits CPU.

For example:

The MC68008 was a 16/32bits CPU with a 8 bits bus.
The G3/G4 PowerPCs (PPC603, MPC755, MPC7450...) are 32bits CPUs with a 64bits data bus.

With a 32bits CPU, aligned 32bits word adresses are 0000_0000, 0000_0004, 000_0008 ... to ... FFFF_FFF0, FFFF_FFF4, FFFF_FFF8, FFFF_FFFC.

Some CPUs can do unaligned accesses, usually slower than aligned ones. An example : x86.

In that case, you could access a 32bits value at address 0000_0001.


Could PRNGs make use of more internal state?

Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, [insert your favorite argument about why $2^{19937}$ is a somewhat large number here].


How to efficiently get frequency of subranges and update its values altogether?

Almost one year later... I tried to solve it today without looking my previous code and I got ACC'ed now. (ideone link)

Reading my question now, I've implemented what I called delta and rotate in a simpler way. I will try to illustrate.

This is how the segment tree for N = 5 looks like after build():

My node struct has:

int freq[9], i, lazy;

The i variable is the position circled in red in the picture, it will hold which position of the freq array contains the frequency for note 0 (which initially is zero). The lazy flag stores pending sums for children (both left and right), blue in the picture.

Now suppose first query for [1, 2]. The query() function will find nodes [1, 1] and [2, 2] and the resulting int fquery[9] array will have values [0,2,0,0,0,0,0,0,0]. The greatest() value then is 1. Ok, this is a simple search.

Now the function chord() will update those ranges by setting lazy += 1 and i -= 1:

Note that since those are leaf nodes, the lazy property does nothing. Also note that since i was decreased, there is no need to update freq[] array. This two things were done in the pre-order traversal of the recursive chord() function.

Now we update the freq[] array of the parents using the post-order traversal of the recursive chord() function by calling update(), this update function is just a merge of left and right child nodes:

These separation of pre-order and post-order traversal of the recursive call was the main point that I didn't understand last year. I was trying to update the parents out of the recursion track, and it caused me TLE.

Now suppose second query for [0, 4]. The query() function will find node [0, 4] and the resulting int fquery[9] array will have values [0,3,2,0,0,0,0,0,0]. The greatest() value then is 1.

Now the function chord() will set lazy += 1 and i -= 1:

Since we found the desired range in the root, this time we don't have post-order traversal.

Now suppose third query for [0, 2]. The query() function will find node [0, 2]. But, we can only reach a node if there is no pending sums. So, we need to resolve the lazy = 1 flag of node [0, 4]. This is what propagate() function does:

Note: the i value of node [0, 2] is 8.

And the resulting int fquery[9] array will have values [0,0,1,2,0,0,0,0,0]. The greatest() value then is 3.

Now the function chord() will set lazy += 3 and i -= 3:

As previously, we update the freq[] array of the parents using the post-order update():

To get the output after all queries, you just need to propagate() every node, doing so the leaf nodes will have the final values. You can check the show() function.

The output for this example will be: 5 6 6 2 2. (The first test case in the URI Online Judge).

Conclusion: The solution to the problem is a standard segment tree with lazy propagation with each node containing an int freq[9] array and an additional index starter holder.


Represent polynomial time complexity as linearythmic

You cannot "demonstrate" that a running time is $\Theta(n\log n)$ experimentally. All you can do is give evidence. Such evidence would be a constant $C$ such that for large $n$, $Cn\log n$ is a good approximation to the empirical running time.

You found the best polynomial approximation to your input. Since $Cn\log n$ is not a polynomial, this kind of approach cannot possibly give you the answer $Cn\log n$. If you want $Cn\log n$ to be a possible answer, you need to include such functions in the family of functions you are optimizing over.

Finally, to demonstrate that $Cn\log n$ is a better approximation that your polynomial approximation or a linear approximation, all you have to do is to compare the error in the approximation $Cn\log n$ to the errors in the other two options. Smallest error wins.


What is the difference between turing reductions and many-one reductions?

You got it backwards. Turing reductions are more general than many-one reduction. A many-one reduction is also a Turing reduction, but some Turing reductions are not many-one reductions. This is provably the case for (arbitrary) computable reductions. For example, there is a Turing reduction from the halting problem to its complement, but no such many-one reduction.

Completeness is defined with respect to many-one reductions since it allows making finer distinctions. Turing reductions, for example, don't allow us to distinguish the halting problem from its complement, or NP from coNP, but many-one reductions do.


Why doesn't everyone use microkernel-based operating systems?

Yes, you use microkernel operating systems. If you use a modern Intel CPU, it includes a copy of Minix which runs on a separate processor that is embedded in the processor that you think you have. Chances are also very good that at least a few of your peripherals use microkernel operating systems internally.

Moreover, you may not use any of these, but a lot of people use macOS, iOS, iPodOS, audioOS, watchOS, and tvOS. They are distinct (though in some cases related) operating systems implemented on top of the Mach microkernel. Or perhaps they use Horizon, the operating system of the Nintendo Switch.

Google seems to be going that way as well, with Zircon. ChromeOS and Android will probably be based on that at some point in the forseeable future.

Having said all that, the way the server world is going these days, especially in cloud computing, is guest operating systems running under hypervisors, which you can think of as related to the microkernel idea.


DFA for a strings whose every subsequence of length five has at least two zeroes

There is a standard technique for problems like this, where the language can be specified in the form

  All words over some alphabet $\Sigma$ where [some condition] is satisfied by all contiguous substrings of a fixed length, $k$.

The key idea here is to define a collection of states $s_i$ where $0\le i \le |\Sigma|^k$. Basically, you are using the states to "remember" the most recently-seen $k$ characters. These states will be part of the finite automaton we'll build for our language.

In what follows, I'll use a simpler language than yours, so that the FA will be sufficiently small to fit here and still be readable. Let
$$
L=\{w\in\{0, 1\}^*\mid \text{every length-3 substring of $w$ contains at least 2 zeros}\}
$$
We'll define states $s_0, s_1, \dotsc, s_7$ to represent the three most recently-seen characters. It's convenient to do this representation in lexicographic order, so $s_0=\mathtt{000}$, $s_1=\mathtt{001}$, $s_2=\mathtt{010}$, $s_3=\mathtt{011}$, $s_4=\mathtt{100}$, $s_5=\mathtt{101}$, $s_6=\mathtt{110}$, and $s_7=\mathtt{111}$. In other words, $s_N$ will correspond to the 3-bit binary representation of $N$.

Now we'll add some more states to get from the start state to the $s$'s. All it takes is to construct a complete tree (binary in this example) having the $s$ states as leaves, like this:

All of the states in the FA above will be accepting states, except for the darkened ones. The $p_i$ states are all accepting, since we haven't yet seen a length-3 string, so we haven't violated the condition that defines the language $L$ and only the patterns $\mathtt{011}, \mathtt{101}$, $\mathtt{110}$, and $\mathtt{111}$ violate the condition of the language. These correspond to states $s_3, s_5, s_6, s_7$. Once we've entered one of these states, we reject the input word, so we might as well merge these into a single "dead" state, $d$, from which there will be no exit.

We're almost done; all that remains is to fill in the transitions among the $s_i$. Because of the way we chose the representations of the states, that's an easy task. If we're in state $s_i$, having just seen characters $b_1b_2b_3$, on input $b$ we'll pass to the state $s_j$, corresponding to the new pattern $b_2b_3b$. If you think about it for a moment, you'll see that $\delta(s_i, 0) = s_j$ where $j\equiv 2i\pmod8$ and $\delta(s_i, 1) = s_j$ where $j\equiv 2i+1\pmod8$. Thus, we'll have the following $s$ transitions (recall that we merged states $s_3, s_5, s_6, s_7$ into a single dead state, $d$):
$$\begin{array}{c|cc}
    &  0  &  1 \\ \hline
s_0 & s_0 & s_1 \\
s_1 & s_2 &  d \\
s_2 & s_4 &  d \\
s_4 & s_0 & s_1 \\
 d  &  d  &  d
\end{array}$$

completing the construction. The nice feature of this technique is that it's almost completely mechanical: the only hard part is making the $s$ transitions. The downside is that it produces a pretty big FA. Even in this simple example, we wound up with a 12-state FA, and if we had needed to look at the five most recent characters, we'd have a FA with 31 states just for the $p$s. In fact, if we apply the standard technique for DFA minimization, we would find that the minimal-state DFA for this example language would require only 7 states, with 6 of them being final.


With your modeling, setting $i$, $i_r$, $i_g$ and $i_b$ to false for all vertices yields a solution of the SAT problem and this is not a solution of the graph coloring problem.

You need to add clauses to say that each vertex is blue or green or red, namely
$(i_r\vee i_g\vee i_b)$.
Then it becomes a 3-SAT problem.

Note that if a vertex is assigned to more then one color, then we can take any of its colors and obtain a 3-coloring.


Shortest distance from multiple points to one point

This is quite straightforward

Reverse the direction of each edge.
Apply single source shortest path algorithm with destination as the source.
Reverse the direction again. (Optional, only if you want to preserve the originality of graph)

Time Complexity-
With graph given as adjacency list, it takes $O(E+V)$ to reverse the directions of each edge. With graph given as adjacency matrix, it takes $\theta(V^2)$. Rest you can apply any single source shortest path algorithm like Dijkshtra.

Note that a graph with reverse edges of original one typically called as transpose of the original graph.


picking a word for pumping lemma for L = {a^n b^m c^n b^m a^n | m,n≥0}

If you want to apply the pumping lemma for regular languages, you can pick any word in the language whose length is no less than the pumping length. The same applies to the pumping lemma for context-free languages.

However, some of the words in your list may not be in the language.

$a^k c^k$ is in the language if and only if $k=0$.
$a^k b^m c^k $ is in the language if and only if $k=0$ and $m$ is even.
$b^mb^m$ is always in the language.
$b^m c^n b^m$ is in the language if and only if $n=0$.

Yes, a general approach is to check the balance between different symbols. Had the language been $\{a^nc^n\mid n\ge0\}$ or $\{a^n b^m c^n b^m\mid m,n\ge0\}$, you could select $a^kc^k$ towards a contradiction. You cannot if the language is $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$, since $a^kb^k$ is not a word in the language in the first place. For that language, you can choose $a^kc^ka^k$.

Specifically, here are all the words in $\{a^n b^m c^n b^m a^n \mid m,n\ge0\}$. Note that all of them start and end with the same symbol.

$$\begin{align}
&\epsilon,\\
&aca,\ a^2c^2a^2,\ a^3c^3a^3,\ a^4c^4a^4,\ \cdots\\
&bb,\ a^1bc^1ba^1,\ a^2bc^2ba^2,\ a^3bc^3ba^3,\ a^4bc^4ba^4, \cdots\\
&b^2b^2,\ a^1b^2c^1b^2a^1,\ a^2b^2c^2b^2a^2,\ a^3b^2c^3b^2a^3,\ a^4b^2c^4b^2a^4,\ \cdots\\
&b^3b^3,\ a^1b^3c^1b^3a^1,\ a^2b^3c^2b^3a^2,\ a^3b^3c^3b^3a^3,\ a^4b^3c^4b^3a^4,\ \cdots\\
&\vdots
\end{align}$$


Constructing a Divide and Conquer Algorithm

I believe you have misunderstood the question. The magical merge algorithm merges two lists of size $m$ in time $m^{1-\epsilon}$ for every possible $m$ (of course, such an algorithm is impossible). Since merging usually takes linear time $O(m)$, it is always better to replace it with the magical merge algorithm. You then get a different recurrence for your magical merge sort, and the running time should come out linear rather than $O(n\log n)$.


Selecting k "special" nodes in a graph such that the min distance is maximized?

Assuming $k$ is part of the input, the problem is NP-hard (by reduction from Independent Set; there's an independent set of size $k$ if and only if there's a way to solve your problem and achieve a minimum distance of 2 or greater).

Your current plan is known as the furthest-point heuristic.  It's a heuristic, because it won't necessarily give the optimal solution, though often it gives a solution that's reasonably good.  The furthest-point heuristic has been used, among other things, as a technique to select the initial values for $k$-means clustering.

If you want to find an exact solution, you could express this as an instance of of ILP or SAT.  Suppose we want to test whether min-distance $t$ is achievable.  For each variable $v$, you have a boolean variable $x_v$ that's 1 if $v$ is selected or 0 otherwise.  Now for each pair of nodes $u,v$ such that $d(u,v)<t$, you add a constraint saying that you cannot choose both $u$ and $v$ (e.g., the constraint $x_u+x_v \le 1$ or $(\neg x_u \lor \neg x_v)$).  Finally, you add a constraint that exactly $k$ nodes much be selected, and then you test whether these constraints are satisfiable.  If they are, min-distance $t$ is achievable.  Now repeat using binary search to find the largest $t$ such that the instance is satisfiable.


A megabyte is $2^{20}$ bytes.

The factor of $2$ is because we need to count both reads and writes.


How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?

It seems your confusion comes from the fact that Lemma 5.5 is a bit of a strange statement. In fact, we can replace Lemma 5.5 with the statement that for any problem $B$ such that $B_Y$ is a yes-instance of $B$ and $B_N$ is a no-instance of $B$ we have that $A\leq_{\mathrm{fpt}}B$. The proof of this adapted lemma is precisely the same as Lemma 5.5, only now we use $B_Y$ in the second bullet-point and $B_N$ is the third.

The crucial reason why this works is that we already know that $A$ is fixed parameter tractable. In a sense, this lemma shows that we learn nothing from a fpt-reduction from a problem we already know is fpt.

So, this lemma is in fact useless when trying to create a reduction from a problem we don't know is fpt, such as $k$-Clique.

When you try to apply Lemma 5.5 when $A$ is not fpt (or at least not known to be), you fail to satisfy part 3 of the definition of an fpt-reduction.


It really does not matter for the analysis. The key lemma for analyzing the splay-tree performance is the access lemma. It states that the amortized costs of a splay(x) operation is less than $1+3(r(t)-r(x))$, where $t$ is the root of the tree and $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$.  The weight of a subtree is the sum of the weights of its nodes. (Weights (positive) will be picked depending on the application of the lemma.) The potential function used is $\Phi(T)=\sum_{x \text{ node of } T} r(t)$.

The proof of the access lemma looks at the costs of a single zig/zig-zag/zig-zig etc.  operation. You get

Costs of a zig or zag  operations are $1+3(r_+(u) - r(u))$, where $r_+$ is the rang after the operation and $u$ is the node rotated upwards.
Costs of zig-zig /zig-zag and symmetric operations are $3(r_+(u) - r(u))$.

If you add these differences up for the operations performed in a single splay(x), you get a telescope sum and what remains is $1+3(r(t)-r(x))$.

If you change the order of the rotations you will get the same sum. The only difference is that now the ''+1'' comes from the first rotation and not from the last rotation. You could even do the zig rotation in the middle. All further (classical) analysis relies on the access lemma.

However, the reason why you perform the single rotation last, is that you do not know if the depth of the node is even or odd in advance.


Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }

PDA:

Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"

CFG:

$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$

Yea, thats everything in the CFG!


Which binary search trees have constant time rebalancing time at min/max?

Consider a constant set of $k$ insertions done directly at the max node, and the left and right sub-trees of the root node ($L$, $R$). If each rebalancing operation required only constant time, then only $O(\frac{log(n)}{k})$ of the inserted elements could be in $L$, since the maximal element is a leaf and the tree is balanced.

While this simple analysis is incorrect for non-constant $k$, the intuition still holds - if rebalancing after max (/min) insertion was always constant, repeated max (/min) insertions would cause $R$ (/$L$) to grow larger, and the tree could not be balanced.


What does it mean to prove that a set of binary integers is regular?

The question asks you to construct a DFA for the language

$$L = \{x \in \{0,1\}^* : x \text{ is the binary representation of an integer that is divisible by three}\}.$$

In other words, the DFA should accept a string if and only if this string is the binary representation of a number that is divisible by three.


The regular expression is correct.

You can use a trie-like structure, i.e.


Is any language that can express its own compiler Turing-complete?

The informal statement is not true, as shown by the following programming language.  Any string of, say, ASCII characters is a valid program and the meaning of every program is, "Output a program that just outputs a copy of its input." Thus, every program in this language is a compiler for the language but the language is not Turing-complete.

I'm not sure if your "computability theory version" is equivalent but it is also not true. By Kleene's second recursion theorem, for any coding of Turing machines, there is a TM that accepts its own coding and rejects all others.1 This machine is a counterexample to the proposition.
More concretely, we can achieve the result by choosing a coding. For example, let every odd number code the machine $M$ defined by "If my input is odd, accept it; otherwise, reject" and let the number $2x$ code the machine coded by $x$ in your own favourite coding scheme for Turing machines. $\langle M\rangle$ is in the language $L$ accepted by $M$ but $F_L$ is not Turing complete.

1 Kleene's second recursion theorem says that, for any enumeration $(\phi_i)_{i\geq 0}$ of the partial recursive functions (i.e., for any coding of programs as integers), and any partial recursive function $Q(x,y)$, there is an integer $p$ such that $\phi_p$ is the function that maps $y$ to $Q(p,y)$. So, in particular, let $Q$ be the function that accepts if $x=y$ and rejects otherwise. By the theorem, there is an integer $p$ that codes the program $\phi_p(y) = Q(p,y)$. That is, $\phi_p$ accepts its own coding $p$ and rejects all other inputs.


longest palindromic subsequence / substring and dynamic programming

Finding substring palindromes of maximum size can be solved in linear time in several ways. Right now come to my mind solutions using data structure such as:
- Manacher
- Palindromic Tree
- Binary search + (Hashing or suffix array) (not really linear but almost, $O(n \cdot \log n)$

If you let me use prewritten code to solve this problem I'd choose first option, is probably the faster and easy way, but personally I don't feel comfortable implementing Manacher from scratch.

I'll try to expand in the binary search + hashing solution.

First let's solve the subproblem: is it substring from a to b a palindrome? If you use rolling hash you will be able to determine hash of substring in O(1), so you can hash the string and it's reverse, and ask whether a substring and it's reversed counterpart match in hash. Notice that this solution is susceptible to fail due to hashing collisions, and one way to address this is using some more elaborated data structure such as suffix array.

After having such function, you can binary search over the length of the palindrome, this is: fix a length k, then go over every substring of length k and check whether it is or not a palindrome.

It has a problem, and it is that function is not monotone over k, but this happens because odd palindromes are not contained in even palindromes necessarily, and vice versa. To address this just run two binary search, first over even integers, and second one over odd integers.


How will Big O be with quantum computers?

Big-O has nothing to do with quantum computers. This should be obvious by the fact that Big-O notation was introduced in 1894, long before we had any knowledge of quantum theory … or computers for that matter.
Big-O is simply a convenient notation for classifying growth rates of functions. Big-O doesn't care how you interpret those functions.
So, the definition of Big-O will not change for quantum computers for the simple reason that its definition has nothing to do with computers.


There is no non-trivial complexity lower bound on any interesting problem. In particular, any algorithm not running in $O(|V|+|E|)$ is not known to be tight.
That said, you might be able to show a lower bound in some restricted model, say the decision tree model. For example, it might be possible that any comparison-based algorithm must make $\Omega(|E|+|V|\log|V|)$ comparisons in the worst case, though I am not aware of any such work on the single-source shortest path problem. See also the related question on cstheory.

Another avenue for obtaining conditional lower bounds is accepting some widely believed complexity assumption such as the Exponential Time Hypothesis or some version of the 3SUM hypothesis (whose strongest version was recently disproved by Grønlund and Pettie), though I'm not aware of any such work either in the present case.


Cycles in undirected graph: reducing to minimum

Consider the incidence matrix of your graph, which is the $E \times V$ matrix in which each row contains exactly two 1s, corresponding to the vertices constituting the given edge, and the rest of the entries are 0. We think of the entries as belonging to $\mathbb{Z}_2$. A set of edges is in the left kernel of the matrix iff it is an XOR of cycles; it is known as the cycle space of your graph. You can find a basis for the cycle basis by finding a basis for the left kernel (this is an exercise in linear algebra). The basis will contain $|E|-|V|+c$ elements, where $c$ is the number of connected components.

If you don't like XOR, you can instead orient your edges arbitrarily, and then use the orientation to form a matrix in which each row contains one $1$ entry and one $-1$ entry. The left kernel of the matrix over the integers is known as the integral cycle space (also described in the link above), and it consists of sums (with integer coefficients) of cycles, where now a cycle is a sum of edges, some of which are possibly negated so that the orientations match.


Is knapsack a Linear Programming problem?

The knapsack problem can be modelled as a mixed integer program (MIP) and the linear-programming relaxation of this model can be solved. The linear relaxation does not give a solution to the problem, but it will provide an upper bound to the solution of the knapsack problem (equivalent to a solution of the MIP) which helps the MIP solver in its quest to find the optimal integer solution.