Can I prove that I have x such that f(x) < c without revealing x?

If the function $f$ is publicly known and is efficiently computable, it is possible for Bob to prove that he knows a value $x$ such that $f(x)<c$.  This is known as a zero-knowledge proof of knowledge.  There's lots written on zero knowledge proofs; you can go read about them.

In particular, given any predicate $\varphi(x)$ that is computable in polynomial time, there exists a polynomial-time zero-knowledge proof of knowledge that you know $x$ such that $\varphi(x)$.  If $f$ can be computed in polynomial time, then the predicate $f(x)<c$ can certainly be tested in polynomial time, so it can also be proven in zero knowledge in polynomial time.

However, that is not enough to solve the ultimate problem you want to solve.  It sounds like what you ultimately want is a fair exchange protocol.  Sadly, such protocols typically aren't super-realistic, if you want them to be "all-digital" and avoid any trusted parties; if Alice and Bob know each other and have some kind of relationship, you're probably better off signing a contract.  But if you want to read about the topic, you can start with https://crypto.stackexchange.com/q/8333/351 and https://crypto.stackexchange.com/q/8352/351 and continue reading from there.


How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$?

A function $f\colon \{0,\ldots,N-1\} \to \{0,\ldots,N-1\}$ accepts an input from $\{0,\ldots,N-1\}$ and outputs something from $\{0,\ldots,N-1\}$. Just like any function $f\colon A \to B$.

In this case, we are interested in $N$ of the form $2^n$. That is, we are interested in values of $N$ such that $N = 2^n$. For example, $N = 256$. We identify the set $\{0,\ldots,N-1\}$ with the set of binary strings of length $n$, using binary notation. For example, if $N = 8$, then the interpretation works as follows:

0 is interpreted as 000.
1 is interpreted as 001.
2 is interpreted as 010.
3 is interpreted as 011.
4 is interpreted as 100.
5 is interpreted as 101.
6 is interpreted as 110.
7 is interpreted as 111.

As an example, the complementation function $f\colon \{0,\ldots,7\} \to \{0,\ldots,7\}$ is given by $f(x) = 7-x$. You can check that it corresponds to complementing the binary representation of the input.


Do compilers of high programming languages always compile them directly to machine code?

I've seen compilers that compile directly to object code.

I've seen compilers that compile to assembler code.

I've seen compilers that compile to byte code for a virtual machine.

I've seen compilers that compile to bit code which is intended to be further compiled to code for slightly different processors.

I've seen compilers that compile to a different language.

I've seen compilers for Javascript specifically that start interpreting code, then compile it very quickly to not very good code, then compile it carefully to reasonably good code, then compile it with a highly optimising compiler to very fast code, all depending how often some code is executed.


Your grammar will generate:
$S\rightarrow 0S12\rightarrow 00S1212\rightarrow 001212$ which is not in the required language.


Finding max value algorithm with subset comparison

Consider any algorithm that uses less than $n-1$ comparisons. We run the algorithm, responding as follows:

If one of the sets is bigger than the other, we say that its sum is larger.
If the two sets have equal size, we say that their sums are equal.

We can represent each comparison as a vector of length $n$: the comparison $\sum_{i \in A} w_i \gtrless \sum_{i \in B} w_i?$ (where $w_i$ are the weights) corresponds to the vector $1_A - 1_B$, i.e., the vector having value $1$ at the $A$-coordinates, having value $-1$ at the $B$-coordinates, and having value $0$ elsewhere.

Let $\mathbf{x}_1,\ldots,\mathbf{x}_m$ denote the vectors corresponding to comparisons of sets of equal size (so $m < n-1$), and let $\mathbf{1}$ be the constant $1$ vector. Since $m+1 < n$, there is a non-zero vector $\mathbf{v}$ orthogonal to all of $\mathbf{x}_1,\ldots,\mathbf{x}_m,\mathbf{1}$. We can assume that $|v_i| \leq 1$ for all $i$.

Consider the vector $\mathbf{w}_\delta = \mathbf{1} + \delta \mathbf{v}$, where $|\delta| < 1/n$. It is not hard to check that $\mathbf{w}_\delta$ is consistent with our replies to the algorithm. Yet $\mathbf{w}_\delta$ and $\mathbf{w}_{-\delta}$ have different maximal values, so the algorithm will make a mistake on at least one of them.

This argument even works when we are allowed to ask arbitrary queries of the form $\operatorname{sgn}(\sum_i x_i w_i)$.


Showing that deciding whether a given TM accepts a word of length 5 is undecidable

Suppose that $M$ halts on input $w$ and consider the behaviour of $M'$ when it is given input $w'\!$. $M'$ first deletes its input $w'$ and replaces it with $w$, which means that the behaviour of $M'$ doesn't depend on what input it actually receives. Then, $M'$ simulates $M$ on input $w$. So, if $M$ halts on $w$, $M'$ halts for every input, becaues $M'$ ignores its input and just pretends to be $M$ running with input $w$. Likewise, if $M$ does not halt on $w$, $M'$ doesn't halt for any input.


How do I tell if $G$ is a forest in log-space?

Using Reingold's algorithm, you can count the number of connected components in a graph. For example, you can count the number of vertices which have the minimal index in their connected component (assuming some arbitrary ordering of the vertices), that is, the number of vertices $i$ that are not connected to any $j < i$.

Now use the following criterion: A graph contains a cycle iff there is an edge whose removal does not increase the number of connected components.


Efficient algorithm to check if a vector exists in the span of a subset of vectors

Equivalently, your problem can be stated as:

Given a $m \times n$ matrix $M$ over $\mathbb{F}_2$ and a vector $v \in \mathbb{F}_2^m$, find a vector $x\in \mathbb{F}_2^n$ such that $M x=v$ and the Hamming weight of $x$ is as small as possible.

There are some hardness results for this problem.  For instance, this post argues that the problem can't be approximated within a constant factor, within polynomial time (even for randomized algorithms), assuming standard complexity-theory assumptions.

See also https://cs.stackexchange.com/a/59922/755 and https://cstheory.stackexchange.com/a/10112/5038 and https://cstheory.stackexchange.com/q/27460/5038 and https://cstheory.stackexchange.com/q/10396/5038 for related work, including some algorithmic techniques that might be relevant.


Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L

I'm assuming by $\lambda$ you mean the empty word and by $n_0(w)$ the length of a word.

The proof for the first part is not correct: You argue that every word in $L^2$ has length at least $2$ and every word in $L^3$ has length at least $3$. From that it does not follow that every word in $L^3$ is longer than every word $L^2$, because there could also be a word of e.g. length $3$ in $L^2$. Consider for example $L = \{a\}^\star \setminus \{ \lambda \}$, that is, the set of all non-empty $a$-sequences. You have $a \in L$ and $aa \in L$, thus $aaa = a \cdot aa \in L^2$, but also $aaa = a \cdot a \cdot a \in L^3$.

Instead, what you want to say is that there is a word of minimal length $n$ in $L^2$, and because every word in $L$ has length at least one, the shortest word in $L^3$ has length at least $n+1$.

More formally: Let $\lambda \notin L$. Thus $\forall w \in L: n_0(w) > 0$. Pick $w \in L^2$ such that $n_0(w)$ is minimal. Assume $w \in L^3$. Since $L^3 = L^2 \cdot L$, it follows that $w = u \cdot v$ for $u \in L^2$ and $v \in L$. Since $n_0(v) > 0$, it follows $n_0(w) > n_0(u)$. But then $n_0(w)$ is not minimal. Contradiction.

For the second part: Assume $L^2 \not \subseteq L^3$ and $\lambda \in L$. Thus there is $w \in L^2$ such that $w \notin L^3$. But since $L^3 = L^2 \cdot L$, it follows $w = w \cdot \lambda \in L^3$. Contradiction.


Difference between computation in proposition proof and definitional computation?

What Agda is showing you in the source code in both cases are the propositional proofs, i.e., elements of the identity type. In Agda the judgemental (definitional) equality is invisible to the user. Agda uses it in the background to verify that terms have required types. When it has to compare $a$ and $b$, it normalizes both of them (based on judgemental equalities, such as $\beta$-reduction) and compares the normalized values for syntactic equalities. There is a theorem which says that $a$ and $b$ are judgementally equal if, and only if, they have syntactically equal normal forms.

When judgemental equality has the property that things are equal preciely when they have syntactically equal normal forms, then people sometimes call it computational equality because it "computes" by computing normal forms. There is a lot of confusion in terminology.

To test judgmental equality in Agda, we can use refl to show that two things are judgmentally equal (because the rule for refl states that refl a has type b ≡ c if, and only if, b and c are both judgmentally equal to a). Here are some examples:

 open import Relation.Binary.PropositionalEquality
 open import Data.Nat

 -- this works, the normal form of 2 + 3 is 5
 p : 2 + 3 ≡ 5
 p = refl

 -- this works, the normal form of 0 + m is m
 q : ∀ m → 0 + m ≡ m
 q _ = refl

 -- this does not work, because hte normal form of m + 0 is m
 -- r : ∀ m → m + 0 ≡ m
 -- r _ = refl

You can also show that $2 + 3 = 5$ by providing an element p' of 2 + 3 ≡ 5 which is not refl, such as the one you posted in the question. In the text you read, they were just trying to demonstrate the normalization steps by making them explicit as elements of an identity type (without saying so explicitly, probably). The thing to remember is that in Agda you will never see "a proof of judgemental equality", as that always happens in the background.


How to go about proving an algorithm correct?

To prove the correctness, we have to prove actually the function
rmax(x,y) returns the the maximum number with index between x and
y in the array S[1..n], provided the hypothesis: 1≤x≤y≤n.

There is a semantic technique that often works nicely for recursively
defined functions such as this one.

Your function can be defined as the least fixed-point of a functional:

F = λ rmax, x, y. if y-x≤1 then max(S[x],S[y]) else
                  else max(rmax(x,(x+y)/2), rmax((x+y)/2+1,y))

I have changed a bit the style, for convenience. You note that F is a
function of 3 arguments, and you original function rmax is defined
as its least fixpoint in the semantic domain. Also, here rmax is a local name for the first argument of F. I could replace it by any other name (alpha conversion). I kept rmax only for readability.

Now, the way you prove correctness is by checking that this
functionnal preserves correctness when it is applied to a function
foo that is correct, when it is defined (it is undefined for example
if it does not terminate, but being defined is actually a formal
semantic property).

That is, you only have to check that if the function foo(x,y) is correct, then
the function F(foo) is also correct.

