Your problem is known as the Maximum coverage problem. If $S$ is a solution (a set of at most $k$ sets), then an element is covered if it belongs to $\cup_{X \in S} X$. You want to find a solution that maximizes the number of covered elements. This problem is known to be $\textrm{NP}$-hard (see below for a possible reduction) and admits a greedy approximation algorithm that will cover at least a $\left( 1- \frac{1}{e} \right)$-fraction of the elements covered by an optimal solution.

In addition, there is an easy reduction from $3$-SAT to your problem.

Consider an instance of $3$-SAT with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. You can obtain an instance of your problem by creating two sets $T_i$ and $F_i$ for each variable $x_i$. The sets are defined as follows:

$T_i = \{ j \mid x_i \in C_j \} \cup A_i$ ;
$F_i = \{ j \mid \overline{x_i} \in C_j \} \cup A_i$,

where $A_1, \dots, A_n$ are arbitrary pairwise-disjoint sets, each containing $m+1$ integers between $m+1$ and $m+n(m+1)$.

Deciding whether you can select $n$ sets such that their union has cardinality at least $m+n(m+1)$ is now equivalent to deciding whether the $3$-SAT formula is satisfiable.


Theoretical foundations of Divide and Conquer

A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak
 (in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)


Can this question be solved without knowing the Page Table Entry?

Your answer and calculation is correct, if we used a one-level page table.

However, a one-level page table is probably not a very likely implementation strategy, so it's more interesting to analyze the space consumption for a more plausible implementation strategy and work out what this would look like.

A two-level page table is probably a more likely implementation strategy.  The first 9 bits of the virtual address will be used as an index into the first-level table; they yield the entry in the second level.  The next 11 bits of the virtual address will be used as an index into the second-level table.

With this strategy, the size of the entire page table is $1+k$ pages, or $(1+k) \times 2^{12}$ bytes, where $k$ is the number of second-level table entries.  The worst case is $k=2^9$, in which case the entire page table takes up approximately $2^9 \times 2^{12} = 2^{21}$ bytes, i.e., 2 MB.  In other words, the worst case for a two-level page table is approximately the same as the size of a one-level page table.  However, the best case is much less.

I don't know how the books got 8 KB, but that seems clearly wrong, absent further assumptions; that would only allow 4096 entries in the entire page table, which clearly isn't enough to maintain a virtual-to-physical mapping for all of virtual memory.


This isn't probably a standard name, but in The Implementation of Functional Programming Languages in Section 16.2.4 Simon Peyton Jones calls it S'. It is defined as an optimization combinator

S (B x y) z = S' x y z

The following example is from the mentioned section. Consider

λx_n...λx_1.PQ

where P and Q are complicated expression that both use all the variables.
Eliminating lambda abstractions leads to quadratic increase of term sizes in n:

P Q
S P1 Q1
S (B S P2) Q2
S (B S (B (B S) P3)) Q3
S (B S (B (B S) (B (B (B S)) P4))) Q4

etc., where Pi and Qi are some terms. With the help of S' this gets only linear:

P Q
S P1 Q1
S' S P2 Q2
S (S' S) P3 Q3
S (S' (S' S)) P4 Q4


Strings which are not in a language generated by a Grammar

Read the question again, this time focus better. Take the grammar of the question, not the grammar in your mind.

I only need to see the rules for S to know that the strings in (3) are not part of the language.

S is the start symbol. Look at the rules for S. Think why I'm saying that aba and aa cannot possibly be in the language, without me having to look at any other rules whatsoever. You should be able to say "Looking at the rules for S, it is obvious that all strings in the language either xxx or yyy".


Presentation of context rules for the lambda-calculus

The two formulations are saying almost the same thing. Hankin's presentation has a symmetry rule ($\frac{M=N}{N=M}$), which is strange: it ends up defining the relation “$M$ reduces to $N$ or $N$ reduces to $M$”. That's unusual; usually, when a relation is written $=$, it's either explicitly defined to be an equivalence relation (with explicit or deducible rules for reflexivity symmetry and transitivity) or implicitly defined as the equivalence induced by the explicitly-given rules.

