An unquantified CNF formula consisting of clauses containing a single positive literal plus any number of negated literals is always satisfiable.  To produce a satisfying assignment, you simply set all the positive literals to true, satisfying all the clauses.  If you existentially quantify the variables associated with the positive literals and allow arbitrary quantification of the remaining variables, the formula is still satisfiable, and  for the same reason.  In the proof of the theorem, $P_\mathit{\Phi}$ is the subset of such clauses from the Horn formula $\mathit{\Phi}$.  Thus $P_\mathit{\Phi}$ by itself is always satisfiable.  It follows that $\mathit{\Phi}$ can only be unsatisfiable if, out of the sets of remaining clauses (denoted $N^+_\mathit{\Phi}$ and $N_\mathit{\Phi}$), a clause requires one of the previously set positive literals in $P_\mathit{\Phi}$ to be set false and there is no other way to satisfy the previously satisfied clause.


What important/crucial real-world applications use blockchain?

Apart from Bitcoin and Ethereum (if we are generous) there are no major and
important uses today.

It is important to notice that blockchains have some severe limitations.  A
couple of them being:

It only really works for purely digital assets
The digital asset under control needs to keep its value even if it's public
All transactions need to be public
A rather bad confirmation time
Smart contracts are scary

Purely digital assets

If an asset is actually a physical asset with just a digital "twin" that is
being traded, we will risk that local jurisdiction (i.e. your law enforcement)
can have a different opinion of ownership than what is on the blockchain.

To take an example; suppose that we are trading (real and physical) bikes on the
blockchain, and that on the blockchain, we put its serial number.  Suppose
further that I hack your computer and put the ownership of your bike to be me.
Now, if you go to the police, you might be able to convince them that the real
owner of the bike is you, and thus I have to give it back.  However, there is no
way of making me give you the digital twin back, thus there is a dissonance: the
bike is owned by you, but the blockchain claims it's owned by me.

There are many such proposed use cases (trading physical goods on a blockchain)
out in the open of trading bikes, diamonds, and even oil.

The digital assets keep value even if public

There are many examples where people want to put assets on the blockchain, but
are somehow under the impression that that gives some kind of control.  For
instance, musician Imogen Heap is creating a product in which all musicians
should put their music on the blockchain and automatically be paid when a radio
plays your hit song.  They are under the impression that this creates an
automatic link between playing the song and paying for the song.

The only thing it really does is to create a very large database for music which
is probably quite easy to download.

There is currently no way around having to put the full asset visible on the
chain.  Some people are talking about "encryptions", "storing only the hash",
etc., but in the end, it all comes down to: publish the asset, or don't
participate.

Public transactions

In business it is often important to keep your cards close to your chest.  You
don't want real time exposure of your daily operations.

Some people try to make solutions where we put all the dairy farmers' production
on the blockchain together with all the dairy stores' inventory.  In this way we
can easily send trucks to the correct places!  However, this makes both farmers
and traders liable for inflated prices if they are overproducing/under-stocked.

Other people want to put energy production (solar panels, wind farms) on the
blockchain.  However, no serious energy producer will have real time production
data out for the public.  This has major impact on the stock value and that kind
of information is the type you want to keep close to your chest.

This also holds for so-called green certificates, where you ensure you only
use "green energy".

Note:  There are theoretical solutions that build on zero-knowledge proofs
that would allow transactions to be secret.  However, these are nowhere near
practical yet, and time will show if this item can be fixed.

Confirmation time