F(foo) = λ x, y. if y-x≤1 then max(S[x],S[y]) else
                 else max(foo(x,(x+y)/2), foo((x+y)/2+1,y))

When y-x≤1, we know that either x=y or x=y-1, since by
hypothesis 1≤x≤y. In both cases we see that max(S[x],S[y]) is the
right answer.

Otherwise, we see that 1≤x≤(x+y)/2≤n and 1≤(x+y)/2+1≤y≤n. Hence the
hypothesis is verified for the two calls to the function foo. So,
since the function foo is correct by hypothesis, each call (when
giving a defined result) returns the maximum array value between the
bound given by its parameters (if it is defined). Since both ranges
cover the range between x and y, the maximum of these two values
is the maximum value between x and y.

Note that there is no base case in this recursion. The reason is that
it starts using with the totally undefined function $\bot$ (read "bottom"), which is
thus always correct when it is defined.

Note that this does not prove termination of the algorithm. But you get that easily by induction.

Some further explanations.

This proof is in a way very similar to the proof suggested by Yuval
Filmus. It is not too surprising as they are both supposed to prove
the same result. However they are quite different in spirit. Yuval's
proof is a recursion on the steps of an actual interpretation of the
program (operational semantics). The proof I am proposing is by
recursion on the structure of the program code seen as an infinite
program defined as the limit of an infinite sequence of finite program
(denotational semantics). It assumes continuity properties (so that
passing to the limit makes sense), which are verified for usual
computing operations and predicates.

The former proof is on the use of the program, while the latter is on its structure.


why not just use a random number generator as a hash function?

If I understand the question correctly, the answer is simple: if Hash(object) returns 27 when you call it this afternoon, we want Hash(object) to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is implementing hash tables, and we want to be able to access what we put into a hash table tomorrow with the key we used today.

In your example, you might want to add a contains(value) method; using the hash, this would be as easy as checking self.hash[value] =? value. Otherwise, you'd need to iterate through the entire array to see if some position contains value.


Min-cut in graph with demands/lower bounds

Max flow and min cut are dual problems, in a technical sense: there are linear programming formulations of both, and these linear programs are dual to each other. This is explained in the Wikipedia article on the max-flow min-cut theorem.

Given a variant of the max flow problem, you can find the corresponding min cut problem by writing the linear programming formulation of the max flow problem, and dualizing it. I'll let you figure out what you get in your cases.


You are asking why we can model the equation $a \lor b$ as two directed edges in a graph. The answer is that mathematics is a free country, and we are allowed to do whatever we want. The only restriction we have to obey is that whenever we claim a result, it must be accompanied by a valid proof.

This representation is used in an algorithm that decides whether a 2SAT instance is satisfiable. As you mention, an edge from a literal $\ell_1$ to a literal $\ell_2$ means that if $\ell_1$ is true, then $\ell_2$ has to be true. Indeed, if $a \lor b$ holds then if $\lnot a$ is true, $b$ must be true, and vice verse, if $\lnot b$ is true, $a$ must be true.