Giving separate rules for different context forms is equivalent to stating a single context rule and, separately, describing contexts. For example, for the pure lambda calculus, you can have a separate deduction rule for each way to decompose a term syntactically:
$$
\frac{M \to N}{M\,Z \to N\,Z} \qquad
\frac{M \to N}{Z\,M \to Z\,N} \qquad
\frac{M \to N}{\lambda x.M \to \lambda x.N}
$$
or you can have a single deduction rule plus a grammatical presentation of contexts:
$$
\frac{M \to N}{C[M] \to C[N]} \qquad
C ::= [] \mid C Z \mid Z C \mid \lambda x. C
$$
(In both cases, that's in addition to the beta rule.)

Other notions of reduction with more restrictive contexts can be expressed in two ways as well. For example, weak head reduction (which forbids reduction under lambda) can be given as the beta rule plus either
$$
\frac{M \to_H N}{M\,Z \to_H N\,Z} \qquad
\frac{M \to_H N}{Z\,M \to_H Z\,N}
$$
or
$$
\frac{M \to_H N}{C_H[M] \to_H C_H[N]} \qquad
C_H ::= [] \mid C_H Z \mid Z C_H
$$

If you're going to manipulate several different notions of reduction, the presentation in terms of contexts is more compact: there's a single context rule, and its formulation is usually obvious so it can be omitted, all that needs to be stated is the permitted contexts if some syntactically valid contexts disallow reduction.

If you're only ever going to use a single notion of reduction, introducing contexts requires some extra syntactic baggage. But this extra baggage has the advantage of making it clearer what's going on: it makes it easier to see where a reduction is happening in a context and where actual computation is happening. So it's a pedagogical trade-off.


Decidability of $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$

Hint: Let $s_0$ be the starting state, $F$ the set of accepting states, and $q$ the transition function. The mapping $k \mapsto q(s_0,a^k)$ is eventually periodic and can be determined explicitly. The predicate $(s,k) \mapsto q(s,b^k) \in F$ is eventually periodic and can be determined explicitly. So the predicate $k \mapsto q(q(s_0,a^k),b^k) \in F$ is eventually periodic and can be determined explicitly.

Similarly, you can check whether a DFA accepts some word of the form $a^k b^k c^k$. The fact that the languages $\{ a^k b^k \mid k \in \mathbb{N} \}$ and $\{ a^k b^k c^k \mid k \in \mathbb{N} \}$ are not regular doesn't play any role here.


What is an algorithm for minimizing the standard deviation of m sums summed from n summands? [with attempt]

No, your algorithm does not always produce the optimal solution.  When $m=2$, this is (at least as hard as) the Partition problem, which is NP-hard.  Wikipedia discusses the greedy algorithm and lists a counterexample which shows that your algorithm does not work.


Why is Uniform cost search called "uniform" cost search?

Truth to be told, I am not completely sure about my answer, so take it with a grain of salt:

Uniform Cost Search is just a variant of Best-First Search. Among other variants, take Breadth-First Search where $f(n)$ equals $d(n)$, its depth. This actually means that nodes are not treated uniformly since different paths to the same node might result very easily in different depths ---with different costs if the costs of the operators are different among them. Much the same happens with Depth-First Search where nodes are distinguished by the path that led to them.

What makes Uniform-Cost Search a uniform search is that nodes are distinguished just by $g(n)$ so that all paths that lead to a particular node n are considered to be equivalent (and they are indeed when seeking the optimal solution), with the first one (the one with the optimal value) being expanded, and all the others being discarded. In this regard, I would consider a number of Best-First Search variants, uniform such as $A^*$ where nodes are uniformly treated according to $f(n)=g(n)+h(n)$ with $h(n)$ being an admissible estimate.


How do you represent basic arithmetic using boolean function?

Hint: Use the standard reduction from CircuitSAT to SAT.  Equivalently: Use the Tseitin transform.

I assume you do know how to write a boolean circuit to test whether $x>y$.  If not, consult a textbook.


What is the algo used for Phonetic Search

Take a look at Soundex, Levenshtein edit distance, and related ideas.


Is floating point representation same as IEEE representation?

Well, not exactly. Floating point is more the abstract idea for "a fractional number" (of arbitrary magnitude) or rather "a number of varying precision.

On the other hand, IEEE(754) is a specific implementation of this idea. Other standards exist and all of them implement "floating point" numbers.


Finding edges with minimal weight sum, such that every simple cycle contain at least one edge

To turn some of my hints into an answer, the problem with your solution is that the DFS phase doesn't do anything to optimize the weight of the complement of the tree.  Here is a solution.

Let $G=(V,E)$ be your graph, $w : E\to \mathbb{Z}$ the weight function, which we extend linearly to $2^E$.  Call the set we are looking for $B$.

Property (1) implies that $C := E\setminus B$ is acyclic.  Otherwise, $C$ contains some cycle, contradicting the fact that $B\cap X\neq \emptyset$ for every cycle $X$ in $G$.

Property (2) implies that $w(C)$ should be as large as possible.  Since $w(B) = w(E) - w(C)$, minimizing $w(B)$ is just maximizing $w(C)$.

So, the algorithm is just to compute the maximum weight forest in $G$, and return the complement.  (The MWF isn't necessarily a spanning tree if there are negative weights.)


What is the difference in SMO algorithm for SVM and SMO for one class?

Both the papers attempt to develop Sequential Minimization Optimization (SMO) approaches for two kinds of Support Vector Machine (SVM) formulations, which include the conventional SVM and one-class SVM. The basic idea behind the SMO approach is to make the underlying SVM formulation scalable for larger datasets. This is a challenge since the SVM is a kernel method, and using it for large datasets requires computation of the kernel matrix whose size is of the order of the number of training samples. Thus, there is a high memory and computational requirement, moreover, issues pertaining to matrix stability may arise. In order to address this issue, the SMO approach adopts a method where pair-wise Lagrange multipliers are optimized instead of solving the entire Quadratic Programming Problem (QPP) as in the conventional case. The selection of the Lagrange multipliers may be based on heuristics. This (SMO) makes the approach (SVM) scalable for larger datasets, which is the underlying similarity between the use of SMO for SVM and one-class SVM.

In order to understand the difference between the two, it is important to understand the difference between the purpose of the SVM and one-class SVM, and subsequently the difference in their formulations (the optimization problem for each). This eventually translates into the difference in applying the SMO strategy for each of these cases.

The conventional SVM for binary classification aims to find a separating hyperplane $w^Tx+b=0$ with coefficients $w$ and bias $b$ for training data $x$ (and class labels $y$) with maximum margin ($\frac{1}{\|w\|_2}$) which is at least unit distance from points of the two classes which lie close to the separating hyperplane. This is achieved by the soft-margin formulation involving trade-off using positively constrained slack variables $\xi$ and user-defined parameter $C$ as below:

$\min_{w,b,\xi} \frac{1}{2}  \|w\|_2^2 + C \sum_i \xi_i$

subject to

$y^i (w^T x^i + b) + \xi_i\geq 1$,
$\xi_i \geq 0$

In  practice, the kernel trick is used to map the data to a high-dimensional kernel space $K$ that induces linear separability and the dual of the above formulation in terms of the Lagrange multipliers $\alpha$ is solved, which is given as

$\min_{\alpha} \frac{1}{2} \sum_i \sum_j y^i y^j K(x^i,x^j) \alpha_i \alpha_j - \sum_i \alpha_i$

subject to

$\sum_i \alpha_i y^i = 0, \alpha_i \geq 0$

On the other hand, in case of the one-class SVM, we would like to determine whether the test sample belongs to a specific class, determined by the training data (having $M$ samples), or not. Consequently, the one-class SVM is solved by

$\min_{w,b,\xi} \frac{1}{2} \|w\|_2^2 + \frac{1}{C M} \sum_i \xi_i - b$

subject to

$w^T x^i \geq (b - \xi_i)$,
$\xi_i \geq 0$

The dual for the one-class SVM is then given as

$\min_{\alpha} \frac{1}{2} \sum_i \sum_j  K(x^i,x^j) \alpha_i \alpha_j$

subject to

$0 \leq \alpha_i \leq \frac{1}{CM}, \sum_i \alpha_i = 1$

The derivation of the SMO algorithm follows the steps presented in the two papers, and the difference arises out of the nature of the two SVM formulations and their corresponding dual problems. Details of the derivation may be found in the respective papers, and newer strategies for selection of the Lagrange multipliers for optimization may also be found in literature.


Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

Since $\log n = O(n^{\epsilon})$ for an $\epsilon > 0$, if you can prove an approximation ratio of $O(\log n)$, then approximation ratios of $O(n^{\epsilon})$ (for any $\epsilon > 0$) immediately follow. You should always prove the best approximation ratio that you can, unless:

The best approximation ratio holds only in expectation, and some other approximation ratio holds with high probability.
You have several incomparable approximation ratios (this is more common in expressions involving more than one parameter).

That is, your worse guarantee needs to have some advantage over your better guarantee for you to report both.

Regarding practical performance, you are highlighting the fact that asymptotic performance can be misleading when it comes to evaluating algorithms in practice. The most well-known instance is probably "fast" matrix multiplication, which is usually slower than the trivial algorithm. Here you have two options:

Prove non-asymptotic guarantees on the approximation ratio, say $100\log n$ and $(2/\epsilon)n^{\epsilon}$. This allows you to obtain concrete guarantees for every $n$.
Do experiments. The experiments reveal the actual approximation ratio on the average. If you can fit your results to a nice function, you can say that empirically, the average approximation ratio is (say) $10\log n$, though in the worst case all you know is (say) $100\log n$. Experiments, however, are not so welcome in theoretical papers, unfortunately.


Terminology for a graph obtained from another by adding edges

If $H$ is made by adding only edges to $G$, then $G$ is a spanning subgraph of $H$. However, I'm not aware of any way of phrasing it that makes $H$ the subject of the sentence.


Is it a problem that "successful" machine learning algorithms have large VC dimension?

When left with a discrepancy between theory and data, data is king.  Theory is intended to be predictive -- to make predictions about the world -- but when it fails to predict what we actually observe and experience, when its predictions disagree with our experience, then there is obviously something lacking in the theory.

In this case, VC theory just isn't adequate to understand modern practice in machine learning.

Unfortunately, VC theory ignores methods like regularization.  Regularization is widely used in practice, so that's a pretty important gap in VC theory.  VC theory counts the number (size, dimension) of possible models, and treats all of them as "equally valid/likely".

When we train a model with regularization, we depart from that paradigm.  Regularization implicitly encodes the assumption that "all else being equal, simpler models (explanations) are more likely to be correct".  In other words, regularization is essentially an application of Occam's Razor.  In effect, regularization encodes some kind of prior on the distribution of likely models: not all models are equally likely; simpler models are more likely to be right.  Classical VC theory doesn't take that into account, and thus can't make useful predictions about the behavior of machine learning methods that use regularization.

Practitioners aren't "brushing aside" the theory.  Rather, VC dimension simply doesn't seem to be super-relevant to practice.  It is too limited.

It's still an open question to understand why techniques like deep learning work so well.  VC dimension was an early attempt to understand machine learning -- a powerful, beautiful, valiant attempt, one that may still be of some interest -- but ultimately one that doesn't seem to give us the whole picture, perhaps partly because it does not account for things like regularization and our priors on the model.


Designing DFA for accepting a string with a 1 in the tenth place from the right over an alphabet {0,1}

Your idea is correct.

Using the Myhill-Nerode theorem, it can be proven that the DFA for this language with the minimum number of states has $2^{10}=1024$ states.

Firstly, it is easy to see that the language is regular using an NFA of $11$ states. In the start state, have transitions for $0,1$ to itself, and a transition for $1$ to another state. From there, have a single common transition for $0,1$ from a given state to a new state each time. The last state is the final state. Thus, the string is accepted if $10$ characters earlier, the symbol was a $1$, which enabled the strings symbols to enter this "chain".

Your equivalent DFA will need to remember the each of the last $10$ symbols, which give $2^{10}$ combinations. It can be shown that every string using the given alphabet can be divided into $2^{10}$ equivalence classes over this language, one for each combination.

For any two strings over this alphabet, if they have the last $10$ symbols the same, then every string appended will result in either both being accepted by the language or both rejected by the language. They will be accepted if the first symbol is a $1$, and rejected otherwise. So, they are equivalent.

For any two strings whose last $10$ symbols are not the same, there must exist some position where they differ. By simply appending any string such that the resultant string has the symbols from this position at $10$ places from the end, one must be accepted and the other must be rejected. So, they cannot be equivalent.

If the number of symbols are less than $10$, prepend with leading zeroes, and the argument still holds.

Thus, we have $2^{10}$ equivalence classes, and by the Myhill-Nerode theorem, any DFA for this language must have at least $2^{10}$ states.


The output of an LCG with modulus $m$ is in range $[0\dots m-1]$. Hence the choice of $m=32767$ forbids the output to be $32767$. Perhaps the OP wants $m=32768$.

We want to compute $(a\cdot x+c)\bmod m$ for known constant integers $a$ $c$ $m$ on a system restricted to integers in $[0\dots32767]$ (or is it $[-32767\dots32767]$ or $[-32768\dots32767]$, but that only makes the problem easier).

We can compute $z=(x+y)\bmod m$ on this system, assuming $0\le x<m$ and $0\le y<m$, as

if (m-x > y) z = x+y; else z = y-(m-x);   when $0<m\le32767$, or as

if (32767-x >= y) z = x+y; else z = (y-(32767-x))-1;    when $m=32768$

From this primitive, it is easy to build $(a\cdot x)\bmod m$ by an addition chain, then $(a\cdot x+c)\bmod m$.


Is Bin-Packing with only 2 types of objects polynomial?

The problem can be solved in polynomial time. See A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths, An Asymptotically Exact Algorithm for the High Multiplicity Bin Packing Problem, or On the bin packing problem with a fixed number of object weights.


You can use Ogden's lemma. Choose the word $w = 0^p1^p0^p$ for large enough $p$, and mark the rightmost $0^p$. Ogden's lemma gives you a decomposition $w = uxyzv$ with $xz$ pumpable and containing at least one marked point. Since $xz$ contains a $0$, it can't contain a $1$, as otherwise $ux^2yz^2v \notin 0^*1^*0^*$. A simple case analysis now leads to a contradiction.


As a sparse matrix is mostly made of zeros.
Using a 2-dimensional array for all elements will be an inefficient way to represent such data as more than half of the array will be zeroes which is the reason for the increased time cost for finding bandwidth in your case.

In your case if you have a matrix $M$ of size $n * m$ then you'll be using a 2 dimensional array of size $n*m$. However it is not necessary to do so

A more efficient way will be to represent only the non zero elements using a 2 dimensional array with only three columns.e.g.

------------------------
 R    |   C    | V
------------------------
 0    |  0     |  1
------------------------
 0    |  3     |  4
------------------------
 1    |  5     |  11
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .

Where R is the row of the nonzero element,C is its column and V is its value in a given matrix.

In this way if you have $t$ nonzero elements in the Matrix then you need to access only $3*t$ elements in the above 2-dimensional array.

Now you can find the maximum and minimum values of C for any row R and can calculate their difference.

The largest difference you'll come across will be the bandwidth.I hope it makes sense.


Which sort algorithm to choose given two specific arrays?

I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime.

Suppose you have an algorithm which works very fast in that case. Then, given any array of integers, you can split it up into an array of even integers and an other of odd integers in linear time. You can then run your super fast algorithm on these arrays to sort your original array super fast as well. Thus, a faster algorithm for this case would lead to a faster algorithm in the general case. So you can safely choose to use whatever sorting algorithm is fastest in the general case (asymptotycally $O(n\log n)$).


How do I compute the address of the next element?

The offset should be 4 bytes, since 1 byte is 8 bits and 32 bits contain 4 bytes.


Lambda Calculus Prove Equality Excessive (Haskell-oriented)

Another way is to continue from where you got stuck, in the inductive step. You have:
$(Sx+n)−Sx=S(x+n)−Sx$

Now you can prove the following lemma by induction on y:

  Lemma:  $Sx - Sy = x - y$

  case 0:     $S(x) - S(0) = pred (S(x) - 0) = pred(S(x)) = x = x - 0$
  given $Sx - Sy = x - y$, case $Sy$

  $Sx - S(Sy) = pred (Sx - Sy) = pred (x - y) = x - Sy$

then you continue:

$(Sx+n)−Sx=S(x+n)−Sx =^{(lemma)} (x + n) - x =^{(IH)} n $


The idea is to decode the more frequently used symbols with less number of bits than the less used ones

So ur example means we can compress more if we decode A, B, C in less bits than E, D rather than equiprobable decoding
    By Huffman Coding A, B, C is represented by 2 bits (that's log 4); while D, E  take 3 bits (log 8)
    This way ur expected coding size is minimal (2.25* text length) because u expect ur file to have 0.25 of its characters as A,... 0.125 as E,...

I hope this makes it clear...


Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

First of all, there are many reduction concepts, but I assume you mean the polynomial reduction ($\le_p$).

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows:
\begin{align}
\Sigma_{0}^{p} & := P \\
\Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}
\end{align}

Let $A$ and $B$ be two languages over alphabets $\Sigma_A$ and $\Sigma_B$, respectively. Let $k \in \mathbb{N}_0$, $B \in \Sigma_{k}^{p}$ and $A \le_p B$. Since $A$ is polynomially reducible to $B$, there exists a function $f: \Sigma_A^\star \rightarrow \Sigma_B^\star$ (computable in polynomial time), such that $x \in A \Leftrightarrow f(x) \in B$. So we have an algorithm that decides $A$, which first transforms the input for $A$ to an input for $B$ using $f$, and then uses the algorithm for $B$ on the transformed instance. Therefore, $A$ is in $max\left\lbrace P, \Sigma_k^p \right\rbrace$.

If $k = 0$, $\Sigma_k^p = \Sigma_0^p = P$, then $A$ is also in $P = \Sigma_0^p$, since the transformation requires at most polynomial time and $B$ is in $P$.

If $k > 0$, the transformation is negligible and $A \in \Sigma_k^p$.


Why is the class of recursively enumerable languages not closed under complementation?

The statement you quote is an argument why the proof for showing that $\mathrm{R}$ (the set of recursive languages) is closed against complement does not work for $\mathrm{RE}$ (the set of recursively enumerable languages). It's not a proof of the reverse in itself -- another proof may still work!

The problem is that flipping the result of a TM only works if you get a result; $\mathrm{RE}$ promises only an acceptor, not a decider, which may loop if the input is not in the language. Therefore, you can not flip properly; all you'd get is a machine that says "no" of the word is not the language but loops otherwise. That's a machine for $\mathrm{co\text{-}RE}$, not $\mathrm{RE}$.

As for why $\mathrm{RE}$ is not closed against complement, the site you link contains all the answers; let me reiterate.

If $L$ and $\overline{L}$ are both semi-decidable, then both are decidable.
Hence, if $\mathrm{RE}$ was closed against complement, we'd have $\mathrm{R} = \mathrm{RE}$.
But we know that $\mathrm{R} \subsetneq \mathrm{RE}$ (by witness of the halting problem), so this can't be true.


There's a special reject state. Unlike a DFA, which is terminated by the definition when it reaches the end of the input, the machine decides when it stops, by jumping to one of the halting states (depending on exactly what definition you're using, there might be just one "halt" state, or there might be separate "accept" and "reject" states).
Almost. If the Turing machine accepts or rejects every input, then swapping accept and reject does indeed compute the complement, since you reject every string that you would have accepted, and vice-versa. However, we can also define languages in a weaker way, where the Turing machine accepts all strings in the language but, for a string not in the language, it might reject or it might just get stuck in an infinite loop (this is called "accepting", "recognizing" or "semi-deciding" a language).  In this case, just swapping the accept and reject states doesn't complement the language, since the inputs that loop forever don't reach either state, so you'd conclude that such a string is neither in the language nor it's complement, which can't possibly be right.
No. Normally, when defining space classes, we use a slightly different model.  When considering space-bounded computations, we Turing machines with three tapes: a read-only input tape, a write-only output tape and a read/write working tape. In this model, we only count the space used on the working tape. Because the input tape is read-only, you're not allowed to write to its input, unless you first copy the input to the working tape, in which case you're using space $n$.


Instructing operating system - Knowing it's functionalities

There are many possible OSes, each one with its own design philosophy and technical conventions. Here's a rough, but reasonably common design for an OS.
Beware that, for brevity, I had to simplify things a bit and cut some corners. OS design is a huge topic (we have whole university courses covering that!), so don't expect this to be comprehensive.

First, we exploit some hardware support to separate the OS from the userland processes. At any time, a bit register inside the CPU tells whether the CPU is executing in "OS mode" (AKA supervisor mode) or "user mode".

In OS mode, the CPU runs unrestricted, and can read/write everywhere in RAM, modify any register of the CPU, send messages to devices ("To video card: make pixel at 542,234 black"), and so on. In user mode, the CPU can only read/write at some RAM address, and use only some CPU registers. It can not directly send messages to devices.

Crucially, it can not flip the bit which turns the CPU into OS mode, otherwise a process could bypass the protection and pretend to be the OS.

Well, almost. The CPU actually allows executing a kind of magic instruction -- let's call it help! -- which precisely flips that bit and put the CPU in OS mode. There is a big catch, though: help! also acts as a jump to a special address in RAM where OS code lies. So, a process can not go in OS mode and still execute its code, but it has to jump to a specific location, causing a part of the OS code to be executed.

Usually, before asking help!, the process writes some numbers in the CPU registers.

After help! is called, the OS reads those CPU registers, and interprets those numbers as a request from the process. For example, if in register r1 there is number 0, this could be a request to change a pixel in the screen (the pixel having coordinates in registers r2 and r3 and the new color in r4).
The OS then runs the code to ask the video card to change that pixel. Since every card likely requires a different message to be sent for that, the OS first calls a device driver with an hardware-independent message (color pixed X,Y as C) and that driver will then craft and send the message to the video card. Note that the driver is run in OS mode -- it is a component of the OS (in this basic design, at least).

If instead register r1 there is number 1, this could request a file to be opened (the file name being specified by r2). This could involve asking the disk diver to access the disk.

And so on. When the OS is done, it flips the CPU mode back to "user mode" and jumps to the process code, so that it can continue.

There are usually many possible requests from a process to the OS, usually specified by an ABI (application binary interface) which describes what registers to write and with what. Sometimes there's no public ABI, but programmers are supposed to call instead a usermode library, typically written in the C programming language. That library has a public API (in C), and will provide a bridge from that to the internal OS unpublished ABI.

There requests are known as "system calls" or "syscalls", by the way.

If you want to do a syscall in python, without relying on absolutely any library, you can not. This is because bare python does not give you a way to control the registers, or to run the help! instruction. Python is not special here, bare C also does not allow that, as with most programming languages.

Usually, though, one exploits some library. Or, if one really wants to go low-level, one can write a small module directly in assembly, and then call that from C or python (or anything else). That could require to use a "foreign function interface", so to link the assembly module with the language. In C it's usually very easy to do, since the language is low level. In python, calling assembly could be harder to do, but it's surely doable.

I strongly recommend you try to read an OS textbook. It should cover these topic in much more detail than we can do here.


It stands for "given by" or "defined by". The function $g \circ f$ is a function from $A$ to $C$ which maps $a$ to $g(f(a))$.


Finding a kernel for d-Bounded degree deletion

Reduction Rule 1. Let $V$ be the set of vertices which are isolated. Convert the instance from $I = (G,k,d)$ to $I^{'} = (G -V, k,d)$. If $I^{'}$ is a yes instance, then so is $I$, because adding back the isolated vertices do not add on to the degree of other vertices. And isolated vertices have already have degree 0 ($\le d$ as $d \ge 0$). And if $I$ is a yes instance so is $I^{'}$, as $G-V$ is a sub-graph of $G$, and $k$ and $d$ remain same across the two instances.
Reduction Rule 2. If a vertex $v$ has degree $\ge k+d+1$ then it has to be kept in the deletion set. Otherwise $k+1$ of its neighbours have to be kept in the deletion set. Which cannot be done, as maximum size of deletion set is $k$. Thus after this reduction all vertices will have degree $\le k+d$.
Reduction Rule 3 If there are two vertices $v$ and $w$, such that degree of both of them is $\le d$. Then the edge $vw$ can be removed converting the instance from $I = (G, k,d)$ to $I^{'} = (G-\{vw\}, k,d)$. If $I$ is a yes instance so is $I^{'}$ as $G-\{vw\}$ is a sub-graph of $G$, with $k$ and $d$ remaining same across the instances. And if $I^{'}$ is a yes instance so is $I$, as adding back $vw$ can make the degree of $v$ and $w$ at most $d$ (as they initially had degree $\le d$).
Rule $1$ might be applied after applying Rule $3$ as well.
Now considering a graph where vertices with degree $\le d$ don't share an edge, no vertex is isolated and and all vertices have degree $\le k+d$ (ie. none of the above rules applied). Let $A$ be the set of vertices with degree $\le d$ and let $B$ be the set of vertices with degree $> d$. We can argue that $|B| \le k(k+d) +k$, otherwise the output is no. Because if $|B| > k(k+d) +k$, then as most $k$ elements will be chose from $B$ for the deletion set, and  $ > k(k+d)$ elements will be left (in $B$). And as each of them has degree $> d$, they each have at least one edge going into the deletion set. But the deletion set can only accommodate $k(k+d)$ edges. Also as each vertex in $A$ has at least one neighbor (and all of them in $B$), the maximum number of vertices in $A$, will be bounded as $|A| \le |B|(k+d)  \le (k(k+d)+k)(k+d) = k(k+d)(k+d+1)$.
So $|A| + |B| \le k(k+d) + k(k+d)(k+d+1) = k(k+d)(k+d+2)$.


Largest possible cost of a shortest path in which every edge's length is either -1, 0, or 1

a shortest path between any two nodes has at most n - 1 edges

This is only true for simple paths (paths with no repeat nodes). If there is a negative-cost cycle, you can take the cycle multiple times to get a shorter path.


Word Frequency with Ordering in O(n) Complexity

I suggest a variation of distribution counting:

Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say maxWordCound . -- $O(n)$
Initialize an array of size maxWordCount. Entry type are lists of strings. -- $O(n)$, since the count can't be higher.
Traverse the trie and for each node add the corresponding string to the array entry indicated by the count. -- $O(n)$, since the total length of strings is bounded by $n$.
Traverse the array in descending order and output the desired number of strings. -- $O(n)$, since that is a bound on both the size of and the amount of data in the array.

You can probably replace the trie by other data structures in the first phase.


how to verify permutation generated in constant amortized time?

For a number $m$, let $\alpha(m) = \max \{ k : k! | m \}$. This sequence starts at $\infty,1,2,1,2,1,3,\ldots$. I claim that in iteration $t$ of the algorithm (where $1 \leq t \leq n!-1$), we have $n-1-k = \alpha(t)$. The average value of $\alpha(m)$ is roughly
$$
\left(1 - \frac{1}{2}\right) 1 + \left(\frac{1}{2} - \frac{1}{6}\right) 2 + \left(\frac{1}{6} - \frac{1}{24}\right) 3 + \cdots = \\
1 + \frac{1}{2} + \frac{1}{6} + \cdots = e-1.
$$
Since the running time of each step of the algorithm is proportional to $n-1-k$, we get that the algorithm runs in constant amortized time.

It remains to prove the claim $n-1-k = \alpha(t)$, which I leave to the OP.


Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution

As @YuvalFilmus suggests, these distributions are very close to being geometric. They aren't geometric, since they're bounded, which is what threw me off, but think about it this way:

A geometric distribution corresponds to the number of Bernouli trials up to and including a first success (in some formulations: not including the first success). The distribution parameter p is the probability of succeeding in each individual experiment. Now,

Our first "experiment" involves sampling the most significant bit (or byte): Will it be 0, or something else? A 0 is a success, something else is a failure.
Our second "experiment" is the same, but for the second-most-significant bit (or byte).
and so on.

In a geometric distribution proper, experiments never cease until the first success. In our case, $k$ experiments are conducted, and if you've failed them all then you're simply at 0, with probability $2^{-k}$.


Use any rolling hash, e.g., the Rabin-karp rolling hash, Buzhash, or CRC.  See also the following resources:

additive hash function
Can ropes (AVL trees) be interned?
https://crypto.stackexchange.com/q/17935/351
https://crypto.stackexchange.com/q/11420/351
the answers to https://crypto.stackexchange.com/q/1558/351


What is the point of the "check" array in a triple-array trie?

It is a bit confusing. Suppose the alphabet has size $\Sigma$.

Basically the idea is that instead of allocating each state an entire block of $\Sigma$ elements in next[] to hold the target states for each possible input character, most of which would just hold a special "this transition is invalid" sentinel value since there are typically only a few valid transitions from each state, check[] lets us "overlap" these blocks of $\Sigma$ elements, and thereby save space, provided there are no "collisions" -- that is, elements in next[] that correspond to valid transitions from more than one state.

A crucial piece of information that seems to be missing from the article (I only read down to the beginning of the next section, "Double-array Tree") is that initially all check[] values must have some special "no current owner" sentinel value (which in practice would be something like -1).

Think of each element in next[] as a resource slot, which can be either unallocated (as it is initially), or allocated to exactly one source state: check[i] tells you which source state the i-th element is allocated to (or if it is unallocated). The rule is: If a source state s does not own the slot in next[] that corresponds to the transition on some character c, then there is no valid transition from state s on character c. Specifically, check[base[s] + c] != s, which literally means "State s does not own slot base[s] + c in next[]", also implies "State s has no transition on character c".

In this way, all the elements of next[] that would have been set to a "this transition is invalid" sentinel value in the original every-state-gets-its-own-block-of-$\Sigma$-elements-in-next[]-to-itself scheme become available to be used by some other source state. If some such element, say at position i, is later needed by some other state s, then check[i] will be set to s at that time.

Example

First let's initialise the triple-array trie data structure.

Suppose the alphabet is the digits 0-9, the states range from 0-49, and we have the following transitions for state 17, to which we allocate the block of 10 elements starting at position 20 in next[]:

Transitions from state 17
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     3     |     40     |      23     |
|     5     |      6     |      25     |
|     8     |     13     |      28     |

After adding this information to the triple-array trie, base[17] = 20, next[23] = 40, next[25] = 6 and next[28] = 13, and check[23], check[25] and check[28] are all set to 17, with every other element in check[] remaining at its initial value of -1.

Now suppose we that we have the following transitions for state 35, to which we try to allocate the overlapping block of 10 elements starting at position 22 in next[]:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      24     |
|     3     |     33     |      25     | <-- COLLISION

There is a problem, since next[25] is needed by both source states. We detect this by noticing that check[25] != -1. In this case, either state 17's or state 35's range of slots in next[] has to be reallocated somehow. Let's reallocate state 35's range. First, undo the allocation already done (set check[24] back to -1; it is not necessary or helpful to change next[24] to anything, since there is no meaning attached to the value of next[i] when check[i] == -1). Now we will try to reallocate state 25's slot range to start at position 24 in next[]. (Why 24? It's just a value that I know will work. In practice, you would probably need to just keep trying different starting points until one worked, and there is no guarantee that any will work.) Now it looks like this:

Transitions from state 35
| Character | Next state | next[] slot |
|-----------+------------+-------------|
|     2     |     10     |      26     |
|     3     |     33     |      27     |

And there will be no collisions. So after adding the information for states 17 and 25 to the data structure, we will have base[17] = 20, base[35] = 24, and next[] and check[] look like this:

|  i  | next[i] | check[i] |
|-----+---------+----------|
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
| 20  |don'tcare|    -1    |
| 21  |don'tcare|    -1    |
| 22  |don'tcare|    -1    |
| 23  |   40    |    17    |
| 24  |don'tcare|    -1    |
| 25  |    6    |    17    |
| 26  |   10    |    25    |
| 27  |   33    |    25    |
| 28  |   13    |    17    |
| 29  |don'tcare|    -1    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |
|  .  |    .    |     .    |

Now let's try some queries.

Is there a transition from state 17 on character 5? First see if state 17 owns the relevant entry in next[]: check[base[17] + 5] = check[25] = 17, so it does (and the destination state is then given by next[25] = 6).
Is there a transition from state 35 on character 1? check[base[35] + 1] = check[25] = 17 != 35, so state 35 does not own this entry in next[] => there is no transition from state 35 on character 1.


What does one mean by addressing capability of a microprocessor?

It means that the CPU can access 16MB of memory directly, since each memory address is 24 bits long. This is although the registers are only 16 bits long (the trick is the segment registers).


Closure of CFL against right-quotient with regular languages

Imagine you have a pushdown automaton (PDA) $X$ for $A$ and a DFA $Y$ for $B$.

You want to build a PDA $Z$ for $A/B$. You can do as follows:
the states $Q_Z$ of $Z$ are $Q_X\times Q_Y$. There are two phases:

Phase 1: You just read the input word and advance in $X$, states of $Y$ are ignored. This corresponds to the word $w$ of your language.

Phase 2: When you reach the end of $w$, you are allowed to perform $\epsilon$-transitions in order to reach an accepting state of $X\times Y$. So you guess a word $x$ that will continue to advance in $X$ and start to advance in $Y$, and that has to reach acceptance in both automata simultaneously. If there is an accepting run of this automaton, then the input word $w$ is in $A/B$ since you guessed the witness $x$ (and vice-versa, if $x$ exists, then it can be guessed by your automaton $Z$).

The reason why $B$ has to be regular instead of CFL is that you cannot manage two stacks at the same time, if you want to stay CFL.


I think you are referring to Hamming Distance. See http://en.wikipedia.org/wiki/Hamming_distance.

As for a game, having the extra condition that intermediate modifications must be real words is the Word Ladder. See http://en.wikipedia.org/wiki/Word_ladder.


How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?

The normal way to tell is through measurement: we try different choices for the threshold, benchmark each one, and choose the best.  This can be tricky, as the best threshold might vary from computer to computer (depending on, e.g., the relative speeds of CPU vs RAM, the size of various caches, and so on).  So, a plausible approach might be to benchmark on multiple different platforms and then choose one threshold that seems to do ok on most of them.

Asymptotic running time analysis probably won't be very helpful, because the constants matter a lot; and because the cache/memory hierarchy probably matters a lot, and standard running time analysis doesn't model the memory hierarchy very well.


Let  $\gamma_{ij},\delta_{ij}$ be the number of characters $\sigma_j$ in $\gamma_i,\delta_i$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $a_1,\ldots,a_N,b_1,\ldots,b_N$ such that for all $j \in \{1,\ldots,K\}$,
$$
\sum_{i=1}^N a_i \gamma_{ij} = \sum_{i=1}^N b_i \delta_{ij}.
$$

While integer programming is hard in the general case, in this case we can solve it using linear programming in polynomial time. I claim that the program above has a solution in non-negative integers iff it has a solution in non-negative reals. One direction is obvious. In the other direction, suppose that the linear program corresponding to the integer program above (replacing non-negative integers with non-negative reals) is feasible. Then there is a solution for the program above in the non-negative rationals (every vertex of the polytope would do). Multiplying this solution by a common denominator, we obtain a solution of the original integer program.


Avoiding loops in Bellman-Ford algorithm

As far as we know, you can't.  The problem of finding the shortest simple path in a graph is NP-hard; it is equivalent to the problem of finding the longest simple path (just negate all edge lengths), which is at least as hard as Hamiltonian path, which is NP-hard.  Therefore you shouldn't any simple modification to Bellman-Ford to yield an efficient algorithm for this problem; best guess right now is that no such algorithm exists.

See also https://cstheory.stackexchange.com/q/17462/5038 and https://en.wikipedia.org/wiki/Longest_path_problem.  According to Wikipedia, the longest path problem is fixed-parameter tractable and can be solved in time exponential in the length of the longest path and linear in the size of the graph, which also applies to your problem as well.


Two increasing functions from the set of positive integers to the set of positive integers such that neither f (n) is O(g(n)) nor g(n) is O(f (n))


Removing and reinserting elements to minimally mimic a changeset

Hint #1:

   Suppose you are only given the final configuration of the stack (not the changeset that led to it).  Could you find any sequence of moves that would lead to that configuration?  Could you find a sequence of moves that would lead to that configuration, and that makes at most one move per block?

Hint #2:

   Where does block 1 go to?  Where does block 2 go to?


Linear time multiplication on RAM machine?

The page is not fooling you. I'll refer you to the original paper, but accordingly they show the following:

  Theorem 6.1 There exists an SMM which performs integer-multiplication in linear time, i.e. there is a constant $c$ such that any $2N$-bit input is read as the concatenation of two $N$-bit integers $x$, $y$, and after at most $cN$ many steps their product $z=xy$ is output in binary representation.

It is a rather detailed paper which would be silly to write up all here. See below.

Schönhage, A. (1980). Storage Modification Machines. SIAM Journal on Computing, 9(3), 490-508. https://doi.org/10.1137/0209036


Why does RAID-5 require an additional disk for parity blocks?

I think you've misunderstood what the parity data is. They're not parity checks, so it's not true that "each parity block is specific to each disc it belongs to." The parity data is to allow recovery from a failed disc.

Let's go back to RAID-4 for a second, and assume we have three discs: discs $0$ and  $1$ are data and disc $2$ is parity. "Parity" means that the $b$th block of disc $2$ is the xor of the $b$th blocks of discs $0$ and $1$. The point is that, if any single disc fails, we can recover its data because the $b$th block of any disc is the xor of the $b$th block on the other two discs. For this to work, it's crucial that the parity data is on a separate discs. If you only had two discs and put the parity data on those discs (e.g., each disc was two-thirds data blocks and one-third parity blocks) then the failure of a single drive would destroy some blocks and their corresponding parity data, so you'd be unable to recover the data using just what was left on the remaining disc.

RAID-5 is the same idea except that, instead of putting all the parity data on the last disc, it's spread across all the discs. So, for a three-disc set-up, a third of the blocks would have parity data on disc $2$, a third on disc $1$ and a third on disc $0$.

The point of using RAID-5 rather than RAID-4 is that every time you write data, the corresponding parity block must be updated. If all parity data is on the same disc, that disc will be written to much more than the other discs ($k$ times as much, in a $k$-disc sytem), so it will fail faster. Spreading the parity data across the discs evens out the wear on them.


Time Complexity of k-clique problem with fixed k

A polynomial algorithm does exist for finding whether a graph contains a triangle. For one, you can go over all triplets $x,y,z$ of vertices, and check if the graph contains the triangle $\{x,y\},\{y,z\},\{x,z\}$. This algorithm takes $O(n^3)$. Surprisingly, there is a faster algorithm: take the adjacency matrix $A$ of the graph, and compute the trace of the matrix $A^3$. The graph contains a triangle iff the trace is positive. This algorithm takes $O(n^\omega)$, where $\omega < 2.373$ is the exponent of matrix multiplication.


Alex Aiken's Coursera course on compilers is very nice. I suggest to take it
and do all exercises. Another interesting looking online course can be found here, although I have not checked it out in detail (I would be interested in opinions about it).

As to books, here are a couple.

Modern Compiler Implementation in Java (second edition) by Andrew
Appel and Jens Palsberg.
Engineering a Compiler, by Keith Cooper, Linda Torczon.
Basics of Compiler Design by Torben Mogensen. It's free.


Supporting data structures for SAT local search

The needed data structure is an occur list, a list for each variable containing the clauses the variable occurs in.  These lists are built once, when the CNF is first read.   They are used in steps 3 and 5 below to avoid scanning the whole CNF formula to count satisfied clauses.

A better algorithm than flipping every variable is:

Make a list of only the variables that occur in the unsatisfied clauses.
Choose a variable $x$ from this list.
Count how many clauses that contain $x$ are satisfied.
Flip $x$.
Count how many clauses that contain $x$ are satisfied.
Unflip $x$.
Subtract the result of step 3 from step 5 and record it for $x$.
Repeat steps 2-7 for the rest of the variables found in step 1.
Flip the variable with the highest number recorded in step 7.

A reference for the data structure (often also known as an adjacency list) is for example Lynce and Marques-Silva, Efficient Data Structures for Backtracking SAT solvers, 2004.


Reducing "multiple satisfiability" to normal SAT

CNF-SAT can be reduced to QUADRUPLE-SAT by adding two new variables, $x_1$ and $x_2$, and adding the following CNF clauses.

$(x_1 \lor \lnot x_1)$

$(x_2 \lor \lnot x_2)$

Because $x_1$ and $x_2$ can take any value and not affect satisfiability, if the original formula had at least one solution then the new formula will have at least four.  And if the original formula had no solutions then the new formula will still have none.

Since CNF-SAT is NP-complete, then this reduction to QUADRUPLE-SAT proves the NP-completeness of the QUADRUPLE-SAT.


The math behind converting from any base to any base without going through base 10?

This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that a number is not its digit representation. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a sequence of sounds which you make when you communicate a number). What is confusing you is the fact that you never see a number but always its digit representation. So you end up thinking that the number is the representation.
Therefore, the correct question to ask is not "how do I convert from one base to another" but rather "how do I find out which number is represented by a given string of digits" and "how do I find the digit representation of a given number".
So let us produce two functions in Python, one for converting a digit representation to a number, and another for doing the opposite. Note: when we run the function Python will of course print on the screen the number it got in base 10. But this does not mean that the computer is keeping numbers in base 10 (it isn't). It is irrelevant how the computer represents the numbers.
def toDigits(n, b):
    """Convert a positive number n to its digit representation in base b."""
    digits = []
    while n > 0:
        digits.insert(0, n % b)
        n  = n // b
    return digits

def fromDigits(digits, b):
    """Compute the number given by digits in base b."""
    n = 0
    for d in digits:
        n = b * n + d
    return n

Let us test these:
>>> toDigits(42, 2)
[1, 0, 1, 0, 1, 0]
>>> toDigits(42, 3)
[1, 1, 2, 0]
>>> fromDigits([1,1,2,0],3)
42

Armed with conversion functions, your problem is solved easily:
def convertBase(digits, b, c):
    """Convert the digits representation of a number from base b to base c."""
    return toDigits(fromDigits(digits, b), c)

A test:
>>> convertBase([1,1,2,0], 3, 2)
[1, 0, 1, 0, 1, 0]

Note: we did not pass through base 10 representation! We converted the base $b$ representation to the number, and then the number to base $c$. The number was not in any representation. (Actually it was, the computer had to represent it somehow, and it did represent it using electrical signals and funky stuff that happens in chips, but certainly those were not 0's and 1's.)


Understanding state table for turing machine

They're the same Turing Machine, to be specific - the top diagram is a representation of the tape before the TM has run, and the bottom diagram is after.

There's no key regarding how to read the state transitions but I'm assuming >> means shift right one cell, << means shift left one cell and 1 means stay put.

You are right that the first move would be to index 2, using the first rule. But this rule applies three more times still, so the head ends up at index 5, where it encounters 0 and enters state S1 via the second rule - at the same time writing 1 at index 5.

The head then shifts back all the way to index 0 (one cell at a time) using the third rule, at which point the fourth rule is used (read 0, switch to S2, shift right). So it moves right to index 1 and then stops, as S2 is the final state.


Whether the algorithm is polynomial or not with input size which is not polynomial

This depends on how precisely the words are meant.

In computer science, we often lack perfect (or even good) information about the behavior of algorithms. As a result, we tend to approximate or create upper bounds and talk about those instead of actual behavior. In most contexts, when you say “the algorithm requires superpolynomial space” what you mean is that in the worst case, we cannot prove that the algorithm uses less than superpolynomial space.

This is very different from the literal interpretation of your words, where an algorithm requires superpolynomial space if there exists an input for which it use superpolynomial space.

So why does this matter? Writing $k$ units of space generally requires at least $k$ units of time in the contexts where we are interested in doing space analysis. Therefore if the algorithm in fact requires superpolynomial space, it must require superpolynomial time. Additionally, if we cannot prove it doesn’t require superpolynomial space, then it follows that we cannot prove that it doesn’t require superpolynomial time. However, it is possible for us to not be able to prove that it doesn’t require superpolynomial space and in fact requires polynomial time.

Additionally, it’s possible that in your context writing $k$ units of space can be done in much less than $k$ time. There do exist computation models where space is much cheaper than time in this sense, but in those contexts we rarely care about space complexity, because it’s so cheap.

So, the answer in most contexts is no, but it’s very important to think carefully about what your words mean.


The phrase is explained by the rest of the passage.  I'll give a larger excerpt of the paper for context.

  A seminal paper by Selman, Mitchell and Levesque considered the empirical performance of DPLL-type solvers running on uniform-random SAT instances.  It found a strong correlation between the instance's hardness and the ratio of the number of clauses to the number of variables in the instance. Furthermore, it demonstrated that the hardest region (e.g., for random 3-SAT, a clauses-to-variables ratio of roughly 4.26) corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance: the probability that a randomly-generated formula having a given ratio will be satisfiable.

The non-algorithm-specific property is the probability that a randomly-generated formula having a given clauses-to-variables ratio will be satisfiable.  While the perceived hardness of a particular instance will vary depending on the algorithm used to solve it, the probability that a randomly generated SAT instance is satisfiable does not change if you use different SAT solvers.  Yet these two properties are somehow linked.

An example of an algorithm-specific property would be the apparent hardness of pigeon-hole problems encoded as SAT instances.  It's been proven that deciding the unsatisfiability of such instances requires exponentially long proofs in the resolution proof system, and thus exponentially long runtimes of solvers implementing that system.  However, a solver that implements a simple procedure to break the symmetry of such instances (such as forcing a specific ordering of the pigeons in the holes) allows unsatisfiability to be decided in polynomial time.


Looking for sources: Graph search in social media

Facebook graph search is a relatively new technology pioneered/announced by Facebook that attempts to search for relevant info based on social connections in a social media system (eg Facebook). ie it finds relevant info based on exploring information "nearby" on the "social graph".
in this way, basically every person on Facebook doing the same search with same search terms might come up with different results based on how it interrelates with what their friends are posting about. this also can be seen as part of a trend where the major online services are encroaching on each others prior territory, eg Google's recent introduction of Google+ social network. conversely Facebook is now encroaching on Google's lucrative and highly-developed search engine technology.
there is a huge amount of media coverage [cited in the wikipedia article] but mainly at a superficial level of a product introduction. in contrast to Googles pagerank algorithm, the Facebook algorithm did not appear to originate in open scientific research, but instead is a mostly proprietary technology developed within Facebook. Facebook is not going to want to release many details, but the following is useful for an overview, written by Xiao Li, an engineering manager on the natural language team for Graph Search, and Maxime Boucher a research scientist for Graph Search.

Under the Hood: The natural language interface of Graph Search

also it will be natural for Facebook to insinuate this algorithm as highly developed and competitive with Pagerank but because its in early stages of development, one would not expect highly advanced results competitive with Pagerank at least at first (because Pagerank has been highly developed over a decade etc) with respect to mere semantic capability. on the other hand Facebook has access to a social graph, and it would be expected to prove superior quality in some types of searches that best leverage/focus on ones personal social network.
there does not appear to be much open scientific research outside of Facebook related to this topic. however the following seems to be a publication of some of the principles in a previous prototype/experimental iteration/version called Unicorn which the new feature is probably originating from/growing out of.

Unicorn: a system for searching the social graph

Unicorn is an online, in-memory social graph-aware indexing system designed to search trillions of edges between tens of billions of users and entities on thousands of commodity servers. Unicorn is based on standard concepts in information retrieval, but it includes features to promote results with good social proximity. It also supports queries that require multiple round-trips to leaves in order to retrieve objects that are more than one edge away from source nodes. Unicorn is designed to answer billions of queries per day at latencies in the hundreds of milliseconds, and it serves as an infrastructural building block for Facebook's Graph Search product. In this paper, we describe the data model and query language supported by Unicorn. We also describe its evolution as it became the primary backend for Facebook's search offerings.


Does FACTORING have optimal substructure or analog to it?

No.  There's no known optimal substructure like that.  Such a substructure would naturally lead to algorithms for factoring large composite numbers, which is a notoriously hard problem.  For numbers that are products of two primes, there is no known optimal substructure; these are the kinds of numbers that are used in the RSA cryptosystem, and factoring them has been studied in great depth in the literature.  However, the best factoring algorithms known don't use optimal substructure; instead, they use other number-theoretic ideas.

Another way to put it: recursion does not seem like a useful approach to factoring products of two primes efficiently.  The natural way to recurse is to find a divisor $d$ of $n$, then recurse on $d$ and $n/d$; but that's a chicken-and-egg problem, because finding a divisor of $n$ is exactly the problem that's hard.  For instance, when $n$ is a product of two primes, factoring is the problem of finding a (non-trivial) divisor of $n$.  So, the problem is that, to figure out what to recurse on, you first need to solve the problem itself.  My thanks to @Raphael for this helpful way of thinking about things.


Number of special paths between two nodes

To start, notice that a room is only useful if v[i] divides k, where v[i] is the value of the room i. One other important thing to see is that, is the worst case there are at most 7 different primes (2*3*5*7*11*13) in the prime factorization of k and at most 19 primes total (2^19). This gives us a good hint that we can use a bitmask to represent the value of each node in such a way that lcm(v[i], v[j]) = v[i] | v[j] (bitwise or).

After having the graph pre-processed (with only the useful nodes and with the bitmask pre-computed for every node and for k), we can do DP on the graph that can be seen as a DAG because we will never go through the same node twice. Our state will then be (cur_node, cur_bitmask).

There's only one final detail for this to fit in memory. One should notice that for the second dimension of the DP is very sparse so we can use a map for each node to keep the DP results.

Hope my explanation was clear enough, if not, feel free to clarify your doubts :)

Sample implementation: http://pastebin.com/KLfyyvhv


Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

Here is one space-efficient memory-hierarchy-aware in-memory data structure that might be a reasonable choice.  The data structure is a binary search tree with 16-byte nodes.
Each node is either an internal node or a leaf node:

An internal node points to two children.  It has a value $v$, a left child $\ell$, and a right child $r$.  All integers $\le v$ are in the left child; integers $>v$ are in the right child.

A leaf node holds a run-length encoding of a bitmap.  Notice that an interval has a very short run-length encoding, so this is slightly more general than storing an interval in each leaf (it is a hybrid somewhere between a binary tree of intervals and a binary tree of bitmaps).

Each node of the tree is responsible for some interval of integer values $[s..t]$.  The root is responsible for $[0..\text{MAX}-1]$.  For an internal node containing the value $v$, its left child is responsible for $[s..v]$ and its right child is responsible for $[v+1..t]$.  A leaf that is responsible for $[s..t]$ has a run-length encoding of the bitmap for the integers in the interval $[s..t]$.
How do we pack each node into 16 bytes?

I'll assume the tree contains at most $2^{32}$ nodes in the tree.  Therefore, each node can be referred to by a 32-bit label.  We'll have an array $A$ of nodes, and the node with label $i$ will be stored at $A[i]$.  With this optimization, each child pointer can be stored in 32 bits (rather than 8 bytes for a 64-bit pointer).  Note that the restriction to $2^{32}$ nodes is not very restrictive; unless your machine has more than 64 GB of RAM, you couldn't fit anything larger in memory anyway.

I'll assume that $\text{MAX} \le 2^{64}$.

The first bit of the node will indicate whether it is an internal node or a leaf node, leaving 127 bits for the rest.

Internal nodes: We need 64 bits for the two child pointers.  That leaves us 63 bits for the value $v$.  We'll store the value $v$ as an offset within the interval for that node.  In other words, if the internal node is responsible for the interval $[s..t]$, then we'll store $v$ as the value $v-s$.  (We know $v \in [s..t]$, so it follows that $v-s$ is a non-negative integer.)  A 63-bit unsigned int is plenty for this offset.  (If we wanted to use an offset that is larger than will fit in a 63-bit unsigned int, then we just split the range artificially.  Since $\text{MAX} \le 2^{64}$, this will impose at most one or two extra splits at/near the root.)

Leaf nodes: We have 127 bits for the run-length encoding of the bitmap corresponding to the interval $[s..t]$.  We can use any convenient run-length encoding.  If the run-length encoding of the bitmap does not fit within 127 bits, we split the interval: we turn it into an internal node with two children.
If you know something about the typical distribution of lengths of runs (i.e., the lengths of intervals, the lengths of the gaps between intervals), you can choose a run-length encoding that is optimized for that distribution.  Otherwise, you can use any convenient generic run-length encoding scheme (e.g., recursive Rice-Golomb encoding); see also this Wikipedia page on compressed bitmaps.

Notice that we don't store $s$ or $t$ in each node, but that's OK.  The interval $[s..t]$ for a particular node is determined by the path that we took to reach that node.  As we traverse down from the root, we can keep track of the interval $[s..t]$ and update it each time we follow a child pointer.
If you wanted, you could combine with this with some sort of self-balancing binary tree scheme )or a self-optimizing binary tree, such as a splay tree), but it might not be necessary in practice, depending upon the access pattern in your application, and it definitely adds complexity.


