Efficiently labelling training data in machine learning

You can't.  You can't squeeze blood out of a stone.  There's no such thing as a free lunch.  You can't get something from nothing.  If you want labelled images, you will need to label them yourself, or find some existing data set that comes with labels.  There are no shortcuts.

Yes, this is tedious and labor-intensive.  This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, we often spend the majority of our time (or more!) just assembling data sets, and only a small fraction on the actual learning algorithms themselves.

I know you could do various shortcuts, like trying to write a quick program to label them.  But if that program makes mistakes, you'll just be training your machine learning algorithm to make the same mistakes -- so that's not actually helpful.

If you want to reduce the amount of labelling effort, there are ways to reduce the effort -- but still they will require a significant amount of manual labelling.  Nothing comes for free.  For instance, you can use active learning algorithms to identify which instances to label.  A simple example of that is to manually label a few hundred images as your initial training set, train a classifier, apply it to all remaining images, pick out the 20 images that the classifier is least confident on, manually label those 20 images, add them to the training set, and repeat.  (This is an application of uncertainty sampling.)  There are other, more sophisticated methods out there as well.

Another plausible approach is to somehow cluster the images, then manually label a few images from each cluster.  This has issues, though, as you'll need some reasonable way to cluster the images, and that might be a non-trivial task.  (One possible approach for clustering is to take some existing, pre-trained ImageNet classifier -- e.g., VGG, Inception, ResNet, etc. -- throw away the last layer or last two layers, and use the output before those layers as the input to some clustering algorithm like k-means.  Doing k-means clustering directly on the raw image probably won't work well, but if you do it on the vector of activation values at some deep layer near the end of a good pre-trained classifier, then you might get better results.)

Finally, we often use data augmentation to make the classifier more robust.  For instance, for each image in the training set, we might generate 10 more copies, where each copy is rotated or translated or cropped by a random amount, and add that to the training set.  This tends to help make the classifier more robust to changes in orientation or pose -- but it doesn't give you something for nothing.  You still need a large training set that contains many different kinds of tables.


Search a preprocessed text with online queries

By building a suffix trie.

If you wish to preprocess the search query, then there is this algorithm by Boyer–Moore, whose complexity is believed to be linear after applying Galil Rule (details in the same page).

Other than that, if you can preprocess the whole text before hand and construct a Suffix Trie, then you can achieve many things. But the main limitation is it requires a lot of space.

See Suffix Trees and the lecture from MIT (Complete List)

See also Popular String searching algorithms.


How to generate an instance for an NP_hard proof, where each element has two inputs?

As you noted yourself, the problem in general is NP-hard.  You can reduce from Partition by letting due date $d = B = (\sum X)/2$, where $X$ is the input to Partition, and let there be two processes.

The proof is quite straight forward and left as an exercise.


Tried to derive the Z combinator and instead derived another

If I inline (u => (f)(n => u(u)(n))) into (u => u(u)) I get:
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))

Which is exactly the Z-Combinator.
From wikipedia:
let Z = f =>
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

My derivation:
let fix = f =>
    (u => f(n => u(u)(n)))
    (u => f(n => u(u)(n)))


how did they get this answer for the words that don't have bba and abb?

The textbook's answer does appear to be incorrect, as you note it does not generate $abb$ (and just to rule out an alternative interpretation of the exercise - "all strings that include neither $abb$ nor $bba$ - it does generate $bba$).

However your answer is also incorrect unfortunately - it doesn't generate $bba$.

There are a couple of reasonably sensible ways to get a correct answer (of course there's always many many techniques, and different people prefer different ones).

The first is the "intuition" approach, break the problem into the two parts, "the strings that don't have $bba$" and "the strings that don't have $abb$", then combine. With this method you have to then think about how such strings would look, and convince yourself that you haven't missed any cases.

The very formal method is to construct the expression from smaller, verifiable building blocks. In this case, we can easily construct a DFA for the strings that do contain $abb$ and one for the strings that contain $bba$, then we can use the intersection construction to get a DFA for the intersection of the two languages, take the complement DFA, then convert this to a regular expression.

What they seem to have done, and messed up or made a typo in one part, is the formal-but-not-quite-as-silly-as-option-2 method, where we make the two small DFAs, take their complements separately, convert each to a regular expression, then combine. I'll do the half that they seem to have gotten wrong (the bit that allows $abb$ but not $bba$, which is the first half of their expression).

The initial DFA is:

Taking the complement we get:

This second DFA recognises all the strings that don't contain $bba$. Now we convert this to a regular expression using the normal state elimination algorithm. If you haven't seen this yet, it will appear shortly in whatever course you're studying, or you can look over this explanation, but for the moment (and for the sake of keeping this answer on track!) hopefully it's acceptable that there is an algorithm for doing this conversion. In principle this algorithm can result in slightly different regular expressions depending on the order you eliminate the states, so if you have a go at it, you may not end up with quite the same regular expression (if you try one particular order, you get a real mess).

After all that we get the regular expression:
$$
(a+ba)^{\ast}b^{\ast}
$$

If we then proceed and do the DFA for strings containing $abb$, take its complement and derive the regular expression, we get (picking the right elimination ordering) the same as their second half, $b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$, and combine them and get the final answer:
$$
(a+ba)^{\ast}b^{\ast}+b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}
$$


Enumerate all non-isomorphic graphs of a certain size

Probably the easiest way to enumerate all non-isomorphic graphs for small vertex counts is to download them from Brendan McKay's collection. The enumeration algorithm is described in paper of McKay's [1] and works by extending non-isomorphs of size n-1 in all possible ways and checking to see if the new vertex was canonical. It's implemented as geng in McKay's graph isomorphism checker nauty.

[1]: B. D. McKay, Applications of a technique for labelled enumeration, Congressus Numerantium, 40 (1983) 207-221.


How to Apply Elementary Axioms from Kleene Star to an Inequality

I assume that in your definition $a \leq b$ iff $a + b = b$.

First, note that if $a \leq b$ and $b \leq a$, then $a = a + b = b + a = b$.
Therefore, in order to show that $a = b$, it is sufficient to show that $a \leq b$ and $b \leq a$.

Now, you want to show that $(a + b)^\ast = (a + ab + b)^\ast$. As explained in the previous paragraph, it is sufficient to show that inequalities with $\leq$ in both directions hold ("[...] for them to be equal the sets should be contained in each other").

The inequality $(a + b)^\ast \leq (a + ab + b)^\ast$ is almost trivial:

$$(a + b) + ab = a + ab + b $$

therefore $(a + b) \leq (a + ab + b)$, and by monotonicity (your ER-3), it thus holds

$$(a + b)^\ast \leq (a + ab + b)^\ast.$$

The other direction is a bit trickier.

By monotonicity (ER-2), (def-$\leq$), (Ax-1):

$$a(a + b)^\ast \leq (a + b)(a + b)^\ast \leq 1 + (a + b)(a + b)^\ast \leq (a+b)^\ast$$

Analogously, $b(a + b)^\ast \leq (a+b)^\ast$.

From both previous statements, again using monotonicity (ER-2):

$$ab(a+b)^\ast \leq a(a+b)^\ast \leq (a+b)^\ast.$$

To summarize: so far, we know that $a$,$b$ and $ab$ are all $\leq (a+b)^\ast$.

Now, observe that from (ER-1), it follows that if $x \leq w$ and $y \leq w$, then $x + y \leq w + y \leq w + w = w$. Thus, from $a\leq (a + b)^\ast$, $ab \leq (a + b)^\ast$ and $b \leq (a + b)^\ast$, you obtain:

$$(a + ab + b)(a+b)^\ast = a(a+b)^\ast + ab(a+b)^\ast + b(a+b)^\ast \leq (a + b)^\ast.$$

Since additionally $1 \leq (a+b)^\ast$ (directly from Ax-1), you obtain:

$$1 + (a + ab + b)(a+b)^\ast \leq (a+b)^\ast.$$

With (Ax-3) it follows:

$$(a + ab + b)^\ast = 1\cdot(a + ab + b)^\ast \leq (a + b)^\ast$$

Thus, both inequalities hold, hence we get the equality.

You cannot simply "remove" $^\ast$, nothing is told about "inverse" in the definition of a Kleene algebra. I also don't know what you mean by "$\ast$-height".


Let u and v be two strings. What about the reverse order of their concatenaited string?

No, $(u\cdot v)^R\not=u^R\cdot v^R$ more often than not.

For example, if $u$ is the string $race$ and $v$ is the string $car$. Then  $$(u\cdot v)^R=(racecar)^R=racecar$$
while
$$u^R\cdot v^R=(race)^R(car)^R=ecarrac.$$

Here are a few related exercises. All variables stand for strings.

Exercise 1. If $u$ or $v$ is the empty word, then $(u\cdot v)^R=u^R\cdot v^R$.

Exercise 2. If $u$ or $v$ are words of length 1 such that $(u\cdot v)^R=u^R\cdot v^R$. Then $u=v$.

Exercise 3. If $u=u^R$ and $v=v^R$, can we guarantee $(u\cdot v)^R=u^R\cdot v^R$?

Exercise 4. Prove that $(u\cdot v)^R=v^R\cdot u^R$.


Terminology for property of recursion definitions

This sounds to me like a Catamorphism, specifically, a Tree Fold. If you're familiar with the foldr list function of functional programming (I believe Python has this too), this is also a catamorphism.

In general, the categories functions are divided into like this are called recursion schemes. The classic introduction to them is Bananas, Lenses, Envelopes and Barbed Wire. If you're familiar with Haskell, the modern translation guide might help.

Some more information is provided in the Origami Programming paper.


Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\epsilon$, the accepting states to be the classes of the words in $L$. For each pair of states $s_1,s_2\in \Sigma^*/\equiv_L$ and letter $t\in\Sigma$ we will have the value of the transition function $\delta(s_1,t)=s_2$ if and only if for a word (equivalently, for all words) $x\in s_1$ we have that the word $xt\in s_2$.
(b) The examples that you showed work. The classes of the words $ab^n$, for $n=1,2,...$ are all different. In fact, if $x=ab^m$, $y=ab^n$ and $m>n$, then taking $w=ab^nab^n$ we get that $xw\not\in L$, while $yw\in L$. Therefore, $x\not\equiv_L y$.


If L is context free and R is regular then R – L must be context free?

Context-free languages are not closed under complement. This is a fairly well-known result.


P/NP - Polynomial Reduction vs Certificate

Problem A is in NP if:
  B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A

Not quite right. The class P is a subset of NP anyway, and hence A is already NP if it is in P. The question is whether A is in P or not.