You can, like Ethereum, make the block time as small as you would like.  In
Bitcoin, the block time is 10 minutes, and in Ethereum it is
less than a minute (I don't remember the specific figure).

However, the smaller block time, the higher the chance of long-lived forks.  To
ensure your transaction is confirmed you still have to wait quite long.

There are currently no good solutions here either.

Smart contracts are scary

Smart contract are difficult to write.  They are computer programs that move
assets from one account to another (or more complicated).  However, we want
traders and "normal" people to be able to write these contracts, and not rely on
computer science programming experts.  You can't undo a transaction.  This is a
tough nut to crack!

If you are doing high value trading, and end up writing a zero too much in the
transaction (say \$10M instead of \$1M), you call your bank immediately!  That
fixes it.  If not, let's hope you have insurance.  In a blockchain setting, you
have neither a bank, nor insurance.  Those \$9M are gone and it was due to a
typo in a smart contract or in a transaction.

Smart contracts is really playing with fire.  It's too easy to empty all your
assets in a single click.  And it has happened, several times. People have lost hundreds of millions of dollars due to smart contract errors.

Source: I am working for an energy company doing wind and solar energy
production as well as trading oil and gas.  Have been working on blockchain
solution projects.


It's true.
If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar.  You already know how to do that in cubic time.
If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.


Solving $T(n) = T(n/2) + T (n/3) + n $ with recurrence tree

On the one hand, clearly $T(n) \geq n$ (see detailed proof below). On the other hand, let us find prove by induction that $T(n) \leq Cn$, for large enough $C$. The base case trivially holds for $C \geq T(1)$. For the inductive step, we have
$$
T(n) = T(n/2) + T(n/3) + n \leq C\cdot (n/2) + C\cdot (n/3) + n = [\tfrac{5}{6}C+1]n.
$$
(We're cheating here a bit since $n$ isn't necessarily a multiple of 6.) If $C \geq 6$, then $\tfrac{5}{6}C+1 \leq C$, and so we can conclude that $T(n) \leq Cn$, thus completing the inductive step. In total, if we take $C = \max(T(1),6)$ then the proof goes through, hence
$$ n \leq T(n) \leq \max(T(1),6) n. $$
This implies that $T(n) = \Theta(n)$.

Finally, let us prove that $T(n) \geq n$. We first prove that $T(n) \geq 0$. The proof by induction. The base case clearly holds, and the inductive step is a consequence of
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + 0, $$
using the inductive hypothesis twice. Finally,
$$ T(n) = T(n/2) + T(n/3) + n \geq 0 + 0 + n = n. $$


Computing coefficients of $p(x)^n$ in time $O(n \log n)$

Suppose $n = 2^k$ and for $0\leq i \leq k$, set $p_i(x) = p(x)^{2^i}$. We want to efficiently compute $p_k(x)$.
It is clear that for $0\leq i < k$, $p_{i+1}(x) = p_i(x)^2$. Using the Cooley-Tukey algorithm, knowing $p_i(x)$, we can compute $p_{i+1}(x)$ in time complexity $O(d_i\log d_i)$ where $d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$.
We can know compute $p_k(x)$ by successively computing $p_1, p_2, …, p_{k-1}$. The total time complexity will be:
$$O\left(\sum\limits_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$
Now for the general case where $n$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $n$, like in fast exponentiation.


How do I determine if this argument is valid?

The argument $\frac{P}{C}$ means "If we assume that $P$ is true, we can prove that $C$ is true." For example, $\frac{A}{A\lor B}$ because, if you can prove that $A$ is true, then $A\lor B$ is also true: there's no way that $A$ can be true but $A\lor B$ can be false at the same time.

In the argument you've been give, $P$ and $C$ are completely unrelated. There is a way that $P$ can be true and $C$ can be false at the same time: specifically, $P=\mathrm{true}$, $C=\mathrm{false}$. Therefore, the argument is not valid.

You don't calculate the conclusion, per se. rather, you look for a situation in which the premise is true but the conclusion is false. If you can find such a pair of premise and conclusion, the argument is invalid. Conversely, if you can prove that the premise being true always makes the conclusion true, the argument is valid.

I don't understand what your teacher is trying to say. It's not enough to show that the argument is valid for one particular instantiation of $P$ and one particular instantiation of $C$. "Valid" means it works for all instantiations. Also, the examples of $P$ being "I am thirsty" and $Q$ being "I drink some water" doesn't work.  There are situations where you are thirsty but you don't drink water (maybe you drink nothing; maybe you drink juice), and situations where you're not thirsty but you do drink water (maybe you're Mark Zuckerberg at a Senate hearing), as well as situations where you're thirsty and drink, or not thirsty and don't drink.


find a regular expression and FA that each define $L_1 \cap L_2$

Hint: Every non-empty string in $L_1$ starts with $a$. Every string in $L_2$ starts with $b$.


Find a language $L$, such that $L \notin \mathbf{P}$, but $L^* \in \mathbf{P}$

Am I on the right track? It seems to me that I'm trying to prove something stronger than what I'm asked

That looks like an excellent approach. Proving something stronger is sometimes easier1 and usually useful.

What's particularly nice about your template for $L$ is that it opens up new questions about what happens if you generalise to $L = A \cup B$ where $A$ and $B$ are in different complexity classes and $B \subset A^*$. The extreme of $A$ regular and $B$ undecidable is good enough, but you could also consider $B \in NP^c$, $B \in EXP^c$, maybe specific context-free $A$, ... Perhaps it would be an interesting question to ask how close they can be to each other while still getting some kind of separation. If you enjoy this kind of thing, there may be a mini research project in it.

1 This is particularly true of proofs by induction, where proving a tight bound often makes the inductive step work where a loose bound wouldn't.


FOL substitution - is it possible to substitute two variables with each other? e.g. $\theta=\{x/y,y/x\}$?

Given the usual substitution function $[x/y]$ s.t.

  $M[x/y]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$,

your desired function can be defined as follows:

  $M [x//y] =_{df} M[x'/y][y/x][x/x']$ provided $x'$ doesn't occur in $M$.

Example. Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then:

\begin{align*}
D &= C~[Q~//~R]\\
&= [m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)][Q'/R][R/Q][Q/Q'] \\
&= [m(P,X,Y)←m(Q,X,Z),m(Q',Z,Y)][R/Q][Q/Q']\\
&= [m(P,X,Y)←m(R,X,Z),m(Q',Z,Y)][Q/Q']\\
&= m(P,X,Y)←m(R,X,Z),m(Q,Z,Y)
\end{align*}


Multi-dimensional Knapsack with added one-per-group constraint

One reasonable starting point is to try formulating it as an instance of integer linear programming, and apply an ILP solver.  This might not be the best possible algorithm, but it is simple and easy to try.

Let $A_{i,j}$ be the $j$th vector in the $i$th set.  Define zero-or-one variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means you have picked the $j$th vector from the $i$th set.  Then you have constraints of the form

$$\sum_{i,j} A_{i,j} x_{i,j} = t$$

where $t$ is the target vector.  (Notice that this is a sum of vectors, so it actually turns into 30 different equations, one per dimension.)  Also to ensure that you pick exactly one element from each set, we have

$$\sum_j x_{i,j} = 1$$

for every $i$.  Then send that to an ILP solver.


Prove grammars with long derivations generate infinite languages

G is in CNF. We can ignore the derivation S->eps since it is the only derivation of an empty string so it is only part of a derivation of length 1. I assume that the start symbol S counts as one of the "variables" or non-terminals, so there are (v-1) other non-terminals. S can only appear at level zero of the derivation.

In a derivation, every step replaces a non-terminal with a terminal, or increases the number of non-terminals by 1. Therefore, if N generates a string x of terminals and non-terminals, x is either a single terminal with a one-step derivation, or x consists of at least two symbols.

If G generates a string s, and in the derivation a symbol N derives itself (N -> x N y, where x, y are strings of terminal and non-terminal symbols), then we found that either x or y are non-empty, and derive non-empty strings of terminals (since they were part of a derivation). And since we derived N -> x N y, we can derive N -> $x^k N y^k$ for any k > 0, so the language is infinite.

So we have seen that if a non-terminal N occurs twice in any derivation, the language is infinite. Now look at the derivation of a tree. Level k of the tree has at most $2^k$ nodes. If the tree has a height h, then the nodes at levels $k = 0$ to $k = h-1$ may have contributed a derivation step, for a total of $2^h-1$ derivation steps. If a string s is derived in more than $2^v$ steps (actually, in $2^v$ or more steps), then it has a height v+1 or greater. If you look at a node at level v+1, then there are v non-terminals at levels 1 to v, and since there are only v-1 non-terminals after than S, one non-terminal must occur twice. Which makes the language infinite.

We can make any grammar epsilon-free quite easily: Introduce a new symbol $S_0$ and a rule $S_0->S$, so that $S_0$ will not occur on any right hand side of a rule. Then as long as there is a derivation N->eps with N ≠ $S_0$, remove that derivation, and for every rule with N on the right hand side, add rules with any possible subset of these N's removed. Remove all duplicate rules, and the only rule containing eps that is possibly left is $S_0 -> eps$. In an epsilon-free grammar we have the same fact that if the grammar contains a string s where the derivation contains a derivation N -> x N y where x or y are non-empty, then the language is infinite.


Is it possible to create a human thinking and acting program on a computer?

Quantum computers have the same power as classical computers, only they can apparently solve some problems much faster. In order to simulate a human, you need to consider two aspects:

Cognitive aspect: The program should behave like a human being.
Physical aspect: The object should look like a human being.

Turing suggested a way of sidestepping the second issue. He suggested limiting the interaction to a text-based "chat". Even in this case, the computer has to careful regarding reaction times: the computer can presumably type faster than a human and perform calculations faster.

There are several variants of the Turing test, but one of them involves many testers and two interviewees: a bona fide human and a computer. The computer is trying to pass as human. An interviewer gets assigned either the human or the computer, and should guess which is which. The computer passes the Turing test if the interviewer guesses no better than a random coin toss.

Current computers are not able to pass the Turing test. Whether they could potentially pass the test is at this point a philosophical and religious question. One advantage that humans have over computers is their large brain and their long learning period. However, if we could build large enough computers, so far we don't understand the algorithmic behavior of the brain, and so cannot mimic it. Artificial intelligence tries to ape human intelligence using different "hardware". Whether this approach can be successful or not is not clear.

In the past few decades, focus has switched from trying to emulate the brain to trying to solve certain tasks, such as translation. Modern techniques use statistical tools that are not aimed at mimicking behavior but only at mimicking competence. This approach works much better than earlier approached which did try to understand what human cognitive processes are based on. Perhaps this approach is hopeless if the goal is passing the Turing test.

So what is missing for artificial intelligence to succeed? Higher processing power? Computation techniques mimicking brain functions? Mechanisms like the Universal Grammar which might be hiding in our genes? Nobody knows. But for many people, there is no theoretical barrier, only practical ones.


Find all items which are subsets of an item

Your problem is the same one faced by SAT solvers who want to eliminate subsumed clauses from a CNF formula.  Any clause $B$ that contains a superset of the literals of another clause $A$ in the formula is redundant and can be removed without changing the satisfiability of the formula.  We say $A$ subsumes $B$, so $B$ can be discarded.  Instead of single valued literals, you have these item tuples but it is the same problem as finding $A$.

The algorithms used are refinements of the naive algorithm, where you iterate through each element of a potential subset, checking to see if it occurs in $x$.
If you sort $x$'s items you can reduce the linear time search to log $\vert{x}\vert$.  If you use a hashtable to store $x$'s items you can have amortized constant time for each search.  Because of the hashing overhead, save this optimization for large sets.  Bitmask signatures for each set allow you to do a cheap initial check, only doing the expensive iteration and searching of $x$ if the bitmaps can't rule out a subset match.


EQtm is not mapping reducible to its complement

Your language is $\Pi_2$-complete: it can be written as a $\Pi_2$ formula, and TOT can be reduced to it. The complement is therefore $\Sigma_2$-complete. No computable reductions can exist between $\Pi_2$-complete and $\Sigma_2$-complete sets (why?).


In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?

I think it is the "two general" problem.

The "two general" problem is informally stated as follows [1]:

  The commanding general of the first division wishes to coordinate a simultaneous attack. The generals can communicate only by means of messengers. Normally, it takes a messenger one hour to get from one encampment to the other. However, it is possible that he will get lost in the dark or, worse yet, be captured by the enemy.

What is the difference between this and your "message-exchanging" problem?

[1] Reasoning about Knowledge. By Ronald Fagin, Joseph Y. Halpern, Yoram Moses and Moshe Vardi.


Question regarding terminology used to describe Benes networks

I think they are talking about a path that goes from the left edge to the right edge, and then back to the left edge again.  That path will never visit any node more than once.  By "without collisions", they mean that the left-to-right part of the path will never intersect with the right-to-left part of the path.

I think.


How to choose the maximum number of nodes (with constraints) from a graph

Assume the set of nodes have weights $v_1 < v_2 < \dots < v_n$.

Two observations that follow immediately from your restrictions:

Your selection has to be a set of the form $v_i, v_{i+1}, \dots, v_n$.
Every chosen node is neighbour of another chosen node.

That is, we want to find

$\qquad\displaystyle \min \{ i \mid \forall j \geq i\ \exists j' > j\,.\ j \in N(j')\} $

where $N(i)$ denotes the neighbourhood of nodes with (weight-)index $i$.

Therefore, the following algorithm solves the problem in time $O(n \log n)$ (assuming an adjacency matrix):

Sort the nodes by weight.
Choose nodes greedily from the back of the list as long as the new node is neighbour of one of its predecessors (and you have chosen less than $x$).
Output the result.

I'll leave the proofs of correctness and runtime to you.

Now, if weights can be equal we may be able to take some more nodes; if $v_i$ is the first weight we don't pick according to the above algorithm, we have to check all $k$ nodes of weight $v_i$ we have not checked yet, picking as many as we can. This adds a fix-point iteration with at most $k$ iterations running in time $O(k)$ each.

An alternative is to sort the weights in to buckets and pick reachable nodes from the next smallest buckets. Details again left to the reader.


Case where anti-dependency doesn't need pipeline stalling

You can eliminate anti-dependences (WAR dependences) with register renaming, so if you're doing renaming there will be no stalls from anti-dependences.  The other case is if you already know the write isn't going to interfere with the read (for example you know all the instructions with reads in them have already done their register reads).

Note that the traditional "5-stage" pipeline is doing the equivalent of register renaming using its bypass registers, so in that case you never need to stall.


Let me start of with a recommendation: treat Landau notation just as you (should) treat rounding: round rarely, round late. If you know something more precise than $O(.)$, use it until you are done with all calculations, and Landauify at the end.

As for the question, let's dig through this abuse of notation¹. How would we interpret something like $h \in O(f + O(g))$? We should replace $O$ with its definition from the inside out. So, we get

$\qquad \displaystyle \exists g' \in O(g).\, h \in O(f + g')$

and then

$\qquad \displaystyle \exists g' \in O(g).\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + g'(n))$

which is equivalent to

$\qquad \displaystyle \exists c > 0.\,\exists d>0.\, \forall n.\, h(n) \leq d(f(n) + cg(n))$.

As certainly² $d(f(n) + cg(n)) \leq cd(f(n) + g(n))$, we see that this is equivalent to $h \in O(f + g)$; the loss of precision is ignored by $O$ anyway.

What about other combinations, say $h \in O(f + \Omega(g))$? If we try the same here, we get

$\qquad \displaystyle \exists g' \in \Omega(g).\, h \in O(f + g')$.

But this is a tautology: $h$ is certainly bounded above by something arbitrarily large. So, combining upper and lower bounds in this fashion is not meaningful.

$O(.)$ and the other Landau symbols map functions to function classes. Feeding it a function class is not immediately meaningful.
At least if we consider only positive functions, which we can safely assume when talking about runtimes. I'm not sure this works in general.


Why do we use RSA if it is not secure against chosen ciphertext attack?

The exact quote from the book is

  The basic RSA algorithm is vulnerable to a Chosen Ciphertext Attack (CCA)

So the answer to your question is that we don't use the "basic RSA algorithm" in practice. The basic RSA algorithm is also sometimes referred to as textbook RSA. Textbook RSA is malleable, which is why it is vulnerable to a chosen ciphertext attack. The attack works like this.

Eve has a ciphertext $c$ that she wants to learn the corresponding plaintext $m$ for. She has access to a decryption oracle that will decrypt any $c'\neq c$. So, she chooses a random value $r<n$ and computes $c'=c\cdot r^e\bmod{n}$. Note that since $c=m^e\bmod{n}$, we have $c'=(mr)^e\bmod{n}$ and $c'\neq c$.

Eve submits $c'$ to the decryption oracle, which returns $mr$. Eve now divides this by $r$ to recover $m$.

In practice, no one should use textbook RSA. To thwart this particular attack, we use padding. This removes the malleable property of RSA.


Why we can't use non-deterministic turing machines in this case?

Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In other words, the TM always halts.

In your approach the TM machine has to guess infinitely many strings and check if their forth power belongs to $L(G)$. A nondeterministic Turing machine cannot check infinitely many strings in finite amount of time.

Decidability problems efficiently solved by non-deterministic Turing machines are also solved by deterministic Turing machines. In other words, their computational powers are equivalent.


Why is it important for functions to be anonymous in lambda calculus?

The main theorem regarding this issue is due to a British mathematician from
the end of the 16th century, called William Shakespeare. His best known
paper on the subject is entitled "Romeo and Juliet" was published in
1597, though the research work was conducted a few years earlier,
inspired but such precursors as Arthur Brooke and William Painter.

His main result, stated in Act II. Scene II, is the famous theorem:

  What's in a name? that which we call a rose
  By any other name would smell as sweet;

This theorem can be intuively understood as "names do not contribute
to meaning".

The greater part of the paper is devoted to an example complementing
the theorem and showing that, even though names contribute no meaning,
they are the source of endless problems.