Partitioning bag of sets such that each set in a group has a unique element

It is NP-hard. Here is a reduction from a variant of vertex cover:

Given a graph $G$ with $n$ vertices and a positive integer $k$ where $n+k$ is even, determine whether there is a vertex cover with size $k$.

This variant is also NP-complete.
Given an instance graph $G$ with $n$ vertices $v_1,\ldots,v_n$ and $m$ edges $e_1,\ldots,e_m$, as well as an integer $k$, we construct $nm+1$ elements $x_{11},\ldots,x_{1m},\ldots,x_{nm},y$. We define $U=\{x_{11},\ldots,x_{1m},\ldots,x_{nm},y\}$ for convenience. Also,

For each vertex $v_i$, we construct a vertex set $S_i=U\backslash\{x_{i1},\ldots,x_{im}\}$.
For each edge $e_j=(v_{i_1},v_{i_2})$, we construct an edge set $T_j=(U\backslash\{x_{i_11},\ldots,x_{i_1m},x_{i_21},\ldots,x_{i_2m},y\})\cup\{x_{i_1j},x_{i_2j}\}$.

We ask if $\{S_1,\ldots,S_n,T_1,\ldots,T_m\}$ can be partitioned into $(n+k)/2$ groups such that within each group each set has at least one element not found in any other set in that group.
If there is a vertex cover with size $k$, say without loss of genrality $\{v_1,v_2,\ldots,v_k\}$, then the partition can be $\{S_1,T_{c(1,1)}, T_{c(1,2)},\ldots\}, \ldots, \{S_k,T_{c(k,1)}, T_{c(k,2)},\ldots\}, \{S_{k+1},S_{k+2}\},\ldots,\{S_{n-1},S_n\}$ where $v_i$ covers $e_{c(i,1)}, e_{c(i,2)}, \ldots$ (if $v_i$ and $v_{i'}$ both cover an edge $e_j$, we arbitrarily allocate $T_j$ to one of the groups containing $v_i$ and $v_{i'}$.)
On the other hand, if there is a $(n+k)/2$-partition, we can always adjust it to the form above without increasing the number of groups, thus obtain a vertex cover with size at most $k$. First, we observe that