By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. Assuming B is in NP gives no useful information about A, since it is possible that B is in P as well (remember that P $\subseteq$ NP). However, assuming (and probably that is what you meant), that B is NP-Hard, then, by reducing B to A, we prove that A is also hard for NP class, and hence unless P=NP, the problem A is not in P.

Now back to the question. What we know so far, P $\subseteq$ NP. There are more classes above NP like EXP and under P like L for example. Which means,
$$L \subseteq P \subseteq \mathit{NP} \subseteq \mathit{EXP}.$$
Check the link for more information about the classes. However, one characterization of problems in NP, is that they all admit a certifier, that can in polynomial time in the size of the input, say if the given instance is a yes instance. For example, for travelling salesman, which is an NP-Complete problem, the certificate is a path. You can clearly certify it, by checking if it visits all cities and each city exactly once and return to the beginning. Since P $\subseteq$ NP the same works for P problems. Like shortest path. given a shortest path between two vertices, you can certify it it is a shortest path. For example, the certifier can compute a shortest path in polynomial time and compare the lengths.

Now the interesting part about certificates, is to certify if a problem admits a certificate for the negative answer. That means, given an instance and a certificate, the certifier can tell in polynomial time, if the instance is not in the language. Problems that admits such a certifier belong to the class co-NP. It is believed that NP $\neq$ co-NP unless P = NP. The class P belongs to the intersection of both classes and hence we can certify both negative and positive answers in polynomial time.

Summary

Reducing $A$ to a polynomial problem proves that it is solvable in polynomial time.
Reducing an NP-Hard problem to $A$, proves that $A$ is NP-Hard and probably not in P. In this case, even if the problem is in NP and hence is NP-complete, we can only say about $A$ that it is NP-hard, we still do not not if it is in NP.
A problem is in NP if there is for each instance that belongs to language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
A problem is in co-NP if there is for each instance, that odes not belong to the language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
The class P belongs to the intersection of P $\cap$ co-NP.


Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument.

Say that the target is zero. If the first access to the array is left of center, answer $-1$, and mentally set the elements to the left to be $-2,-3,\ldots$. If the first access is right of center, answer $+1$, and mentally set the elements to the right to be $2,3,\ldots$.

Suppose the first access was right of center, say position $i$, and consider the second access. If it it to the right of the first access, then you already know what to answer. Otherwise, there are two cases. If the accessed position $j$ is less than $i/2$, answer $-1$ (and fill in elements to the left). If it was more than $i/2$, answer $+1/2$ (and fill in elements to the right up to position $i$).

Continuing in this way, at each step the number of positions which could contain the target element is at most halved at each step. Finally, when only one element is still at stake, without querying it, the algorithm cannot know for sure whether the array contains the target element or not. It takes $\log_2 n$ steps to reach this step.

The foregoing actually shows that binary search is optimal for searching a sorted array.


Relationship of algorithm complexity and automata class

Here are some known results:

$\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.
$\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.
$\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.
$\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.
The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.
Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.


Show that checking if there exists word not containg patterns from list is in $PSPACE$

i think you are in the right direction, i will try to expand your answer a bit.
first we want to prove that a problem is in PSPACE, which means there exists a TM that solves the problem with a polynomial space tape.

let M be a NTM that receives $w=<Σ,list>$ and does the following algorithm:

1) guess word of length $i=1...k$ given the $Σ$.this can be done in polynomial space depending on our input, since $O(k)=O(|w|)$ space.

2) check if there exists a pattern in the list which matches any of the strings of the word. this phase needs describing how exactly it can to be done, but it can certainly be done in polynomial space of $|w|$. hint: use 2 special characters to check each sub-string at a time.

and now since $PSPACE=NPSPACE$ (as you mentioned) ,if there exists a NTM that solves the problem in Polynomial Space tape we can conclude the problem is in $PSPACE$ and your solution was in a good direction.


Confusing method of proving PSPACE-completness