As pointed out by Shakespeare, names can be changed without changing
meaning, an operation that was later called $\alpha$-conversion by Alonzo
Church and his followers. As a
consequence, it is not necessarily simple to determine what is denoted
by a name. This raises a variety of issues such as developing a
concept of environment where the name-meaning association are
specified, and rules to know what is the current environment when you
try to determine the meaning associated with a name. This baffled
computer scientists for a while, giving rise to technical
difficulties such as the infamous Funarg problem. Environments remain
an issue in some popular programming languages, but it is generally
considered physically unsafe to be more specific, almost as lethal as
the example worked out by Shakespeare in his paper.

This issue is also close to the problems raised in formal language theory,
when alphabets and formal systems have to be defined up to an
isomorphism, so as to underscore that the symbols of the alphabets are
abstract entities, independent of how they "materialize" as elements
from some set.

This major result by Shakespeare shows also that science was then diverging
from magic and religion, where a being or a meaning may have a true name.

The conclusion of all this is that for theoretical work, it is often
more convenient not to be encumbered by names, even though it may feel
simpler for practical work and everyday life. But recall that not
everyone called Mom is your mother.

Note:
The issue was addressed more recently by the 20th century American logician
Gertrude Stein. However, her mathematician colleagues are still
pondering the precise technical implications of her main theorem:

  Rose is a rose is a rose is a rose.

published in 1913 in a short communication entitled "Sacred Emily".


How to represent zero as floating point number?

Note: In the interest of making this somewhat self-contained, I am using terminology from the most recent versions of the IEEE-754 standard. Prior to 2008, "subnormal numbers" were called "denormal numbers", and "binary32" was called "single precision". Some textbooks/papers/etc may use the old terms.
The representation that you are talking about here is called, in IEEE-754, normal numbers. A normal number is one which has a single nonzero digit on the left-hand side of the radix point (i.e. decimal point or binary point) of its mantissa.
The representation for zero uses a slightly different representation, namely, subnormal numbers.
Taking binary32 as our example, there are three fields:

The sign bit, which is 1 bit in size.
The exponent field, which is 8 bits in size.
The significand field, which is 23 bits in size.

The sign bit is 0 if the number is positive, and 1 if it is negative.
There are 8 bits reserved for the exponent field, so we can store a number between 0 and 255. We encode the exponent with with a bias of 127, using only the range of -126 to 127 for normal exponents.
The significand field is used to store the mantissa. In binary, the only nonzero digit is 1, so it is not stored explicitly in the IEEE-754 representation of normal numbers. So, for example, to represent the number $3$, we first express it in normal form:
$$+1.1_2 \times 2^1$$
The sign bit is 0 (because the number is positive). The exponent field is $1 + 127$, the true exponent plus the bias, which is 10000000 stored as a bit field.
The mantissa is $1.10000000000000000000000_2$. In normal form, the digit before the binary point is always $1$, so we don't store it, giving 10000000000000000000000 for the significand field.
The reason for the distinction between "mantissa" and "significand" is because the mantissa is the true mathematical mantissa of the number, but the "significand" is only the bits that we need to store.
Using this biased representation for the exponent gives us two bit patterns that we didn't use: 00000000 and 11111111.
The "all ones" pattern is used for values that are not finite numbers: infinity and NaN ("not a number"). I won't talk further about these here.
The "all zeroes" pattern is used for subnormal numbers. What it means is that the mantissa is the significand field with an implicit zero before the binary point, and the exponent is fixed to be -126. So, for example, if the sign bit is zero (positive), the exponent field is all zeroes, and the significand field is 10000000000000000000000, then this represents the number:
$$+ 0.10000000000000000000000_2 \times 2^{-126} = 2^{-127}$$
By setting the sign bit, the exponent field and the significand field to all zeroes, this gives us a representation for zero. Plus, it's the most desirable representation as far as programmers are concerned: if you have zeroed-out memory (all of the bits are set to zero) and read it as a floating-point number, it means zero.
There is also a representation here for negative zero. This is by design, but the reasoning behind it is beyond the scope.
Now this is all binary, and you are asking about decimal. IEEE-754 also defines a decimal floating point format, with two different binary encodings. While the exponent is always base-10, the mantissa/significand field can be either binary or densely packed decimal. The idea is still the same. One exponent value is reserved, and zero is represented using that special value.


All words containing at least twice as many zeroes as ones

The language is context-free. As you read the string, you'll need a counter comparing two values: $\#_0 \cdot 2$ and $\#_1$. Such counter can be implemented using the stack of the PDA.
When a $0$ is read:

if there is a $1$ on top of the stack, pop it. If the stack is now empty, add a $0$, otherwise pop again.
else add $0$ to the stack twice

When a $1$ is read:

if there's a $0$ on top of the stack, pop it.
else add $1$ to the stack

It is easy to see* that the stack contains now the difference between $\#_0 \cdot 2$ and $\#_1$, encoded as the number of symbols on stack and the symbol used. After the entire string has been scanned, the top symbol of the stack tells which of the numbers is greater: if the top symbol is $0$ or the empty stack symbol, accept. Otherwise reject.
*If you need a more formal proof of this construction's correctness, it is fairly easy proven by induction: first establish that the symbols of the stack represent the correct counts after reading the first symbol, then perform an induction step with the assumption that the first $n$ symbols resulted a correct count on the stack and showing that the $n+1$th symbol read doesn't violate this correctness.


How to come up with the runtime of algorithms?

This part of computer science is called analysis of algorithms. Many times people are satisfied when they are given a guarantee that an algorithm’s performance is not worse than a specified bound and they dont’t care about the exact performance.

This bound is conveniently denoted with the Landau-notation (or big-Oh notation) and in case of $\mathcal{O}(f(n))$ it is an upper bound. That is for inputs of size $n$ the algorithms complexity is guaranteed not to exceed (a constant times) $f(n)$. Most of the time it is clear from the context what the “unit” this bound is measured in is. Note that “runtime” measured in actual time units (seconds, minutes, etc.) is frowned upon as you can’t compare them meaningful across different computers. Typically a “costly” elementary operation is identified, like compares and exchanges in sorting algorithms, or pushs and pops if the algorithm includes a stack, or updates to a tree data structure used in the algorithm. This elementary operation is understood as to be the dominating one, that has the largest contribution to the algorithm’s complexity, or perhaps it is more expensive than another one in a particular setting (multiplications are considered to be more expensive then additions for example). It has to be selected so that the cost of other operations are (at most) proportional to the number of the elementary operations.

This upper bound is called the worst-case bound or the worst-case complexity of the algorithm. Because it has to hold for all inputs of the same size $n$ and the worst-case inputs incur the highest (worst) cost. The actual performance for a specific input of size $n$ may be a lot lower than this upper bound.

While it is possible to do an exact analysis it is usually much more involved to arrive at an exact result. Also, an exact analysis means accounting for all operations in the algorithm, and that requires a rather detailed implementation; while counting elementary operations can be done from a mere sketch of the algorithm most of the time. It is nice if such an analysis is possible but it is not always necessary.  Because small inputs are not much of a problem, you want to learn what happens when the input size $n$ gets large. Knowing that the algorithm’s complexity is bounded by $5n^2+3n-2\log(n)$ is nice but overkill when looking at the performance asymptotically ($n\rightarrow \infty$), because the term $n^2$ dominates the others for large $n$. So proving an upper bound of $\mathcal{O}(n^2)$ suffices.

If you have two algorithms and you can guarantee that one performs like $\Theta(n^2)$ and the other like $\Theta(n)$ you can easily decide which one is “faster”, has a lower “cost”, uses less elementary operations, just by noting that a quadratic function grows faster than a linear function. In practice that means that the linear algorithm finishes earlier or that it can process larger inputs in the same time. But it might be that the constants hidden by $\Theta$ are such that for practical $n$ the $\Theta(n^2)$ algorithm is faster.

However if you have three algorithms all with a $\mathcal{O}(n^3)$ guarantee on their complexity you are hard pressed when you have to decide which algorithm to choose. Then more detailed bounds are needed, or perhaps even an exact analysis.

It may very well be that this analysis is hard to do and you can’t give a tight bound. Then there is a gap between the actual worst-case performance, perhaps $n^2$ and your bound of perhaps $\mathcal{O}(n^3)$. Then a clever idea, a more involved analysis is necessary to close the gap and provide an improved bound. This is just an improvement of the bound not to the algorithm. Typically you have to argue more carefully when you want to prove a tighter bound.

This all said, an analysis of an algorithm can be as simple as looking at the implementation and counting the nesting depth of the for loops to conclude that the operations in the innermost loop are executed not more than $\mathcal{O}(n^3)$ times when say three loops are nested.

For some types of algorithms the analysis follows always the same pattern, so there is a theorem like the master theorem, that tells you generically what the algorithms performance will be. Then you only have to apply the theorem to get the bound.

Perhaps you are faced with a recursive algorithm and you are able to describe the algorithms complexity by a recurrence relation. Then solving the recurrence gives the desired bound.

Typically you have to exploit some properties of the inputs. Sorting algorithms are deeply connected to permutations and knowing something about the number of inversions in a permutation helps a lot when analysing the performance.

There is no general approach on how to proceed in an analysis. As discussed above it depends on the algorithm, its inputs, its implementation, the elementary operation choosen, what mathematical tools you have at hands, the desired sharpness of the bound.

Some may prefer a smoothed-analysis or an average-case analysis over a treatment of the worst-case. Then different techniques are necessary.


Time in circuits corresponds to the depth.
Therefore by polynomial time means polynomial depth.

The number of processors is the size of the circuit,
i.e. number of the gates in the circuit.
So by exponential number of processors you allow exponential size.
This would be the class $\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$.
But every function is already in $\mathsf{DepthSize}(2, 2^{n^{O(1)}})$
(think of the CNF of the function you want to compute).

The take away is that exponential number of processors is
too strong to be useful by itself.

One reasonable restriction to put is to limit the amount of communication
between different processes.
E.g. we each process can only communicate with
only polynomially many other processes and the messages have polynomial size.
That would be $\mathsf{PSpace}$ as explained in answers to Aterm's question on cstheory.
Another way to see it to remember that
$\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$,
problems computable by alternating Turing machines in polynomial time.
Alternation in Turing machines is essentially forking new processes and then joining after they finish by taking the conjunction/disjunction of their return values.


Algorithm for fewest number of moves with artificial minimum

We construct a directed graph $G'$ with $V'=V \times \{0, \dots, k\}$ when $k$ is the lower bound on the path length.
For every edge $uv$ in $E$ and $i<k$ we add $(u,i)(v,i+1)$ and $(u,k)(v,k)$ to $E'$.