If there is a path from some literal to its negation – from $x$ to $\lnot x$ or from $\lnot x$ to $x$, for some variable $x$ – then clearly the formula is not satisfiable, since $x$ cannot be both true and false. A more delicate argument shows that if no such paths exist, then the formula is satisfiable. This is proved by showing how to find a satisfying assignment for the formula (it's a nice exercise).


Decision tree complexity of deciding whether array is "zigzag"

You can prove a lower bound of $n-3$ comparisons, almost matching the trivial upper bound of $n-1$ comparisons (surely the gap can be closed with a bit more work). The proof uses an adversary argument. Whenever the algorithm compares two elements $s<t$, the answer is always $A[s]<A[t]$ unless $s=n-1$ and $t=n$, in which case the answer is $A[n-1]>A[n]$.

It is always consistent that the array is zigzag, with $i=n-1$ and $j=n$ (the order is $A[1] < A[2] < \cdots < A[n-2] < A[n] < A[n-1]$). Now suppose you make less than $n-3$ comparisons. In particular, if you think of your comparisons as edges on the graph on vertices $\{1,\ldots,n-2\}$ (we ignore comparisons to $A[n-1]$ or $A[n]$), then the graph is disconnected. In particular, there are vertices $s<t \leq n-2$ which weren't compared. It is therefore consistent that $A[s] > A[t]$ whereas $A[t] < A[n-1] > A[n]$ (for example, the order could be $A[1] < \cdots < A[s-1] < A[t] < A[s] < \cdots < A[n-2] < A[n] < A[n-1]$), in which case the array isn't zigzag since it has two disjoint decreasing parts. Hence the algorithm doesn't know the answer.


Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

Here is a thesis on exactly this topic:

  Subramaniam, Lavanya. "Partition of a Non-simple Polygon Into Simple Polygons." Master's
  thesis, University of South Alabama, 2003.
  PDF download.

Fig.10f, p.23.


Checking the validity of a pyramid of dominoes

I can think of a brute force solution. Try all 6!*(2^6) options. i.e. create all legal permutations of the pyramid and test each one if it holds the condition. It will take around 50K iterations to do.


An example of such an algorithm is randomized Quick Sort, where you randomly permute the list or randomly pick the pivot value, then use Quick Sort as normal. Quick Sort has a worst case running time of $O(n^{2})$, but on a random list has an expected running time of $O(n\log n)$, so it always terminates after $O(n^{2})$ steps, but we can expect the randomized instance to terminate after $O(n\log n)$ steps, always with a correct answer.
This gives an subset of Las Vegas algorithms. Las Vegas algorithms also allow for the possibility that (with low probability) it may not terminate at all - not just terminate with a little bit more time.
These in turn are really just a type of Monte Carlo algorithm, where the answer can be incorrect (with low probability), which is at least conceptually different to maybe not answering.

There's a whole bunch of detail I've left out of course, you might want to look up the complexity classes ZPP, RP and BPP, which formalise these ideas.


Anotation rules for while rule in deductive verification

As you have already said, the second and third rule include a variant t to prove termination whereas the first rule does not consider it.

The second rule guarantees that the variant is always non-negative. This is necessary to have a lower bound for the variant which decreases every iteration.

The third rule relaxes that condition a little bit. The variant is always non-negative except in the last iteration (where e is false at the end of the block). This still guarantees termination (who cares about the variant if we know it's the last iteration?).

I think whether you choose the second or third rule is a matter of taste. Until now I knew only the second one. It should be easy to alter code or a variant whose correctness can be shown by the third rule such that it is also provable with the second one.

Choosing the first rule is of course only an option if you're not interested in termination.


Does there exist a Reed-Solomon-like code over decimal symbols?

The property of Reed–Solomon codes that you mention is known as Maximum Distance Separability, and codes with this property are known as MDS codes. In coding theory the most popular type of code is a linear code, and these are only defined over alphabets which are prime powers. However, in the literature you can find some papers on MDS codes on arbitrary alphabets; I'll let you research that yourself.

For the specific case $N=1$, there is a very simple MDS code, namely checksum: you add to the original data a new digit whose value is the negated sum of the other digits (so that all new digits sum to zero). This code can detect any single error.


Can you solve 3D Tic Tac Toe with Minimax?

You could precompute the optimal move for all possible configurations, and store that in a lookup table.  Once that's done (and it only needs to be done once), it would make your program extremely fast at runtime.

Your board has a total of 24 cells (8 cells at each level, times 3 levels), so there are at most a total of $3^{24}$ possible calculations.  Therefore, as a naive upper bound, your table will need to have at most $3^{24}$ entries.

In fact, due to gravity plus the fact that you don't need to store configurations where one player has already won, there will be many fewer configurations that you need to store in your table.  Call a configuration relevant if no one has won yet, and it is a reachable configuration (i.e., it doesn't violate the gravity rules).  Then your table can be stored as a dictionary/map: for each relevant configuration, it stores the optimal move when in that configuration and which player will win assuming optimal play (first-player win, second-player win, tie).  Now your job is to precompute that dictionary, with one element per relevant configuration.

It is possible to show that the number of relevant configurations is at most $13^8 \approx 2^{29.6}$: in particular, the number of configurations that satisfies gravity and has no vertical win is $13^8$.  This is only an upper bound; the true number of relevant configurations is even smaller still, as this estimate doesn't take into account that there's no need to store any configuration containing a horizontal or diagonal win.

To speed up the precomputation, you can avoid repeating effort (i.e., use "dynamic programming").  For instance, one approach would be to start by enumerating all relevant configurations containing 23 full cells and compute the optimal move for each; then enumerate all relevant configurations containing 22 full cells and compute the optimal move for each; and so on.  At each stage, when you compute the optimal move, you add it to the table along with who ultimately wins.  Notice that this makes it very easy to compute the optimal move at each stage, since you only need to search at depth 1 and then you can immediately look up what will happen thereafter in the table.

The running time of the precomputation will be some small constant times $N$, where $N$ is the number of relevant configurations.  We know that $N$ is smaller than $2^{29.6}$, and probably substantially smaller.  Therefore, I expect this precomputation to be something you could run within a few days on a modern PC, and store on the filesystem in a reasonable amount of space.

As a further optimization, you can use symmetry to further reduce the number of configurations you need to compute or store.  In particular, given any  configuration, you can find a bunch of other equivalent configurations through symmetry (flip horizontally, flip vertically, rotate).  For each set of equivalent configurations, you only need to consider and store one.  In particular, given a configuration, the first thing you'd do is map it to a canonical equivalent configuration (so that all equivalent configurations map to the same canonical); then you only need to compute or store canonical configurations in the lookup table.  I suspect this will reduce $N$ by a factor of 8 or so.


Min path cover for a three-layer graph with all paths traversing all layers

I think this can be solved by reduction to a circulation problem.
Introduce a graph with source $a$ and sink $z$.  The edges are as follows:

All edges will have infinite capacity, lower bound 0, and cost 0 unless mentioned otherwise.
Add an edge $z \to a$ with cost 1.
Add edges $a \to c_i$ for each color $c_i$ and $s'_k \to z$ for each smell $s_k$.
For each allowable combination $c_i,t_j$, add an edge $c'_i \to t_j$, and each allowable combination $t_j,s_k$, add an edge $t'_j \to s_k$.
Add edges $c_i \to c'_i$, $t_j \to t'_j$, $s_k \to s'_k$ with lower bound 1.

Find the minimum cost solution to this circulation problem.  I think there exists an integral solution, and it can found in polynomial-time.
The solution corresponds to a collection of fruits, and the cost of the solution is the number of fruits required.  Each unit of flow corresponds to a fruit.  The structure of the graph ensures that each attribute is covered by at least one fruit.


Represent a DNF formula as a multivariate linear formula?

Usually one represents disjunction by addition and conjunction by multiplication, so a suitable polynomial would be $(x + y) \cdot (z + w)$ (I renamed $i$ to $w$ here as to not create confusion w.r.t. the imaginary unit).
Note that plugging in $0$ or $1$ depending on the desired truth values yields 0 precisely if the original formula would evaluate to false while any value greater than zero indicates that such an assignment would satisfy the formula.
You mention linear in your title, however I do not think that there is a sensible way to represent propositional formulas by linear functions.


What is the point of the "respect" requirement in cut property of minimum spanning tree?

I don't have the book handy. I assume that

"safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
the goal is a correctness proof of Prim's algorithm¹.

Now, say the cut did not "respect" $A$. That means that there already is an edge in $A$ that crosses it. By choosing a second edge from that cut -- which may happen even with pairwise distinct weights! -- we may introduce a cycle and lose the tree property.

By requiring that the cut "respects" $A$ we know that $A \subseteq S$ and we can not introduce a cycle².

The assumptions of this theorem may be stronger than strictly necessary -- as long as we do not create a cycle, we do not per se need to care about other edges in the cut -- but we can build an algorithm around them, so the theorem is a convenient way to ensure its correctness.

Note how the theorem directly implies that fact since Prim's algorithm maintains such a cut and chooses light edges from it to grow the tree.
In the algorithm, we'll always have $A=S$.


Determining if a list contains two numbers whose difference is less than k

Let $f(x) = \lfloor x/k \rfloor$. Create a hash table which stores $f(x_1),\ldots,f(x_n)$; furthermore, for each $y \in \{f(x_1),\ldots,f(x_n)\}$, count how many elements map to $y$, and what is the minimal element mapping to $y$.

If any of the cells contains more than one element, then these two elements are at a distance of less than $k$. Otherwise, go over all elements, and for each $x_i$, compare $x_i$ to the minimal element mapping to $f(x_i)+1$, checking whether the two elements are at distance less than $k$. If no elements at distance less than $k$ have been found in this way, then no such elements exist.


is it possible to minimize pushdown automata?

Unfortunately the problem is not computable.  It is undecidable even to tell if two arbitrary PDAs are equivalent; minimizing a PDA is even harder.


Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm

It seems the algorithm tries to calculate n-1 gcd's simultaneously, and performs n-1 operations as long as one of the gcd's is not found. And since at least one gcd (gcd (n, 1)) takes n iterations, it is $\Theta (n^2)$.

Of course that is just due to the stupid implementation, but probably a good example for estimating the runtime of an algorithm, not the runtime of a problem.

You need to show that $n^2$ is not $o(n log^k n)$ for any k.


As you state in your comment, you could use a variety of different approaches. Your question isn't limited to the vector space model. Various language models rely on these concepts as well. Here are two approaches:

N-Grams

One popular approach is the use of n-grams. This approach involves treating adjacent words as one word. For instance, "big house" would be stored in your controlled vocabulary as "big," "house," and "big house" if you chose to use 2-grams (bigrams). Probabilities would be computed per n-gram

Pros: accurately keep track of probabilities of n-grams occuring, easy to extend from unigram model (just follow same ranking functions for unigrams such as tf-idf or Okapi BM25)

Cons: exponentially larger memory usage, many bigrams will only occur once

Inverted Index per Document

This approach requires storing an inverted index within each document in addition to an inverted index of the whole corpus. This would mean that you wouldn't need to store n-grams. Of course, you wouldn't have important information such as the term frequency or document frequency of an n-gram. The idea is that you look up the first word in the n-gram and find it in the document. You compare succeeding words to see if there is an n-gram present there.

Pros: less memory usage (no need to keep track of n-grams in documents), more flexibility (such as ignoring words that don't match)

Cons: less information stored (no TF, DF, etc.), more space needed per document (for inverted index), additional lookup needed, ranking this may be difficult

  If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

This completely depends on the ranking function and how you choose to weight each thing. How common are qwe and asd? How common is zxcrty? Would you want to give additional weight to larger n-grams? These are all important considerations.


Intuition behind this specific algorithm for time series

During the forward pass, you compute F such that F[i] represents the maximum possible profit when restricting yourself to the elements with indices 0,1..,i.

During the backward pass, you compute B such that B[i] represents the maximum possible profit when restricting yourself to the elements with indices i,i+1,..,n-1 (where n is the size of your list). The reason you track the max is that because you are going backwards in time when populating B, you want to sell before you buy.

Now M[i] = F[i-1] + B[i] represents the maximum profit when doing a first buy/sell among indices 0,1..,i-1 and a second buy/sell among indices i,i+1..,n-1, so you are sure that the first sell will happen before the second buy (because the first sell happens at index i-1 at the latest and the second buy at index i at the earliest).

Reciprocally, suppose the optimal solution has two buy/sell's happening at indices b1, s1, b2, s2 (in increasing order). Then you know that M[b2] will be at least as big as the profit achieved by this solution (equal in fact, because it can't be bigger) as b1,s1 happens before index b2, and b2,s2 happens after (or at) b2.

Thus, by taking the maximum over all M[i] you will necessarily hit M[b2] at some point and get the maximum profit. And if the optimal solution has only one buy/sell it will be at M[0] = F[n-1] = B[0] = M[n-1] which you also consider.


Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

You have at least two options.

If the number of cards is very small, as in your example, then you can go over all possible subsets of cards and compute their sum, taking note of the one closest to 21. Then go over all of them again and output the ones achieving the best sum. With a realistic number of cards this will be very fast.

What they might have expected you to answer is to use dynamic programming. For each sum from 2 to 21, go over all cards and see if it is achievable from an earlier sum (including 0), and if so, annotate this with all possible cards. Now find the best sum and follow the edges back to 0.


The important thing to note is that when merging the MST and the Matching, you create a multigraph. This means even when you merge, even if there are edges that already exist, you add them anyway. So you will always end up with even degree vertices.

This is step 4 of the algorithm as seen on Wikipedia.

So in your second case, you now have a multigraph where edges $(Somerville \rightarrow Everett)$ and $(Belmont \rightarrow Cambridge)$ each show up twice.


A recursive language minus a recursively enumerable language results in a recursive language?

Let $L$ be an r.e. language which is not recursive (for example, $L$ can be the language of descriptions of Turing machines that halt on the empty input). Then $\Sigma^*$ is recursive but $\Sigma^* \setminus L$ is not recursive (exercise).

More generally, when faced with a question like this, try the following two approaches in parallel:

Try to prove the claim.
Try to refute the claim using a counterexample.

The two approaches can even feed each other.


Is there a known, fast algorithm for counting all subsets that sum to below a certain number?

Subset below-sum appears to be NP-Hard. This is informal, but consider, if you can solve subset below-sum in polynomial time, you can solve subset sum in polynomial time.

Given: does any subset of $S$ sum to exactly $n$?
Let $A$ be $subset\_below\_sum(n)$ and $B$ be $subset\_below\_sum(n + 1)$. If $B - A \gt 0$, the answer is yes, otherwise, the answer is no.


In general, there is no obstacle to define a rewrite system as above, and a few sources do indeed require rules 1. and 2. only as additional hypotheses.

However the hypotheses are almost always necessary (but not sufficient!) for both termination and confluence, which is indeed the main object of study of rewriting as a field.

Perhaps it's useful to remind why this is the case:

Termination:

If $x\rightarrow t$ is allowed as a rule, then any term $u$ rewrites to $t[u/x]$. In particular, the system is non-terminating.
If $l\rightarrow r$ and $r$ contains a fresh variable $y$ not in $l$, then for example, $l\rightarrow r[l/y]$, and so the system is non-terminating.

Confluence:

Take $x \rightarrow f(x)$ and $g(a)\rightarrow b$. Then
$$ g(f(a))\leftarrow g(a)\rightarrow b$$
for instance, breaking confluence. In particular, you can "insert" an $f$ around any term you like, which makes confluence very hard to satisfy.
If there are constants $a$ and $b$, then given the rule $f(x)\rightarrow g(y)$, you get
$$ g(a)\leftarrow f(x)\rightarrow g(b)$$
again, breaking confluence.

Now every theorem involving either termination or confluence could be prefaced with "assuming 1. and 2. holds, ..." but it makes sense to restrict your attention to systems where the theorems aren't trivially false. I don't think anyone would be shocked by a paper which lifts these restrictions though, at least condition 2. (condition 1. really creates anarchy). Condition 2. is mostly about non-determinism, for which rewriting is a nice framework in general.

There are some systems in which free variables can appear in the RHS, but usually not any fresh variable $y$ is allowed: there are additional constraints which need to be satisfied, e.g.

$$f(x) \rightarrow  f(y)\ \mid\ 0\leq y < x $$

where $x$ and $y$ are allowed to be integers. These types of systems are called constraint rewriting systems and are extensively studied.


The question whether $L = NP$ is an open problem [1], so yes, it is possible.  However, it is considered unlikely, or in other words, most believe that $L \subsetneq P \subsetneq NP \subsetneq PSPACE$, but we only know that $L \subsetneq PSPACE$ [2, 3].

References:

[1] Taking Passes at NP Versus L — Gödel's Lost Letter and P=NP
[2] L/P/PSpace vs P/NP — cstheory.stackexchange.com
[3] If P=NP, then is L=NL? — cs.stackexchange.com


What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

This kind of scheduling problem might fall within the area of operations research.
I would suggest using integer linear programming.  You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).
I'll outline a way you could formulate this as an instance of ILP.  We'll let $\ell$ range over locations, $t$ over teams, and $i$ over months (time periods).  Introduce the following zero-or-one variables:

$x_{t,\ell,i}=1$ if team $t$ is at location $\ell$ during month $i$.

$s_{\ell,i}=1$ if you start renting the location $\ell$ at the start of month $i$.

$e_{\ell,i}=1$ if you terminate (end) renting the location $\ell$ at the end of month $i$.

$a_{\ell,i}=1$ if location $\ell$ is available for use during month $i$.

$m_{t,i}=1$ if team $t$ moves at the end of month $i$ to a new location.

Then all of your constraints can be expressed as linear inequalities:

$\sum_{\ell} x_{t,\ell,i}=1$: each time has a home somewhere in each month.

$x_{t,\ell,1}=1$ if $\ell$ is the starting location for team $t$; $x_{t,\ell,24}=1$ if $\ell$ is the ending location for team $t$.

$s_{\ell,1}=1$ if $\ell$ is one of the original 250 locations.  $s_{\ell,1}=0$ if $\ell$ is not one of the original 250 locations.