This technique is also known as computation history method. Given a Turing machine $M$ you (or another TM $M'$) inspect its computation "flow" or "history" configuration by configuration. You can think of TM configuration as snapshot of the tape content plus machine's state at some particular time. Every step of a TM generates a new configuration. The set of all that configurations is a computation history. If computation halts then that set is finite.

UPDATE: (on David Richerby comment) The following paragraph may be irrelevant to the question since I overlooked "sequence (of polynomial length) of configurations" in OP which is different from "the sequence of configurations where each is of polynomial length".

Polynomial length requirement:  because you want to prove PSPACE membership, maximum number of used tape cells must be polynomial. That's why an accent made on polynomial length.

Transitions betweens configurations in sequence are legal: you want be sure that machine's transitions between states were really made according to the machines's transition rules, otherwise the run is not legal. For example if a configuration $C_i$ differs from the configuration $C_j$ by 3 symbols (assuming a single tape TM) then you can say that transition is not legal, since the TM cannot change 3 symbols in a single step.

Also note that if one TM $M$ simulates another TM $M'$ then if $M'$ uses polynomial space then the whole simulation also uses polynomial space since simulation itself takes polynomial space.

Example of use of configurations:
Assume you know that a certain class of TM machines use no more than, say, $n$ cells of tape where $n$ is input size. Then halting problem for this class of TMs is decidable. Since a TM has finite number of states $|Q|$ and alphabets $|\Sigma|$, and since we that it uses at most $n$ cells, we simply can compute that the TM has at most $n|Q||\Sigma|^n$ configurations. Then you simulate that TM and check if at some point it repeats it's configuration then there must be an infinite loop and so it never halts (since the tape use is bounded!, the TM may not move infinitely move its head to the right and right symbols). The latter class is also known as linear bound automata.


NL Completeness Log space reduction $PATH$ to $EQ_{DFA}$

It is easier to think about a reduction from $\overline{PATH}$ (since it is NL-complete, this answers your question in the positive). You can treat the graph as a DFA, with initial state $s$ and a single accepting state $t$, and ask whether this automata is equivalent to some DFA for the empty language. Note that the alphabet here is not really important, and you could simply use fresh letters for each vertex.


Minimum number of nucleotides to force duplicate substring

The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is  repeated.

The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$.  The length of this sequence is $k^n=64$  symbols.  A de Bruijn sequence is a cyclic string such that every possible length-$n$ string occurs exactly once as a substring of it.  It is known that a de Bruijn sequence of length $k^n$ exists.  If we take the de Bruijn sequence $x_1 x_2 \cdots x_{64}$, then $x_1 x_2 \cdots x_{64} x_1 x_2$ is an ordinary string where every possible length-3 string occurs exactly once as a substring.  In particular, no length-3 substring of $x_1 x_2 \cdots x_{64} x_1 x_2$ is repeated.  There are also standard algorithms to find such a string.


How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

One possible way, is to use the pumping lemma, but one needs to be careful about the details. For simplicity let's discuss only the pumping lemma for regular languages (but I believe a similar method can be used when considering the CFL-pumping lemma).

Let's assume that $\langle A \rangle$ is a well-defined way to encode DFAs, that begins with describing the number of states, then list the transition for each state, etc.
Also assume that any string that is not "well formatted" under this encoding just describes a DFA that rejects all words.

Let $n$ be the pumping length.

Let $A=B$ be a $2^n$-state DFA that accepts all words. The encoding of $A$ begins with stating it has $2^n$ states, that is the first part is of length $\log(2^n)=n$ bits at least.

Now let's use the pumping lemma on $w=\langle A,B\rangle$ (which is longer than $n$, so the pumping lemma applies). We can split $w$ into $xyz$ such that $|xy|\le n$, that is, the part we pump "lies" in the part that describes the amount of states in $A$.
Now, we pump the word down. That is, consider the words $w'=xz$ which should be also in $L_E$ by the pumping Lemma.

However, we can interpret $w'$ as being $w'=\langle A',B\rangle$ where $A'$ is a malformed encoding (it begins with stating the DFA has less then $2^n$ states, but then it describes transitions of $2^n$ states, which is inconsistent with the claimed number of states).

Therefore, by our assumption $L(A')=\emptyset$ while $L(B)=\Sigma^*$. Thus, $\langle A',B\rangle \notin L_E$ and we reached a contradiction.


Counting number of sums from contiguous subarrays of an array

You almost surely can't get better than $O(n^2)$ in the worst case since the number of different sums can be in $\Theta(n^2)$.

Consider e.g. the array $[1,2,4,8,\dotsc, 2^n]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.

The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.


Can I compute closest split pair of points where distance is strictly less than delta

Yes, as you have observed, we can just compute pair of points whose distances are strictly less than $\delta$ in the "combine" step of the "divide-conquer-combine" algorithm, where we examine the minimal distance between the points to the left and the points to the right.

However, it is not enough to just compute the next 3 points.

The above graph, taken from CLRS, illustrates the original argument for 7 in the case of non-pairwise distinct points and for 5 in the case of pairwise distinct points. For the sake of clearer explanation, assume the central line $l$ is the vertical axis and $\delta=\delta_L=\delta_R=1000$. Let the strip consist of the area between the line $x=1000$ and $x=1000$, excluding those two lines. This strip contains only the points that are strictly less than 1000 away from the central line $l$. Suppose all distinct points in the strip in the ascending order of vertical coordinate are $s_0, s_1, s_2, s_3, s_4$.

Suppose we have verified that $d(s_0,s_i)\ge1000$ for $i=1,2,3$. Can we conclude that there is no point $s$ such that $d(s_0,s)<1000$?

No. It might happen that
$$\begin{align}\\
s_0&=(79,0)\\
s_1&=(-921,1)\\
s_2&=(999,500)\\
s_3&=(-999, 998)\\
s_4&=(79, 999)
\end{align}$$

Note that $d(s_0, s_4)= 999<1000$. In fact, $d(s_i,s_j)\gt1000$ for all $i$ and $j$ except $d(s_0, s_4)$.
$$\begin{align}
d(s_0, s_1)&=\sqrt{1000001}  \\
d(s_0, s_2)&=\sqrt{1096400}  \\
d(s_0, s_3)&=\sqrt{2158088}  \\
d(s_0, s_4)&=\sqrt{998001}  \\
d(s_1, s_2)&=\sqrt{3935401}  \\
d(s_1, s_3)&=\sqrt{1000093}  \\
d(s_1, s_4)&=\sqrt{1996004}  \\
d(s_2, s_3)&=\sqrt{4240008}  \\
d(s_2, s_4)&=\sqrt{1095401}  \\
d(s_3, s_4)&=\sqrt{1162085}  \\
\end{align}$$
So if we only compute the distance with the next 3 points, we will not find that shortest edge from $s_0$ to $s_4$ at the end of the algorithm.

The above counterexample shows that it is not sufficient to just compare 3 following points of every point in a middle strip only containing points strictly less than $\delta$ from the center line, even if we assume that all points are distinct.


Your problem is known variously as the lost cow problem or the cow-path problem, and is a standard example in online algorithms. The algorithm you describe is 9-competitive, which is optimal for deterministic algorithms. For randomized algorithms the competitive ratio is roughly 4.6. See for example a writeup apparently by Rudolf Fleischer.


Can a more powerful encoding of an input make an algorithm that is polynomial in the number of inputs become exponential?

There are $2^{n^2}$ labelled directed graphs on $n$ vertices.  Therefore, any such graph requires at least $n^2$ bits to represent it.  So, there is no hope for an encoding scheme that always uses at most $O(\log n)$ bits and can encode all graphs.

If you want to focus on labelled directed graphs with $n$ vertices and $m$ edges, there are ${n^2 \choose m}$ of them, which for $m \ll n^2$ is approximately $(e n^2/m)^m / \sqrt{2\pi m}$, and thus you'll need at least $m \lg (n^2/m) + O(m)$ bits to represent all of them.  Notice that this is $\Omega(m)$, so there is no hope for an encoding scheme that uses only $O(\log m)$ bits (or $O(\log(m+n))$ bits) and can represent all such graphs.

Of course, you can consider encodings that are logarithmically short, but they can only express a tiny fraction of all possible graphs.  Yes, if you wanted to represent the input in that way and solve a reachability problem on such a graph, then ordinary DFS would take time exponential in the size of the input.

Related: You might be interested in succinct data structures.


Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)

You don't need sophisticated data structures or algorithms to handle this case.   Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test whether $x$ is in $S$.  If you have a set $S$ and want to be able to query whether a point $x$ is in the set, then standard data structures suffice.  You don't need anything fancy: you can just store all the points of the set in a hashtable.  Queries just involve a lookup into the hashtable.  Or, you can use a balanced binary tree, or any other standard dictionary data structure.

The running time per query is basically expected $O(d)$ time or $O(d \lg n)$ time, where $d$ is the number of dimensions, if you choose the data structures appropriately.  This is essentially optimal, since even just reading the point takes $O(d)$ time.  In principle, you could get the running time down to expected $O(\lg n)$ time per query, if you cared, by taking a random projection onto a subset of $O(\lg n)$ coordinates, though I'm not sure whether it'll be significantly faster in practice.


Increasing an edge weight. Shortest time to recompute an $MST$?

If you're required to solve this "one-shot" problem, you're not allowed to perform any pre-processing, and you don't have any additional assumption, then a running time of $O(m)$ is the best you can hope for.
Indeed, consider an edge $e$ such that the fundamental cut $C_e$ induced by $e$ contains $\Theta(m)$ edges. All edges in $C_e$ have distinct weights that are strictly larger than the weight $w_e$ of $e$. For every value of $m$, it is easy to come up with a graph $G$ , an associated MST $T$, and and edge $e$ that satisfy these properties.
Suppose that there is a (deterministic) algorithm $A$ with a running time of $o(m)$. Then, when $A$ is run with inputs $G$, $T$, and $e$ there is at least one edge $f \in C_e$ whose weight is never read by $A$, and such that $f$ is not added to the new MST $T'$.
We can then run $A$ with inputs $G'$, $T$, and $e$, where $G'$ is a copy of $G$ in which the weight of edge $f$ has been set to $w_e$. The returned MST must still be $T'$, but this is incorrect since the new MST must include edge $f$.


how to reduce the time complexity of this code?

To get quadratic time, do the following:

Let $M = N(\text{NODE})$ be the neighbours of NODE in $G$.

Compute $G' = (G - \text{NODE})^3$, the 2nd power graph of $G$ without the vertices from NODE.

Then you do the following:  For every two vertices $u$ and $v$ in $M$, if $uv \notin E(G')$, add $uv$ to $G$.

This way you don't have to compute shortest_path anymore.


Is this solution to the dining philosopher's problem entirely valid?

The description of an altruistic philosopher given in this answer, that you quoted in your question, is slightly imprecise. What it really is going on is that:

  A possible approach for avoiding deadlock without incurring in starvation is to introduce the concept of altruistic philosopher, that is  a philosopher which drops the fork that it holds when it realizes that no one can eat because there is a deadlock situation.

So the actual condition for altruism is stronger than the one in your quote. Another important condition is that the fork that is put down by the altruistic philosopher is handed over to the philosopher waiting for it, e.g. by waking up the process that is waiting on the resource. (Otherwise the deadlock situation could actually reappear one instant later).

I apologize for the confusion I may have created in this regard. In my stackoverflow answer I simplified the actual model to convey the basic idea, but this left out some details that are important for "formally proving" the correctness of the solution.

Note: I don't have the time to write down a formal proof in this moment, so I will try to make a simple argument.

The pre-conditions are as follows:

Ph_i is the altruistic philosopher
Ph_i holds the left fork and the right fork is hold by its successor Ph_{i+1}
There must be a deadlock: every Ph_k is holding the left fork

the actions performed are:

Ph_i gives his left fork to its predecessor Ph_{i-1}

the post-conditions are as follows:

Ph_{i+1} becomes the new altruistic philosopher
Ph_{i-1} is now holding two forks and can eat
After eating, Ph_{i-1} puts down both forks.

The important invariant is that the predecessor of the altruistic philosopher is guaranteed to eat after a deadlock situation.

Given N philosophers, the round robin policy guarantees that each philosopher becomes altruistic exactly once in a sequence of N deadlocks.
Hence, each philosopher is guaranteed to eat (at least) once every N deadlocks (because it is the predecessor of an altruistic philosopher exactly once every N deadlocks).

This is, of course, the analysis of the worst-case possible outcome. Depending on the work-load, deadlocks may not arise so frequently and in this case each philosopher would have the chance to eat pretty much anytime it wants.

The naive solution to the dining philosophers presented in this answer is quite effective for the limited purposes of teaching Model Checking / Formal Verification techniques. However, I would not assume that it is the best engineering solution for practical situations because it requires one to detect a deadlock. Also, it may be hard to reduce practical problems to the simple scenario of the dining philosophers (e.g. there could be many more resources involved, the order in which resources are grabbed is not fixed, etc.).


Let $X$ be a random variable distributed uniformly over $[0,20]$. Your constraints imply
$$ \mathbb{E}[f(X)] \geq \frac{K}{20}, \qquad \mathbb{E}[g(X)] \geq \frac{Q}{20}. $$
We conclude that
$$ \mathbb{E}[f(X)+g(X)] \geq \frac{K+Q}{20}, $$
and so there is some point $x \in [0,20]$ such that $f(x) + g(x) \geq (K+Q)/20$. In particular, $R \geq (K+Q)/20$. This bound is tight, as shown by the functions
$$ f(x) = \frac{K}{20} \mathbf{1}_{x \in [0,20]}, \qquad g(x) = \frac{Q}{20} \mathbf{1}_{x \in [0,20]}. $$


Corner cases in the Interleave Lower Bound for BSTs

Leaves have no interleaving since they only have left sub-trees. Therefore you should apply the bound to all non-leaves, in which case the lemmas in the appendix go through. The resulting lower bound should be exactly the same.

The paper in question appeared first in a conference (FOCS) and then in a special issue dedicated to papers from the conference. Usually the conference reviewers are recruited to do the journal reviews as well, in the case of a special issue. This lowers the standard for reviews, since conference reviews are often not very exacting, and when reviewing the same paper for the journal, the reviewers won't bother to read the paper again. Exacerbating this phenomenon is the fact that the lower bound appears in an appendix.

The experts probably realized this inaccuracy right away, and knew that it wasn't a real problem, so didn't bother to comment about it if they noticed it at all.


Can CPU's 'shortcut' adding 0, multiplying by 1, and multiplying by 0?

Yes, there are processors which detect some kind of do-nothing operations, handle them specially so that they take less time than what they would take if they were handled naïvely.  In some cases, there are even recommended instructions to use for NOP (NOP are sometimes useful to align the code with a memory boundary, having NOP of various lengths available help the relieve the decoding part), the wikipedia page for NOP has a list which gives the normal meaning for some of them.

But

what you think as a do-nothing operation may not be one if you take into account things like resetting flags or the side effects of memory accesses -- and a processor should behave correctly in such matter;
I'd not rely on this as an optimization; more as an encoding trick or as a way to reduce the op-code pressure;  they are working when the operands are statically known to have no effect and in such cases, the code writer -- human or compiler -- should avoid the operation if possible;
detecting dynamically that the value has no effect is probably more costly than what would be gained by doing so.  That said, some relatively simple processors have operations which take a time which depend on the arguments (for arithmetic operations, don't think I've seen this for something else than integer multiplication and division, or for floating point operations)


Proving that a derived language is regular

Hint: while reading $w_1$, guess $w_2$ and gather enough information so that in the end you can decide whether $w_1 w_2 \in L$.


I'm trying to understand DFAs is my DFA correct in this question if not why?

This dfa is incorrect.
To start, a dfa MUST define a transition for every node, including accepting nodes.

Anyhow, the current dfa would have accepted the language L = { w | w is a series of 1's and a single 0 at the end }

To correct this, you need to add another transition from B to A when it recieves 1 and a transition from B to itself when recieving 0. This is required to allow strings with 0 in the middle to also be accepted


Understanding 2's complement multiplication using Booth's algorithm

So, it goes like this, we have Q = 0011 and Q-1 = 0 in the beginning.
At the start, we have

count = 4(Q0 Q-1) = (1 0)

so we perform the A←(A-M) operation, according to the figure each time when we perform any operation in register A, we assume that its value is 00000000 for +M and 11111111 for −M. Performing A←(A-M) yields the first partial product

A = 11111111+00001001 = 11111001

Now, we have

count = 3(Q0 Q−1) = (1 1)

note here, when we have (Q0 Q−1) as (1 1) or (0 0), we'll just skip and put all 0s in the partial product by shifting it by 1 bit to the left (as we do in multiplication) as it's done in the book, which is the 2nd partial product

A = 00000000+00000000 = 00000000shifting it left by 1 bit, 00000000

Now, we have

count = 2(Q0 Q−1) = (0 1)

so we perform the (A←A+M) operation, which gives us the 3rd partial product

A = 00000000+00000111 = 00000111shifting it left by 2 bits, 00011100

Now, we have

count = 1(Q0 Q−1) = (0 0)

as mentioned above, we'll just skip and put all 0s as the 4th partial product

A = 00000000+00000000 = 00000000shifting it left by 3 bits, 00000000(this isn't illustrated in the figure 9.14(a))

after this operation count = 0 and then we'll sum up all the partial products as
   11111001 (1st partial product)
   00000000 (2nd partial product)
   00011100 (3rd partial product)
 + 00000000 (4th partial product)
-------------------
   00010101 (final product)

As we all know (00010101)2 = (21)10. That's what done in the figure 9.14(a), but shown in a different (or COMPACT) way as
   11111001
   0000000
 + 000111
-------------------
   00010101

Well, you can make it more compact like this:-
   11111001
 + 000111
-------------------
   00010101

But all of 'em will give you the binary representation of 21.


Decidability of CFG that accepts at least one odd length string

You cannot compute the intersection of two context-free grammars, at least not if you expect the answer to be another context-free grammar. The reason is that context-free languages are not closed under intersection (consider $a^nb^nc^m \cap a^mb^nc^n = a^nb^nc^n$).

However, context-free languages are closed under intersection with a regular language, and moreover there is an efficient algorithm that, given a context-free grammar $G$ and an NFA $A$, computes a new context-free grammar for the language $L(G) \cap L(A)$. You should use this algorithm in your second step.

Another problem with your solution is that it's not clear what you mean by "$L(O)$ contains only odd length strings". There are many languages that contain only odd length strings, for example the empty language. You want $L(O)$ to contain only and all odd length strings, that is, you want it to be the language of odd length strings.


Difference between BSP model and synchronous round model in distributed computing

In the CONGEST model of distributed computing, the topology of the computer network is a graph $G$. In each round, each node can send a message to each of its neighbours in $G$. Typically, we assume that $G$ is unknown, we interpret the structure of $G$ as the input, and we are interested in solving graph problems related to the structure of $G$.

This is the key difference. In BSP there is no underlying graph topology that limits communication; in CONGEST there is a graph that determines who can talk directly with whom.

However, things get interesting if we set $G = K_n$ in the CONGEST model. That is, the network topology is a complete graph on $n$ nodes. This way we arrive at a model called the congested clique.

The congested clique is very closely related to the BSP model. The key difference is the following:

Congested clique: the bandwidth constraints are on the edges; for each pair of nodes $u$ and $v$, in each round $u$ can send at most $b$ bits to $v$.
BSP: the bandwidth constraints are on the nodes; for each node $u$, in each round $u$ can send at most $B$ bits in total to all other nodes, and receive at most $B$ bits in total from all other nodes.

Clearly, any congested clique algorithm is trivial to simulate in the BSP model if we have $B = nb$, with only a constant overhead. [I am ignoring some issues related to the local computation.]

Lenzen (2013) shows that the converse is also true: any BSP algorithm can be simulated in the congested clique model if we have $B = nb$, with only a constant overhead.

In summary, if we eliminate $G$ from the CONGEST model, we basically arrive at the BSP model. Hence the graph $G$ is the only difference between the models.


Is impredicative Set consistent with the excluded middle?

I'm not an expert, but my understating was not that it it was inconsistent, but that it implies proof irrelevance. That is, if $s,t:T$ then $s=t$.

This gives many undesirable properties, like having $1=2$, but I'm not sure it actually implies bottom.
This answer had similar details.


Is there a proof that "undetectable" malware cannot be written?

For every malware, there exists some detector that will detect it.  (For instance, given a specific malware $M$, consider the detector that just checks whether its input is $M$ or not, and if it is, outputs "malicious".)

Conversely, Cohen's result shows that for every detector that classifies all benign samples correctly, there exists some malware that it won't detect.

So, there is an unavoidable arms race, if you want to try to detect malware statically.


Suitable choice for moderate-size square matrix multiplication?

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.


Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

There is a simple way to obtain a grammar for the language $L_{\geq} = \{a^ib^jc^k : i+j \geq k\}$ given a grammar for the language $L_= = \{a^ib^jc^k : i+j = k\}$. Starting with a grammar for $L_=$, change all rules mentioning $c$ to rules mentioning a new non-terminal $C$, and add the two productions $C\to c \mid \epsilon$.

Concretely, if we start with the following grammar for $L_=$:
$$
\begin{align*}
&S\to aSc \mid T \\
&T\to bTc \mid \epsilon
\end{align*}
$$
then the corresponding grammar for $L_{\geq}$ is
$$
\begin{align*}
&S\to aSC \mid T \\
&T\to bTC \mid \epsilon \\
&C\to c \mid \epsilon
\end{align*}
$$

Of course, this is not quite the restriction we were after. It is possible to modify the grammar for $L_{\geq}$ to a grammar for $L_{>} = \{a^ib^jc^k : i+j > k\}$ by "signalling" within the grammar that at least one $c$ was actually dropped. This requires duplicating some of the non-terminals and rules. Details left to you.

Another modification which will produce $L_{\geq}$ from $L_=$ replaces each $a$ by a non-terminal that generates $a^+$, and each $b$ by a non-terminal that generates $b^+$:
$$
\begin{align*}
&S\to ASc \mid T \\
&T\to BTc \mid \epsilon \\
&A \to Aa \mid a \\
&B \to Bb \mid b
\end{align*}
$$
Again we can use signalling to get $L_>$ rather than $L_{\geq}$. Details left to you.


Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

As others have pointed out in the comments, your definition of homomorphism is highly unusual. In particular, any function whose image is a single vertex is a homomorphism by your definition, thus trivializing the decision problem. The usual definition is as follows:

A homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $uv\in E(G)$ we have $\varphi(u)\varphi(v)\in E(H)$.

For the usual definition, the problem is known to be NP-complete for every non-bipartite $H$. The reference (according to Wikipedia) is Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110. (For bipartite $H$, on the other hand, there is a homomorphism if and only if $G$ is bipartite. Thus the decision problem is just bipartiteness of $G$, which is in PTIME.)

A few other notion are somewhat halfway between your definition and the usual one:

A strong homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $u,v\in V(G)$ we have $uv\in E(G)$ if and only if $\varphi(u)\varphi(v)\in E(H)$.
An embedding from $G$ in $H$ is an injective homomorphism, that is a homomorphism $\varphi$ such that for all $u,v\in V(G)$ with $u\not=v$ we have $\varphi(u)\not=\varphi(v)$.
An induced subgraph mapping is an injective strong homomorphism.

[EDIT]

For each of these variants, the problem is in PTIME for fixed $H$.
When injectivity is required, one can reject an instance if $|V(G)|>|V(H)|$, so only a finite set of graphs remains. For strong homomorphisms, we can have $\varphi(v)=\varphi(w)$ only if $v$ and $w$ have the same neighbours. Hence after some polynomial time preprocessing, we can again assume injectivity.


Derive a Context Free Grammar from a language

You're on the right track: $A$ recognizes $a^*$ (i.e. $\{a^n \mid n \ge 0\}$), $B$ recognizes $(ca)^*$ and $C$ recognizes $b^*$.

You need to assemble them correctly. $Ab | Bb | Cb | b$ recognizes words that are made of something recognized by $A$ followed by $b$, or of something recognized by $B$ followed by $b$, etc. A word in $L$ consists of a part that's recognized by $A$ followed by a part that's recognized by $B$, etc. So the pieces need to be concatenated together: $S_1 \to ABCb$.

$S_1$ recognizes $\{a^n (ca)^m b^{p+1} \mid m,n,p \ge 0\}$. This is too much: $L$ consists only of the words for which $n = p$ in this decomposition. Instead of defining $A$ and $C$ separately, you need to relate them. Whenever you put an $a$ on the left of the $B$ part, put a $b$ on the right.
$$ \begin{align}
  S_2 &\to B \\
  S_2 &\to a S_2 b \\
\end{align} $$
This constraints the number of $a$'s on the left to be equal to the number of $b$'s on the right. The words in $L$ actually have one more $b$ on the right. One way to add that $b$ is to append it at the end:
$$ S \to S_2 b $$
Another approach is to tack on the $b$ to the end of the $B$ part. $S$ and $S'$ recognize the same language, with slightly different parse trees.
$$ \begin{align}
  S' &\to B b \\
  S' &\to a S' b \\
\end{align} $$

To construct the parse trees, work out where each rule is applied to recognize the sample words.


Difference between CNOT and 2nd bit bitflip

The controlled NOT gate is represented by the matrix
$$
\begin{pmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
$$
In contrast, the matrix corresponding to negating the second bit is
$$
\begin{pmatrix}
0&1&0&0\\
1&0&0&0\\
0&0&0&1\\
0&0&1&0
\end{pmatrix}
$$


Let the $i$th item have profit $p_i$, and assume there are $n$ items passing by.
We can construct a graph where the nodes are pairs $(k, b)$ where $k$ is the number of timesteps, and $b$ is the number of items in our bagging area. We have $0 \leq k \leq x$ and $0 \leq b \leq c$.
Then, avoiding invalid nodes and/or nonsensical self-edges,

Add edges from $(i-1, b)$ to $(i, b + 1)$ with weight $-p_i$. These represent scanning an item.

Add edges from $(i, b)$ to $(i + 1, b)$ with weight $0$ for all $i$. These represent skipping an item.

Add edges from $(i, b)$ to $(i + b, 0)$. These represent bagging all scanned items.

Now we have a directed weighted acyclic graph, in which we can find the longest path in linear time. And the longest path between $(0, 0)$ and $(x, 0)$ precisely gives us the maximum profit (and following the path also gives us the steps used).
There are $O(cn)$ edges, and thus that is our complexity.


Counting the number of satisfying assignments to $F$ is at least as hard as determining whether there is a satisfying assignment.  (If the count is 0, there are no satisfying assignments; if the count is $\ge 1$, there is a satisfying assignment.)
For CNF formulas, testing whether there is a satisfying assignment is the SAT problem, which is a classic example of a NP-hard problem.
Counting the number of satisfying assignments of $F$ is at least as hard as determining whether all assignments satisfy $F$.  For DNF formulas, this is NP-hard, too.


Updated answer, based upon the revised question:

It sounds like resolution does exactly what you want, so I suggest you implement the resolution algorithm (combined with a subsumption test). Implementing this is a straightforward programming exercise which should take you only a few hours.

Original answer to an earlier version of the question:

I don't know if there are any dedicated solvers aimed at solving this problem, but one "poor man's approach" might be to implement this using an off-the-shelf SAT solver.  The approach will depend on what you are looking for: in particular, from what space consequences are allowed to come from.

A useful building block

Let me first observe that you can use a SAT solver to determine whether a candidate clause is indeed a consequence or not.  This will be a useful building block below.

Suppose $\varphi(x)$ is a formula, on boolean variables $x=(x_1,\dots,x_n)$.  Let $c(x)$ be a clause.  You can easily use a SAT solver to test whether $c(x)$ is a consequence of $\varphi(x)$.  In particular, you test whether $\varphi(x) \land \neg c(x)$ is satisfiable; if it is satisfiable, $c(x)$ is not a consequence, otherwise $c(x)$ is a consequence.

Finding consequences that are conjunctions of literals

If you want each consequence to be a conjunction of literals, you can find the minimal consequence using a SAT solver.  In particular, it suffices to use dumb search.  Focus on clauses that contain a single literal; there are only $2n$ possibilities for them.  Test each of them to see which ones are consequences (if any); this requires $2n$ invocations of the SAT solver.  In other words, for each variable $x_i$, test whether $x_i$ is a consequence, and also test whether $\neg x_i$ is a consequence.

Now you have a bunch of consequences, say the literals $\ell_1,\dots,\ell_m$.  Then $\ell_1 \land \dots \land \ell_m$ is also a consequence -- and it turns out it is the minimal consequence (minimal, among the space of conjunctions of literals).  This procedure requires $O(n)$ invocations of the SAT solver, so it should be pretty efficient.

Finding consequences that are disjunctions of literals

If you want to consequences to be disjunctions of literals, it's also possible to find all minimal consequences (minimal, among the set of disjunctions of literals), though it is somewhat more complex.  Let me build up the ideas step-by-step:

Finding a single consequence. You can use a SAT solver to find a single consequence of $\varphi(x)$ (not necessarily a minimal consequence).  Feed $\neg \varphi(x)$ to the SAT solver, and let it find a satisfying assignment, say $x=\alpha$.  Then from this it is possible to identify a consequence (not necessarily minimal) of $\varphi(x)$.  In particular, the clause $x\ne \alpha$ is a consequence of $\varphi(x)$.  To put it another way, consider the clause $c(x) = \ell_1 \lor \dots \lor \ell_n$, where $\ell_i$ is either $x_i$ or $\neg x_i$ according to whether $\alpha_i$ is false or true; then $c(x)$ is a consequence of $\varphi(x)$.  This is a somewhat trivial and boring consequence, but it is a valid one.
Finding a minimal consequence. Once you have a single consequence $c(x)= \ell_1 \lor \dots \lor \ell_n$, it is now possible to to minimize it.  In particular, we will look for a minimal subset $S \subseteq \{1,2,\dots,n\}$ such that $c_I(x) = \lor_{i \in I} \ell_i$ is a consequence of $\varphi(x)$.  How do we do that?  We can simply try removing one literal at a time from $c(x)$ (removing one index at a time from the set $I$), testing at each step whether the result remains a valid consequence.  If removing a literal from the disjunction leaves it a valid consequence, go ahead and remove that literal; if after removal, it is no longer a valid consequence, then don't remove it.  Each test requires a single invocation to the SAT solver, so this procedure requires $n$ invocations of the SAT solver.  When you are done, you have a single minimal consequence $c_1(x)$ of $\varphi(x)$.
Finding another consequence.  Next, I will show to find a second consequence.  Let me explain using an example.  Suppose that $c^1(x) = x_1 \lor \neg x_3 \lor x_7$ (say), and suppose we know that $c^1(x)$ is a minimal consequence: no literal can be removed from this disjunction while keeping it a consequence.  We want to find a second minimal consequence $c^2(x)$ that is a disjunction of literals.  What can we say about the set of literals that appear in $c^2(x)$?  Well, either $c^2(x)$ does not contain the literal $x_1$, or it does not contain the literal $\neg x_3$, or it does not contain the literal $x_7$ (otherwise it would be a consequence of $c^1(x)$, i.e., subsumed, and thus not minimal).

So let's search for some consequence that satisfies these constraints.  One way to do this is to search for a satisfying assignment to $\neg \varphi(x) \land (\neg x_1 \lor x_3 \lor \neg x_7)$, by feeding this to a SAT solver.  Suppose the SAT solver gives us a satisfying assignment $x=\alpha$.  Then this immediately suggests a consequence that is not subsumed by $c_1(x)$, namely, the clause $x\ne \alpha$ (expressed as a disjunction of literals).  If we want, we can minimize this consequence to get a minimal consequence $c^2(x)$.  By construction, $c^2(x)$ will be minimal and different from $c^1(x)$.  This gives us a way to find two minimal consequences.
Finding all minimal consequences. Now it should be clear how to find all minimal consequences.  Suppose we have found $c^1(x),\dots,c^k(x)$, each of which is a minimal consequence of $\varphi(x)$, where $c^j(x) = \lor_i \ell^j_i$.  We define the formula

$$\neg \varphi(x) \land (\lor_i \neg \ell^1_i) \land \cdots \land (\lor_i \neg \ell^k_i).$$

Feed this formula to a SAT solver.  If it is unsatisfiable, you are done: you have found all minimal consequences.  Otherwise, suppose it finds a satisfying assignment, say $x=\alpha$.  Then this immediately supplies a  new consequence, which you can then minimize as above, to get a new minimal consequence $c^{k+1}(x)$.  Now you can iterate until there are no more to be found.

The running time for this algorithm is best expressed in an output-sensitive measure. If there are $m$ minimal consequence clauses, then this algorithm will complete after making $O(mn)$ queries to the SAT solver.  It might even be somewhat efficient, if you use a SAT solver that allows you to make multiple related queries and that remembers state across those queries.

Finding consequences that are in CNF form

Now suppose you want to allow consequences to be any CNF formula, and you want consequences that are minimal among the set of such consequences.  Then the problem becomes trivial.

In particular, $\varphi(x)$ is a trivial consequence of $\varphi(x)$, and it is possible to show that it is a minimal consequence: any other formula that has the same or more satisfying assignments is subsumed by it, and any formula that has fewer satisfying assignments is not a consequence.

A comment on resolution and on formulating problem statements

Resolution is just a means to an end, not an end goal in itself.  Resolution is one technique that is used in some SAT solvers, but SAT solvers also use other techniques as well -- and that combination of techniques is important.  What we've seen in practice is that current SAT solvers perform a lot better than vanilla resolution on many problems.

Therefore, my advice to you is to articulate the problem statement clearly, and try to keep clear in your mind the distinction between the goal (the problem statement) vs the way you'll achieve the goal (the algorithm you use).  Formulate the goal in a way that describes what you want to achieve, not how you want it to be achieved.  Once you articulate your goal clearly, you might find that resolution is not the optimal method.


Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions?

Given a $CFG \ G$, before converting in $CNF$ you need to clean the grammar, that means (order is important):

  1) eliminate $\epsilon$-productions

  2) eliminate unit productions

  3) eliminate variables that do not derive terminal strings

  4) eliminate unreachable variables from the starting symbol

After this you make substitutions/split rules in order to obtain a CNF grammar.

According to these rules, after your step 3 I would eliminate non generating variables (all the variables can reach a terminal string) and unreachable variables (You cannot reach $S'$ from $S$), to end up with the following productions:

\begin{align*}
  S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\
    \ X&\longrightarrow a\,|\,aX\,|\,Yb\\
 Y&\longrightarrow bY\,|\,b
  \end{align*}

I don't know which procedure you are following (it may vary according to textbooks/instructors), but if you don't apply steps $3$ and $4$ then yes, you could end up with useless symbols in your grammar in CNF.


How to write a grammar for this language?

Your language is regular, and so one way to construct a context-free grammar for it is to first consider a finite state automaton, and then convert it to a grammar. Of course, this methodology only works for regular languages, and is not necessarily the easiest way in every case.


Neural net that alters its own parameters

One can do whatever he likes.

If your algorithm allows richer structure modification than simply adjusting weights, then you can obtain a "net which alters itself", though this doesn't have any special/magical meaning.

Suppose for example that your net's inputs correspond to some properties of an image, and you have a " hidden node" whose input is the average pixel value. During training, you can see whether adding this node lowers your training error, and if so, add it. One can claim that the net magically realized that it needs to use the average pixel value, but this is merely a direct result of your learning algorithm definition.


One of the answers to your question: $f(n) = n$, and $g(n) = n^2$.

Then $f(n) = O(g(n))$ but not $\Theta(g(n))$. This is because $n^2$ is an upper bound on $n$ , for all $n \geq 0$,  but it is not tight (actually we only need the inequality to be true for $n > N$ for some $N$, by the definition of $O()$).

By saying that the bound is not tight, what we mean is that we do not have  $cn^2 \leq n \leq c'n^2$, for large enough $n$'s (it should hold for all $n > N'$ for some $N'$ by the definition of $\Theta()$ if $n$ were $\Theta(n^2)$). Also $c$ and $c'$ are positive here and the following discussion.

Since $n^2$ is upper bound on $n$ it is easy to get $n \leq c'n^2$ part. But we can never get to the $cn^2  \leq n$ part. Even if we take $c$ very small,say 0.01 in the picture, at $n > 100$ it will not remain smaller. So we can never have $n$ between $cn^2$ and $c'n^2$ for all values $n>N'$. This is because we will always find some big number where $c'n^2$ will be above $n$.

$O()$ is just an upper bound, where as $\Theta()$ is a tight bound.  Also if we have $f(n) = o(g(n))$ then the bound in not tight yet it is an upper bound. Then $g(n)$ is a loose upper bound. If $f(n) = o(g(n))$ then any such pair of $f(n)$ and $g(n)$ will satisfy the condition of your question.


The definition of a language, from Hopcroft-Ullman Introduction to Automata and Language Theory, is :

  A set of strings all of which are chosen from some $\Sigma^*$, where $\Sigma$ is a particular alphabet, is called a language.

And from the same book, the definition of a string is :

  A string (or sometimes word) is a finite sequence of symbols chosen from some alphabet.

So strings must be finite. If we represent real numbers by sequences of digits, those sequences would be infinite in length, so that representation won't give us the language of real numbers.

But can we use another representation ? For example, even though we have rationnal numbers with an infinite sequence of digits, we can consider them as a language thanks to fractional representation.

Suppose that the set of real numbers were a language. Let's call that language $L$, and $\Sigma$ its alphabet. $L$ is a subset of $\Sigma^*$, thus $L$ is countable because $\Sigma^*$ is countable. We conclude that the set of real numbers can't be a language because it's an uncountable set.

NOTE : We can explicitly define an injection from $\Sigma^*$ to natural numbers. First, associate for every letter of $\Sigma$ a unique integer, call it $int(a)$. Let $\sigma$ be that bijection, here is its definition :

$$\left \{ \begin{array}{r c l} \sigma(\epsilon) &=& 0 \\ \sigma(\omega) &=& \prod_{i=1}^{|\omega|} \pi(i)^{int(\omega_i)} &;& \omega \neq \epsilon \end{array} \right .$$

Where $\pi(i)$ is the $i^{th}$ prime number and $\omega_i$ the $i^{th}$ letter of $\omega$.


Randomly construct linear combination that is within bounds over two basis

Using barycentric coordinate and keeping sum of coordinate equal to 1 do not sample a convex polytope uniformly.

import numpy as np
import matplotlib.pyplot as plt

N = 1000000  # Number of samples
V = 5 # Generate points within a V-gon

# generate columns that each sum to 1
s = np.exp(-np.random.uniform(0, 1, size=(V, N)))
s /= s.sum(axis=0)

# generate vertex of regular polygon
r = 2
theta = np.linspace(0, 2*np.pi, V+1)[1:]
v_x = r*np.cos(theta)
v_y = r*np.sin(theta)

# generate random points within the polygon
# by linear combination of coordinates of
# vetex where the coefficients sum to 1.
x = (v_x[:, np.newaxis] * s).sum(axis=0)
y = (v_y[:, np.newaxis] * s).sum(axis=0)

# plot density
heatmap, xedges, yedges = np.histogram2d(x, y, bins=50)
extent = [-r, r, -r, r]

plt.clf()
plt.imshow(heatmap.T, extent=extent, origin='lower')
plt.plot(v_x, v_y, color='r')
plt.show()


In a DAG, longest path where every vertex has degree at most 2

First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph).  The result is a smaller DAG.  This can be done in linear time.

Now, find the longest path in the resulting DAG.  This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest_path_problem.


number of comparison in sort algorith with special operation

Let's suppose that it is possible to sort it with $:$ in time $o(nlogn$).
So we use ordinary comparisons: $<$ and $>$. If both $a_i<a_j $ and $a_j > a_i$ is not truth then we conclude $a_i=a_j$.  And now, we can sort in time:
$o(2nlogn)=o(nlogn)$ - it is impossible.


What kind of language uses an infinite alphabet?

The definition of formal language doesn't depend on the alphabet - it remains exactly the same. Things start getting a bit more complicated when you are interested in certain classes of languages. For example, let us consider regular languages. If your alphabet is infinite, the restriction of having only finitely many states seems a bit restrictive. Instead, it makes sense to allow any number of states whose cardinal is strictly less than that of the alphabet (if you allow a cardinal at least as large, every language would be regular). The corresponding notion of regular languages isn't too exciting perhaps, but at least it is a genuine subclass of all languages, which shares some properties with regular languages over finite alphabets.


If you are allowed to use one extra variable, then a queue can simulate a stack, so in this model a queue plus a single extra storage location will suffice.

The idea is to represent a stack, say $[\ a\ b\ c\ $(top), as a queue, (tail) $\langle c\ b\ a\rangle$ (head). Then the operation $\mathtt{push(x)}$ would correspond to $\mathtt{enque(x)}$, so
$$
[\ a\ b\ c\quad \stackrel{\mathtt{push(x)}}{\longrightarrow}\quad[\ a\ b\ c\ x
$$
would be simulated as
$$
\langle\ c\ b\ a \rangle\quad \stackrel{\mathtt{enque(x)}}{\longrightarrow}\quad\langle\ x\ c\ b\ a\ \rangle
$$
The $\mathtt{pop()}$ operation is a bit more complicated. We first enqueue a marker, #, and then keep pulling elements off the head of the queue and placing them back on the tail until we come to the marker, indicating that the last element we pulled off corresponds to the top of the stack, so we don’t replace that element on the queue and we finish by removing the marker. In pseudocode, what we do is:

enque(#)
v = head()              ; save the head element
deque()                 ; remove it
while (head() != #)
   enque(v)             ; put the element back on the tail
   v = head()           ; save the next element
   deque()              ; remove it
deque()                 ; finally, remove the marker

For example, starting with $\langle c\ b\ a\rangle$, we'd have
$$\begin{align}
\langle\ c\ b\ a\ \rangle &\longrightarrow \langle\ \mathtt{\#}\ c\ b\ a\ \rangle \\
&\longrightarrow \langle\ a\ \mathtt{\#}\ c\ b\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ c\ \rangle \\
&\longrightarrow \langle\ b\ a\ \mathtt{\#}\ \rangle \\
&\longrightarrow \langle\ b\ a\ \rangle
\end{align}$$


I would leave a comment but I have less that 50 rep.

So, if I understand the question, DFS (or a way to parse the tree) is inevitable and all you need is an array (one cell for each level, plus one for the leaves) to count how many nodes are on each level. So given the numNodes you can start decrementing from the last (non-zero) element and check which would be the last non-zero element you will reach.

Also you don't actually need a stack, cause it is already implemented from the OS for you. So you just need to use a recursive algorithm passing each time the correct part of the array to the next call to calculate the nodes in the sub-tree. Now, all you need to know is the initial length of the tree. You run again the kind-of the same recursive algorithm but this time you are interested to know the total number of elements in the tree. Then the length of the array would be equal to the length of the total elements in the tree.

Time: O(n)

Space: O(n)

I'm not sure if I can write code here. I hope I was clear :)


Expressivity of neural networks, how much information can be stored

You're probably not going to get a theoretical answer, because analyzing exactly what set of functions can be computed by a particular neural network is messy.  Or, at least, you probably won't get a tight analysis.  There are theorems showing that neural networks are universal approximators, meaning that given sufficient capacity it is possible to express every function, but this doesn't tell you the minimize size needed to express every function; it just tells you that there exists a size that is large enough.
However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $f$ [1].  This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.
The VC dimension is beautiful theory but it's not clear it has a great deal of relevance to modern use of neural networks in practice.
[1] Understanding deep learning requires rethinking generalization.  Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals.  arXiv:1611.03530


You cannot check, in general, whether $S'$ contains at least one element from each subset $C$ in polynomial time w.r.t. $n$.

However, in order to show that the problem is NP it suffices to show that you can check to above condition in polynomial time w.r.t. the instance size, which is in $\Omega( \sum_{X \in C} |X| + \log n)$.


Why is this greedy algorithm claim true?

The claim is not that

$$f_S(B) \ge f_S(C).$$

Rather, the claim is that

$$f_{S_1}(B) \ge f_{S_1}(C).$$

Do you see the difference?  Here $S_i$ is the set of elements chosen (by the greedy algorithm) in the first $i$ iterations, so $S_i=\{A\}$.  Thus, the claim is that

$$f_{\{A\}}(B) \ge f_{\{A\}}(C),$$

i.e.,

$$f(\{A\} \cup \{B\}) \ge f(\{A\} \cup \{C\}).$$

The latter claim is indeed true, as both the left-hand side and the right-hand side are 9 (i.e., $f(\{A,B\})=f(\{A,C\})=9$), since they cover 9 of the "blue dots".


First notice that a "file" is a sequence of 0s and 1s in binary format that are stored in some kind of persistent storage (an hard disk, a CD, an USB key, ...).

According to the the type of information stored in the file (a plain text, a PDF document, an image, a video, a song,  ...) its bits (bytes) are usually arranged using standard rules and they have precise meaning: they follow a file format which specifies how information is encoded in the file.

Usually the name of the file (filename) has an extension (.mp3, .txt, .jpg, .pdf, .tex, ...) that indicates the file format i.e. how information is encoded.

Computer programs like text editors, image editors, video players, music players, ... can read a file in one (or more) format and decode the information stored in it (show the text on the screen, play it, process it, ... ).

Now suppose that you have a bunch of bytes in your head. First you can write them directly in a file using a program like a binary editor. When they are stored in a file, you need to discover its file format ...

first you can try to display it as a text file (like suggested by saadtaame in his answer): many file formats (text data, html files, xml files, ...) store the information in plain text (ASCII);
or you can change its extension (.pdf, .jpg, .mp3, .gif, .avi, ...), and try to open it with some standard programs ... if you are lucky you'll find one that opens it correctly;
or you can do something smarter. You can examine the first bytes of the file (header): they usually have a particular structure or contains specific fixed characters that allow you to quickly find the file format of the whole file.

For example the bytes 6,7,8,9 of a JPEG file are always 0x4a 0x46 0x49 0x46, which correspond to the string "JFIF" in ASCII. Windows PE executables contain the string "This program cannot ..." in the header. The first two bytes of a file in ZIP format are "PK", and so on ...

But there are thousands of file formats out there, so you can also consider using a computer program that given an unknown file can help you to find its file format automatically.

Finally don't forget that the information in a file can also be encrypted or the file format can be proprietary (and closed, i.e. undocumented); in these cases there are very little probability (zero?) to decode the information stored in the files.


Resources about implementing a database table

Databases have some issues that "mere mortal" data storage doesn't concern itself with, such as transaction safety and disk failure.
Here are a few classic papers on the topic:

Astrahan et al (1976), System R: A Relational Approach to Data Base Management, ACM TOMS 1:2, pp 97-137.
Stonebreaker et al (1976), The Design and Implementation of INGRES, ACM TOMS 1:3, pp 189-222.
Stonebreaker (1987), The Design of the POSTGRES Storage System, VLDB '87, pp. 289–300.

There are also some good books that cover the relevant topics, such as Database System Implementation by Garcia-Molina, Ullman, and Widom.


No, quantum computers are not going to have an enormous number of operations per second, in fact they are probably going to be much slower in the foreseeable future. The situation with memory seems even bleaker – so far only a handful of bits.

The big advantage of quantum computers is that they can run quantum algorithms, which work rather differently from classical algorithms. Very informally, they provide a way of going through many possibilities at the same time. This gives an exponential speed up for some tasks, and a polynomial speedup for others – in terms of the number of operations. Even though each individual operation is going to be slower, since you need to run drastically fewer, the overall algorithm would run much faster.


There are $2^{\aleph_0}$ possible oracles, but when fixing an oracle $A\subseteq \Sigma^*$, there are only countably many Turing machines $M^A$ with access to the oracle $A$.

Remember that a Turing machine with access to some oracle is defined in the same manner as a normal Turing machine, but with an additional operation (they can query the oracle). They have a special tape on which they can write a query, and say, three additional special states $q_{ask},q_{yes},q_{no}$. Upon entering $q_{ask}$, if $s\in\Sigma^*$ is the content of the query tape, the machine enters either $q_{yes}/q_{no}$, depending on whether or not $s\in A$.

Nothing stops us from encoding such machines as strings, in the same way we encode regular Turing machines, hence we only have countably many such machines.


Recurrence : $T(n) = 4T(n/2) + Θ(n^2/\log n)$

As mentioned by @Yuval Filmus in the comment, you can use the extension of the master theorem (case 2b). The result is $T(n) = \Theta(n^2 \log\log{n})$.


How to write a regular expression to match a string that starts with the same pattern that it ends with

Since you asked how to approach it, a good starting point for these sorts of problems is to start by understanding the language.  Try writing down all words in the language of length 1; all words of length 2; all words of length 3; all words of length 4; and see if you can spot any possible patterns (about which words are in the language and which aren't).  Then, see if you can prove your guess.

Finally, use that to help you brainstorm ideas for how to express this as a regular expression.

Make sure to read How to prove a language is regular? carefully.


Is the exponent bias $2^{n-1}-1$ or $2^{n-1}$

Both encodings for the exponent are possible, and they are called Excess-$2^{n-1}$ and Excess-$2^{n-1}-1$ - in particular, you might meet such number encodings as Excess-127, Excess-128, Excess-1023 and so on.

The IEEE-754 standard happened to choose the Excess-127 and the Excess-1023 encodings for exponents, so these encodings became more customary. Your book is not mistaken about the exponent bias, it just follows a way, different from this standard.

You can find additional information and nice graphs here.


For any particular string $x$, the question of whether $x \in L(G)$ is decidable (if G is not unrestricted), and that's what you've described.

However, the problem you've given is not whether a particular string is in $L(G)$, but whether any string is in $L(G)$. There are infinitely many strings to try. We can test each one in sequence, and if it is in $L(G)$ then we know it is not empty. But if $L(G)$ is empty, how do we know when to stop? There are infinitely many strings, so we never know if the next string is the one that's in the language. So we never know when to stop.

That said, the decidability greatly depends on what type of language/grammar $G$ is. For context-free languages, this is decidable, since we can make a pushdown automaton and perform a search to see if an accepting state is reachable. But for other, more complicated types of languages this may very well be undecidable.


What you have given is a definition. You can define anything you want.  The class of languages defined as

  A language $L$ is in UC (user71565's class1) if there are a polynomial $q$ and a DFA $A$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $A$ accepts $xy$

is a perfectly legitimate class of languages.  For example, it includes all regular langauges (take $y=\varepsilon$ for every $x$).

However, because this is not the same definition as the definition of NP that you quoted in your question, you shouldn't expect that UC$\,=\,$NP.  In fact, we can quickly see that UC$\,\neq\,$NP, using the pumping lemma and a language such as $\{0^n1^n\mid n\geq 0\}$, which is in NP but cannot be recognized by any DFA.

Interestingly, though, the following definition is equivalent to the normal definition of NP:

  A language $L$ is in NP2 if there are a polynomial $q$ and a deterministic logspace Turing machine $M$ such that $x\in L$ if and only if there is some string $y$ with $|y|\leq q(|x|)$ and $M(x,y)=1$.

That is, we can weaken from a deterministic polynomial-time verifier to a deterministic logspace one, without changing the class of languages defined. This is a consequence of Fagin's theorem, which says that the verifier can actually be a formula of first-order logic.  The expressive power of first-order formulas is strictly weaker than deterministic logspace Turing machines.

1 There's something of a tradition of naming language classes in this way. For example, the class NC of languages decidable in polylog time with polynomially many processors stands for "Nick's class", after Nick Pippenger.


Finding a complexity by solving inequality

You can’t use $O(m) + O(m) = O(m)$ in an inductive proof, since the hidden constant will keep blowing up. To see this more closely, suppose that you bound $C_{n,m}$ with $A\cdot m$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq 2A(m-1) + O(1).
$$
The right-hand side will generally not be at most $Am$.

Instead, let's try to use Pascal's identity, $\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$. We guess that $C_{n,m} \leq A\binom{m}{n}-B$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq \\
A\left(\binom{m-1}{n} + \binom{m-1}{n-1}\right) - 2B + O(1) =
A \binom{m}{n} - 2B + O(1).
$$
For $B$ larger than the hidden constant in $O(1)$, the right-hand side will be at most $A\binom{m}{n} - B$, and so we will be able to prove the induction hypothesis. For given $B$, we can choose large enough $A$ so that $C_{0,k} \leq A \binom{k}{0} - B$ would hold. However, we reach a problem when considering the other base case $C_{k,0} \leq A \binom{0}{k} - B$. Therefore we need to fix our strategy.

At this point, we leave it to the reader to find the right binomial coefficient to add.


Electrical resistance of expander graphs

Next time you ask a question you should try to google it first. I googled "electrical resistance expander graph" and the very first result was a paper stating that $d$-regular graphs have resistance $\Theta(1/d)$.


NP-hard means that all the problems in NP reduces to this.  NP-complete means that it is in NP as well.

Sometimes we say a problem is NP-hard when it is obviously NP-complete.  But this is because we want to stress the hardness of the problem, and also that it should be trivial that the problem is in NP.


Could a quantum computer perform linear algebra faster than a classical computer?

Here are some pointers:

Quantum algorithm for linear systems of equations by Harrow, Hassidim, and Lloyd. This paper shows how to solve sparse systems of linear equations very quickly.
Quantum Algorithms for Linear Algebra and Machine Learning by Anupam Prakash. This PhD thesis proposes a quick algorithm for singular value estimation, and presents several applications.


Finding the size of the smallest subset with GCD = 1

This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union.

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse.

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.


How to "convert" nested loops into code taking advantage of parallel computing?

Let's say you want to iterate over a,b,c,d each ranging from 0..99.  There are two ways to do that.

Approach #1: fewer nested loops

Set up a 100x100 grid, which will handle a,b.  Handle c,d by explicit nested loops:

treatPixel(a,b):
for c in 0..99:
    for d in 0..99:
        doSomething(a,b,c,d)

Approach #2: bigger grid

Set up a 10,000x10,000 grid.  Then decode the x-coordinate to a,b and the y-coordinate to c,d, like this:

treatPixel(x,y):
a := floor(x/100); b := x mod 100
c := floor(y/100); d := y mod 100
doSomething(a,b,c,d)

Which to choose?

Either one should work.

Assuming the number of iterations greatly exceeds the number of compute elements in the GPU, the difference between the two probably comes down to different memory locality effects.  You can try implementing both of them, benchmarking, and seeing if one is faster.  If there is little or no memory access and doSomething() is compute-bound, they'll probably both run at about the same speed.


Would a modern processor/ALU process data bit or byte wise?

Modern processors have 32/64 bits integer and 32/64/80 bits floating-point registers and ALUs. With the addition of SIMD instructions, extra vectorized ALUs are available and can perform operation on up to 64 bytes or 32 shorts (16 bits) or 16 ints (32 bits) or 8 long ints (64 bits) simultaneously and similar figures in floating-point (hence 512 bits at a time - Intel AVX).

A core is a full processing unit packaged in the same physical (multi-)processor.

So in a way, you can say that an octo-core can process 4096 bits of data at a time.

It is not fair to say that a processor ignores bytes, because the arithmetic operations need to know how many useful bits there are, to handle borrows, carries, overflows... Not to mention the floating-point data types, such that the value is split in several bit fields with different roles (sign, exponent, mantissa). In fact, a processor distinguishes dozens of data types of various lenghts.

It would be more true to say that processors don't known about bits because these are never handled individually, but as a minimum grouped in bytes. Even the very first microprocessor in history, the 4004, was handling nibbles (4 bits at a time).


Shortest path with a start vertex that touches all nodes at least once with repeats allowed

Your problem is just a TSP in disguise.

1. Dealing with "visit each node at least once"

First, compute a modified distance matrix $D(i,j)$, $i,j=1,...,n$ using an all-pairs shortest path algorithm, such as the Floyd-Warshall algorithm. That is, you want $D(i,j)$ to be the shortest path length from node $i$ to node $j$. Using Floyd-Warshall you also compute a matrix $S(i,j)$ that gives the successor of $i$ on the shortest path from $i$ to $j$.

Now apply a TSP algorithm to the distance matrix $D$. This will give you a tour $T$ that goes through each node exactly once. You now expand each step of $T$ into a shortest path (you can do this using the matrix $S$). That is, if some step of $T$ goes from $i$ to $j$, you expand it into the shortest path from $i$ to $j$. Concatenating all these paths gives a tour $T'$ that visits each node at least once, with possible repeats. If $T$ is optimal for $D$, then $T'$ must be optimal for the original graph.

2. Dealing with "the tour does not need to return to the starting node"

Preprocess your graph as follows. Add a dummy node, node 0, such that the distance from 0 to the starting node $s$ is 0 and the distance from node 0 to any other node is $M := n \cdot \max_{i,j} D(i,j)$.

Now find a TSP tour on the modified graph using your TSP algorithm of choice.
Because the value of $M$ is so large, any optimal TSP tour will be of the form
$$ 0, s, \pi(1), ..., \pi(n-1), 0$$
where $\pi$ is some permutation of the nodes excluding the start node and node 0. Then the sequence $s, \pi(1), \ldots, \pi(n-1)$ represents your solution.

3. Exact vs heuristic

You can use any algorithm for the symmetric TSP problem. If $n$ is about 30, you will probably not be able to apply an exact (= optimal) TSP algorithm such as the Held-Karp dynamic programming algorithm. A very simple yet reasonable  heuristic you might want to try is 2-OPT, which is straightforward to program. A branch-and-bound approach might also work well in practice.


Finding the best combinations between items of 2 arrays in a sequential manner

Negate the Y values.  Then you are looking for the Pareto-optimal frontier of the set of combinations.

There are standard algorithms for computing the Pareto-optimal frontier of any set.  In particular, see the last part of this answer for an overview of algorithms (the simple cull algorithm, divide-and-conquer, and hybrids between those two).  Those algorithms should be much more efficient than what you were considering before.  For example, the simple cull algorithm has $O(n^2)$ running time to compute the Pareto-optimal frontier of a set of size $n$ (or $O(nm)$ time, if you know the output is of length $m$).

Here's how you can use this in your setting.  First, compute the Pareto-optimal frontier of A and the Pareto-optimal frontier of B.  Then, enumerate all combinations of those two frontiers.  Finally, compute the Pareto-optimal frontier of that list of combinations.  If you use the simple cull algorithm, the running time will be at worst $O(n^4)$, where $n$ is the length of the input lists.  If the output has size $m$, the running time will be at worst $O(n^2 m)$.  In either case, the memory consumption will be $O(n^2)$.  The algorithms might perform better than that in practice, depending on your data.

If you want the output to be in sorted order, you can sort by Y value after computing the set.

I would recommend that you try these algorithms and see what the memory consumption looks like.  If the memory consumption is still too much, then you can let us know.


Which redexes are there in $\lambda s. \lambda z. (\lambda u. z)(\lambda v. v)$? How to substitute arguments?

You must learn how to put in parentheses and then it will be easier to figure out what is what. In the above case, we first put in parentheses:
$$\lambda s . (\lambda z . ((\lambda u. z) (\lambda v . v))).$$
This is the only correct way to put back parentheses. For instance, this is wrong
$$(\lambda s . (\lambda z . (\lambda u . z))) (\lambda v . v)$$
Why is it wrong? Because the rules for writing expressions without parentheses say that when you see $\lambda x . \cdots$ that means that $\lambda x$ binds the whole expression. For instance $\lambda x . x (\lambda y . y)$ is the same as $\lambda x . (x (\lambda y . y))$ and is diffrerent from $(\lambda x . x) (\lambda y . y)$.

If this is not resolving your dilemma you have to explain why you think that the other redex is valid.


How to retrieve reset bit in constant time in a bit array

Access into a bit array is constant time.  In particular, if you have an array that is stored contiguously in memory, indexing into the array takes constant time: reading $A[i]$ takes constant time, regardless of how large $i$ is.  That's all that you need to do to access a bit array.  In particular, if you have an array of bytes, then you can read the $i$th bit of the bit-array by reading $A[i/8]$ and doing a bit-masking operation to get the $(i \bmod 8)$th bit of that byte, and so on.

If you want to find a new session id that is not in use, that can be done in (expected) constant time as long as at least 1/2 of the session ids are not in use.  You simply pick a random session id, check whether it is in use, and repeat until you find one that is not in use.  If at least 1/2 of the session ids are not in use, the expected number of times you need to repeat this until you find one that is not in use is 2 (as it's expected the number of coin tosses until you get a heads, which is a geometric series), i.e., a constant.  Each iteration takes constant time, so the whole thing can be done in $O(1)$ time.

So, a bit array already meets all of your requirements. Just make sure that at least 1/2 of the session ids are not in use.

(What do you do if more than 1/2 of the session ids are in use?  Double the size of the array, copying over the old array if needed.  The doubling will happen rarely enough that the amortized time for each operation remains constant, i.e., $O(1)$.)


What operation is the algorithm performing?

The algorithms counts the number of $1$s in the binary expansion of the input. The code as written seems a little weird because it’s not a function that can be applied to an input, it’s being specifically applied to the defined number. I certainly couldn’t tell you why it’s being applied to that number without a lot more context.


Code is literal programming code (be it C/C++, Java, Python, etc.). We can agree the code will be completely different between languages. In addition, if you are implementing a stack, then you have modify your code depending on what underlying data structure you're using to store the data (c style arrays in C, ArrayLists in Java,  etc.).
ADT is a way to express the basic operations of the data type independently from the code (from any programming language). This leads to pseudocode.
For instance, a queue ADT might have the following functions: enqueue, dequeue, front. The enqueue function takes data and adds it to the back of the queue; the dequeue function removes data from the front of the queue and returns it; finally the front function simply returns the first data in the queue but does not remove it.
The above is the most basic queue ADT, but you could have other functions like back, isEmpty, or even something weird like thirdPlaceInQueue. It all depends on what your needs are. Be careful though, giving too much functionality may lead to a different ADT. For instance, if you gave a queue ADT the ability to add to the front and remove from the back, you would then have a deque ADT.


Language which is recursively enumerable but not recursive

The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.


The hazard stems from the fact that the lw instruction updates register \$r0 at the 5th stage of the pipe (write-back) while the sw and the add instructions require the updated data at the 2nd stage of the pipe (decode/read).

Putting everything on a single time line (assuming the lw execution begins at time $t=1$), the correct value of \$r0 will be available not before $t=4$ and the other instructions must be stalled (at the decoding phase) until this data is available. After $t=4$ a forwarding unit can be used to forward the data to the correct place, e.g., to the execution stage for the sw or to the decoding stage for the add (if needed).


Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $[0,N)$ using only those features.  This is effectively a way of building a perfect hash, where the hash function is expressed as a decision tree applied to the feature vector constructed from the input.

Building the smallest decision tree is NP-hard in general, but there are heuristic algorithms that do a reasonable job.  You might look at the ID3 algorithm, for instance; in many settings it does a pretty good job of building a small (though not necessarily minimal) decision tree.  You can compare that to other ways of building perfect hash functions and see which is computationally more efficient for your particular data set.  Probably the only way to know is to try it out; I'm not sure there is any theory that will give you a definitive answer, as the answer probably depends on characteristics of your dataset that will be hard to model in a theoretical setting.


For a normal stack, the implementation on top of a linked list is indeed questionable. Many other uses of linked lists are disappointing in practice as well.

But consider a lock-free stack where push and pop are atomic. A singly-linked list can offer atomic prepend and atomic "remove head" using atomic Compare-and-Swap (some caveats apply). Implementing an atomic stack on top of an array is a bigger problem, one that to my knowledge has not been satisfactorally solved.

The downside that linked lists tend to weave their way somewhat randomly through memory can occasionally be turned into an advantage: elements that are in some other data structure can have a linked list weaved through them without imposing requirements on the addresses of the elements. For example, elements in a hash map can also have a linked list running through them that records their insertion order, while maintaining fast removal (a dynamic array that records the indexes of the elements in insertion order would still allow fast insertion but not fast removal since it could happen in the middle). Elements can even be in several different linked lists at the same time, an example of that is dancing links algorithm which uses linked lists for columns and rows and elements are in both a column and a row at the same time.


this is the problem of covering points with lines or linear facility location
which is NP-Hard. This is why you couldn't find a greedy solution. There are approximation and exact algorithms for this problem. If you want an exact algorithm that is efficient on large inputs I suggest you a simple version of parametrized solution for this problem.


can more than two arrows point towards the same state from other states in a DFA?

Yes, this is allowed (and in fact, you lose a lot of computational power without it)

here is a definition of DFA (both formal and as drawings) + an example


lower bound of checking if in array are two different elements

Decision tree lower bounds don't quite work here. The obvious way to apply a decision tree lower bound is to consider the output of the algorithm, which is either TRUE or FALSE. Since there are two possible outputs, the decision tree lower bound gives a lower bound of one comparison. Not very helpful.

A more interesting example of the decision tree technique forces the algorithm to output a little more, namely either it outputs YES (all the elements are the same), or a pair of different elements (represented as their indices). You can argue that whenever the algorithm returns NO it actually knows two elements which are different. Considering all inputs of the form $x_1 = \cdots = x_{i-1} = x_{i+1} = \cdots = x_n = 0, x_i = 1$, we see that for each $i$ there must be a leaf of the form $(i,\ast)$. This means that there must be at least $n/2$ NO leaves, resulting in a lower bound of $\log_2(1+n/2)$ on the number of comparisons. This can plausibly be improved to $\log_2(1+\binom{n}{2})$, but both quantities are $\Theta(\log n)$.

The correct way to argue here is using an adversary argument. Consider any algorithm, and trace its execution, always answering YES to any query. Consider the graph whose vertices are all elements (i.e., all indices), and the edges correspond to queries performed by the algorithm. If the graph is not connected, the algorithm can't know whether all elements are the same (indeed, it is consistent both that all elements have the value $0$, or that the elements in the $i$th connected components have the value $i$). Since a connected graph has at least $n-1$ edges, any algorithm must perform as least $n-1$ comparisons. It's not hard to see that this bound is achievable.


To what factor can I compress information from binary to Quinary

Here is a simple way to get the inequality $|f(x)| \leqslant {1 \over 2}(|x| + 3)$. Just encode words by blocks of length $2$ using the coding $00 \to 0$, $01 \to 1$, $10 \to 2$ and $11 \to 3$ and add the suffix $40$ or $41$ for the last letter if the length of the word is odd. For instance,
$f(11011000) = 3120$, $f(11011000\mathbf{0}) = 3120\mathbf{40}$ and $f(11011000\mathbf{1}) = 3120\mathbf{41}$.

One can improve this inequality to
$$
  (*) \qquad|f(x)| \leqslant \biggl\lceil{1 \over \log_2 5}|x| + C\biggr\rceil
$$
where $\log_2 5 \approx 2.3219\cdots$ and $c = \frac{3}{\log_2 5}-1 \approx 0.2920\cdots$. Indeed, the number of words of length $\leqslant n$ in $\Sigma^*$ is $\frac{|\Sigma|^{n+1}-1}{|\Sigma|-1}$. Therefore, there is an injection from $\Sigma_2^{\leqslant n}$ to $\Sigma_5^{\leqslant m}$ if and only if
$$
2^{n+1} - 1 \leqslant \frac{1}{4}(5^{m+1} - 1)
$$
which gives $4(2^{n+1} -1) \leqslant 5^{m+1} - 1$, or equivalently, $2^{n+3} \leqslant 5^{m+1} + 3$. This inequality is already satisfied if $2^{n+3} \leqslant 5^{m+1}$, that is, if $n+3 \leqslant (m+1)\log_2 5$. In particular, if you choose $m = \lceil {1 \over \log_2 5}n + C\rceil$, one can build an injection $f$ from $\Sigma_2^*$ to $\Sigma_5^*$ satisfying $(*)$ as follows. Recall that the shortlex (or radix) order is the order $\leqslant$ on $\Sigma^*$ defined by $u \leqslant v$ if and only if $|u| < |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. The shorlex order is a total order on $\Sigma_k^*$ and hence each word $u$ has a rank $r_k(u)$ in this order. For instance, for $k = 2$ you get $r_2(\varepsilon) = 0$, $r_2(0) = 1$, $r_2(1) = 2$, $r_2(00) = 3$, $r_2(01) = 4$, $r_2(10) = 5$, $r_2(11) = 6$, $r_2(000) = 7$, etc. For $k = 5$, you have $r_5(\varepsilon) = 0$, $r_5(0) = 1$, $r_5(1) = 2$, $r_5(2) = 3$, $r_5(3) = 4$, $r_5(4) = 5$, $r_5(00) = 6$, $r_5(01) = 7$, etc. Given $u \in \Sigma_2^*$, you now define $f(u)$ has the unique word $v \in \Sigma_5^*$ such that $r_5(v) = r_2(u)$ or, if you prefer, $f(u) = r_5^{-1}(r_2(u))$. This $f$ will satisfy $(*)$ but is of course more difficult to compute than the first coding.