Now we search for a shortest directed path from $(s,0)$ to $(t,k)$ in $G'$ to find the shortest path from $s$ to $t$ in the original graph $G$.

The digraph $G'$ has $(k+1)n$ vertices and $(k+1)m$ edges. Hence, the running time is still polynomial

Searching for the shortest odd (or even) path works similarly. Indeed I think that any regular (as in NFA recognizable) constraint on the path can be solved like that.

Edit:
Note that the second entry in the tuples stays the same. To be more precise, consider any path $P=v_0v_1…v_kv_{k+1}…v_n$ on $G$ with length $≥k$. Then there is a corresponding path $P'=(v_0,0)(v_1,1)…(v_k,k)(v_{k+1},k)…(v_n,k)$ on $G'$.
Similarly, every path on $G'$ induces a path on $G$.


Don't guess, but look at the definition which tells you that in order for $f(n) = \Omega(g(n))$ to hold, it must be the case that $\lim_{n \to \infty} f(n)/g(n) > 0$.

If I plug in $f(n)$ and $g(n)$ according to your description, I think I will get $\lim_{n \to \infty} f(n)/g(n) = 0$. You should check whether I made a mistake and draw the appropriate conclusions.


Show that the language of strings not in the union of two regular languages is regular

There are several ways to show that a language is regular (check the question How to prove a language is regular?)

Specifically for the language in your question, start with DFAs for $L_1$ and $L_2$ and try to construct an NFA for $X(L_1,L_2)$ using them. More details below:

   Note that $X(L_1,L_2) = \overline{L_1} \cap \overline{L_2}$.
 From the DFA of $L_1$ construct the DFA of $\overline {L_1}$ (making any final state not-final, and vice-versa). Do the same for $L_2$.  Intersection of regular languages can be constructed via product machine (see this question).
 [Of course, if you already know that a complement of a regular language is also regular, and so the intersection of two regular languages – you are done without constructing those DFAs..]


Is computation expression the same as monad?

First of all, computation expressions are a language feature, while monads are mathematical abstractions, so from this point of view, they are completely different things.

But that would not be a very useful answer :-). Computation expressions are a language feature that gives you a syntax which can be used for programming with computations (or data types) that have the monadic structure, but they can be also used with other structures. You can read my F# computation expression zoo paper for more details, but computation expressions can be used with:

Monads, but also additive monads (what Haskellers call MonadPlus or MonadOr)
Composed computations (what Haskellers call monad transformers)
Computations that are monadic, but support other F# constructs like exception handling
Monoids (and a couple of variations without monadic bind)
Applicative functors (though this is only implemented in a research extension)

So, computation expressions are certainly closely linked to monads, but they are not linked to them that closely. This is in contrast e.g. with Haskell's do notation, which is much more closely linked to monads (although even that can be used with computations that are not strictly mathematically monads).


Find the minimum subset of a set of numbers with product divisible by a given integer

Compute all the prime factors of $k$. It would take $O(\sqrt{k})$ time $\approx$ $10^5$ time. Note that, there could be at most $10$ different prime factors of $k$ since considering the $10$ smallest prime numbers gives the product: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$ which exceeds $10^9$. Let us call the prime factors of $k$ as: $f_{1}, \dotsc,f_{10}$ with multiplicities $m_{1}, \dotsc,m_{10}$, respectively. The sum of multiplicities (or total number of prime factors) $\sum_{i = 1}^{10}m_{i}$ could be at most $30$ since $2^{30}$ exceeds $10^{9}$.
Now, you also need to factorize the numbers given in array $a$. However, you do not need to obtain all its factors. You just need to obtain the factors which are among $f_{1},\dotsc,f_{10}$ since other prime factors are irrelevant for $\prod\limits_{x\in m}x \equiv 0\mod k$. Therefore, just check that if an array entry $a[j]$ is divisible by some factors $f_{i}$ (obtained in step 2) and obtain its multiplicity in $a[j]$. Let $m_{i}^{j}$ denote the multiplicity of factor $f_{i}$ for an array entry $a[j]$. Computing all $m_{i}^{j}$ would take at most $\sum_{i = 1}^{10}m_{i} \cdot n = 30 \cdot n$ time $\approx 10^{6}$ time.
Now, you just need a Dynamic Programming approch to obtain the minimum value on size of $m$. Let $A$ denote a matrix of dimension $(m_{1}+1)$x $(m_{2}+1)$ x $\dotsc$x $(m_{10}+1)$ x $n$ such that an entry $A[j_{1}][j_{2}] \dotsc[j_{10}][t]$ denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{t}\}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$. In otherwords, $k'$ is composed of all possible combinations of the factors $f_{1}, \dotsc,f_{10}$. Therefore $k'$ can take at most $(m_{1}+1) \cdot (m_{2}+1) \dotsc (m_{10}+1) \approx 2^{10} \approx 10^{3}$ different values. This bound is based on the assumption that all $10$ factors are distinct. If all the factors are the same the we have $k' \leq 30$ since $2^{30}$ exceeds $10^9$. So I believe $k'$ would take at most $\approx 2 \cdot 2^{10} \approx 2 \cdot 10^3$ different values.