If a group contains at least two vertex sets, then it cannot contain any other set. We call such group a vertex group.
If a group contains exactly one vertex set $S_i$, we call it a mix group. Moreover, if this group contains at least two edge sets, then the edges corresponding to the edge sets in this group must all be incident to the vertex $v_i$. (If a group contains exactly one vertex set $S_i$ and one edge set $T_j$, and the edge $e_j$ is not incident to the vertex $v_i$, we call such group a bad group.)
If a group contains no vertex set, then there exist at most two vertices such that each edge corresponding to an edge set in this group must be incident to one of the two vertices. We call such group an edge group.

The adjustment is roughly described as follows:

We arbitrarily choose two bad groups $\{S_i,T_j\},\{S_{i'},T_{j'}\}$ and regroup them as $\{S_i,S_{i'}\},\{T_j,T_{j'}\}$. We repeat this process until there are at most one bad group.

If there is still a bad group $\{S_i,T_j\}$, suppose $e_j$ is incident to $v_{i'}$, then consider the group containing $S_{i'}$. There are two cases:

This group is a vertex group, say $\{S_{i'}, S_{i''}\}$. Then we regroup these sets to $\{S_{i'},T_j\}$, $\{S_i,S_{i''}\}$.
This group is a mix group. Then we simply move $T_j$ to this group.