$a_{\ell,i} = s_{\ell,1} + \dots + s_{\ell,i} - (e_{\ell,1} + \dots + e_{\ell,i-1})$.

$x_{t,\ell,i} - m_{t,i} \le x_{t,\ell,i+1} \le x_{t,\ell,i} + m_{t,i}$.

$\sum_t x_{t,\ell,i} \le a_{\ell,i}$.

Now the cost is a sum of the moving costs (a linear function of the $m$'s), the rent costs (a linear function of the $a$'s), and the early termination fees (a linear function of the $e$'s), so the cost is a linear function of the variables.  Thus, you have an ILP instance, which you can give to an ILP solver and ask it to find the optimal solution -- or the best solution it can find within a set time bound.  You'll have about $350\times 200 \times 24$ variables, i.e., about 1.6M variables, which is large but not necessarily infeasible.


Let $S$ denote the languages accepted by such machines.  The question wants you to prove $S=L$.

When you have a complicated-looking task, it often helps to break it down into pieces.  So, a first helpful hint on how to break it into pieces: try to prove $S \subseteq L$.  Separately, try to prove $L \subseteq S$.  (If you still can't solve it, then you're able to ask a more specific question about one or the other of those.)


Efficient computation of Kronecker product

You cannot fill a matrix with $n_1 n_2 m_1 m_2$ entries in time faster than $\Theta(n_1 n_2 m_1 m_2)$. Some considerations:

There may be a way to reduce the number of multiplications (FFT?) by using extra additions, but it won't improve the asymptotic complexity;
This is easy to parallelize;
You can do this on-the-fly, i.e. store the matrix M as "Kronecker product of A and B" and perform the multiplication only after a request for an element M[p,q].
Conceptually you can forget about the rectangular shape of a matrix and think about the situation where you have two vectors $\left[x_1,...,x_k\right], \left[y_1,...,y_m\right]$ and want to compute $k \cdot m$ products $x_i y_j$ for each $i,j$.


Ternary decision tree for the lower bound of comparison sort with 3-way comparisons

The proof would be exactly the same, using a ternary tree (where each internal node has three children) instead of a binary tree. A ternary tree of depth $d$ has at most $O(3^d)$ notes, so a sorting tree would have to satisfy $n! = O(3^d)$, which implies that $d = \Omega(n\log n)$.


Does a recursive call reset to the beginning of the method if the call is in the middle?

A recursive call is no different than any other call. Here is what happens when you call procedure X:

The current address is pushed into the stack.
Jump to the beginning of X.
When X concludes, pop the return address from the stack, and jump there.

It doesn't matter whether X is the current procedure or a different one.


Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree

We first observe the following: There is an optimal cover $C$, and no leaf is in $C$. This is true since in any optimal cover $X$ you can replace all leaves in $X$ with their parents, and you get a vertex cover which is not larger than $X$.

Now take any optimal cover $C$ that does not contain leaves. Since no leave is selected, all parents of the leaves have to be in $C$. In other words, $C$ coincides with the greedy cover on the leaves and their parents. Next, we take out all edges that have been covered already. We can now apply the same argument again: In the remaining tree, no leaf needs to be selected, but then their parents have to be selected. And this is exactly what the greedy algorithm does. (A vertex becomes a leaf iff all of its children are selected in the previous step.) We repeat this argument we determined a complete vertex cover.


What properties does a co-RP problem need to be in P?

Considering from my comment that there exists an upper bound to the runtime of $A$: $p(n)$ then there are only $2^{p(n)}$ possible ways a coin-flip of a randomized algorithm can manipulate the outcome of the result.

If the error propability of $A$ I described as $f$ is a fraction with part $\frac{g(n)}{2^{p(n)}}$ then creating a deterministic program that runs $g(n)$ many times plus one different paths of a possible computation of $A$ it is guaranteed that at least one of these paths would have identified the false positive as false.

Therefore we can skip the journey through $RP$ into $ZPP$ and can argue that if $g$ is a polynomial function we need to run $g(n) + 1$ times the polynomial Algorithm $A$ resulting in a polynomial runtime of $(g(n)+1) \cdot p(n)$ that deterministically solves $x\in L$ or $x \not\in L$ with an error propability of $0$, therefore placing $L$ in $P$.

This is but one case where, given a randomized algorithm that places a language $L$ clearly in $co-RP$ places $L$ also in $P$.


Okay I understood the issue.

Properties of B+ Tree.

All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
All the leaves are in same depth, and here d = 2.
Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.
All the data pointers are contained in leaf nodes.
All elements should be contained in leaf nodes.
There should be between d to 2*d keys at node except possibly the root.
There should be between d + 1 to 2*d + 1 child pointers.

In the B+ Tree given below, each node has 2 and 2*2 data entries except possible the root. Each node has a mininum of 2 keys.

Only root of the B+ Tree can only fewer than d keys, its the only exception we have.

In my question, when you remove 19, the property of B+ Tree is not violated but when you remove 20, the total number of elements contained in the node is less than d. Hence redistribution and merging have to be performed so that the property of B+ tree is not violated.


Summing two array using FFT: time complexity analysis

Since all elements are in the range $[1,10n^{1.5}]$, all elements $A+A$ are in the range $[2,20n^{1.5}]$. So there are $O(n^{1.5})$ distinct elements in the sum. Some of them will be obtained more than once.


The authors you cite have another paper on the topic.

Would you be satisfied with a model which assumes that the properties of the surfaces to be allocated can be summarized by an arbitrarily large but finite set of one-dimensional parameters (say length, depth, northmost point, eastmost point,... really as many as you want but finite) ?

If this is satisfying to you, and you are ok with assuming that people have preferences over surfaces as described by the values of these parameters, you might find useful insights in the theory of fair allocation of bundles of multiple goods. A great (and free) introduction is "Fair Allocation Rules" by William Thomson.

Of course when the dimensions represent parameters describing the shapes to be allocated, you are likely to have unusual preferences which are hard to work with and do not fit nicely with the existing results. Might be worth giving it a try though...


What is the shortest superstring for $\{c (ab)^k, (ba)^k, (ab)^k c\}$?

A shorter superstring is $c(ab)^{k+1}c$, which has length $2k+4$.


How to solve this big O notation of a fraction

The idea is that $x^4 + x^2 + 1 = \Theta(x^4)$, and similarly $x^4 + 1 = \Theta(x^4)$. So the first expression is $\Theta(x^4)/\Theta(x^4) = \Theta(1)$. The second expression can be estimated similarly.

This sort of calculation shows the advantage of asymptotic notation - irrelevant details disappear and calculations become manageable.


Is there a limit on transition function compositions in NFAs?

You can define the transition function of an automaton to be whatever you want, as long as it's a function of the appropriate type, i.e., $Q\times\Sigma\to Q$ fora DFA and $Q\times\Sigma\to 2^Q$ for an NFA.

However, the composition you've attempted doesn't actually make sense.  Since $f$ is the transition function of an NFA, it has type $Q\times\Sigma\to 2^Q$. As such, you can't write $f(f(q_i,\sigma))$, since the argument of the outer application of $f$ is some subset of $Q$, whereas there are supposed to be two arguments: an element of $Q$ and a symbol from the alphabet.  So, for a double-composition, you probably need to write something like
$$\bigcup\{f(q,\sigma)\mid q\in f(q_i,\sigma)\}\,.$$
You can try to work out the triple-composition yourself.

But are you sure you want to do that? You're defining an automaton that says "Every time I read the character $\sigma$, I will do whatever the original automaton would have done if it read three $\sigma$s." As I said, you can make your automaton do whatever you want, but I'd be interested to know the context that makes this a sensible thing to do.


If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

You can compute the average using linearity of expectation.

Let the random variable $X$ denote the number of elements that are retained.  Let $X_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise.   Then $X = X_1+\dots + X_n$, so

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$

Now the $i$th element is retained if and only if it is the largest number among the first $i$ elements in the list.  Therefore, $\Pr[X_i=1]=\frac{1}{i}$, so

$$\mathbb{E}[X] = \frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{n} \approx \log(n) + \gamma$$

In other words, the average length of the remaining list is $O(\log n)$.

I don't know what the distribution is.

As a heuristic, the expected running time of Drop Sort would satisfy a recurrence something like $T(n) \approx T(n-\log(n)) + O(n)$, which corresponds to $O\left(\frac{n^2}{\log n}\right)$ time.


Set of DAG vertices disconnecting a vertex from forbidden vertices

Wikipedia says that, for an undirected graph, you can say:

$A$ is the vertex separator for $v$ and $F$.
$A$ is the separating set for $v$ and $F$.
$A$ is the vertex cut for $v$ and $F$.

perhaps these terms are used for digraphs as well, even though "connected components" are not quite the same thing in digraphs.

edit:  @PålGD suggests the variant "separator", similar to the second option.


Whats the difference between an oracle and a decider in Computational Theory?

Oracles are entities capable of deciding even undecidable problems. Deciders, on the other hand, are essentially Turing machines (without an oracle) and therefore cannot solve undecidable problems (e.g. Halting problem).

  I understand the point of a oracle is that we don't have to know how it gets its answer but it will always give us the right answer.

This is in fact the key difference.

An oracle doesn’t have an implementation, it is just a black box giving answer to any particular question (most importantly, the ones we cannot answer), whereas a decider has to be well defined Turing machine. In other words, we must know how a decider gets the answer, meaning it cannot answer any question.


A typical job on Blue Waters is using about 10% of the machine and consumes a total of 75 node hours.  Blue Waters has about 27500 nodes, so that means some of those "75 node hour" jobs are running in just a couple of minutes.  That allows scientists to use the machine somewhat interactively.  (You can see the moving averages here: http://xdmod.ncsa.illinois.edu/#tg_usage:group_by_Jobs_none)

Supercomputers are just large collections of smaller computers.  The main reason we collect them together in one place is that we can share the cost most efficiently that way.  You are trying to create a computer that can do a lot of work, and for which the total cost of ownership (the total cost of the computer, the power, and the maintenance), is minimized over the lifetime of the computer.

There are several factors involved in the total cost of ownership: The cost of the equipment is one.  To minimize the cost of ownership you want the equipment to be doing useful work as large a percentage of the time as possible (ideally 100% of the time, realistically somewhat less, like 95% would be considered good), until the equipment burns out or becomes obsolete.  In contrast, the computer in your laptop or your phone is probably actually in use less than 10% of the time you own it (you are asleep 33% of the time, you are eating and relaxing about half the time you are awake, and even when you are "using" the computer, the processor is idle most of the time.)

The second is the cost of power. There are several parts of this: the first is the cost of the power itself.  Part of that cost is consumed in transporting the power from the power plant to the computer.  Part of it is lost in the computer's "power supply" (which is just converting AC power into DC power).  A larger AC->DC converter can usually be made more efficient.  Additionally computers turn useful electric power into waste heat.  So you also need to pay to remove the heat.  Again, larger air conditioners can usually be made more efficient than multiple small air conditioners.

The third is the cost of maintenance.  By putting together a bunch of computers and designing them so that when one goes down the rest keep running you can amortize the cost of maintenance staff over a much larger number of computer nodes than you could if the nodes were all different and placed in different buildings (or cities).

The details: Blue Waters has 288 cabinets.  Each cabinet has 96 "nodes".  Each node is a pretty normal high-end computer.  Most nodes have 2 AMD Opeteron 6276 processors running at 2.3GHz, and 64GByte of DRAM.  About 1/6 of the nodes instead have a single AMD Opteron 6276, an NVidia K20 GPU, and 38GByte of DRAM.  If you wanted, you could buy something similar to a "node" for about \$3000 or \$4000 and put it in your living room to play video games.  Blue Waters has about 27648 nodes.  https://bluewaters.ncsa.illinois.edu/hardware-summary

Each node probably consumes a bit more than 500 Watts, and turns that power into heat.  If you had a node in your living room to play video games it wouldn't be a particularly big deal.  It would consume some electricity from the wall socket and generate about as much heat as a small personal space heater.  In the winter that would be kind of nice and cozy.  In the summer you'd have to run your air conditioner more frequently to keep your house comfortable.  If you had it running full power all day every day, your electricity bill would go up considerably, perhaps double what you are consuming now.

But when you put 27648 of them together it consumes about 15 Megawatts, and generates a correspondingly large amount of heat.  The true engineering marvel of Blue Waters, like any large data center, is the building itself.  It's an enormous refrigerated box.  The Blue Waters building is particularly interesting because it is a fantastically efficient.  About 85% of the power going into the building is actually used to run the nodes.  I believe I read somewhere (can't find it at the moment) only 15% is lost in power conversion and removing waste heat.  That's a lot better than what you'd get from the 500Watt gaming computer in your living room.  You'd probably need a 750Watt "power supply" and another couple hundred Watts to run the air conditioner.

TL; DR

Let's put it all together.  By putting together thousands of smaller computers and spreading the usage among many many people, we keep those computers running most of the time, sharing the resources in a very efficient way.  It costs a lot of money to give people computers that sit idle most of the time.  The best way to save money on computation is to have people share the computers so the computers are busy most of the time.

Blue Waters is much more than just the computers inside it.  It is specially designed to be as power efficient as possible.  Part of that involves putting it near power plants to reduce power losses in power transmission lines.  Here's a satelite picture of the part of Champaign IL containing Blue Waters to demonstrate:


Why use $\mu$-calculus and not LTL,CTL,CTL*?

As for a $\mu$-calculus formula not expressible in CTL*, see this post.

As for texts on the subject, you are likely to get further ahead by reading papers, as these topics are not covered in many books.
Still, the Handbook of Modal Logic may be a good start.

As for papers, try:

Expressive power of Temporal Logics

This PhD thesis

Emerson's Model checking and the Mu Calculus

And there are many more. Just google terms like "expressive power", "mu calculus" and "temporal logics".


Why there is forward chaining inference engine (reasoner) for description logics only and not for other logics?

This question is a bit strange. I see it's based on the Wikipedia article, but that article is also a bit strange. I will try to clarify some concepts.

First, we have a language that can be used to make claims whose meaning are formally defined. Such a language may allow us to say, for example, that if $x$ is a Person, then $x$ is a Human, which can be done in first order logic as $\forall x (\neg\mathsf{Person}(x) \vee\mathsf{Human}(x))$, in a rule language like Datalog as $\mathsf{Person}(x) \rightarrow
\mathsf{Human}(x)$, in description logics as $\mathsf{Person} \sqsubseteq \mathsf{Human}$ and so forth.

Second, we have semantics, which formally defines the meaning of claims in the language. One way in which the semantics of a language can be defined is using model theory, which essentially maps terms in the language to sets, elements, and relations between sets; for example, we can map the term $\mathsf{Person}$ to a (hypothetical) set $P$ and $\mathsf{Human}$ to a (hypothetical) set $H$, and define the above claims as formally meaning $P \subseteq H$. This gives rise to the notion of models, where for example, $P := \{ \mathrm{Fred}, \mathrm{Jill} \}$ and $H := \{ \mathrm{Fred}, \mathrm{Jill}, \mathrm{Tom} \}$ is a model satisfying a given set of formal claims (since $P \subseteq H$), while $P := \{ \mathrm{Fred}, \mathrm{Tom} \}$ and $H := \{ \mathrm{Fred}, \mathrm{Jill} \}$ is not a model (since $P \not\subseteq Q$). In turn, models give rise to entailment between sets of formal claims, where for example, given $\{ \mathsf{Person}(\mathrm{Tom}), \mathsf{Person} \sqsubseteq \mathsf{Human} \}$ (in whatever language), we know this entails $\{ \mathsf{Human}(\mathrm{Tom}) \}$ as any model of the former set of claims must be a model of the latter set of claims.

Third, we have reasoning procedures to decide entailment. One way in which this is done is to use inference rules. For example, we may derive a rule such as $(\mathsf{C} \sqsubseteq \mathsf{D} \wedge \mathsf{C}(x)) \rightarrow
\mathsf{D}(x)$ to support reasoning with respect to the $\sqsubseteq$ operator in description logics. This rule may be applied for forward-chaining or backward-chaining. But there are many forms of reasoning procedures suitable for different types of languages; for example, for more expressive description logics, (a finite set of Horn) rules is not sufficient to guarantee complete reasoning, and so tableau-based methods are often used. Also one reasoning procedure can be useful for reasoning in different languages, where Datalog, for example, is natively based on rules.

Returning to the question:

  Reasoner is forward chaining inference engine (https://en.wikipedia.org/wiki/Semantic_reasoner) as opposite to Prolog backward chaining SAT solver (for queries).

A "reasoner" can adopt multiple strategies, including, but not limited to, forward-chaining on rules. Engines that apply tableau-based methods, backward chaining, resolution, etc., are also "reasoners". (The article you base the question on never claims that reasoners are forward chaining rule engines, but mentions this as one strategy.)

  Why there is reasoner for description logics and not for other logics?

There are reasoners for other logics. For example, Vampire is a reasoner for first-order logic, XSB is a reasoner for Prolog, or just check here for a list of different reasoners for different languages.


How do I build a read/write 4-nibble RAM memory system using flip flops?

You need to put multiplexers and selector/decoders around your flipflops.

The read path needs to multiplex each nibble using the 2 address line.

The write path is selecting with these two address lines with nibble should be modified.


Converting non-deterministic algorithm to deterministic

Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions.

Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice.  Forking might be done by calling the operating system's fork() call (very expensive), or by capturing all the relevant state of the variables and storing it in a set of pending items to explore (potentially tedious to write the code), or by replacing the choice() with a recursive call that makes a copy of all of the relevant state (i, S') and iteratively tries each of the possible choices (easiest to implement in this case).

Here is an example of how to implement the latter transformation.  The state at the choice statement is the value of S' and i.  So, we do the following:

search(S', i, u):
    if u in S'
        return
    S' = S' + u   # this needs to copy the set, not update it destructively
    i = i + 1
    if i>n:
        for_each u in S'
            print u
    else:
        for u in [1,2,..,n]
            search(S', i, u)

Subsets(n):
    for u in [1,2,..,n]:
        search(emptyset, 1, u)

Notice how search contains all of the code after the choice statement, until the next choice statement.  We had to rip the for-loop over i apart to make this work, but the transformation was fairly mechanical.

This is a general method that can be used on any terminating non-deterministic algorithm -- not just this one.


Enumerating all the walks in a graph between a start vertex and a terminal vertex?

If the input graph is undirected:

If the source vertex $s$ and target vertex $t$ are in different components of the graph, then there are no walks from $s$ to $t$.
If $s$ and $t$ are in the same component, and that component has only one vertex (so in particular, $s=t$), then there is exactly one walk from $s$ to $t$, namely the unique walk that starts at $s$ and has length $0$.
Otherwise, there are infinitely many walks from $s$ to $t$.

If the input graph is directed:

Let $S$ be the subset of vertices reachable from $s$, and let $T$ be the set of vertices from which $t$ is reachable.  Finally, let $H$ be the induced subgraph of the input graph $G$ with vertices $S\cap T$.  Every walk in $G$ from $s$ to $t$ is actually a walk in the subgraph $H$.

If $H$ is empty, there are no walks from $s$ to $t$.
If $H$ is a non-empty directed acyclic graph, then $s$ is the unique source, $t$ is the unique sink, and every walk from $s$ to $t$ is actually a simple path.  The number of paths in a dag from a source to a sink can be computed in $O(m)$ time by dynamic programming.  Remaining details are left as a homework exercise.
Otherwise, there are infinitely many walk from $s$ to $t$.


3-COL with a restriction on a number of vertices colored with a particular color

For a fixed parameter like 50, the problem can be solved in "polynomial time": guess which vertices to color A, then solving a 2-coloring problem for the remaining vertices.  The running time will be something like $O(|V|^{52})$, since there are $O(|V|^{50})$ ways to choose a set of at most 50 vertices; and 2-coloring can be solved in $O(|V|+|E|)=O(|V|^2)$ time.

Of course, this solution is solely of theoretical interest.  An algorithm whose running time is $O(|V|^{52})$ is technically polynomial-time, but it's completely and totally infeasible in practice for any interesting graph.

In contrast, if the parameter 50 is part of the input, then the problem remains NP-hard (consider what happens when you pass in $|V|$ as the value of this input; then you have the standard 3-COL problem).  This highlights the difference between a value that is fixed vs is an input to the problem.

Perhaps a simpler example to illustrate that difference is vertex cover: vertex cover is NP-complete, but if I ask you whether there exists a vertex cover of size $\le 50$, that can be done in polynomial time, for similar reasons -- the running time will be $O(|V|^{50})$ or so.  In particular, if you want to know whether there exists a vertex cover of size $\le k$, that can be done in $O(|V|^k)$ time.  When $k$ is a fixed constant, this is polynomial time; but when $k$ is part of the input, then this is exponential time (it is $\ge 2^k$).


Count $A$'s and $B$'s. The next $A$ will only exit at $D$ iff the first two levers are in right position. When does that happen? The first lever toggles at every $A$, but the second lever interacts with the $B$'s.

At the same time, the situation for $B$ is symmetric. The next $B$ will not exit $D$ only if both levers are left. When does that happen?


Greedy algorithm to find Minimum Dominating Set in a tree

Any negative answer that says that no greedy algorithm will work cannot be proved rigorously since we do not have a definition of an greedy algorithm. So I will just say, no, it is very unlikely that there is a greedy algorithm that will always yield a minimum dominating set if it is given a tree graph as input.

The most common greedy algorithm for dominating set is to repeatedly selecting a vertex with the maximum number of adjacent vertices that are not selected and that are not connected to any vertices selected (not dominated) so far until all vertices are dominated. The following graph illustrates how soon it fails. In the first step we will select vertex 0, the only vertex whose degree is greater than 2. Then we will select vertex 2, 4, 6 for our dominating set. However, the minimal dominating set, {vertex 1, vertex 3, vertex 5} has only three vertices.

Furthermore, any strategy that avoids selecting a vertex that has been dominated might not succeed at all. According to Do Almost All Trees Have No Perfect Dominating Set? by BQ Yue, the average number of perfect dominating sets among all trees of order $n$ is likely approaching zero as $n$ goes to infinity.

A proper strategy to find a minimal dominating set for a tree is dynamic programming. Root the tree at an arbitrary vertex if it is not rooted yet. Now you start computing recursively the minimal dominating set for each subtree with its root included in the set as well as with its root not included in the set.


Is there an algorithm to share parts of strings?

It is a shortest superstring problem and not allowing internal substrings is just an implementation detail.


Independent set and its complement are NP-complete and co-NP-complete, respectively. If you found a polynomial-time reduction between those two problems, you'd have proven that NP$\,=\,$co-NP, resolving one of the biggest open problems in theoretical CS.


Proving $\{0^{2^n}\}$ is not regular using pumping lemma

If you choose $k = 2$ then, writing $|y| = m$, we get
$$ xy^2z = 0^{2^n+m}. $$
Since $1 \leq m \leq n$, we have
$$ 2^n < 2^n+m \leq 2^n+n. $$
Cantor's theorem shows that $n < 2^n$, and in particular,
$$ 2^n < 2^n+m < 2^{n+1}. $$
Therefore $xy^2z \notin L$.

Let me take this opportunity to mention another misconception. There are some non-regular languages which satisfy the pumping lemma. Therefore the fact that you couldn't prove that a certain language is non-regular using the pumping lemma does not imply that the language is regular.


Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$

Uniformly sampling from a simplex with equation $\vec{a} \cdot \vec{b} = 1$, and reject samples out of bounds.

Several answers are posted here for uniform sampling over a simplex: Uniform sampling from a simplex


Is "Reachable Object" really an NP-complete problem?

A problem $P$ is NP-complete if:

$P$ is NP-hard and
$P \in \textbf{NP}$.

The authors give a proof of item number 1. Item number 2 is probably apparent (and should be clear to the paper's audience). For the proof of item number 1, you only need a (many-one) reduction from some NP-complete problem (e.g., SAT) to $P$; there is no need to construct a reduction in the opposite direction.


Minimum spanning tree formulation as integer program

Yes, it's possible.

It's trivially possible that every problem in P can be reduced to LP in polynomial time, for uninteresting reasons: given an instance of the decision problem, the reduction solves the decision problem (in polynomial time), then either outputs a feasible LP instance or an infeasible LP instance (where these instances are hardcoded).  I realize that's pretty uninteresting and probably not what you wanted.


Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $


What is f(x,y) in Digital Image Processing?

Yes, it represent the intensity at that point.

f( x, y ) gives the intensity of a channel at position (x, y)

Source : https://courses.cs.washington.edu/courses/cse557/00wi/lectures/imageprocessing.pdf


Regular expressions and semi-linear sets

Your claim is correct for a one letter alphabet $\Sigma = \{a\}$. We prove by induction that $\psi(r)$ is linear for every regular expression without addition. When $r = a$, $\psi(r) = 1$. When $r = r_1 r_2$, by the induction hypothesis $\psi(r_1) = u_0 + \sum_i \mathbb{N} u_i$ and $\psi(r_2) = v_0 + \sum_j \mathbb{N} v_j$, and so $\psi(r) = u_0 + v_0 + \sum_i \mathbb{N} u_i + \sum_j \mathbb{N} v_j$. When $r = r_1^*$, $\psi(r)$ is a subset of $\mathbb{N}$ closed under addition. Let $g = \operatorname{gcd}(\psi(r))$. Then $\psi(r)/g$ is a numerical semigroup, and so finitely generated, say $\psi(r)/g = \sum_i \mathbb{N} u_i$. So $\psi(r) = \sum_i \mathbb{N} gu_i$.

This argument doesn't quite work when $|\Sigma| \geq 2$, although there are some notions of GCD for multidimensional vectors, see for example this interesting presentation by Vadim Ponomarenko. Perhaps the argument above can be pushed through, or perhaps a different argument, which uses the fact that $\psi(r_1)$ is linear, exists. It's also possible that the claim is wrong in this case.


NP completeness proof of sensor selection problem

Your problem is an instance of a geometric cover problem.  Specifically, it appears to be very close to the discrete unit disc cover problem (just scale down all distances by a factor of $d$), which is apparently NP-hard but also admits reasonable approximation algorithms.


There are two parts to your question that need to be addressed.

  What transformation are you performing?
  Why does that help learning?

The transformation of taking your input and turning them into "Z-scores" is really just centering and standardizing the variance for each variable. The reason I put "Z-score" in quotes is because there is no reason to assume that this transformed variable is distributed normally. All you have done is taken a random variable with some unknown distribution and transform it to a random variable with mean 0 and variance 1. That doesn't necessarily mean it is normally distributed. Formally, if we have $$X \sim f(\mu, \sigma^2)$$ where $X$ is a random variable $f$ is the distribution with mean $\mu$ and variance $\sigma^2$, then $$\frac{X - \mu}{\sigma} \sim f(0, 1)$$ using the basic properties of mean and variance. Nowhere does this require $X \sim N(\mu, \sigma^2)$, which is where Z-score comes from.

With that said, why does this help? By centering your data (removing the mean) from both your training data and labels, you don't need to estimate a bias term. Bias (or mean measured effect) is function of the mean of your data; therefore if your data have mean 0, you should have no measurable bias term. Setting all variables to have unit variance places them all on the same scale. Oftentimes in real data the different variables in your model may have widely different variances, which could lead to difficult to compare effect sizes. Setting everything to have similar variance simplifies interpretation.


Finding a minimum weight perfect matching in Christofides TSP algorithm

There is the Blossom algorithm by Edmonds that determines a maximal matching for a weighted graph.


Impossibility of Distributed Consensus with One Faulty Process

Adding context:

  If $E_i\in\mathscr C$, let $F_i = e(E_i)\in\mathscr D$. Otherwise, $e$
  was applied in reaching $E_i$, and so there exists $F_i \in \mathscr
D$ from which $E_i$ is reachable.

Of course, without the definitions of $E_i$, $e$, $\mathscr C$, and $\mathscr D$, this isn't much use either. We're given a configuration $C$. $e$ is by assumption an event applicable to $C$. $\mathscr C$ is the set of all configurations reachable from a given configuration $C$ where event $e$ has not been applied. $\mathscr D$ is all the configurations you get when you apply $e$ to the configurations in $\mathscr C$. $E_i$ is a(n $i$-valent) configuration reachable from $C$.

The first paragraph of the lemma shows that $e$ is applicable to all configurations in $\mathscr C$. Given this, if $E_i\notin \mathscr C$, then, by definition of $\mathscr C$ and the fact that $E_i$ is reachable from $C$, $E_i$ must be reachable via some configuration that applies $e$. Any run from $C$ to $E_i$ must have a first time where $e$ is applied. Any configuration before that is in $\mathscr C$ by definition. The configuration at the point $e$ is applied is in $\mathscr D$ by definition and the fact that $e$ is applicable to all configurations in $\mathscr C$. That configuration is $F_i$.

Again, your second quote lacks context. The "such steps" mentioned in it are the steps from a bivalent configuration to a univalent configuration. Avoiding "such steps" is only relevant if we must start from a bivalent initial configuration, which is what Lemma 2 establishes. Lemma 2 critically depends on allowing up to one faulty process. If the protocol did not have to work correctly in the face of up to one faulty process, then Lemma 2 would not apply.

The idea of Lemma 2 is that if we have two configurations that differ only in how the input register is set for a single process, then if they can both reach a decision without ever executing that process (i.e. that process is faulty), then they must reach the same decision, since, once we remove that process, they have the same set of processes with the same initial state receiving the same messages. If we assume there are no bivalent initial configurations (for contradiction), then by partial correctness it is necessarily the case that there are two configurations that would make different decisions, but differ from each other only by a single process' input. Thus a contradiction.

It's trivial to make a consensus protocol when no processes are faulty. Simply pick one process (via setting its initial state appropriately) to be the Decider. It copies its input to its output. All other processes do nothing. Clearly this scheme won't work if the Decider is faulty.


Reduce undecidable language to decidable language?

... but then $A_{\mathrm{TM}}$ would be decidable!

No. Because your $f$ is not computable since one cannot compute whether $M$ accepts $w$, as Yuval Filmus said in the comment.


Confusion with first condition of Chomsky Normal Form

Yes, your context-free grammar is in Chomsky Normal Form.

A grammar is in CNF whenever its rules are of one of two types, either $A\to BC$ or $A\to a$, where $A,B,C$ are nonterminals, and $a$ is a terminal symbol.

This means that every context-free grammar is equivalent to a cf grammar in CNF, up to the empty word.
This means that by conversion into CNF one might loose the empty word. Nobody cares. Wikipedia refers to Hopcroft and Ullman as the source for CNF, and here is what H&U write:

  Theorem 4.5 (Chomsky normal form, or CNF)
  Any context-free language without $\epsilon$ is generated by a
  grammar in which all productions are of the form
  $A\to BC$ or $A\to a$. Here, $A$, $B$, and $C$, are variables and $a$ is a terminal.

Except that some people with a wretched feeling for precision did not like this idea. They came up with a complicated formulation, just to capture the empty string. Probably something like "If the language contains $\epsilon$ then we allow the production $S\to \epsilon$, where $S$ is the axiom, and $S$ does not occur on the right-hand side of productions."

Well, your example grammar does not generate $\epsilon$ anyhow, so I would not bother. Chomsky didn't, Hopcroft and Ullman didn't. However, this is not legal advise. So, if someone is checking your exams, then I would consult that person.

Fun fact, Chomsky called "his" normal form "regular grammars"(!) and added a more restrictive condition: no two rules $A\to \alpha$ and $A\to \beta$ could share a common symbol in their right-hand sides $\alpha$ and $\beta$ (unless of course $\alpha =\beta$). (Definition 8, page 149, in the 1959 Chomsky paper linked at wikipedia).


How to represent symbolic knowledge using real numbers - theory about neural networks and natural/analog computing?

No, probably not.  I think you're expecting too much from the current state of the art in word embeddings.  Word embeddings don't magically capture all semantic knowledge.  They don't reflect perfect understanding of the language.  Instead, they're just useful mappings where similar words often have similar embeddings.  Moreover, the way word embeddings are constructed has nothing to do with logical formulas.

I don't think you're going to find that word embeddings solve the problem of converting from natural language to formulas.

I don't know what would count as a general theory of encoding algorithms for you.  There are certainly multiple papers that propose different methods of constructing different word embeddings; you could read those to understand the state of the art.


Turing Machine remembering copied symbols

Once you've hit the '&' separator, move left until you see the '#', then move one cell to the right and replace the '1' with an 'x' (and change to state $p$ to "remember" you've seen a 1) or a '0' with a 'y' (changing to state $q$ to "remember" you've seen a 0). Now move right until you pass the '&' separator and see a '#'. Replace that with a '1' if you were in state $q$ or with a '0' if you were in state $p$. Now move to the left until you see a 'x' or a 'y', move one cell to the right and repeat what you've done before. Continue the process until everything on the left is a string of 'x's and 'y's, then make one more pass, restoring the values to their originals.


Can anyone give me an instance of 3SAT with exactly one solution?

The empty 3SAT instance (over no variables) has one solution.


Is < binary relation a strict partial order on IEEE doubles?

Yes, it is. (Though you need to consider signed zero as well as NaNs.) For extra confirmation:

So, the floating-point operator< does not form weak order and therefore does not form a total order. It is, however, a partial order.

However, it cannot be extended to non-strict partial ordering <= because there's no (reflexive) equality for doubles (NaN != NaN).

It can be extended, but <= as defined by IEEE isn't that extension.


Suppose the abstract SQL you're considering has support for infinite-precision "big" integers that can store any integer values, and that these support *, +, and = in WHERE clauses.

Fix the schema as $k$ such integer values columns called x_1, ..., x_k.

Query equivalence in this schema is undecidable by a reduction to the satisfiability of Diophantine equations (Hilbert's 10th problem):

A system of Diophantine equations can be described as a multivariate-polynomial with integer coefficients $p(x_1, \dots, x_n) = 0$. Determining whether or not there is any tuple $(x_1, \dots, x_n) \in \mathbb{Z}^n$ that satisfies the equation is known to be an undecidable problem.

This condition can be directly represented as the WHERE clause in the SQL described above: WHERE p(x_1, ..., x_k) = 0 (expanded using * and +).

Determining whether or not SELECT * FROM t WHERE p(x_1, ..., x_k) = 0 is equivalent to SELECT * FROM t WHERE false is determining whether or not p(x_1, ..., x_k) has some assignment of integers $x_1, \dots, x_k$ such that $p(x_1, \dots, p_k) = 0$; thus if we were able to determing the equivalence of SQL queries, we would be able to determine the satisfiability of Diophantine equations.

Because the satisfiability of Diophantine equations is undecidable, so must this query equivalence problem.

The above doesn't rely on any particularly interesting features of SQL -- it certainly doesn't rely on any tricky "Turing complete" features of many SQL implementations -- it relies solely on the embedded ability to evaluate expressions involving integers. That means this is unfortunately rather unenlightening, but it also makes it hard to pare down SQL to something that won't immediately have undecidability creep in.

Like any theoretical result on decidability would, this does require arbitrary precision integers are supported. While I don't know of any popular SQL implementation that truly supports unbounded integers, PostreSQL for one documents arbitrary-precision integers that support at least 1000 digits of precision, which is likely "large enough" to say an abstract model of SQL supports unbounded integers.

It might be worth analyzing a SQL without any support for arithmetic operators like + and *, though I think it might be possible to emulate both + and * using SUM and JOINs; even without SUM I think it may be possible.


Determine in which class $L=\big\{\langle M_1,M_2,w\rangle\mid M_1,M_2\text{ are TM and }L(M_1)\cap L(M_2)=\{w\}\big\}$

No. It is not correct.

For example, suppose that $x=0$, $w=00$, $L(M_1)\bigcap L(M_2)=\{x,w\}$.  If $M_1(x)$ or $M_2(x)$ takes more than $|x|=1$ steps to answer "yes", then your proposed algorithm will failed.


Finding the minimum subset within a cycle

Using Kaveh's reduction in this related question, we only have to solve the case where the given intervals cover the entire circle $[c,d]$.

Here's an algorithm that almost calculates the optimum, in $O(n\log n)$. Replace each interval $[a,d] \cup [c,b]$ by the two intervals $[a,d],[c,b]$, and now solve the original problem. Let $O$ be the optimum of the original problem, and $S$ be the optimum of the new problem. I claim that $S-1 \leq O \leq S$.

First, given any solution to the new problem, we can find a solution to the old problem with the same cost, showing that $O \leq S$. For the other direction, take some optimal solution. If it doesn't use any split interval, then $S = O$. Otherwise, let $I_\min$ be the split interval minimizing $a$, and let $I_\max$ be the split interval maximizing $b$. If we drop all other split intervals, then whatever remains is still a cover of the circle. If $I_\min \neq I_\max$ then $S = O$, and otherwise all we know is that $S \leq O+1$.

It's plausible that this algorithm can be adapted somehow to actually find the optimum. (Most algorithms that work on interval graphs also work on circular-arc graphs.)


Need Help Understanding MST Cutset Formulation

The first constraint makes sure the induced subgraph remains connected : there must be an edge between every pair of subsets of $V$ ; or in terms of graph theory,  for every cut, at least one edge must cross the cut. For example, if $S=\{a\}$, the constraint is
$$
\sum_{(u,a)|u\neq a} x_{ua} \ge 1
$$
and this imposes that $a$ does not end up alone.

The second constraint makes sure you end up with $n-1$ edges, which is a characteristic of a tree.


Fast computing of a matrix power for large integer values in C++

Since your matrices are small $(50 \times 50)$, you  can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$.
Write $t$ in binary so that  $t = 2^{k_1} + 2^{k_2} + \dots + 2^{k_\ell}$.
Then $M^t = \prod_{i=1}^\ell M^{2^{k_i}}$. Moreover, for $k_i \ge 1$  you have $M^{2^{k_i}} = \left( M^{2^{k_i - 1}} \right)^2$, so you need at most $O(\log t)$ matrix multiplications.
Here is a pseudocode where "&" denotes "bitwise and" and "~" denotes "bitwise not":
Power(M, t):
  if(t & 1):        //Handle odd values of t (this saves a multiplication later)
     R = M;
     t = t & ~1;    //Clear the least significant bit of t
  else:
     R = I;

  i=1;
  B=M;                //B will always be M^i, where i is a power of 2
  while t!=0:
     i = i*2;         //Advance i to the next power of 2
     B = B*B;         //B was M^(i/2) and is now M^i

     if(t & i):       //i is of the form 2^j. Is the j-th bit of t set?
        R = R*B;      //Multiply the result with B=A^i
        t = t & ~i;   //Clear the j-th bit of t

  Return R;


What do you call a "non-probabilistic Bloom Filter"?

This is related to the notion of "fast path, slow path" from computer systems.  In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first test whether the input falls into that case and if so solve it and return immediately; otherwise, fall back to the complex computation.  For instance, the slow path might have to handle corner cases and difficult situations that arise only rarely.


Algorithm for commonalities across related objects

I came up with the idea of hashing when I just started looking at this, but seems that the range of the input data is not given, so it's very hard to decide on a specific algorithm.

However, there's another idea:

During input, create a table for each id, record all the linkedId of it, and the sum of linkedIds of it.
After recording all the input, you have tons of ways to find those ids whose sum of all linkedIds are the same, put them into groups, like an $O(n^2)$ brute-force or some $O(n\log(n))$ discretization. This step is a kind of classification, all ids in a group may not be the equivalent, but equivalent ids must be in the same group
Traverse through all groups, find those equivalent ids

This is expected to be a lot more efficient than brute-force. Hope it can help you.


"P may collapse" vs. Time hierarchy theorem

The polynomial hierarchy is not $\mathsf{DTIME}(n^k)$ for various $k$, but rather a polynomial time version of the arithmetical hierarchy.


Solving $T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n$ without the Master Theorem

Let's suppose $n=3^k$. Then we have:
$$T(n)=3^kT(1)+2n\log \frac{n^k}{3^{k-1}\cdots3^0}=n+2n\log 3^{k^2-\frac{k(k-1)}{2}} =\\
=n+2n\log n \cdot \frac{\log_3 n+1}{2}   $$
Hope it helps.


Analyze undirected weight graph and generate two sub graphs

Sorry about the poor explanation, but after a lot of help here, Stack Overflow and Math Exchange and a lot of reading, I finally understood that what I'm actually trying to do is:

Given a Graph G, obtain two disjointed trails of approximately the same size so that every edge is visited by one of those trails.

Thanks to everyone!


The set of all eventually periodic words is not Buchi Recognizable?

Note that every non-empty Büchi recognizable language contains at least one eventually periodic word and that the class of all Büchi recognizable languages is closed under complement. Thus, if the language $L = \{w \in \Sigma^\omega \mid w \text{ is eventually periodic}\}$ was Büchi recognizable its complement $L^C$ is also Büchi recognizable but of course contains no eventually periodic word contradicting the first fact I stated.


How does a buffer overrun corrupt the return address?

When your code calls a function, the called function usually allocates memory for its variables, just before the memory where the return address is stored (the address of the caller).

Let's say you have an array int a[100], and a double variable x. The compiler may quite reasonably allocate memory for x either just before or just after the memory for a. In the first case, setting a [-1] = 100; a [-2] = 1000; will likely change x. In the latter case, setting a [100] = 100; a [101] = 1000; will do the same thing. Trying to store into an array, using an index that is too small or too large, is called a "buffer overflow".

Now if you store a [102] = 0; or a [103] = 0; then chances are that this overwrites the memory where the caller's return address was stored. And if the function tries to return, the processor will start running code at the address that you stored into a [102] and a [103] with all kinds of negative consequences.


Distribution of IEEE 754 single precision floating point over number line

The idea is that a (not denormalized) floating point number is stored as
$2^x \times 1.m_0 \ldots m_{k-1}$ (in binary),
where $x$ is the exponent and $m_0 \ldots m_{k-1}$ is the mantissa of length $k$. Two successive numbers with this exponent differ by $2^{x-k}$, since this minimal difference is $2^x \times 0.0\ldots01$, with $k-1$ zeroes after the dot. The minimal and maximal differences (among not denormalized numbers) are attained for the minimal and maximal $x$.


Constant-depth threshold circuit for $\mathrm{PP}$

Yes, Anuj Dawar and Yuguo He claim in their paper titled "Parameterized Complexity Classes uder Logical Reductions" [1] that $\mathrm{SAT}$ is $\mathrm{NP}$-complete, even under quantifier-free first-order projections, which are reductions even weaker than $\mathrm{AC}_0$ reductions.

The same result also holds true for $\mathrm{PP}$ with $\mathrm{MAJSAT}$.

First-order projection can be done in constant depth.

All that is left to be shown is proving that $\mathrm{MAJSAT}$ can be decided in constant depth. Indeed, our threshold circuit for this language has an overall $\mathrm{MAJ}$ gate as the output gate that receives the result from exponentially many result of every possible assignment to the variables of the given 3-$\mathrm{SAT}$ formula. And for each variable assignment, we can, in constant depth, evaluate the formula with this assignment.

[1] Anuj Dawar, Yuguo He, Parameterized Complexity Classes uder Logical Reductions, https://www.cl.cam.ac.uk/~ad260/papers/mfcs09.pdf


Proof that no O(n) multiplication algorithm exists

There is a conditional $\Omega(n\log n)$ lower bound due to Afshani, Freksen, Kamma, Green Larsen, Lower Bounds for Multiplication via Network Coding.


how to solve simultaneous equation with O(n)

As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$.

We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ again that are bigger than our current $j, k$ since $A$ is sorted, thus our $j, k$ can only ever decrease giving $O(n)$ instead of $O(n^2)$.

In Python:

i = 0
j = k = len(A) - 1

while i < len(A):
   while j >= 0 and -A[i] < 4*A[j]:
       j -= 1

   while k >= 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None


Is there any algorithm can solve the following equations efficiently?

One way, which is numerically probably a bad idea, is to use Newton's identities. They give the value of the elementary symmetric functions given the power sums, and from the elementary symmetric functions you can construct a polynomial whose roots are the answers to your problem. Let $p_k = k! c_k$, and let $e_k$ be the sum of all $\binom{n}{k}$ products of $k$ variables out of $x_1,\ldots,x_n$. Newton's identities state that
$$ ke_k = (-1)^{k-1} p_k + \sum_{i=1}^{k-1} (-1)^{i-1} e_{k-i} p_i. $$
Using these identities, you can compute $e_1,\ldots,e_n$. Now consider the polynomial
$$ P = x^n + \sum_{i=1}^n (-1)^i e_i x^{n-i}. $$
The unique solution to your equations are the $n$ roots of $P$.
As an example, let's do the case $n = 2$. We have $e_1 = p_1$ and
$$ 2e_2 = -p_2 + e_1 p_1 = p_1^2 - p_2. $$
The polynomial $P$ is therefore
$$ x^2 - p_1 x + \frac{p_1^2-p_2}{2}. $$
For $n=3$ we calculate additionally
$$ 3e_3 = p_3 - e_1 p_2 + e_2 p_1 = p_3 - p_1 p_2 + \frac{p_1^2-p_2}{2} p_1 = \frac{2p_3 - 3p_1p_2 + p_1^3}{2}. $$
The polynomial $P$ is therefore
$$ x^3 - p_1 x^2 + \frac{p_1^2-p_2}{2}x - \frac{2p_3 - 3p_1p_2 + p_1^3}{6}. $$


Upper and lower tangent line to convex hull from a point

Let's assume that the convex polygon $P$ is defined as an ordered list $(p_0,p_1,...,p_{n-1})$ of points, and for each such point $p \in P$ we are able in $O(1)$ time to find a previous point $Prev(p)$ and a next point $Next(p)$ according to this order, taking into account that:
$$Prev(p_0)=p_{n-1}$$
$$Next(p_{n-1})=p_0$$
The binary search over this list is very similar to a binary search over a regular array - on each step you have a $p_{left}$ point, a $p_{right}$ point and a $p_{mid}$ point. You check some condition on the $p_{mid}$ point and then choose a $[p_{left},p_{mid}]$ interval or a $[p_{mid},p_{right}]$ interval for the next step.
The condition you want to check is the following one. In order for the $p_{mid}$ point to be the tangential point for all lines going through the query point $S$, both neighbors of the $p_{mid}$ point must be on the same side of the line, connecting the point $S$ and the $p_{mid}$. You'll have to choose, which side of this line is right and which side is wrong - this will define, which tangent line you'll get (upper or lower). So, if the previous point $Prev(p_{mid})$ is on the wrong side, then you choose the left interval. Similarly, if the next point $Next(p_{mid})$ is on the wrong side of this line, then you choose the right interval for the next step. This algorithm will stop on one of two tangential points if and only if the point $S$ is located outside of the polygon $P$.
The algorithm doesn't need any preprocessing of the convex polygon $P$ and nevertheless finds tangential points for any query point, located outside of the polygon, in $O(\log n)$ time.


Converting regular language to regular expression by replacing commas with union

Regular expression represent one way of describing regular languages, but there are other notations which you can use to depict such formal languages. E.g. you can use the standard grammar notation ( $S \to aB, B \to bC, \ldots $) or you can use a nondeterministic finite automaton and therefor a deterministic finite automaton to describe a regular language.

Both of your given examples are of the notation-type "regular expression", which can have multiple forms. An 'or' can be e.g. represented as union ($u$), by square brackets ($[abc]$) or maybe a comma like you used in your first example. This is just a matter of what convention you agree to.


Is it possible to decide if a given algorithm is asymptotically optimal?

Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage.

We reduce the halting problem on blank tape to your problem about running-time optimality.

Let $M$ be a given Turing machine. Let N be the following Turing machine:

$N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES.

There are two cases:

If $M$ does not halt on blank tape, the machine $N$ will run for $\Theta(2^n)$ steps on input $n$. So its running time is $\Theta(2^n)$. In this case, $N$ is obviously not optimal.
If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.

In short:

$$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$$

Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable.

A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses.

Even a stronger statement is true: we can't decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).


No. The first language is non empty (e.g., it contains the word "ba"), while the second language is empty.


"Deterministic" means "if you put the system in the same situation twice, it is guaranteed to make the same choice both times".

"Non-deterministic" means "not deterministic", or in other words, "if you put the system in the same situation twice, it might or might not make the same choice both times".

A non-deterministic finite automaton (NFA) can have multiple transitions out of a state.  This means there are multiple options for what it could do in that situation.  It is not forced to always choose the same one; on one input, it might choose the first transition, and on another input it might choose the same transition.

Here you can think of "situation" as "what state the NFA is in, together with what symbol is being read next from the input".  Even when both of those are the same, a NFA still might have multiple matching transitions that can be taken out of that state, and it can choose arbitrarily which one to take.  In contrast, a DFA only has one matching transition that can be taken in that situation, so it has no choice -- it will always follow the same transition whenever it is in that situation.


Recurrence relation (not solvable by the master theorem)

Wikipedia has a slight extension of the master theorem which covers your case: case 2b here.
For the recurrence $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log_b a}/\log n)$, it gives $T(n)=n^{\log_b a}\log\log n$.


Find pair of complex numbers with maximal sum

Observations:

The pairing mechanism creates the Minkowski sum of the two sets.
The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls. (See e.g. previously linked Wikipedia article).
Given a set of points in the plane, the point furthest from the origin must be a vertex of the convex hull.
The convex hull of a set of $n$ points can be found in $O(n \lg n)$ time. (In fact in $O(n \lg h)$ time, where $h$ is the number of points on the convex hull).

  For two convex polygons P and Q in the plane with $m$ and $n$ vertices, their Minkowski sum is a convex polygon with at most $m + n$ vertices and may be computed in time $O(m + n)$ by a very simple procedure...

given in the Wikipedia article.

Combining these observations gives an $O(n \lg n)$ algorithm.


Your assumptions are wrong, and I suggest picking up a textbook on quantum computing.

The state of $n$ qubits can be described by $2^n$ complex numbers $\varphi_x$ whose squared magnitudes sum to 1. You can think of these $2^n$ complex numbers as indexed by $\{0,1\}^n$. When you "read" the $i$th qubit (the technical term is "measure"), what happens is that with probability $p_b := \sum_{x\colon x_i=b} |\varphi_x|^2$ you see the value $b$. Moreover, from now on the value of this qubit will always be $b$ (unless you apply quantum operations to it). The rest of the state is updated accordingly: $\varphi_x := 0$ if $x_i \neq b$ and $\varphi_x := \varphi_x/\sqrt{p_b}$ if $x_i = b$.


What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?

Go to a website selling computers (or phones). Check how many cores the computers have, and whether they support hyper threading. So there you get the number how many threads can actually run at the same time.

On the other side, your software can use a single active thread, or 100 active threads. Some software can actually make use of many threads, other software can't. Your computer however can run more than one software at the same time, so there will be more active threads.

So everything is M:N. M = 1 or N = 1 is possible but rare. If M < N then some cores are unused and might as well not be there. If M > N then at any point in time, at most N of the M threads are running. And M changes all the time.


If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

There's no clear relationship, except that bigger inputs will tend to take longer.  What we call the "running time" in complexity theory is the number of basic operations but we just choose some set of basic operations and assume that they all have the same cost.  That's fine for asymptotic analysis but it doesn't correspond to the actual running time, as measured by a clock.

For example, imagine your algorithm consists of an initialization phase that takes one second, regardless of the input, plus a quadratic time loop that takes $n^2$ milliseconds to process $n$ items.  Complexity theory just says that your algorithm has running time $\Theta(n^2)$, so doubling the size of the input multiplies the running time by four.  Asymptotically, this is true but, if you double the input size from $10$ to $20$, the running time only changes from $1.1\,\mathrm{s}$ to $1.4\,\mathrm{s}$, which is nothing like a factor of four (it's less less than $30\%$).

Another problem is that complexity theory doesn't model the sheer... well, complexity of modern computers.  A simple example: suppose your quadratic algorithm runs in half a second on an input of length $\ell$.  Great, it's going to run in just over half a second on a similar input of length $\ell+1$, right? Maybe.  Or maybe it takes ten seconds because your data doesn't fit in the cache any more.