Now, assuming 1 based indexing for the matrix $A$, we define the DP steps as follows.
The Main DP step:
$$
    A[j_{1}][j_{2}]\dotsc[j_{10}][t+1] = \min \left\{\begin{array}{lr}
        A[j_{1}][j_{2}]\dotsc[j_{10}][t], & \textrm{do not pick $a[t+1]$}\\
        1 + A[j_{1}-m_{1}^{t}][j_{2}-m_{2}^{t}]\dotsc[j_{10}-m_{10}^{t}][t], & \textrm{pick $a[t+1]$}\\
        \end{array}\right.
  $$
The Base Step:
$A[j_{1}][j_{2}]\dotsc[j_{10}][1] = 1$ if $j_{i} \leq m_{i}^{1}$ for all $1 \leq i \leq 10$. And $A[j_{1}][j_{2}]\dotsc[j_{10}][1] = \infty$ otherwise. Here $\infty$ means that it is not possible to satisfy the constraint $\prod\limits_{x\in m}x \equiv 0\mod k'$ given $m \subseteq \{a_{1} \}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$.
The Required Ouput:
The output of the DP procedure would be the solution: $A[m_{1}][m_{2}]\dotsc[m_{10}][n]$ which naturally denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{n}\}$ and $k' = k = \prod_{i = 1}^{10} m_{i} \cdot f_{i}$.
Running Time Analysis of DP:
The size of the matrix $A$ is $(\textrm{number of possible value of $k'$}) \cdot n \approx 2 \cdot 10^3 \cdot 10^4 \approx 2 \cdot 10^{7}$. Computing each entry takes 2 or 3 operations. Therefore total running time would be $\approx 6 \cdot 10^7$.

Thus the overall running time is $\approx 10^5 + 10^6 + 6 \cdot 10^ 7 \approx 10^8$. I have done the loose analysis, so it should be doable in 3 sec.
Total Space Complexity  $\approx $ size of the matrix $A$ $\approx 2 \cdot 10^7$


Using inductive hypothesis on recurrence relation?

We can open up the recursion to obtain
\begin{align}
T(n) &\leq n \log n + 2\lfloor n/2\rfloor \log \lfloor n/2 \rfloor + 4\lfloor \lfloor n/2 \rfloor/2\rfloor \log \lfloor \lfloor n/2 \rfloor/2\rfloor \\ &\leq
n\log n + n \log (n/2) + n\log (n/4) + \cdots \\ &\leq
n\log n + n\log n + \cdots \\ &= O(n\log^2 n),
\end{align}
since it takes $\Theta(\log n)$ steps to get to the base case.
If you're more careful, you can show that in fact $T(n) = \Theta(n\log^2 n)$.


An approach to determine whether language is regular or not?

I'm not aware of any completely "algorithmic" method to decide whether a language is regular.

For the specific language you are interested in, you can start by observing that it can be written as combination of unions and intersections of a finite number of regular languages:
$$
\bigcap_{\alpha \in \Sigma} \left( L_{2,\alpha} \cup L_{3,\alpha} \right),
$$
where:

$L_{2,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 2.
$L_{3,\alpha}$ is the language containing all words $w$ such that $|w|_\alpha$ is divisible by 3.

It is easy to show that all these languages are regular (since, in each language, $\alpha$ is now fixed). A DFA for $L_{2,\alpha}$ has two states $q_0, q_1$ where $q_i$ means that the number of characters equal to $\alpha$ encountered so far is $i$ modulo 2. A DFS for $L_{3,\alpha}$ is similar but has $3$ states.

The regularity of $L$ follows from the fact that regular languages are closed under union and intersection.


Rényi entropy at infinity or min-entropy

Suppose $p_1 = \max_i p_i$. We have
$$ p_1^n \leq \sum_{i=1}^N p_i^n \leq N p_1^n. $$
Therefore
$$ \frac{n \log p_1 + \log N}{1-n} \leq H_n(X) \leq \frac{n \log p_1}{1-n}. $$
As $n \rightarrow \infty$, $\log N/(1-n) \rightarrow 0$ while $n/(1-n) \rightarrow -1$.


Minimum number of tests to identify subset of modules that trigger a bug?

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer.  The solution is: delta debugging.  Delta debugging solves exactly this problem.

Let me elaborate.

Problem statement

I am interpreting your question as asking about the following problem:

We have $M$ software modules, and some way to run the program in a way where only a subset of them are active (and we can choose the subset freely).
There is a subset $S$ of $N$ of the modules.  There's a fault that is triggered whenever we run the program with all of those modules active.  In other words, if the set of active modules is a superset of $S$, a fault will occur; otherwise, no fault will occur.
The fault is perfectly reproducible and detectable.
Now, we want to find the set $S$ using as few tests (invocations of the program) as possible.

Solution: delta debugging

Delta debugging will solve this problem.  If you have $M$ software modules, and some subset of $N$ of them are responsible for the fault, delta debugging can find the minimal subset that trigger the fault.

Delta debugging works by starting with all of the modules active, and gradually removing some of them.  It picks out some chunk of modules, and tries running the program with those modules inactive.  If the fault still occurs, then we know that none of them are responsible for the fault, so they can be permanently deactivated in all future tests.  Delta debugging starts with large chunks, and gradually reduces the chunk size: it first tries deactivating the first $M/2$ modules, then deactivating the second $M/2$ modules; if neither of those offers any progress, then it tries deactivating the first $M/4$ modules, then the second $M/4$ modules, then the third $M/4$ modules, and then the last $M/4$ modules; then it moves on to chunks of size $M/8$; and so on.

For more details, allow me to point you to a nice description of delta debugging.

Delta debugging is efficient

Delta debugging is expected to take about $O(N \lg M)$ tests, to find the subset.

You might notice how this is a nice generalization of binary search.  When $N=1$, binary search needs $O(\lg M)$ tests, just as delta debugging does.  The difference is that delta debugging also scales nicely when $N>1$.

You might also notice that this is close to optimum.  We can prove a $\Omega(N \lg(M/N))$ lower bound (roughly).  In particular, there are ${M \choose N}$ possibilities for the subset $S$, and each test provides one bit of information (either it triggers a fault or not), so it is easy to see that we need at least $\lg {M \choose N}$ tests.  Now

$$\lg {M \choose N} \approx \lg (M^N/N!) \approx N \lg M - N \log N \approx N \lg M - 0.7 N \lg N \ge N (\lg M - \lg N).$$

Therefore, delta debugging is approximately asymptotically optimal, in terms of the number of tests required.

For a more detailed performance analysis, see this analysis by Jesse Ruderman.

Discussion

That said, I am somewhat skeptical of whether this will be useful in practice.  A crucial assumption here is that you could run the program with a chosen subset of its modules active, and the rest artificially deactivated.  I don't see how to do that in practice.  Therefore, I do not see how this can be applied in practice.

I suspect your theoretical model of the problem probably needs to be adjusted, but since you didn't tell us anything about your particular application setting or the justification for your model, I don't have enough information to specify how to fix the model.

Typically, delta debugging is used for a different purpose.  Normally, delta debugging is used to reduce the size of the test case (not the size of the program).  Say you have a test case with $M$ lines that crashes your program, but only a subset of $N$ of the lines are actually necessary to trigger the crash (the rest are all irrelevant), and you want to find the minimal subset of lines needed. In other words, given a long complex test case that crashes your program, you want to "minimize" it: to find a smaller, shortest test case that also crashes the program -- because small test cases usually make the debugging process easier.  Then delta debugging can be used to solve that problem; in fact, that's what it was invented for, and what it's most commonly used for.


3-Dimensional Matching with at Most $2n$ Hyperedges

The restriction $m < 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m < 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' < 2n'$ assuming $n>0$. Also, this reduction can be generalized for any constant $c > 1$ to show that 3-dimensional matching is NP-complete with the restriction that $m < cn$.

For solving the problem faster I suggest to find some other restrictions in the instances you have. For example in graphs, the natural parameter to express sparseness would be degeneracy.


BFGS vs L-BFGS -- how different are they really?

No, they're not the same.  In some sense, L-BFGS is an approximation to BFGS, one which requires a lot less memory.  BFGS and L-BFGS are explained in great detail in many standard resources.

Very crudely, you can think of the difference like this.  BFGS computes and stores the full Hessian $H$ at each step; this requires $\Theta(n^2)$ space, where $n$ counts the number of variables (dimensions) that you're optimizing over.  L-BFGS computes and stores an approximation to the Hessian, chosen so that the approximation can be stored in $\Theta(n)$ space.  Effectively, L-BFGS uses the approximation $H \approx M^\top M$ for some $k \times n$ matrix $M$ (I think).

Each step of L-BFGS is an attempt at approximating/guessing what the corresponding step of BFGS would do.  However, a single step of L-BFGS takes a lot less space and time than a single step of BFGS.  Consequently, you can do many more steps of L-BFGS within a particular time bound than BFGS.  Therefore, you might find that L-BFGS converges faster, because it can do so many more iterations within a given amount of time than BFGS can.

I don't know what a nonsensical minimum means, or why BFGS would converge to something worse than L-BFGS if both were allowed to run for an unbounded amount of time.


Definition of Disjointness for binary strings

We identify a binary string with a set in the following way: $x \in \{0,1\}^n$ corresponds to the set $\{ i \in [n] : x_i = 1 \}$. In particular, $0^n$ is identified with the empty set.


Leo's deterministic reduction for Earley Parsing

I found the problem: Essentially, I misunderstood the definition. It says that

  it is [B→αA.,k] with [B→α.A,k] being the only item in Ii with the dot
  in front of A, or if it is on the deterministic reduction path above
  [B→αA.,k].

Which should be interpreted as [B→αA.,k] should be considered to be created corresponding to [B→α.A,k]. The basic idea which seems to be elided in Leo's paper but given in Grune et al. (2008) is that, the deterministic reduction is basically simply an eager completion with all intermediate results thrown away. With this change, the parser works correctly.

(The "Parsing Techniques A Practical Guide" by Grune et al. from 2008 is the book I refer to here.)


Creating sum of all numbers within a sequence

From the top of my head I would use a greedy approach, always remove the lowest available number so the potential sum of later steps lessens the least this way. But I do not have a proof for this finding the top possible sum, especially not at 0:21 on Monday :-).

With 2,1,5,3,4(0) it would go to 2,5,3,4(2+1+5=8), then to 2,5,4(8+5+3+4=20), and end at 2,4(20+2+5+4=31). So it finds your sum, but this is just one case.


How can an extended linearizable history G be equivalent to sequential history S?

The idea of linearizability is that the parallel events behave as if each of them happened at a single point in time, during the duration of the actual execution of the event. Given a sequence of events, if the end point of event $A$ precedes the starting point of event $B$ then in any linearization, the time point of $A$ must precede the time point of $B$. These are the constraints $\rightarrow_G$, which we can think of as a partial order. The events are linearizable if the constraints are extendable to a linear order $\rightarrow_S$ such that the semantics match — the outcome of the events is the same as if they were applied in the order underlying $\rightarrow_S$. Perhaps this is what was meant by equivalence, though as you mention, it is clearly applied to the wrong objects. What is equivalent here is the actual turn of events and the turn of events given the order $\rightarrow_S$.


In memory paging, how does the S.O. know where the page is in secondary Memory?

The first thing is that when the page-table entry is invalid you are allowed to use all the other bits in the page-table entry for whatever you want.  So, for example, you could use it to store an offset into the swap space, or a disk block number.

But that's actually not the whole story.  Each process on most operating systems has some kind of segment map that describes for each valid range of logical addresses what's in that range.  Ranges that contain read-only data (such as the code segment, usually) don't need to be swapped.  Instead they can just be reread from the executable that contains them if they are needed again.


How do you read this context-free language?

The language defined as $\{a^ib^j\mid 2i=3j+1\}$ is just the set of all strings of $i$ copies of $a$ followed by $j$ copies of $b$, where $2i=3j+1$. Trying various values of $i$ and $j$ and realizing that both $i$ and $j$ must be integers, we see that the admissible solutions are
$$
(i,j)=(2, 1), (5, 3), (8, 5), (11, 7), \dotsc
$$
For example, with $i=5, j=3$ we see that $2i=2(5) =10=3(3)+1=3j+1$. The corresponding strings are
$$
aab,\quad a^5b^3,\quad a^8b^5,\quad a^{11}b^7 \dotsc
$$
and so on.

With a bit of thought, we can make a PDA for this language by pushing two $a$ markers on the stack for each $a$ we read and then popping off three $a$s for each $b$ we see. If we wind up with a single $a$ on the stack after having read all the $b$s, we pop that off and go to the accept state.

It's worth noting that the PDA you picture does not accept the language described. That one accepts the language $\{a^nb^{2n-1}\mid n>0\}$.


Proof that recursive languages are closed under concatenation

Imagine you have an algorithm $A$ that decides $L_A$ and an algorithm $B$ that accpts $L_B$. How would you write a program that checks whether any given word $w$ can we written as $w=uv$ with $u \in L_A$ and $v \in L_B$?

   Broad hint: how many possible choices for $u$ and $v$ are there?


Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)


Building functionally complete boolean circuits out of trinary logic

It is not possible to "invert" a value. Here is a list (computed in Python) of all unary functions achievable using your gate (the order of inputs is abc):

aaa
aba
abb
abc
aca
acc
bbb
cbb
cbc
ccc

An inverter would have one of the patterns ba?, c?a, ?cb (depending on which two values you choose to encode True and False), which none of these functions have.

On the other hand, it is possible to compute all monotone functions. Use a for True and c for False. The Or gate is realized as $x \lor y = (xy)$. The And gate is realized as $x \land y = ((((xb)y)b)a)$. (Note that your gate is symmetric but not associative.) There might be other solutions, e.g. using b and c.

Edit: Here is how to extend this to a complete simulation using double wires, according to vzn's suggestion. We represent True by (a,c) and False by (c,a). Negation is accomplished by swapping the two wires. The Or gate is formed by applying the Or gate described above for the first wire, and the And gate for the second wire. The And gate is defined analogously.

Further edit for the curious: here is how to compute all unary functions. We start with the list abc,aaa,bbb,ccc corresponding to the identity function and all constants. We now repeatedly choose two members and compose them, i.e. given functions $f,g$, we compute the function $(fg)$. Eventually the process stabilizes, that is generates no new functions, and we get the ten functions listed above.


By definition, a language $L$ is P-complete if for every language $M \in P$ there is a logspace reduction $f_M$ such that $x \in M$ iff $f_M(x) \in L$. Now suppose that $L$ is P-complete and that for some language $L' \in P$ there exists a logspace reduction $g$ such that $x \in L$ iff $g(x) \in L'$. Then for every language $M \in P$, $x \in M$ iff $g(f_M(x)) \in L'$, and so $L'$ is P-hard since the composition of logspace reductions is a logspace reduction.

Generalizing, this sort of argument always works as long as the composition of two legal reductions is a legal reduction. This is the case for both polynomial time reductions and logspace reductions.


Find if there is matrix that satisfying the following conditions

Hint #1:

   This can be solved with network flow.

Hint #2:

   Imagine $r_i$ units of flow entering the $i$th row, and $c_j$ units of flow leaving the $j$th column.  Does that give you any hints how to set up the graph for a network flow problem?


How to find several rectangles with minimum area to cover the red cells

The way I created the pictures in my comment is by Integer Linear Programming, specifically the following model:

$\text{minimize } x \cdot area \\
\text{for each red cell } (i,j): \: \sum_{k \in covers(i,j)} x[k] \ge 1 \\
x \in \{0, 1\}$

Where the decision variables x[i] refer to whether or not to use rectangle i, covers(i, j) is the set of rectangles that contain the cell (i, j), area is the vector of the areas of the rectangles, and the set of rectangles used is all 2x2, 2x3, 3x2 and 3x3 rectangles that fit on the grid and contain at least one red cell. You can use a slightly smaller set, for example it is never necessary to use a piece that's bigger than 2x2 that covers only 1 red cell, it could always be replaced by a 2x2 piece and give a better solution. Any rectangles of other legal sizes can be constructed from these pieces so they can be left out.

Actually even fewer rectangles can be used. For example, a rectangle that can be replaced by a smaller rectangle without uncovering any red cells is redundant. There is also the case where a 3x3 can be replaced by 2 2x2 rectangles, that potentially overlap, such that they together cover (at least) the same red cells, making the 3x3 redundant.

Experiment shows that presolving removes almost all columns (for relatively sparse problems), suggesting that it should be easy to a-priori not-generate many of them. I have not looked into that too deeply yet.

Despite ILP being NP-hard, large instances such as this or even this were solved in a couple of seconds. Maybe there is also an inherently efficient way though, I'm not sure.


How to enhance my skills as a programmer

You don't need books. You need to write lots of programs. Since you are interested in cryptography, you should practice writing programs that involve mathematics. A good way to do so is to join Project Euler and just go down the list. Good luck!


How do deal with the following situations using Prim's algorithm?

First of all , MST of a connected graph is a subgraph with the following properties:
i. Spanning Tree: No cycles -> n-1 edges(easy to prove)
ii. If we sum up the weights, we get the lowest possible.

Prim's algorithm is a greedy algorithm, which means that we always choose the best choice in every step(greedy).

From i, you can see that you never get self loops (acyclic).
Yes, because it's the edge with the lowest weight not because it is the only edge in this moment from D to connect in E; there maybe exist another edge eg. C->E would have been the next choice had the weight between D->E is 5.
No, it does not get to a non-terminating loop, you never choose the same edge again. Think like, there is a set S with all the edges that have not been discarded, after you choose the edge e then S is changed to S-e. In your example the best choice is to choose E->F.


Is it still transfer learning if you consider input as well as output? (neural networks)

This type of transfer learning only applies if you have the same features.  If you don't, you'll either have to do something else, or find some way to first extract a common set of features from both, or choose a feature set that is the union of the two features.  The latter choice would handle the example you gave of hotel reviews vs restaurant reviews.

That said, there is emerging evidence that for deep neural networks, it's not clear that transfer learning (pre-training on a different task) provides any advantage in aaccuracy over training from scratch on the second task.  Recent research has shown that if you train long enough on the second task, you get accuracy as good as if you start with weights from a network that was pre-trained on the second task.  So, it appears the main advantage of this kind of transfer learning might be to speed up training time, rather than to build better models.


RPI cluster performance related to network performance

I think i have solved it now. The problem was that in the example in the source they had:

8*3,50*16 and i was assuming (which is a very bad thing to do) that i should change everything except the 16, that it was a constant of sorts. Turns out, my RPI should have somewhere between 0 and 2 in the last multiple, alas it should be

4*1,2*x where x is somewhere between 0 and 2 (as my estimation) thus i have only to find out the actual number for X, and for some reason it seems hard to find it, one would have thought that the instructions per second or instructions per cycle would be documented for RPI.

bottom line, there was nothing wrong except for my thinking. sorry for this post, i should had read up a little bit more before i posted. I blame it on stress.

EDIT: i forgot to give the source that helped me solve the problem, here it is:

https://www.gpike.com/en/raspberrypi/benchmarking#hplc

and thx for the help!


Converting regular (Type-3) grammar to a deterministic finite state automaton

As Rick Decker said, the algorithm doesnt guarantee that the conversion from G will yieald a DFA. Therefore I should convert to a NFA and than to the DFA. The howto is here.


Why does the Pumping-lemma for context-free languages use uvwxy, but the one for regular ones uvw?

Both pumping lemmas have an intuitive explanation in terms of an automaton that can recognize a language.

A regular language can be recognized by a finite automaton. All words are recognized through:

either a finite path through the automaton: words that are shorter than the pumping length;
or a path that goes through a node at which there is a loop, in which case it is possible to go through the loop any number of times: that's the $y^n$ part, where $y$ is the path through one round of the loop and $n$ is the number of lops.

A context-free language can be recognized by a pushdown automaton. All words are recognized through:

either a finite path through the automaton: words that are shorter than the pumping length;
or a path that includes both a loop with pushes to the stack, and another loop with corresponding pops. Pushes and pops have to balance in order to get an empty stack at the end. Then the word contains a loop with pushes $v$, some further path $w$, and a loop with pops $x$. The number of runs through the two loops has to be the same, but it can be any number, hence the middle bit $v^n w x^n$.

You can also get a similar intuition from the ways regular and context-free languages can be specified by a regular expression and a context-free grammar respectively.

If a word is recognized by a regular expression, then:

either the word does use a part of the expression under the $^*$ (Kleene star) operator, and that part $y$ can be repeated any number of times;
or the word doesn't use any part of the expression under a star, and it can't be longer than the expression itself.

If a word is recognized by a context-free grammar, then:

It may be that the word is recognized by a parse tree where there is a subtree $\mathcal{T}_1$ which is recognized by the nonterminal $A$, and a subtree $\mathcal{T}_0$ of that subtree is recognized by the same nonterminal $A$. In that case, let $w$ be the part of the word that is recognized by $\mathcal{T}_0$ and $vwx$ be the part that is recognized by $\mathcal{T}_1$. You also get a valid parse tree if you replace $\mathcal{T}_1$ by $\mathcal{T}_0$ or vice versa. Furthermore, since $\mathcal{T}_1$ contains $\mathcal{T}_0$, after replacing $\mathcal{T}_0$ by $\mathcal{T}_1$, you can replace the copy of $\mathcal{T}_0$ inside $\mathcal{T}_1$ by $\mathcal{T}_1$, and so on. This means that you can replace $vwx$ by $w$, $v^2wx^2$, $v^3wx^3$, etc. and still get a word with a valid parse tree.
Otherwise, there is no subtree of the parse tree which reuses the same nonterminal, and in that case the length of the word is bounded because the depth of the parse tree is bounded by the number of nonterminals in the grammar.


I can suggest two approaches:

Brute-force search

First try to find if there is a way to place the element, without redistributing any previously placed elements.

If not, try to find a way to place it, by redistributing exactly one previously placed element.  This can be done by enumerating all possibility for which element you redistribute and where you redistribute it to, to see if that leads to a valid placement.

If not, try to find a way to place it, by redistributing exactly two previously placed elements.  This involves enumerating all combinations of two previously placed elements to redistribute.

In general, if $n$ elements have been previously placed and $r$ redistributions are needed, this will involve enumerating ${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose r}$ possibilities, which is $O(n^r)$.  This might scale OK if you expect $r$ to be very small but becomes slow once $r$ is large.

SAT solver

To get a more scalable solution, I suggest you use a SAT solver.

There's a natural way to encode your problem as SAT.  Introduce boolean variables $x_{i,j}$, meaning that element $i$ gets placed in set $j$ after redistribution.  Each constraint is a clause (disjunction of some $x_{i,j}$'s).  Also, we can represent the requirement that at most $r$ redistributions be used as the sum of $\neg x_{i,j}$ over all pairs $(i,j)$ that correspond to an element that is currently placed in set $j$ (before redistribution).