After the adjustment above, there is no bad group any more.

For each group containing no vertex set, due to Observation 3, there are two vertices $v_i,v_{i'}$ such that each edge corresponding to an edge set in this group is incident to at least one of $v_i,v_{i'}$. For convenience, we denote respectively by $\mathcal{T}_i$ and $\mathcal{T}_{i'}$ the edge sets with corresponding edges incident to $v_i$ and $v_i'$ (one edge $e_j$ may be incident to both $v_i$ and $v_i'$, we arbitrarily allocate $T_j$ to one of $\mathcal{T}_i$ and $\mathcal{T}_{i'}$). Consider the group(s) containing $S_i$ and $S_{i'}$. There are four cases.

$S_i$ and $S_{i'}$ belong to the same group, then we regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\}$.
The two groups are both vertex groups, say $\{S_i,S_{i''}\},\{S_{i'},S_{i'''}\}$. We regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''},S_{i'''}\}$.
The two groups are both mix groups, we then simply move $\mathcal{T}_i$ to the group containing $S_i$, and $\mathcal{T}_{i'}$ to the group containing $S_{i'}$.
One is a mix group (say the group containing $S_i$) and the other is a vertex group (say $\{S_{i'},S_{i''}\}$). We then move $\mathcal{T}_i$ to the group containing $S_i$ and regroup remaining sets to $\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''}\}$.

After these adjustments, there are only vertex groups and "good" mix groups. The vertices corresponding to the vertex sets in these "good" mix groups form a vertex cover.
As a result, the decision version of your problem is NP-complete.


Putting as many items as possible with weight and size limit

Consider the following variant of subset sum problem:

  Given a set of $2n$ positive integers and a positive integer target $W$, is there a subset with size $n$, the sum of whose elements is $W$?

This problem is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Now given an instance of this variant $x_1,\ldots,x_{2n}$ and $W$, denote $S=\sum_{i=1}^{2n}x_i$. We construct $2n$ items $1,\ldots,2n$, where Item $i$ has weight $x_i$ and size $S-x_i$, and construct a box with weight limit $W$ and size limit $nS-W$. We can see there is a subset with size $n$ the sum of whose elements is $W$ if and only if we can put $n$ items into the box.

As a result, your problem is NP-hard in general.

However, there are only five kinds of sizes in your specific problem, so you can try some brute force method. Suppose you choose $c_1$ items with very small size, $c_2$ items with small size, $c_3$ items with medium size, and $c_4$ items with large size. You can enumerate all possible values of $c_1,c_2,c_3,c_4$. For each possible values of $c_1,c_2,c_3,c_4$, you can then greedily pick items. This algorithm runs in $O(nn_1n_2n_3n_4)$ time where $n_1,n_2,n_3,n_4$ are the number of items with very small, small, medium, and large sizes respectively.


What's the difference between Clock and Second Chance Page-Replacement Algorithm?

Clock is second chance.  Given the same input they will both produce the same replacements at the same points in time.  The only difference is the details of implementation.  Second chance is usually described in terms of a "fifo" which is assumed to be a linked list where there is a pointer to the head and tail and every node contains a pointer to next.  Then when you remove a page from the head of the fifo you do it by setting head = head->next.  When you insert a page on the tail of the fifo you do it by setting tail->next = new_node, tail = new_node, new_node->next = NULL.

Clock is just a simpler (and slightly faster) implementation of a fifo where you keep a circular linked list.  tail->next points to what was the head in our old structure.  We only need one pointer, the pointer to tail.  Now removing a node from head is simply tail->next=tail->next->next and inserting a node on the tail is new_node->next = tail->next, tail->next = new_node, tail = new_node.  This is all about the same as the non-circular version.  The efficiency comes when you need to move a node from the head to the tail.  That's just tail = tail->next with the circular list.

Two-handed clock

By adding a second clock hand to the clock algorithm you get an extremely low-cost approximation of not-recently-used (which is an approximation of least-recently-used.)

In the two-handed clock algorithm you have two clock hands.  One of the hands is just like before, it points at the next page being considered for replacement.  When a replacement is required we just keep moving this clock hand (clearing reference bits) until we find a page with the reference bit cleared, and that's the page that gets replaced.  (So this clock hand is just doing the clock implementation of second chance.)

The second clock hand is another pointer into the circularly linked list.  The purpose of the second hand is to clear reference bits.  Every once in a while you clear the reference bit on the linked-list node that the second hand is pointing to, and set second_hand = second_hand->next.  This eliminates one of the problems with second chance, which is that when a page is only used a small amount right after it is first fetched then second-chance will require two cycles through the fifo before that page gets replaced.  In the two-handed clock algorithm those "short-term usage" pages get replaced after just one cycle through the fifo.

Another replacement algorithm you might look at is WSClock of Carr and Hennessy.  It is a combination of the two-handed clock with a bunch of heuristics that are helpful in practice.


A question about the work per recursive call in FPT vertex cover of size k algorithm

You do not need to create any new graph.
You can simply maintain an additional array $VT$ of size $|V| = n$ such that $VT[i] = 1$ if the vertex $i$ is deleted from the graph. Otherwise, $VT[i] = 0$.
While accessing an edge $(i,j)$, first the algorithm can check if $VT[i]$ and $VT[j]$ are both $0$ or not. If both are $0$ then the algorithm access that edge. Otherwise, it does not.
In addition to it, maintain the count of edges a vertex $i$ is currently connected to. Suppose the count is stored in an array $C$ of size $n$. In the beginning of the algorithm $C[i]$ is initialized to the $degree(i)$.

Accessing an Undeleted Edge: Go to the adjacency list of that vertex which has $VT[i] = 0$ and $C[i] \neq 0$. Since we know that at least one edge in the list is not deleted, the algorithm will find an undelete edge in $O(n)$ time. Updating the count array after deleting a vertex takes $O(n)$ time. Overall operation is $O(n)$ time.


How to efficiently determine whether a given ladder is valid?

This is not a complete answer.
I give a simpler statement of the problem
and some remarks.
We start with a graph where vertices are labeled with $[n]$.
We have an operation that adds a directed edge from $v$ to $u$ to the graph,
and if $label(v)<label(u)$ switches their labels.
Given a directed multi-graph $G$ with $n$ vertices and $e$ edges,
check if it can be obtained using using the operation above.
It is easy to see that the problem is in $\mathsf{NP}$:
a certificate is a (polynomial size) sequence of operations resulting in the $G$.
Observation
It seems that we can assume without loss of generality that
all edges to the last vertex are added at the end of the sequence and
all edges from it are added at the start of the sequence.
This can be generalized to other vertices.
Assume that we have remove all vertices with labels larger than $label(v)$.
All edges to $v$ are added at the end of the sequence and
all edges from $v$ are added at the start of the sequence.
I think it should be possible to combined this observation with Havel-Hakimi to give a polynomial time algorithm.


Can two neighbors in a graph be at the same depth in a DFS tree?

I think you are correct:

All neighbors of a node will be of rank one less (the node we got here from) or one more (or two more, etc) because we will rank them before we back out of the node.


Identifying events related to dates in a paragraph

In general, the problem of identifying dates and other temporal markers in text is called the problem of extracting temporal references. The search linked will take you to papers related to this.


Prove the language of numbers divisible by 3 is not regular using pumping lemma

You cannot choose any string for the pumping lemma. You have to choose one that is at least as long as the pumping distance of the language (which exists when it is regular), but you do not know which it is, so you have to assume it is some value named $p$ (or some other name) and you assume you have a well chosen string in the language that is greater than $p$.

Another point is that I would say that $\epsilon$ is not the representation of a decimal number, rather than say it is not divisible by $3$.

All this being said, modular arithmetics works pretty well with divisibility constraints, divisibility by a constant, I mean. And Finite Automata are usually friendly to modular arithmetics because it is defined on finite sets of values (or classes of numbers).


How convert instances of a language efficiently into 3SAT instances?

The idea is to reduce an instance  $x$ to $\phi$ that uses only $O(T(n))$ symbols and clauses. $\log T(n)$ will be the length of binary representation of each symbol. This is the upper limit that you cannot cross if you want to solve the problem. So, you will have to optimize quite a bit. See the oblivious TM and state representation in Arora and Barak to get an idea.


Does real linear programming produce bipartite perfect matching using maxflow reduction?

Let us consider $K_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative answer to your first question.

On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found algorithmically. An integral max flow does correspond to a maximum matching.


Why does the effectiveness of my reinforcement based neural network recede after a while?

There seems to be some kind of overfitting happening.It happens when noise and fluctuation in data is learned as concept by your Neural Network Model.

https://en.wikipedia.org/wiki/Overfitting


Is there an efficient algorithm for this vertex cycle cover problem?

Let a cycle cover of a directed graph be a collection of vertex-disjoint cycles such that each vertex is in exactly one cycle. So if I understand you correctly, given a directed graph $G$, you want a maximum cycle cover, where each cycle is of length at least $k$ (perhaps for $k=2$, or $k=3$ at least). A cycle cover where each cycle is of length at least $k$ is called a $k$-cycle cover.

Deciding if a digraph $G$ has a 2-cycle cover is solvable in polynomial time. The problem of deciding whether $G$ has a 3-cycle cover is NP-complete. The corresponding optimization problem (i.e., finding a maximum weight 3-cycle cover) is APX-complete, and has an $((3/5)-\epsilon)$-approximation algorithm (for any $\epsilon > 0$). The good news here is that one can also compute a maximum weight 2-cycle cover in polynomial time (provided edge weights are nonnegative).

For details and proofs of the above claims, see [1].

[1] Bläser, Markus, and Bodo Manthey. "Two approximation algorithms for 3-cycle covers." Approximation Algorithms for Combinatorial Optimization. Springer Berlin Heidelberg, 2002. 40-50.


This problem is known as frequent itemset mining, or more precisely, maximal itemset mining.  You can take a look at the Apriori algorithm and the FP-Growth algorithm.


How to find a 2-wise independent hash family that is not 3-wise independent?


What's the right way to think about a CFG symbol with an infinite null derivation?

The infinitely large parse tree you propose does not represent the parse of any sentence, because its leaves are not all terminals.

A more precise statement would be that $A$ cannot derive the empty sentence. You can produce an arbitrarily long derivation of $A$ by repeatedly using the rules $A \to A B$ and $B \to \epsilon$ but none of those derivations is empty. Since the precise definition of "nullable" is "a non-terminal which can derive the empty sentence", $A$ is not nullable.

If a FIRST/FOLLOW implementation crashes on that input, then the implementation is buggy. The correct computations are:

$$\begin{align}
FIRST(A) &= \{x\} \\
FIRST(B) &= \{y, \epsilon\} \\
FOLLOW(A) &= \{y, \epsilon\} \\
FOLLOW(B) &= \{y, \epsilon\}
\end{align}$$


When do you use amortized time complexity and when to use unamortized?

You can find the motivation for the amortized analysis from this reference:

The motivation for amortized analysis is that looking at the worst-case time per operation can be too
pessimistic if the only way to produce an expensive operation is to "set it up" with a large number
of cheap operations beforehand.

Hence, unamortized (asymptotic) analysis means considering time complexity of an algorithm (instead of each operation) when each operation can be counted in constant time.


The difference between a Hoare Triple/Assertion and a Typed Function

You are putting your finger on angular stone of program verification.
At a very rough and high level you can think a derivation in Hoare logic as proving a property, thing which can somehow be translated in a type derivation.

More precisely you are almost (you're slightly limiting yourself with Hoare logic) rediscovering the very deep Curry-Howard correspondence with asserts that mathematical proof and type derivation are the same thing.


Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6

Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it may be that you missed some condtitions from the original question.


Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000_2$ does not fit into 8 bits and will thus be represented as 0000 0000. Therefore $255 + 1 =$ 1111 1111 + 0000 0001 = 0000 0000 and in that sense 1111 1111 acts as if it was $-1$. Two's complement is based on this observation.

For a deeper understanding of it, I suggest reading the wikipedia page on it. Note that as long as you you don't need to directly manipulate bits of your integers and your numbers don't go out of range, it makes no difference what signed integer representation is used.


Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

Assume you have to check whether $\#A \ge \frac 43\#B$, then this is equivalent to  $3\#A \ge 4\#B$. This can be solved: just push 3 symbols for every $A$ and pop four of them for every $B$ (changing this a little when the number gets negative).

Adapt this to your fraction.


Proof of SAT is randomly reducible to UNIQUE-SAT

Q: $x_1,...x_n$ are unknown literals, how can we construct $f_k$ with unknown literals and where $y_1,...,y_m$ came from?

$x_1, \ldots, x_n$ are variables, each of which can appear as a positive literal ($x_i$) or a negative one ($\lnot x_i$). To construct an equivalent formula $f_1$ of another formula $f_1'$, you don't have to know the values (truth assignments) of $f_1'$. (A simple example is $x_1 \to x_2 \Leftrightarrow \lnot x_1 \lor x_2$.)

The variables $y_1, \ldots, y_m$ are unimportant (at least in this Lemma). The Lemma define the "equivalence" of the two formulas $f_1$ and $f_1'$ by equality on the $x_i$ values (leaving $y_i$ values unspecified).

  Q: How do we come to the such construction of $f'_1$ and why showing only $f'_1$ sufficient for the proof?

Each $f_i$ (and $f_i'$) is independent and similar. Therefore, the case of $f_1'$ is sufficient for the proof. To justify the construction of $f_1' = f \land (x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} \oplus 1)$, you should prove the following two points:

Each solution $v$ to $f_1'$ satisfies $f$.

This is trivial by the definition of $f_1'$.

Each solution $v$ satisfies the equation $v \cdot w_1 = 0$.

This is the tricky part. We argue as follows:

First, $$v \cdot w_1 = x_{i_1} + x_{i_2} + \cdots + x_{i_j} \text{ (here `+` is over GF[2])} = x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j}$$
The first equality follows from the fact that other $w_l$ with indices $l \neq i_1, i_2, \cdots, i_j$ are all 0 (according to the definition of all $x_{i_j}$).

Because $v$ is a solution to $f_1'$, we have $$x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} \oplus 1 = 1$$
Thus,
$$v \cdot w_1 = x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} = 0$$


Is there a fundamental difference in LIFO and FIFO entropy coding?

LIFO and FIFO encoders with adaptive models are equally capable, with minor implementation differences.

Fabian Giesen writes about this in a blog post:

  Reverse encoding

  As mentioned above, ANS coders are LIFO: whatever order you encode symbols in, the decoder will produce them in the opposite order. All my ANS coders (including the public ryg_rans) use the convention that the encoder processes the data in reverse (working from the end towards the beginning), whereas the decoder works forwards (beginning towards end).

  With a static model, this is odd, but not especially problematic. With an adaptive model, decoder and model have to process data in the same direction, since the decoder updates the model as it goes along and needs current model probabilities to even know what to read next. So the decoder and the model want to process data in the same direction (forward being the natural choice), and the rANS encoder needs to be processing symbols in the opposite order.

To reiterate, in a FIFO coder,

Run the model forwards on the data to obtain intervals corresponding to estimated probabilities
Run the encoder forwards on this list of intervals.
Run the decoder, generating the decompressed data in its original order.

In a LIFO coder:

Run the model forwards on the data to obtain intervals
Run the encoder in reverse on this list of intervals. Streaming is done by encoding in blocks, which can be as large as your memory capacity.
Run the decoder, generating the decompressed data in its original order.


Is there a way to determine whether a list of integers can be a prefix function?

Denote by $p$ the input prefix function. Refer to the characters of a word having $p$ as prefix function by their indexes $V=\{0,1,2,...,\operatorname{length}(p)-1\}$. We will keep a set of pairs $D$ of elements of $V$ to represent the characters that must be different. Finally, $V$ will be partitioned into equivalence classes according to the characters of the word that must be equal. I assume that to answer this question it is also given which is the alphabet $\Sigma$ of allowed letters to use. A possible variant of the question would give also a dictionary $L$ of allowed words.

Algorithm

A non-zero as first entry tells you right away that the sequence is not a prefix function.

Each positive value in $p$ tells you equality between certain pairs of characters of the potential word having that (presumptive) prefix function. Keep track of the equivalence classes that these equalities define, maybe with a disjoint set union data structure.

If you ever find an increase by more than $1$ ($p[k+1]>p[k]+1$) you can return immediately that it isn't a prefix function.

Whenever, the sequence doesn't increase it will also tell you one pair of characters that must be different. Collect these pairs in $D$.

Run by the pairs $D$ of vertices that must be different. If any belong to the same class return false.

Finally, consider the graph $G$ with vertices given by the equivalence classes obtained above and where the edges are the elements of $D$. If only the alphabet $\Sigma$ is given, then we compute if the vertices of $G$ can be colored with the elements of $\Sigma$ such that adjacent vertices don't get the same color. In the variant in which the dictionary $L$ is given, then we check if any word in $L$ has the length of $p$ and its characters that are in positions being in the same equivalence classes are equal, and the characters forming a pair in $D$ are different. If these conditions are satisfied we output true. Otherwise we output false.

Let's do your examples.
Example 1: Given $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, then $V=\{0,1,2,...,12\}$. That $p[0]=0$ tells us that we don't return false right from the beginning. That $p[1]=0$ tells us that characters $0$ and $1$ must be different. So, we insert $\{(0,1)\}$ in $D$. That $p[2]=0$ makes us insert $(0,2)$ in $D$. The rest of the entries of $p$ increase by $1$. So, we never return with a false caused by an increase larger than $1$. Moreover, there are no new insertions in $D$, but we do get the equivalence classes $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$. Since the two pairs in $D$, $(0,1)$ and $(0,2)$ don't consist of elements belonging the same equivalence class then we output true. Well, conditional of the variants of the problem in which the alphabet is small and the variant in which the dictionary of all words are given.
For example, the word $1231231231231$ has $p$ as prefix function. Well, if the alphabet has less than $2$ letters then we could give the example $1221221221221$. If the alphabet has only $1$ letter, we would need to output false.
Example 2: Given $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, then $V=\{0,1,2,...,12\}$. That $p[0]=0$ makes us not return false from the beginning. That $p[1]=1$ tells use that $0$ and $1$ are in the same equivalence class. That $p[2]=0$ makes us insert $(0,2)$ in $D$. That $p[3]=1$ tells us that $0,1,3$ are in the same equivalence class. That $p[4]=0$ makes us insert $(0,4)$ in $D$. that $[5]=1$, tells us that $\{0,1,3,5\}$ are in a equivalence class. I guess you can continue. At the end the only equivalence class with more than $1$ element is $\{0,1,3,5,6,9,12\}$. The rest of the characters are on their own equivalence classes. In $D$ we have the pairs $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$. None of these consist of characters from the same equivalence class. So, we return true.
For example, the word $0010200130450$ has $p$ as prefix function.
Let me add an example that returns false to have an example of that case.
Example 3: Given $p=(0,0,1,2,3,4,2,0)$, then $V=\{0,1,2,...,6\}$. Since $p[0]=0$ we don't return false from the beginning. That $p[1]=0$ makes us insert $(0,1)$ in $D$. That $p[2]=1$ tells us that $0,2$ are in the same equivalence class. That $p[3]=2$, tell us that $1,3$ are in the same equivalence class and that $0,2$, which we already knew are also equivalent. That $p[4]=3$ tells that $0,4$ are equivalent, $1,3$, which we knew, and $2,4$, which by now we knew too. That $p[5]=4$ tells that $1,3,5$ are equivalent. Now, that $p[6]=2$ tells us that $6$ and $1$ are equivalent. That's okay so far. But it also tells us that $0$ and $5$ are equivalent. Now, the problem with that is that that makes $1$ (which is equivalent to $5$) in the same equivalence class as $0$, but $(0,1)$ is a pair in $D$. So, we will have to return false.


A more rigorous proof on a Bellman-Ford's corollary

I think your proof is correct, but there are 2 things that I would like to comment:

I think that when you are proving the $\rightarrow$ direction and you say:

"Each edge of the path $p$ will be relaxed by Bellman-Ford, an operation which will only decrease $v.d$. Therefore we can conclude, that $v.d < \infty$
after the algorithm terminates."

there is an assumption that a call to RELAX will necessarily decrease $v.d$. But this is not necessarily true, as a call to RELAX can leave $v.d$ untouched. So, you would need to prove that in BELLMAN-FORD there would be a call to RELAX that necessarily decreases $v.d$.
The alternative argument you are proposing (use the "Path-relaxation property") would work fine here, though.

Since this is a corollary, I think the authors expected you to use the previous Lemma to solve it (of course, solving it via a different reasoning is ok too).
In this case, we have Lemma 24.2:

Lemma 24.2
Let $G = (V, E)$ be a weighted, directed graph with source $s$ and weight function $w: E \rightarrow \mathbb{R}$, and assume that $G$ contains no negative-weight cycles that are reachable from $s$. Then, after the $|V| - 1$ iterations of the for loop of lines 2-4 of BELLMAN-FORD, we have $v.d = \delta(s, v)$ for all vertices that are reachable from $s$.

We can use it to prove the corollary:
$\rightarrow$: If there is a path from $s$ to $v$, by Lemma 24.2, we have $v.d = \delta(s, v)$, where $\delta(s, v)$ (the shortest path weight from $s$ to $v$) is less than $\infty$ since there is a path.
$\leftarrow$: If BELLMAN-FORD terminates with $v.d < \infty$ when it is run on $G$, by Lemma 24.2 we have that $\delta(s, v) = v.d < \infty$, which by definition of $\delta$ means that there is a path from $s$ to $v$.


Every state in subset automaton is reachable

Any regular language is accepted by arbitrarily large automata with no inaccessible states. Let $M = (Q, \Sigma, \delta, q_0, F)$ be an automaton with no inaccessible states.  For any natural number $n$, we can write $[n]=\{0, \dots, n-1\}$ and define a new automaton

$$M_n = (Q\times [n], \Sigma, \delta_n, (q_0,0), F\times [n])\,,$$

where $\delta_n((q,i),\sigma) = (\delta(q,\sigma), i+1\bmod n)$ for any $q\in Q$, $i\in[n]$, $\sigma\in\Sigma$.

The effect is that each state counts modulo $n$ the number of characters that have been seen so far, but this has no effect on the behaviour of the automaton, other than making the state space bigger.

The automaton $M_n$ might have inaccessible states, so delete them. But note that, after reading any word of length $0\leq \ell<n$, the automaton is in some state of the form $(q,\ell)$, so at least $n$ states are accessible.  Setting $n = 2^{|Q|}$ gives you an exponentially bigger automaton, but why stop there? :-)

Thanks to @holf for the elegant fix to the problem of the disconnected state space.


Which properties of context sensitive languages are decidable?

When considering questions like this you need to make explicit what representation you are using for your languages. In the following I will assume you are using context-sensitive grammars as input for your problems.

1) is a well known undecidable property of context-sensitive grammars.

2) as well as 3) and 5) are obviously undecidable as they are undecidable for a proper subclass of context-sensitive grammars, namely the context-free grammars.

4) is trivially decidable as the answer is always yes because the complement of a context-sensitive language is itself context-sensitive.


Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

There is no sequence of functions $f_1,...,f_{n^c}:\{0,1\}^{2^n}\rightarrow\{0,1\}^{n^d}$, such that for all $s_1\neq s_2\in\{0,1\}^{2^n}$ $\exists i\in\{1,...,n^c\} : f_1(s_1)\neq f_i(s_2)$.

Examine the function $F:\{0,1\}^{2^n}\rightarrow \prod\limits_{i=1}^{n^c}\{0,1\}^{n^d}$ defined by $F(s)=\left(f_1(s),f_2(s),...,f_{n^c}(s)\right)$.

The domain of $F$ is of cardinality $2^{2^n}$, while its range is of cardinality $\left(2^{n^d}\right)^{n^c}=2^{n^{c+d}}$. Since for large enough $n$ it holds that $2^{2^n}>2^{n^{c+d}}$, $F$ is not one to one, and thus the condition is not satisfied.


Strict-Binary Tree - Same Post-order & Pre-order sequences?

It is possible only If all nodes have same value.