Thus, you can represent the problem of finding a solution using at most $r$ redistributions as an instance of SAT, and solve it using an off-the-shelf SAT solver.  Use binary search over $r$ to find the minimal number of redistributions needed.

I expect that this will scale much better.


Why did Google not use an NP problem for their quantum supremacy experiment?

there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems.

This statement is wrong. There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve.

What you are probably thinking of is NP-complete problems which is a subset of the NP problems for which we have very, very good evidence to think they are hard. However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

Factoring is also thought to be hard, but the evidence for this is only "very good" and not "very, very good" (in other words: factoring is likely not NP-complete). Factoring is one of very few natural problems which falls in between not being NP-complete and not being easy.

The list of problems that we know that are easy to verify, easy to solve on a quantum computer but hard classicly, is even shorter. In fact, I do not know of any problem other than factoring (and the very closely related discrete logarithm problem) with this property.

Moreover, any easy to verify problem would likely have the same issue as factoring: $53$ qubits is not that many, and $2^{53}$ is huge, but just within reach of classical computing. $2^{53}$ less than $10^{16}$, and most classical computers can execute on the order of $10^9$ operations per second. We could run through all possibilities in about $1/3$rd of a year on a single classical desktop computer.

Quantum computers have very few applications which they're known to be good at, and are essentially useless for most hard NP problems.


question about the construction of BSTs using a repeated sequence of rotations

Actually any BST can be transformed into balanced BST using $\mathcal{O}(n)$ rotations.

High level explanation: We convert given BST to right going chain(see fig-1 below). Then we convert that chain to balanced BST.

First convert given BST into right-going chain. Which can be accomplished using $n-1$ right rotations as follow.

Consider initial-right-chain $C$ of $root$ and all node that can be reachable from $root$ by following only right pointers.

Now, note that for any node $N$ in $C$ left child of node $N$ can be added into $C$ by right-rotating $N$. In doing that we don't loss any node from $C$.

So, by at most $n-1$ right rotation all node will be in $C$ because root will always be in $C$ from start.

Now, consider sequence of rotations $R: r_1, r_2, ..., r_m$ required to convert tree $T_1$ to right-going chain.

Now, consider sequence of rotations $S: s_1, s_2, ..., s_k$ required to convert balanced BST (containing same number of node as $T_1$) to right_going chain.

Then apply $r_1, r_2, ..., r_m, s_k', s_{k-1}', ..., s_1'$ to $T_1$. Here $s_i'$ denotes inverse operation of $s_i$.

Which will transform $T_1$ to balanced BST using at most $2n-2$ rotations.

   1
    \
     2
      \
       3

 figure - 1

Ref: CLRS 3e exercise 13.2.4


How can I prove the languages of incompressible words is undecidable?

Consider the word $w_n$ that is the output of $M'$ given input $n$.

Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w_n)\le c + O(\log n)$. If $n$ is large enough, we get
$$K(w_n)\lt n = |w_n|.$$

That is a contradiction since, as you have noted, $w_n$ should be incompressible.


Can the pre-order traversal of two different trees be the same even though they are different?

Tree Examples (image):

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /
 3

This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.

Tree B root׳s value is 1, having a left child with value 2 and a right child with value 3.

In both cases the Preorder traversal is 1->2->3.


How can I embed a Knowledge Graph in a vector space?

I would encourage you to start with this survey paper by Nickel et al.: https://arxiv.org/abs/1503.00759

Recent notable models:

ComplEx-N3: Lacroix et al. Canonical Tensor Decomposition for Knowledge Base Completion. 2018.
HypER: Balazevic et al. Hypernetwork Knowledge Graph Embeddings. 2018.
TuckER: Balazevic et al. TuckER: Tensor Factorization for Knowledge Graph Completion. 2019.
M3GM: Pinter and Eisenstein. Predicting Semantic Relations using Global Graph Properties. 2018.

Regarding your particular question, the Pxk matrix contains k-dimensional row vectors, one for every entity-pair in the knowledge base (P many) and the kxR matrix contains k-dimensional column vectors, one for every binary relation in the knowledge base. Note though that the paper you referring to here is already an extension over traditional knowledge graph embedding methods in that it assumes additional first-order logic background knowledge.


Equivalence from multi-tape to single-tape implies limited write space?

Sipser's book handles this case:

  If at any point $S$ moves one of the virtual heads to the right onto a $\#$, this action signifies that $M$ has moved the corresponding head onto the previously unread blank portion of that tape. So $S$ writes a blank symbol on this tape cell and shifts the tape contents, from this cell until the rightmost $\#$, one unit to the right. Then it continues the simulation as before.


Counting inversions in an array of 1 to N

You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum_{i=1}^{|A|}\sum_{j=i+1}^{|A|}[A_j<A_i]$$

Where $[A_j < A_i] = 1$ when $A_j < A_i$ and $0$ otherwise.


Turing machine where the next step is determined by the state and the symbols up to the read/write head

Suppose we are given a language $L$ of words of finite length. We will construct machine $M_L$ that runs as the following.

$M_L$ starts at state $q_0$. On input $x$ of finite length that is put to the right of its head, $M_L$ will move right all the way to the end of input, keeping the input and state intact. (This might mean nothing if the input is empty.) When $M_L$ read the first blank symbol, what is written on the tape up to the current point exclusive is exactly the input $x$. (If current point should be included, let $M_L$ go back a cell.) It halts, changing state to

$q_1$, an accepting state if $x\in L$,
or $q_2$, a rejecting state otherwise.

It is clear that $M_L$ decides $L$.

Well, it is reasonable to say that that $M_L$ does not compute $L$ at all. $M_L$ just knows effectively each and every word in $L$ without any computation. When $L$ is infinite or even undecidable, we are not able to build or truly simulate such a machine within any bounded time by any known physical means and intelligence. Hence, we would not believe those imaginary machines contradict the Church–Turing thesis.

Exercise.  Given a modified type of turning machine where

$$\delta: Q\times \Gamma^* \to Q\times \Gamma \times \{L,R\}$$

where the next step of the machine is determined by the current state and the content of last $\lceil\log_2n\rceil$ cells that has been read by it, where $n$ is the number of steps the machine has run. Can some unrecognized languages be recognized with these types of machine?


Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

Suppose towards a contradiction that $L$ is regular, and let $n \ge 1$ be its pumping length.
Consider the word $a^{2n}b^nc \in L$. By the pumping lemma there is some value of $k \in \{1, \dots, n\}$ such that, for every $i \ge 0$, the word $a^{2n+(i-1)k} b^nc$ also belongs to $L$.
Picking $i=0$ yields the sought contradiction since $a^{2n-k} b^n c \not\in L$. We can then conclude that $L$ is not regular.


How to determine the average of two strings?

Consider the $d(s,t)$ additions, deletions, and edits that transform $s$ in $t$.
Let $*$ be a new character.
Instead of inserting the prescribed character, insert $*$. Instead of deleting a character, change it to $*$. Instead of replacing a character with the prescribed character, replace it with $*$.

As an example, the edit distance between "mars" and "toast" is 4, and the corresponding edits are:

Change "m" in "t"
Add "o"
Leave "a" unchanged
Delete "r"
Leave "s" unchanged
Add "t"

Replace these steps with:

Change "m" in $*$
Add $*$
Leave "a" unchanged
Change "r" in $*$
Leave "s" unchanged
Add $*$

Applying these steps yields "$**$a$*$s$*$".


Proof of NP-completeness via extra information

No.  Your argument is not valid; it doesn't prove NP-completeness.  You have shown that an ILP solver can be used to solve your problem.  But an ILP solver can be used to solve easy problems, too, so it doesn't rule out the possibility that your problem might be easy (solvable in polynomial time).  The reduction needs to go the other way.  I suggest studying standard material on NP-completeness and reductions, e.g., What is the definition of P, NP, NP-complete and NP-hard? and What are common techniques for reducing problems to each other? and How do I construct reductions between problems to prove a problem is NP-complete?.
As it happens, I believe your problem can be solved in polynomial time; in other words, I believe it is not hard.  I believe the following algorithm solves your problem:

Enumerate over all possibilities $m_L,m_R$ for $\text{median}(K(L))$ and $\text{median}(K(R))$.  For each such possibility:

Find the partition $L,R$ that minimizes $E(L)+E(R)$, subject to the requirement that $\text{median}(L)=\mu_L$ and $\text{median}(R)=\mu_R$.

Output the best solution found at any of these stages.

I show below how to do the innermost step in polynomial time.  This gives a polynomial-time algorithm for your problem, as there are only $O(n^2)$ possibilities for $m_L,m_R$ (i.e., each $m_L,m_R$ must be an element of $\cup_i X_i$).
We'll use dynamic programming for this.  Let $\text{imb}(T,m)$ be defined by
$$\text{imb}(T,m) = (\sum_{t \in T} \text{sgn}(t-m), \sum_{t \in T} (t=m))$$
where the sum is "with repetition", and where
$$\text{sgn}(x) = \begin{cases}
1 &\text{if }x>0\\
0 &\text{if }x=0\\
-1 &\text{if }x<0
\end{cases}$$
$$(x=y) = \begin{cases}
1 &\text{if }x=y\\
0 &\text{otherwise}
\end{cases}$$
Define the imbalance of a partition $L,R$ with respect to $m_L,m_R$ to be the pair $(\vec{b_L},\vec{b_R})$ where $\vec{b_L}=\text{imb}(L,m_L)$ and $\vec{b_R}=\text{imb}(R,m_R)$.  Then we can reformulate the problem as follows:
Given $m_L,m_R$, find $L,R$ that minimizes $E(L)+E(R)$ subject to the requirement that the imbalance of $L,R$ with respect to $m_L,m_R$ is $(0,0)$ (or $+\infty$ if no such partition exists).
Now we can solve that using dynamic programming.  Define $A[k,\vec{b_L},\vec{b_R}]$ to be the smallest possible value of $E(L)+E(R)$ subject to the requirements that $L,R$ are a partition of $X_1,\dots,X_k$ with imbalance $(\vec{b_L},\vec{b_R})$ with respect to $m_L,m_R$ (or $+\infty$ if no such partition exists).  Then $A$ satisfies the recurrence relation
$$A[k,\vec{b_L},\vec{b_R}] = \min(A[k-1,\vec{b_L}-\text{imb}(X_k,m_L),\vec{b_R}] + \sum_{i \in X_k} |i - m_L|,A[k-1,\vec{b_L},\vec{b_R}-\text{imb}(X_k,m_R)] + \sum_{i \in X_k} |i - m_R|).$$
Using this recurrence, you can fill in the array $A$ in $O(Kn^4)$ time, where $n=|\cup_i X_i|$ is the number of elements (counting repetitions): you just initialize every entry to $+\infty$ except that $A[0,0,0]=0$, then fill it in, in order of increasing $k$.  Then, scan  all $A[K,(a,b),(c,d)]$ such that (i) $|a|<b$ and $b>0$, or $a=0$, and (ii) $|c|<d$ and $d>0$, or $c=0$; the smallest such value is the answer to the original problem.


How to prove that average complexity is N/2 for linear search in the unsorted array

First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the array we have already done $k$ comparisons.

If it is at $1$ then you find it in 1 comparison, if it is at $2$, you find it in 2 comparisons, $\dots$, if it is at $n$ then you do $n$ comparison in order to find it. In order to average it you sum the total number of comparisons $1+2+\dots + n = \frac{(n+1)n}{2}$ and divide it by $n$ (size of the array) resulting in $\frac{n+1}{2}$.

More formal proof:
Assume that the input has uniform probability and the the size of the array is $n$. Let $X$ be a random variable denoting the number of comparisons. Then $p(X=x)$ will denote the probability that we do $x$ comparisons. Since the distribution is uniform, $p(X=x) =\frac{1}{n}$. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value
$$E[X] = \sum_{x=1}^{n}{xp(x)} = \sum_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$$


Best combination of values pulled from a matrix

It looks like the assignment problem, and it could be solved in $\mathcal O(n^3)$ using the Hungarian algorithm. In your case the $A$ is the cost matrix and the sum you are looking for is cost in the terms of algorithm.


Hard connected instances for Weisfeiler-Lehman test of isomorphism

Yes, there are non-isomorphic connected graphs that cannot be distinguished by Weisfeiler–Lehman.  The following construction is due to Cai, Fürer and Immerman (An Optimal Lower Bound on the Number of Variables for Graph Identification, Combinatorica 12(4):389–410, 1992; PDF).

Take any connected, $3$-regular graph $G=(V,E)$. We will produce non-isomorphic graphs $G_\parallel$ and $G_\times$ from $G$, that are indistinguishable by Weisfeiler–Lehman.  These will be made by producing a gadget for each vertex of $G$ and, for each edge $xy\in E$, connecting the gadgets for $x$ and $y$ by a pair of parallel edges.

The vertices of $G_\parallel$ are is defined as follows.

For each $xy\in E$, we create four (distinct) vertices, $a_{x,y}$, $a_{y,x}$, $b_{x,y}$ and $b_{y,x}$.
For each $x\in V$, we create a vertex $c_{x,S}$ for each odd-cardinality subset of $\Gamma(x)$ (the neighbours of $x$ in $G$).  So, if $x$'s neighbours are $u$, $v$ and $w$, we create vertices $c_{x,\{u\}}$, $c_{x,\{v\}}$, $c_{x,\{w\}}$ and $c_{x,\{u,v,w\}}$.

The edges of $G_\parallel$ are defined as follows.  For each edge $xy\in E$, we add:

the two edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$;
the edges $a_{x,y}c_{x,S}$ for each $S$ such that $y\in S$;
the edges $b_{x,y}c_{x,S}$ for each $S$ such that $y\notin S$.

Note that $G$ is undirected so if $xy\in E$, then $yx\in E$ also, and we follow the above rules twice for each edge of $G$.

Now, let $xy$ be any edge in $G$ and let $G_{xy}$ be the graph made from $G_\parallel$ by deleting the edges $a_{x,y}a_{y,x}$ and $b_{x,y}b_{y,x}$ and replacing them with the "cross" edges $a_{x,y}b_{y,x}$ and $b_{x,y}a_{y,x}$.  The following lemma is the key point of the construction.

Lemma 1. For any edges $uv,xy\in E$, the graphs $G_{uv}$ and $G_{xy}$ are isomorphic.

Proof sketch. You can move the cross edge around the graph in the following sense.  For any pair of edges $ij,jk\in E$, there's an isomorphism of $G_{ij}$ that exchanges $a_{j,i}$ and $b_{j,i}$ and exchanges $a_{j,k}$ and $b_{j,k}$. This isomorphism is a permutation of the vertices $c_{j,S}$, and it fixes every other vertex in $G_{ij}$.  If you draw the fragment of the graph corresponding to vertex $j$ and its incident edges, the isomorphism should be pretty obvious.

This means that $G_{ij}\simeq G_{jk}$, because the isomorphism "uncrosses" the edge $ij$ and "crosses" the edge $jk$.  Since $G$ is connected, it contains a path whose first edge is $uv$ and whose last edge is $xy$, and we can use the isomorphisms corresponding to each adjacent pair of edges in this path to move the cross in $G_{uv}$ to $xy$. $\Box$

By Lemma 1, we're entitled to use the name $G_\times$ for an arbitrary graph $G_{xy}$.  We now have the graphs $G_\parallel$ and $G_\times$; it remains to show that they're non-isomorphic and that they're indistinguishable to Weisfeiler–Lehman.

Lemma 2. For any connected, 3-regular graph $G$, we have $G_\parallel \not\simeq G_\times$.

Proof sketch. It turns out that the only isomorphisms of $G_\parallel$ and $G_\times$ are isomorphisms induced by isomorphisms of $G$, and isomorphisms of the form used in the proof of Lemma 1.  But no such isomorphism can transform $G_\times$ into $G_\parallel$ because $G_\times$ has a cross edge and $G_\parallel$ does not. $\Box$

Now, indistinguishability.  Weisfeiler–Lehman is definable in so-called "fixed-point logic with counting."  This is first-order logic plus:

counting quantifiers: for each natural number $n$, you can write $\exists^{\geq n}x\,\varphi(x)$, meaning "There exist at least $n$ values of $x$ that satisfy $\varphi$." This can already be expressed in ordinary first-order logic, just by saying that there exist distinct $x_1, \dots, x_n$ that all satisfy $\varphi$, but the (rather subtle) point here is that the counting quantifier only uses just one variable, whereas the "pure" first-order expression uses $n$ distinct variables.
inductive definitions. These let you build up a relation $R$ as follows.  You start with $R=\emptyset$. Then, you add to $R$ all the tuples that satisfy a formula $\varphi$, and keep doing that until you run out of tuples to add.  $\varphi$ itself can depend on $R$, so you can build up some interesting things.

In particular, you can build up an equivalence relation corresponding to the colour-classes of Weisfeiler–Lehman. The counting quantifiers let you talk about the numbe of neighbours of each colour, and the inductive definitions let you recursively refine the colouring based on the number of neighbours of each colour in the previous step.

A separator of a graph $G=(V,E)$ is a set $S\subseteq V$ such that no component of $G-S$ has more than $|V|/2$ vertices. In the following, I say "less than about $2k$" because I'm silently translating from fixed-point logic with counting to so-called "infinitary logic with counting", which roughly doubles the number of variables. I don't remember the exact details, and it's not important enough to hunt them down.

Theorem 3. Let $\varphi$ be a formula of fixed-point logic with counting, using $k$ distinct variables.  If $G$ is a graph with no separator of size less than about $2k$, then $\varphi$ cannot distinguish $G_\parallel$ from $G_\times$.

Proof sketch. Very roughly speaking, while you're evaluating the formula $\varphi$ on $G_\parallel$ or $G_\times$, you might need to consider $k$ vertices as being the value of some variables at the current iteration of an inductive construction and $k$ more variables as being the value of the variables at the previous iteration. The fact that $G$ has no small separators means that, even if we fix those vertices, we can still move the cross around in a large component of the rest of the graph, without the formula "knowing" that we've done that, so the formula can never "see" the cross, so it can never tell the difference between the graph with the cross and the graph without it. $\Box$

For any fixed $d$, $d$-dimensional Weisfeiler–Lehman can be expressed as a formula of fixed-point logic with counting, using some number $k$ of variables ($k\approx 2d$ is enough, as I recall). Since that formula can't tell the difference between the non-isomorphic graphs $G_\parallel$ and $G_\times$ as long as $G$ has no small separators, nor can Weisfeiler–Lehman.

Guess who got a PhD doing this kind of stuff...


Memory access on byte/word addressable memory

The question is probably about address bits, not data bits.

A 4G x 32bits memory size is 16Gbytes.

With a 8bits data bus, you need 34 address bits (typically A[33:0])
With a 32bits data bus, you need 32 address bits (typically A[33:2]. A[1:0] is for selecting individual bytes inside the 32bits word.)


Image segmentation of a high resolution 2D binary image into clusters, threads and points

I would suggest decomposing the black pixels into connected components using standard algorithms.  (For instance, OpenCV has an implementation of this, I believe.)  Then, classify each component based on your rules.

(I'm not seeing what boundary tracing offers over connected component labelling, but you could try it too if you wanted.)

I recommend you try it and see how well it works.  This should be pretty straightforward to try.  I'd caution against over-thinking things and try to figure out the perfect solution before trying anything.  In this domain, often multiple rounds of "try something, identify its shortcomings, and improve" are necessary, because it can be hard to predict how something might fail.

If this works, it will be very efficient (it runs in linear time) and quite simple, so you don't need to worry about it being a "brute force" or "naive" method.  I wouldn't worry about micro-optimizations at this stage.  Instead, implement it and see how well its results seem to be.  Only after you are happy with the quality of the results should you even begin to think about potentially optimizing it -- but I would expect that it might be so fast that there is no point in spending any energy trying to optimize it.

You might discover that the connected components are too large and include both clusters and threads.  If so, that's telling you that your rules aren't quite right yet, and you'll need to investigate more sophisticated solutions.  One possible approach might be to apply a morphological operation, such as a thinning operation or erosion, to remove the threads, compute connected components on the result, and use that to identify clusters.  You might also be able to compute a skeletonization of the shapes, and use that to identify threads (e.g., compute the "thickness" of the shape at each point: for each point $p$ on the skeleton, compute the distance to the boundary in the direction perpendicular to the direction of the skeleton at $p$).  Once you've identified each shape separately, you might be able to compute its bounding box and the fraction of pixels within the bounding box that are black, and use a threshold on that fraction to distinguish clusters from threads -- if you can separate the cluster from the thread.  You might need to experiment a bit to see what works well for your images.


How does cpu fetch active program data (using virtual address) from storage when there is a page fault?

The CPU knows nothing about swapping. This is performed by the operating system.

When a memory access takes place, the MMU consults page tables to find the physical address that is associated to a virtual address. Each page tables contains a number of descriptors that explain to the MMU what the physical address is. A page fault occurs when the descriptor contains an invalid value (i.e. one that does not denote a physical address).

When a page fault occurs, the CPU transfers control to a predefined piece of code in kernel mode and sets a register to the problematic address. The kernel code looks up the address in its own tables to figure out whether it is swapped out or invalid. On many architectures, there are many unused bits in an invalid descriptor, which allows the kernel to store its own data in the page tables. Based on these values, if the kernel determines that the page is swapped out, it will allocate a physical memory page, load the content from swap, modify the content of the faulting descriptor to point to this physical page, and transfer control back to the program so that it executes the memory dereference again. If the kernel determines that the page is invalid, it typically terminates the application, or transfers control to its fault handler.

The layout of descriptors and of any additional kernel data structure is highly dependent on the processor architecture and the kernel. Here's a fictional, simplified example of how it might look like (real machines and operating systems tend to be a lot more complex).

The machine is capable of addressing 4GB of virtual memory and 8TB of physical memory. Each page is 4kB. A page table consists of 1048576 descriptors, each of which occupies 4 bytes. (In the real world, MMUs use 2 or 3, sometimes 4 levels of descriptors, rather than a single gigantic table.)
In each descriptor, the lowest bit indicates whether the descriptor is valid. If the lowest bit is 0, the descriptor is valid, and the corresponding physical page is $2^11 \times d$ where $d$ is the descriptor value. If the lowest bit is 1, the descriptor is invalid, and the MMU ignores the other bits. (In the real world, there are more bits in descriptors for permissions, cache maintenance, etc.)
The operating system uses the 31 higher bits of invalid descriptors to locate a swapped-out page. The OS supports up to 8TB - 4kB of swap; the special value all-bits-one indicates an invalid page. Separate data structures map ranges of swap addresses to ranges of disk locations.


Decision problems: Does a "constant" characteristic function describe a language in P?

Yes, of course they're in P: you can decide them in constant time, which is certainly bounded by a polynomial.

Anybody who tells you that P$\,=\,$NP implies that every problem in P is NP-complete has forgotten about these two trivial problems. Neither of them can be NP-complete, because NP-completeness is defined in terms of many-one reductions, but there cannot be a many-one reduction from a non-trivial probelm to either of the trivial problems. A many-one reduction from $A$ to $B$ must map "yes" instances of $A$ to "yes" instances of $B$, and "no" instances to "no" instances.  But one of the trivial problems has no "yes" instances and the other has no "no" instances, so a problem that has both "yes" instances and "no" instances cannot be reduced to either.


Computer Networks: Does integrity depend on confidentiality?

Confidentiality means that only the sender and receiver know the message. We ensure confidentiality by encrypting the message.

Integrity roughly means that the message being sent cannot be modified in transit. In more detail, it means that there is a way for the receiver to check that the message has not been tampered with. We ensure integrity by adding a hash or checksum to the message.

The two properties are completely independent:

Confidentiality without integrity: Suppose I am sending you a cryptographic key, encrypted using a key we share. An attacker replaces the message with garbage having the same format. You will not notice any difference. The attacker has no way to read the original message, but they can modify it without you knowing it.
Integrity without confidentiality: I can send you a signed message by encrypting a hash of the message using my private key. Anybody can verify that the hash matches the message using my public key, but I'm the only person who can sign it. There is no way to modify the message without invalidating the signature, but the message itself is free for all to see.


Hueristic Algorithm to find the maximum clique

Consider a graph which is the disjoint union of $K_i$ and $K_1$, the isolated vertex.

Let the order of selection of vertices be such that the isolated vertex is last.

Then your heuristic outputs solution 1 for any $i \in \mathbb{N}$.


Reversing a List from a Context-Free Grammar

Your question is not very precise. I assume you want the list of struct_declaration to start from the other end in the parse tree.

Your grammar gives you a struct_declaration_list that looks like

         SDL
        /   \
      SDL    SD
     /   \
   SDL   SD
  /   \
SDL   SD
 |
SD

If you reverse the order in the second part of the rule, you reverse "the pointers" in the list, which may be understood as reversing the order.

struct_declaration_list
    : struct_declaration
    | struct_declaration struct_declaration_list
    ;

Then the parse tree  looks like:

   SDL
  /   \
 SD   SDL
     /   \
    SD   SDL
        /   \
       SD   SDL
             |
            SD

The left-to-right order of SD is in both cases that of their occurrence in the input string (the program).