Set Similarity - Calculate Jaccard index without quadratic complexity

An option would be to use the Signature Scheme of [1], size-based filtering: a scheme which uses size information to reduce the number of set pairs that need to be considered.

They also experiment with a weighted form; where weights are IDF-based.

[1] Arasu, Arvind, Venkatesh Ganti, and Raghav Kaushik. “Efficient Exact Set-similarity Joins.” In Proceedings of the 32nd International Conference on Very Large Data Bases, 918–929. VLDB  ’06. VLDB Endowment, 2006


Selecting a node of a singly-linked list such that the probability of each node being selected is equal

You are absolutely right.

Part of the problem with your friend's solution is that, when he instructs you to make a random choice (in line 3), he did not specify what probability you should use.  It's his job to completely specify the algorithm, and not omit details like that.  If we choose uniformly at random from the two options, then the algorithm does not work, for the reasons you describe.

It is possible to repair the algorithm by choosing appropriate probabilities at each iteration, but doing this right requires some care.

The standard solution to this is reservoir sampling.  (See also Reservoir Sampling - Sampling from a stream of elements for another description of the same algorithm.)
You can view reservoir sampling as an instance of your friend's algorithm, but with the probabilities for each random choice specified fully and worked out carefully so that the algorithm does meet the requirements.


Implementing Deterministic Turing Machine

The reason for that is, if you use Depth-First Search (DFS), there exists the probability of the search going through a path that is infinite in length (loop) and you will never get an answer. If you use BFS it's more likely that you will find a path on to an accept state, if a path to one exists.

For example imagine that you have a tree with 100 children on left from the root and the right child of the root you only have 3. If you use DFS you will traverse the 100-deep left branch and later go right, and now instead having 100 branches just imagine you have infinite number of branches.


Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages

The question actually is easy, provided you take the right definition. RE languages can be defined using a Turing Machine in two equvalent ways. As an acceptor which accepts words in the language and halts (and may halt or loop otherwise), or as an enumerator, which will write the elements of the language (probably in some weird order) onto the output tape (assuming there is a separate working tape).

Using the latter concept several closure operations of the type you mention are trivialities. If I want to shrink, I start my enumerator, and when it outputs a word of the language apply shrink.


When are adjacency lists or matrices the better choice?

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph.
In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes.

Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between nodes $i$ and $j$, otherwise $M[i][j] = 0$.
But if we use adjacency list then we have an array of nodes and each node points to its adjacency list containing ONLY its neighboring nodes.

Now if a graph is sparse and we use matrix representation then most of the matrix cells remain unused which leads to the waste of memory. Thus we usually don't use matrix representation for sparse graphs. We prefer adjacency list.

But if the graph is dense then the number of edges is close to (the complete) $n(n-1)/2$, or to $n^2$ if the graph is directed with self-loops. Then there is no advantage of using adjacency list over matrix.

In terms of space complexity
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + m)$
where $n$ is the number nodes, $m$ is the number of edges.

When the graph is undirected tree then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n)$ is $O(n)$ (better than $n^2$)

When the graph is directed, complete, with self-loops then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n^2)$ is $O(n^2)$ (no difference)

And finally, when you implement using matrix, checking if there is an edge between two nodes takes $O(1)$ times, while with an adjacency list, it may take linear time in $n$.


In reference to the Chomsky hierarchy (and automatas), Which is the linear feedback shift register Languages/automaton?

It has a finite memory, so it's just a DFA (or some of the output-producing variants). If you allow a growing/shrinking feedback register, it is probably equivalent to a Turing machine.


Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

According to TopCoder the correct running time is $O( A^2 \cdot VUW)$.


What does atomicity mean in distributed systems?

There is one primary meaning of the word "atomicity", and one additional property that some people use on occasion.

The primary meaning is that a complex operation (usually called a "transaction"), which requires multiple parties to take action, either happens or doesn't happen. It can't happen only in part.

One classic example (because this is one domain where atomicity is more important than most other considerations) is transferring money from one bank account to another bank account at a different bank. Think of the banks as communicating agents (possibly involving other agents, like an arbitrator or broker). Conceptually, one bank needs to subtract some amount from a number held somewhere, and the other bank needs to add the same amount. The important part is that either both pieces of arithmetic happen or neither happen. What is not allowed is for money to be created or destroyed.

The additional property that some people add is that all agents, or at least the initiating agent, must be able to know in a timely manner whether the transaction happened or didn't happen. Think of a file system sync operation, for example. If that operation returns and signals that it was successful, the client can assume that any data and/or metadata written to the file system before the sync operation has been committed to secondary storage.


I was only familiar with the Hungarian algorithm which only works for bipartite graphs but I've found something that claims to work for general graphs as well.
The basic algorithm is the blossom algorithm, but since you need to find the maximum weight matching you will need Kolmogrov's Blossom V which is based on it.


Smallest set of balls under hamming distance that covers all $n$-bit strings

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.


To be in NPC a problem, C, has to be in NP, and every problem in NP has to be polynomial-time reducible to C.

If P=NP every problem in NP can be solved in polynomial time.

This means that if P=NP, we can for most problems in P define the following reduction to C; Solve the problem in polynomial time, if the instance you are looking at returns true then reduce it to an input to C for which we know that C returns true - Otherwise reduce it to an input for C that we know returns false.

So for an example; if we take C to the problem of determining if a number is even. And we want to reduce the hamiltonian path problem.  We solve the hamiltonian path problem; which we can do in polynomial time since we assume P=NP.  If we find that a hamiltonian path exists we select 2 as input to C.  If we find that no hamiltonian path exists then we select 1.

This of course fails if C always returns true, or always returns false, so those two problems, as noted by Tom, while part of P, can not be part of NPC.  However, all other problems in P will be in NPC if P=NP.


Is it generally possible to convert CNF to Horn clauses?

In "Renaming a Set of Clauses as a Horn Set" Harry Lewis showed that a CNF formula could be converted to Horn form iff a particular 2-CNF formula constructed from the original formula is satisfiable.  The satisfying assignment to the 2-CNF formula tells you which literals to flip.  The 2-CNF formula can be constructed in time quadratic to the number of literals appearing in the original formula.  Faster algorithms have been published since which reduce the problem of Horn-renaming a CNF formula to linear-time if it is possible to do at all.


While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

The bit length of $n$ is $\log(n)$, if we forget about the most significant digits, which is always $1$ except for $n=0$. As a function of $t=\log(n)$ you have $n^{1/2}=2^{t/2}$. It is in terms of the bit length of $n$ that AKS runs in polynomial time, while the naive test doesn't.


A TM s just a program. It does whatever you program it to do. If, for instance, you program it to perform the following:

while (true)
{
   do_nothing
}

, then it will never halt!

The language $L$ goes over all possible machines $M$, and therefore it must encounter some machines that don't halt, for instance, the one stated above.

There is a deep difference between the reason the above machine doesn't halt (it is just programmed to do so), and the reason that any machine for $L$ will not halt–no machine for $L$ exists since that language is undecidable.

regarding your question about finding a more "natural" language that is undecidable, see Is there a “natural” undecidable language?. You may get some more intuition about undecidable languages here.


How to generate branch tables from SSA form?

The book "A Retargetable C Compiler: Design and Implementation" by Christopher Fraser and David Hanson gives some detail on how they lower switch statements to a combination of conditional branches and jump tables. They cite prior work that their technique builds on, so it would be a good start for a literature survey.

There should be nothing particular to SSA that makes generating jump tables harder or easier. An SSA IR like LLVM can include an explicit instruction for an N-way branch, so that generation of jump tables is really about how to lower such an instruction.

(Update: you've edited the question in a way that makes it clear this isn't really about generating jump tables, but rather about re-discovering switch-style control flow from cascading if statements in an IR. This is again probably not specific to SSA. You might look at the "Relooper" algorithm as implemented for Emscripten which deals with more general control-flow restructuring. I'm not aware of a reference specific to recovering N-way branches, but it seems like simple ad hoc approaches should work well.)


Deterministic Multi-tape Turing Machine construction

You could copy the input to 3 tapes, then move the heads on tapes 2 and 3 until they point to the same substring and on tape 3, the end of substring matches the end of string.

The exact steps could be..

   1. copy input
 2. erase first symbol on tape two and first two symbols on tape three
 3. go forward on all tapes until...
 4. if one of the symbols is different than on other tapes, go back to the start of each tape and return to step 2
 5. if tape three reaches end of input, you are done


$P/poly$ is NOT a subset of $RE$. Specifically, the unary non-halting problem (i.e. given a Turing Machine encoded in unary, does it run forever?) is in $P/poly$ but not $RE$. In fact, every undecidable unary language is in $P/poly$.


Can there still be infinite recursion if I remove all left recursion?

Take a look at the following rule in the original grammar.
$\quad S \to aSb \mid bAS$
If you start generation from $S$, you cannot get rid of $S$.
$\quad A \to AaA \mid bAA \mid AAa \mid bAb $
If you continue applying production rules from a sentential form that contains $A$, you cannot get rid of $A$, either.

These rules are called unproductive rules. Unproductive rules and unreachable rules are called useless rules. You may take a look at this question.

If there are useless rules in the original grammar, there will be useless rules after the transformation by pure left-recursion removal procedure. That is why you see "there is still infinite recursion because $A$ calls itself repeatedly". There is nothing wrong with your transformation to that non-left-recursive grammar.

Those useless production rules can be remove by some algorithms.
We can see that the original grammar in the question will become empty after such cleaning. Indeed, the original grammar generates the empty language, the language that contains no words.


Why do we consider the order of growth when analyzing algorithms?

I think the key point in time complexity analysis is it can give us a metric to measure the time independent of any hardware or software dependency directly.

Hence, we can talk about the time complexity based on inputs and outputs of the problem without considering more sophisticated or even complex cases by mentioning that we are talking about the hardware or software specifications.

However, hardware usage is mentioned in some real applications too, somewhere the time complexity can't distinguish the solutions in its abstract asymptotic definition. These kind of analysis are common in AI algorithms which have the same time complexity but have some real differences in real applications and hardware usage. For example, in real applications "Quick Sort" is better than "Merge Sort" because we have a large constant factor in "Merge Sort" time complexity, however, on the paper, in time complexity, "Merge Sort" is better than "Quick Sort" in worst cases.

In sum, time complexity base on the growth can be proper to compare algorithms independent of any hardware or software specifications, although hardware usage in real applications makes sense more!


How is the Subset Sum Problem NP-Complete?

The dynamic programming approaches only solve the problem in pseudopolynomial time.

Recall that the definition of (nondeterministic) polynomial time is that the problem must be solvable by a (nondeterministic) Turing machine whose running time is bounded by some polynomial in the size of the input.  The size of the input is the number of bits required to write it down.

Suppose we want to solve a subset sum instance where the set has size $k$ (i.e., contains $k$ integers), and suppose this takes $n$ bits to write down. The dynamic programming approach builds up a table with $k$ rows and one column for each possible partial sum. How big is this table? Well, surely $k\leq n$, since we can't write down more than $n$ numbers in only $n$ bits.  However, a partial sum is the sum of some number of integers, each of which takes about $n/k$ bits to write down. So that sum is also going to take roughly $n/k$ bits to write down. That means that there are roughly $2^{n/k}$ columns in our table, so our table is exponentially large and we can't populate it in polynomial time.

The algorithm runs in pseudopolynomial time, which means that it runs in time bounded by some polynomial in the numbers represented in the instance, rather than in the number of bits required to write them down.

(In fact, this dynamic programming approach uses even more memory than doing dynamic programming on subsets.  Suppose, for example, that your set is $\{1,100\}$. There are only three nonempty subsets but you're likely to decide that a partial sum could be anywhere between $0$ and $101$, giving a table with two rows and $101$ columns, instead of two rows and three columns.


Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

There is no known method to calculate individual decimal digits of pi quickly. And fast methods for calculating the first n digits of pi in base b are considerably faster than using a method to calculate the k-th digit n times.


Zero-knowledge proof of intractibility of NP-complete problems

"A zero-knowledge proof of the intractability of the Hamiltonian cycle problem" doesn't make sense.  You should refer to the formal definition of a zero-knowledge proof system.  When we talk about a zero-knowledge proof system, it is a zero-knowledge proof system for a family of statements.  For the problem to be interesting, the family needs to be infinite.

"The intractability of the Hamiltonian cycle problem" is not a family of statements; it is a single statement.  It doesn't make sense to talk about a zero-knowledge proof in that sense -- you end up with something trivial and degenerate and uninteresting.

In particular, that single statement ("the Hamiltonian cycle problem is intractable") is either true, or it is false.  If it's true, there is a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "yes, the statement is true".  If it's false, there is also a trivial zero-knowledge proof system for it: the prover sends nothing, and the verifier outputs "no, the statement is false".  Either way, there exists a zero-knowledge proof system that satisfies the definition.  But this is not very interesting or meaningful.

From a formal mathematical perspective, in the phrase "zero-knowledge proof", you shouldn't think about "zero-knowledge" as a modifier to the word "proof".  Rather, you should think about the phrase "zero-knowledge proof system" as an indivisible term with a specific mathematical definition.  A "zero-knowledge proof system" is not even in the same category as a "proof"; they are like apples and oranges.


Does closure under union and concatenation imply closure under Kleene star?

You haven't stated whether you're interested in finite or infinite union, though as you mention, it doesn't really matter due to problem with the empty string. However, instead of giving the answer, let me explain how to answer such questions.

Showing that a language class is closed under operation $O$ given that it is closed under operations $O_1,\ldots,O_m$. You show how to simulate $O$ using $O_1,\ldots,O_m$. For example, suppose that a language class is closed under union and complement. Then it is also closed under intersection, since $A \cap B = \overline{\overline{A} \cup \overline{B}}$.

Showing that if a language class is closed under $O_1,\ldots,O_m$ then it is not necessarily closed under $O$. You given a language class which is closed under $O_1,\ldots,O_m$ but not under $O$. For example, let us show that a language class which is closed under finite union isn't necessarily closed under infinite union. Consider the language class consisting of all finite languages. This class is closed under finite union but not under infinite union.

Given this information, you should be able to answer your question on your own.


This question is refreshing. Answers are given in the headers below.

There exists a Turing machine (TM) without useless states that accepts the same language as an arbitrary given TM.
Let TM $M=⟨Q,\Gamma, b,\Sigma, \delta, q_0, F⟩$ where
$$\delta: (Q\setminus F)\times \Gamma\not\to Q\times\Gamma\times\{L,R\}$$
is the transition function, where $L$ is left shift, $R$ is the right shift. For each state $q\in Q$, $q$ is either useful (reachable) or useless (non-reachable).
Let $Q'$ be the set of all useful states. Let $\delta'$ be the restriction of $\delta$ on $(Q'\setminus F)\times \Gamma$. Then we can check $M'=⟨Q',\Gamma, b,\Sigma, \delta, q_0, F\cap Q'⟩$ is a well-defined TM without useless states that accepts the same language as $M$.
Intuitively, $M'$ is simply $M$ with all useless states removed.

Exercise 3.19 indicates none of the following two languages is decidable.
$$\text{USELESS_STATES}=\{⟨M, g⟩\mid M \text{ is a TM with a useless state } g \}$$
$$\{⟨M, M'⟩\mid M \text{ is a TM and }M'\text{ is defined based on M as above} \}$$

No algorithm can produce a TM without useless states that accepts the same language as an arbitrary given TM.
For the sake of contradiction, suppose there is a such an algorithm $A$.
Let $M$ be a given TM. Applying $A$, we can construct another TM $M'$ without useless states that accepts the same language as $M$.
What is $F'$, the set of final states (a.k.a. accepting states) of $M'$?

If $F'$ is empty, then $M'$ never accepts any word. That is, $L(M')$ is empty.
If $F'$ is not empty, then $M'$ does accept some word since the states in $F'$ are reachable. That is, $L(M')$ is not empty.

Just by checking whether $F$ is empty or not, we will know whether $L(M')$ is empty or not. Since $L(M')$ is the same as $L(M)$, we will also know whether $L(M)$ is empty or not. Hence, we can decide whether $L(M)$ is empty or not.
However, it is well-known that it is undecidable to determine whether an arbitrary given TM accepts no words or not. This is a contradiction.
What we have used in the proof above is the following obvious property of TMs without useless states. Such a TM accepts at least one word if and only if it has at least one final state.
Intuitively, there is no algorithm to determine whether a final state in a TM is useless or not.

Here are two easy related exercise.
Exercise 1. Show the following language is not decidable.
$$\{⟨M⟩\mid M \text{ is a TM that accepts no words}\}$$

Exercise 2. Show the following language is not decidable.
$$\{⟨M, M'⟩\mid M \text{ is a TM and }\\ M' \text{ is a TM without useless states such that } L(M)=L(M')\}$$


Proof of lemma for flow in residual graph

Observe that if $v$ is not a vertex of $p$, then $f_p(u,v)=0$.
When $v$ is in $p$ and not a source nor a sink, then there are only two vertices $v_1$ and $v_2$ such that the edges $(v_1,v),(v,v_2)$ are in $p$. Therefore, in the excess flow at $v$ $$\sum_u f_p(u,v)$$ only has two non-zero terms $f_p(v_1,v)=c_f(p)$ and $f_p(v_2,v)=-f_p(v,v_2)=-c_f(p)$.
So, the excess flow is zero.
To see that $c_f(p)>0$ just recall that it is defined as the minimum of the residual capacities of the edges of $p$. There are finitely many edges in $p$ and by definition of augmenting path the residual capacities of its edges are positive. So, you are taking the minimum of finitely many positive numbers. That results in a positive number.


How these two Turing machine problems are different in terms of their decidability?

The thing you missed is that Turing Machines are strictly more expressive than Context-Free Grammars. CFGs are as expressive as push-down automata (PDA, i.e. automata with one stack).

E.g. the language $L = \{a^nb^nc^n | n > 0\}$ cannot be expressed by CFG (or decided by a PDA), but can be decided by a Turing Machine.

So, for CFG, the emptiness problem is decidable, but somewhere on the way to Turing completeness, this property is lost.


For every $n$ there is a language over $\{a,b\}$ which is accepted by an NFA having $n$ states, but its minimal DFA has $2^n$ states.

Unfortunately I don't remember the reference, but here is how to get almost this result. Let $L_n$ be the language of all words over $\{a_1,\ldots,a_n\}$ that don't contain all letters. Then $L_n$ can be accepted by an NFA with multiple initial states having $n$ states (or with a normal NFA with $n+1$ states), but its minimal DFA has $2^n$ states. Take it as an exercise to prove these statements (for the latter one, use Myhill-Nerode theory).


Are all MST minimum spanning trees reachable by Kruskal and Prim?

As indicated by Raphael's comment and j_random_hacker's comment, the answer is positive. In fact, any MST is reachable by any MST algorithm with some minor exceptions.

For a graph $G$, two weight functions on all edges (to real numbers) are defined as (weakly) comparison-compatible (to each other) if we can extend the strict weak ordering on the edges induced by either weight function to the same strict total order. That is, we can devise consistent tie-breaking rules with each weight function so that the result of comparison of any two edges by one weight function and its tie-breaking rules is the same as the result by the other weight function and its tie-breaking rules.

  Lemma 1: Let $w_1$ and $w_2$ be two weight functions. The following five statements are equivalent to each other.

  $w_1$ and $w_2$ are comparison-compatible.
  In any set of edges, there is a common lightest edge by $w_1$ and by $w_2$.
  In any set of edges, there is a common heaviest edge by $w_1$ and by $w_2$.
  There exists a weight function $w_3$ that assign distinct weights to distinct edges such that $w_3$ is comparison-compatible to $w_1$ and to $w_2$.
  for any edge $e_1$ and $e_2$ such that $e_1$ is lighter than $e_2$ by one weight function, $e_1$ is as light as or lighter than $e_2$ by the other weight function.

Proof of lemma 1 is left as an easy exercise.

  Lemma 2: Let two weight functions $w_1$ and $w_2$ be such that if $e_1\lt_{w_1}e_2$, then $e_1\lt_{w_2}e_2$. Then they are comparison-comptible.

(Hint to) Proof: One approach is to verify the condition 5 of lemma 1. Another approach is to verify the condition 2 of lemma 1 by showing that in any set of edges, a lightest edge by $w_2$ is also a lightest edge by $w_1$,

A comparison-based algorithm on a graph $G$ is defined as comparison-compatible if for any two (weakly) comparison-compatible weight functions on all edges, we can run the algorithm with one weight function in a way that can be repeated without any change with the other weight function. In particular, those two runs of the algorithm will have the same output.

Please note that most if not all MST algorithms can be stated in two flavours. The first flavour assumes that distinct edges of $G$ have
distinct weights, which is used when the main concern is to find one MST (which is in fact also the unique MST). The second flavour allows distinct edges of $G$ to have same weights. Of course in this answer, where the main concern is to find all MSTs, we will only care MST algorithms in the second flavour.

A comparison-compatible MST algorithm can find all MSTs.

To prove the above proposition, we just need to adapt slightly the section, "Kruskal can find every MST" in the computation of the number of MSTs. For any MST $m$ of $G$ with weight function $w_1$, choose a positive weight that is lighter than the absolute difference between any pair of unequal edge weights. If we subtract that weight from the weight of each edge in $m$ without changing weights of other edges, we obtain a new weight function, say, $w_2$. If edge $e_1$ is lighter than $e_2$ by $w_1$, $e_1$ must be lighter than $e_2$ by $w_2$ as well. By lemma 2, $w_1$ and $w_2$ are comparison-compatible. Note that $m$ is the unique MST with $w_2$. (One way to show this uniqueness is to prove that whenever the weight of one MST edge is reduced, any MST with the new weight function must contain that edge.) So any run of the algorithm on $w_2$ will find $m$. Because the algorithm is comparison-compatible, we can run the algorithm the same way with $w_1$ or with $w_2$. Since that run will find the unique MST, $m$ with $w_2$, it will find $m$ as well with $w_1$.

Every MST algorithm is comparison-compatible

The above proposition sounds overbroad. Well, by every MST algorithm, I mean any general comparison-based MST algorithm that I have seen, excluding those apparently pathological ones such as wrong or having unnecessary steps. Since a comparison-compatible MST algorithm can find all MSTs, every MST algorithm can find all MSTs. In particular, each of  the four classic MST algorithms, namely Borůvka's, Prim's, Kruskal's and reverse-delete algorithms can find all MSTs.

Here are three more comparison-compatible MST algorithms.

the delete-heavy-edge algorithm. Start with all edges. Repeatedly find a cycle and remove one of its heaviest edge until no cycle remains.
the add-non-heavy-edge algorithm. Start with the empty set. Iterate through all edges. Each edge is added and, if a cycle is formed, remove one of it heaviest edges.
the replace-by-lighter-edge algorithm. Start with any spanning tree $T$.
Find the cycle in $T$ plus an edge $e$ not in $T$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $T$ and add $e$ to $T$. Repeat until we cannot reduce the weight of $T$ any more.

The following MST algorithm is not comparison-compatible.

the degree-biased Kruskal's algorithm, which is Kruskal's algorithm with the following modification. Suppose when we are going to remove an edge with the minimum weight from $S$ as in the wikipedia's description of Kruskal's algorithm, we have multiple edges with the minimum weight to choose. The edge we choose to remove will be an edge whose sum of degrees of its two vertices is the largest among all choices. This algorithm cannot be comparison-compatible since it does not find the MST $\{ab,bc,cd\}$ of the graph with vertices $a,b,c$, and edge $ab$ of weight $1$ and edges $bc, cd, db$ of weight $2$. This algorithm is considered pathological because of that unnecessary modification.

Please note that all eight MST algorithms mentioned above are comparison-based.

How to show an algorithm is comparison-compatible?

I will use Kruskal's algorithm as an example. Here is the description of Kruskal's algorithm (in the second flavour) on a weighted undirected connected graph $G$.

create a graph $F$ that has the same vertices as $G$ but without edges. So $F$ is a forest of separated trees of a single vertex.
create a set $S$ containing all the edges in the graph.
while $S$ is nonempty and $F$ is not yet spanning

select an edge with minimum weight from $S$.
remove that edge from $S$.
If that edge connects two different trees then add it to the forest $F$, combining two trees into a single tree

output $F$.

Let $w_1$ and $w_2$ be two comparison-compatible weight functions on $G$. Kruskal's algorithm involves the weight function only in the step that "select an edge with minimum weight from $S$". The condition 2 of lemma 1 tells us that we can select a common lightest edge in this step. We can then check easily by induction that we can run all steps in the same way with $w_1$ and with $w_2$. So Kruskal's algorithm is comparison-compatible.

An algorithm is comparison-compatible if, in loose terms, it can be described in three kinds of steps.

do something that does not involve weight.
select an edge with the minimum weight in a given set of edges
select an edge with the maximum weight in a given set of edges

This sufficient condition covers Borůvka's, Prim's,  Kruskal's, reverse-delete, delete-heavy-edge and add-non-heavy-edge algorithm. Note that in order to fit this sufficient condition, we may have to change certain  descriptions of an algorithm without affecting the set of reachable MSTs. Because of the exception of the degree-biased Kruskal's algorithm being comparison-compatible, let me emphasize this sufficient condition is described in loose terms


Is program coding part of computer science?

I read a quote by Bjarne Stroustrup which said that computer science was the study of computers in the same way astronomy is the study of telescopes.

Computer science does indeed study coding in the abstract, particularly among the study of algorithms and data structures. Both of these fields are highly mathematical in nature, and seek to understand the idea of the abstract data type more fully. Of course, practical lessons can be learned and applied to various computers languages, systems, and applications, particularly answering questions like:

  Can it be done?
  What's the way to do it fastest with the least amount of memory?
  How do I compare two different ways to code the same solution to a problem?

When studying algorithms, for instance, Big-O Notation is presented as a way at looking at the computational complexity of an algorithm? Will it finish in linear time? What about polynomial time? In fact, in computational comlexity theory a tremendously important question about what can be solved abstractly with coding is the question of NP-completeness.

When studying coding abstractly, often pseudocode is used to represent instructions as opposed to an implemented language. For example:

  Procedure DoIt()
       Loop from 1 to 100
          If num is divisible by 3
              Print that its divisible by 3
          If num is divisible by 5
              Print that its divisible by 5
  End

Other ways of studying algorithms and data structures include diagrams and graphs, often using tree data structures.


Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges:

1-connectedness (ie. between any 2 nodes in a tree there is exactly one path)
any node can serve as the root of the tree.

Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ starting at $s$ first, some node $y$ starting at $x$ next. wlog $d(s,u) \geq d(s,v)$. note that $d(s,x) \geq d(s,y)$ must hold, unless the algorithm's first stage wouldn't end up at $x$. We will see that $d(x,y) = d(u,v)$.

The most general configuration of all nodes involved can be seen in the following pseudo-graphics ( possibly $s = z_{uv}$ or $s = z_{xy}$ or both ):

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

we know that:

$d(z_{uv},y) \leq d(z_{uv},v)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(z_{uv},x) \leq d(z_{uv},u)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$, otherwise stage 1 of the algorithm wouldn't have stopped at $x$.
$d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$, otherwise stage 2 of the algorithm wouldn't have stopped at $y$.

1) and 2) imply $\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$.

3) and 4) imply $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \, $ equivalent to $\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$.

therefore $d(u,v) = d(x,y)$.

analogue proofs hold for the alternative configurations

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

and

                          (x)        (u)
                          /            \
                         /              \
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /
                         \              /
                          \            /
                          (y)        (v)

these are all possible configurations. in particular, $x \not\in path(s,u), x \not\in path(s,v)$ due to the result of stage 1 of the algorithm and $y \not\in path(x,u), y \not\in path(x,v)$ due to stage 2.


Can we define an ε deterministic finite automaton?

Expanding on adrianN's comment, sure, you can define one if you want but what would be the point?

I guess the definition you have in mind is that the transition function has the form $\delta\colon Q\times (\Sigma\cup\{\varepsilon\})\to Q$. That is, for each state $q$ and each symbol $a$ in the alphabet, there's exactly one state that the automaton moves to after reading that symbol.  For each state, there's also a state the automaton can move to without reading a character of input (this is $\delta(q,\varepsilon)$).

Let's briefly investigate the properties of such a machine.  First, note that, if you don't want a $\varepsilon$-transition from some particular state, you can set $\delta(q,\varepsilon)=q$.  We can also see that this new type of automaton accepts exactly the regular languages. It's a special kind of NFA, so it can't accept any non-regular language.  And any DFA is just one of these automata where $\delta(q,\varepsilon)=q$ for every state $q$, so every regular language is accepted by an automaton of this kind.

So, what have we achieved?  The advantage of DFAs is that they're easy to analyze but it can be hard to construct a DFA to accept a particular language – if you don't believe me, design an algorithm that converts arbitrary regular expressions straight to DFAs, without using NFAs as an intermediate stage.  Conversely, NFAs are quite easy to construct but it can be hard to analyze what they're doing – for example, compare how annoyingly difficult it is to precisely define the language accepted by an NFA, compared to a DFA.

This new type of automaton seems to combine the disadvantages of both: requiring exactly one transition per state per symbol and at most one $\varepsilon$-transition per state means that it's still going to be fiddly to design an automaton that does what you want.  But the fact that the $\varepsilon$-transitions introduce nondeterminism means that it'll be harder to analyze what's going on. Meanwhile, the power of these new automata is exactly the same as the automata we already had, so we don't seem to have gained anything.


The idea is to build a layer graph $G'=\left (V_1,...,V_n\right)$ with $n$ layers, where each layer is a copy of $V$. For each $(u,v)\in E$ we add the edges $\left\{(u_i,v_{i+1}) | 1\le i \le n-1\right\}$, where $u_i$ is the copy of $u$ in $V_i$. In addition we add self edges $\left\{(u_i,u_{i+1}) | u\in V, 1\le i\le n-1\right\}$. You then want to know whether there exists a path $s_1\rightsquigarrow t_n$. Since $G'$ is a layer graph, any path from $s_1$ to $t_n$ is of length $n-1$ (so you dont need to worry about shorter paths anymore). You should now be able to complete the details yourself.


Is the class of non-regular languages closed against Kleene star?

Hint: Suppose $L$ is any language over the alphabet $\Sigma$. If $L$ is not regular then so is $L+\Sigma$, yet $(L+\Sigma)^* = \Sigma^*$ is regular.


While I don't know of any specific algorithms for this problem, you could approach this in a pretty efficient method by breaking it down into separate parts.

I would start by finding the rotation for each individual shape that provides a maximum height while maintaining a valid balancing orientation (is: not on a point like with the triangle).  If a shape has multiple equal heights, i would go with the configuration that gives the greatest surface area on top of it. Once you have this, you can then figure out how to best stack each object in a manor that is able to be balanced.


Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF?

Such an algorithm is described in Koch and Blum, Greibach Normal Form Transformation, Revisited.


Why is the halting problem semi-decidable?

Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity.

  Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.

No, that's not what it says. The halting problem is the computational problem of deciding whether $H$ halts on $x$, given $x$ and $H$ as input. It is important to note that "decide" here means "say yes if it is so, and say no if it is not".

The undecidability of the halting problem states that there is no single algorithm (Turing machine) that solves the halting problem for all $H$ and $x$.

  Now, in halting problem we can't say whether the machine will halt even if the input belongs to the language (YES cases). Then how is it Semi-decidable?

After the above clarification, your confusion here should be clear. It doesn't matter what "we can say". The "semi halting problem" is relaxed: the algorithm still has to say "yes" if $H$ halts on $x$, but it can do whatever it please if it does not (except answer "yes").

This is trivial to implement: just run $H$ on $x$. If it halts, answer "yes". If not, it doesn't matter since we're allowed to loop.


Valid-invalid bit in a process page table

Typically the page table is a tree of fixed size pages.  So each node of the page table contains a fixed number of entries.  Here's the picture of a 32-bit x86 multi-level page table from Wikipedia:

Each page on x86 is $2^{12}=4096$ bytes. Each page table entry is 4 bytes = 32 bits, and contains a pointer to the beginning of another page.  Each page table page contains exactly $2^{10}=1024$ page table entries.  Since the pages are aligned we know that the bottom 12 bits of the pointer would all be zeros, so we use those bits for status bits (including the invalid bit).  The invalid bit is necessary if you want to make the table sparse in any way.


Average access time in two level cache system

First Let's define all given things

L1 Cache hit: 90% & Time: 1ns

L2 and RAM has hit rate 10% out of which 95% which is 9.5% in total

L2 Cache hit: 9.5% & Time 20ns

RAM has hit rate 5% of 10% = 0.5%

RAM hit: 0.5% & Time 220ns

Formula Avg Memory Access Time

AMAT = L1_hit * L1_T + L2_hit * L2_T + RAM_hit * RAM_T

AMAT = 0.9*1 + 9.5*20 + 0.5*220

AMAT = 300.9ns

What is 2 level cache system:

First cache called L1 is reside on CPU is too fast. When CPU needs data, it checks in L1 cache but if it is not there it will go to L2. L2 cache is sometimes on CPU or outside CPU it depends on architecture of CPU. It does similarly and here also it missed then it fetch data from RAM which is expensive process.


How is the key in a private key encryption protocol exchanged?

Whenever Alice and Bob wants to agree on a same private key, the most popular method is to use Diffie-Hellman. It works as follows:

Two public values are first chosen lets say $n=13$ and $g=17$.
(These are usually very large prime numbers and known to everyone
using that protocol).
Alice chooses a Private Value $a = 3$ and Bob chooses a Private
Value $b = 7$. These are private to themselves.
Alice computes: $A = g^a\mod n$ and Bob computes: $B = g^b\mod n$,
in this case $A = 12$ and $B = 4$ and they exchange each others
values (may be through chat), i.e. everybody knows the values of $A$
and $B$.
Alice computes: $K = B^a \mod n$ and Bob computes: $K = A^b\mod n$, in this case $K = 12$.

Now Alice and Bob have both agreed upon the value $K$ as their key. Note that since the value $n$ and $g$ and very large prime numbers it is almost impossible for a eavesdropper to factorize them and compute the key himself.

A problem in private key cryptography is man-in-the-middle attack and that is one of the main reasons to choose public key cryptography over private key cryptography.


How do you translate these 2 regular languages in words correctly?

For 1. it is not quite the reverse; it happened to be a reverse in your example. So if $u = aab$ and $v = abb$ and $uv \in L$, then you know $vu = abbaab \in \text{cycle}(L)$, but you wouldn't be able to say that $bbabaa = v^Ru^R \in \text{cycle}(L)$.

For 2. it is not that you want the concatenation of two strings of equal length, but rather you only want the first half of even-length strings in $L$. That is, if, say, $aabbabbabb \in L$, then $aabba \in L/2$.


Is the problem of evaluating a boolean formula on a given assignment P-complete?

In his 1987 paper "The Boolean formula value problem is in ALOGTIME", Buss showed that Boolean formula evaluation is in ALOGTIME (alternating logarithmic time), which is a uniform version of NC1 and so probably smaller than P. It is also ALOGTIME-complete under AC0 reductions.


In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

Construct a large number of circuits of size $k$, which by construction compute different functions.
Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.


Checking for $3$-colorability by searching for $K_4$ as a minor

Hadwiger's conjecture states that if a graph is not $(k-1)$-colorable then it has a $K_k$ minor. Hadwiger himself proved it for $k \leq 4$. Thus, any graph which is not $3$-colorable has a $K_4$ minor. However, the converse doesn't hold: some graphs having a $K_4$ minor are $3$-colorable. For example, take $K_4$ and split each edge into a path of length $2$ edges. The result is bipartite, and so $2$-colorable.


How can one come up with reasonable IP subnet allocations?

Hints:

Try working out the binary representation of 245.248.136.0 (it's 32 bits) and of 245.248.128.0.
Re-read what the /21 and /22 notation means and how CIDR works.
What is the range of IP addresses included in 245.248.128.0/22?  in 245.248.136.0/21?

I think once you understand the concepts you'll find that this question is straightforward.

Advice: Rather than asking a question about this specific exercise, you might do better to ask a question about some concept you don't understand: e.g., what /N notation means, how CIDR works, etc.  But make sure to do your research first.  There's lots written on CIDR, /N notation, etc.  You can probably clear up your confusion on your own by doing proper reading on those concepts.


Is there a way to test if two NFAs accept the same language?

The decision problem is PSPACE-complete as Shaull noted.

However, it turns out that in practice it is often possible to decide NFA equivalence reasonably quickly.  Mayr and Clemente (based on experimental evidence) claim that the average-case complexity scales quadratically.  Their techniques rely on pruning the underlying labelled transition system via local approximations of trace inclusions.

Just like SAT is NP-complete in a worst-case analysis, yet often turns out surprisingly tractable for real-world instances, it therefore seems likely that NFA equivalence can be decided efficiently for many real-world instances.

Richard Mayr and Lorenzo Clemente, Advanced automata minimization, POPL 2013, doi:10.1145/2429069.2429079 (preprint)


Why does the concatenation of the empty set with any language give the empty set?

Let $L_1, L_2$ be languages, then the concatenation $L_1\circ L_2=\{w\mid w=xy, x\in L_1, y\in L_2\}$. If $L_2=\varnothing$, then there is no string $y\in L_2$ and so there is no possible $w$ such that $w=xy$. Thus for any $L_1$, we'll have $L_1\circ\varnothing = \varnothing$.


Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$

Since you know that the maxium value is achieved when $i$ is the largest prime smaller than $N$, your problem is equivalent to finding the largest prime smaller than $N$.

There are many ways to test for primality, so presumably you could just take your favorite primality test and run a for loop from $N-1$ downwards, to find the first number which is prime.

Perhaps I do not understand what you are asking for.


CPU Cache is managed by which software component?

The CPU caches are operational from the very moment on when the CPU is powered up. Neither the BIOS nor an OS are strictly speaking “necessary” to control the caches. The BIOS and the OS can change cache configuration settings in the CPU but they don’t control the normal operation, this is all built into the CPU itself.


Does a PDA follow a transition if the top stack symbol doesn't match?

TL;DR: No, it does not.

I would guess that your notation a, a -> b means the syntax in a PDA transition such that if we read a character a from the input and we pop a character a from the stack, then we put a character b on top of the stack.

The notation of that transition that I'm used of is written as $$q\xrightarrow{\text{e,d;u}}r,$$

where the left side of the semicolon is what we read, i.e. character e from the input and character (or symbol) d from the stack. Right side of the semicolon is what we put onto the stack: u.

In order for your PDA to follow a transition, it has to match both of the conditions on the left side of the above notation. So, your PDA won't follow that particular transition if the stack symbol doesn't match.

What comes to your second question about having two different transitions with same input but different stack symbol, yes, that is possible based on nondeterminism, but your PDA still has to meet both conditions in the left side of the notation in order to move anywhere.

Hope this had any help!


3Sum Why this O(nlogn) solution doesn't work?

This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1.
The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include it. But this is not justified by anything, and it could well be that all solutions need that element.
A great way to test algorithm ideas like this is to write a small program that generates many small random inputs, and compare the result of your algorithm on each of them to the result of a known-correct brute-force approach.


What is the consensus algorithm that requires an odd number of nodes?

To my knowledge there is no quorum-based consensus algorithm that requires an odd number of nodes (processes). That's because such algorithms don't require a majority in the sense that a higher number of processes accept a value. A majority in these algorithms means that at least $N / 2 + 1$ processes accept a value, where $N$ is the total number of processes.

The reason for this is that a quorum-based algorithm requires that every decision made is known by at least one member of each one of the possible quorums in the system. One simple way (but not the only one) to achieve this is to require that every quorum is composed by $N/2 + 1$ processes and that the vote is unanimous inside a quorum.

For example, in a system with two processes two votes are required and the system is not fault tolerant. For three processes two votes are required. For four, three votes. For five, three votes.


Create a random graph based on the Degree Distribution and Clustering Coefficient Distribution

You may want to have a look at the block two-level Erdos-Renyi model (BTER). The usual preferential attachment mechanism for generating scale-free networks doesn't capture the clustering coefficient right, and small-world networks aren't scale-free; the BTER model can capture both scale-free and clustering behavior. I think they have some way to make it work for an arbitrary degree distribution (not just scale-free). The link I gave above has code for generating BTER graphs too.


Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete?

Yes, it is $NP$-complete even if $d=4$.

Note that unless $P=NP$, we cannot prove $NP$-completeness for $d=2$ because it is merely  the problem of counting the number of connected components of a given graph.

Reduce from Exact-Cover-by-$3$-sets (X3C).

Given an instance of X3C, we construct an instance of our problem as follows.

The set of elements is $E=\{e_1,e_2,\dots,e_n\}$.
The set of $3$-sets is $C=\{s_1,s_2,\dots,s_m\}$.

This will be a YES instance (of X3C) iff there exists $C'\subseteq C$ with $|C'|=\frac n3$ that cover each element exactly once.

Now, set the set of variables $V=C\cup E\cup C^{up}$ where $C^{up}=\{s_j^{up}|s_j\in C\}$, that means each element is a varialbe and each $3$-set is also a variable. And for each set $s_j$, we add a new variable $s_j^{up}$.

Note that, X3C remains $NP$-complete even when each element belongs to at most $2$ sets and each pair of $3$-sets shares at most one element.

So, here come the equations.

For each $3$-set $s_j\in C$ where $s_j=\{e_a,e_b,e_c\}$, add the following equations:

$\{s_j,e_a,e_b,e_c\}$
$\{s_j,s_j^{up}\}$
$\{s_j,s_j^{up},e_a\}, \{s_j,s_j^{up},e_b\}, \{s_j,s_j^{up},e_c\}$

Finally, set $k=\frac n3$.

We have done with our reduction. Now we have to prove its correctness.

Proof of correctness: (sketchy)

For one direction, if we have a solution $C'$ to our given X3C, it is obvious that $C'$ is also a solution to our instance.

For the other direction, note that it is w.l.o.g to assume that a (minimal) solution contains only variable in $C$. Because if it contains an element (in $E$), we can safely remove it from the solution and add one of the containing $3$-sets (that the element belongs to) to the current solution (if that set has not already been present in the current solution).

So, now a subcollection $C'\subseteq C$ is a solution to our problem. We show that it is also a solution to the original X3C instance.

For each $s_j\notin C'$, it must be the case that all $3$ contained elements of $s_j$ must be deducible. For otherwise, $s_k$ becomes unreachable.

For each element $e_i\in E$, it must be the case that one of the $2$ sets containing it must be included in $C'$.$\blacksquare$

Take @xskxzr's example: The given X3C instance is $E=\{e_1,\dots,e_9\}$, $C=\{s_1,\dots,s_5\}$ where $s_1=\{e_1,e_2,e_3\}$, $s_2=\{e_4,e_5,e_6\}$, $s_3=\{e_2,e_5,e_8\}$, $s_4=\{e_6,e_7,e_9\}$, $s_5=\{e_1,e_4,e_7\}$.

Our set of variables will be $V=C\cup C^{up}\cup E=\{s_1,\dots,s_5,s_1^{up},\cdots,s_5^{up},e_1,\dots,e_9\}$.

Our set of equations will be:

$\{s_1,s_1^{up}\},\dots,\{s_5,s_5^{up}\}$
$\{s_1,e_1,e_2,e_3\}$, $\{s_2,e_4,e_5,e_6\}$, $\{s_3,e_2,e_5,e_8\}$, $\{s_4,e_6,e_7,e_9\}$, $\{s_5,e_1,e_4,e_7\}$
$\{s_1,s_1^{up},e_1\},\{s_1,s_1^{up},e_2\},\{s_1,s_1^{up},e_3\}$
$\{s_2,s_2^{up},e_4\},\{s_2,s_2^{up},e_5\},\{s_2,s_2^{up},e_6\}$
$\{s_3,s_3^{up},e_2\},\{s_3,s_3^{up},e_5\},\{s_3,s_3^{up},e_8\}$
$\{s_4,s_4^{up},e_6\},\{s_4,s_4^{up},e_7\},\{s_4,s_4^{up},e_9\}$
$\{s_5,s_5^{up},e_1\},\{s_5,s_5^{up},e_4\},\{s_5,s_5^{up},e_7\}$

And $k=\frac n3=3$.


Proof that $A^* - \{x\} = A^+$ such that $A=\{a,b\}$ and $x \in \{a,b\}^*$

Your problem is that in going from $A^*-\{x\}$ to $\{a,b\}^*-\{\{a, b\}^*\}$ you went a step too far. In the first expression, $x$ is a single string over the alphabet. Replacing that with the general expression $\{\{a,b\}^*\}$ is incorrect, if for no other reason that $\{\{a,b\}^*\}$ is a set consisting of a set of words and not a single word.

To complete this answer, see newbie's comment on your original post.


Does the conservative two phase locking protocol produce cascadeless schedules?

Yes, the conservative 2PL does not garantuee cascadelessness. Requesting all locks at the beginning of the transaction is used to prevent deadlocks.

If you want to prevent cascading rollbacks, you need to have a look at how the locks are released. There are two versions of the 2PL-Protocol that garantuee cascadeless schedules: the strong 2PL and the rigorous 2PL, which is even stricter.

Schedules that satisfy the strong 2PL may release read-locks at any time and all write-lock at the end of the transaction. Schedules that satisfy the rigorous 2PL may only release all locks at the end of the transaction.

Lets have a look at what happens to your schedule if you use the conservative and rigorous (or strong) 2PL.

\begin{array}{lcr}
\mbox{$T_1$} & \mbox{$T_2$}\\
\\
\mbox{lock-exclusive(a)}  \\
\mbox{lock-exclusive(b)}  \\
\mbox{read(a)} \\
\mbox{a=a+50} \\
\mbox{write(a)} \\
\mbox{read(b)} \\
\mbox{b=b+100} \\
\mbox{write(b)} \\
\mbox{unlock(a)} \\
\mbox{unlock(b)} \\
\mbox{} & \mbox{lock-exclusive(a)}\\
\mbox{} & \mbox{read(a)}\\
\mbox{} & \mbox{a=a+50}\\
\mbox{} & \mbox{write(a)}\\
\mbox{} & \mbox{unlock(a)}\\
\end{array}

Because $T_1$ is not allowed to do $\mbox{unlock(a)}$, $T_2$ can not request the lock and therefore can not start. $T_1$ continues until the end and releases its lock. Now $T_2$ can start.

You can also see here that a conservative, rigorous 2PL leads to a serial execution of Transactions that access the same variables.


Conceptual explanation of negative weights?

What is the significance of negative weight edges in a graph?

Above link answers your query.

One more example:-
If we want to design some architecture then in the whole circuitry there is flow of current. The whole circuitry can be modeled as graph with device components as vertices and the path between them as edges. In these paths the resistance can be taken as negative weights.


How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?

First of all, backreferences can not be simulated by finite automata as they allow you to describe non-regular languages. For example, ([ab]^*)\1 matches $\{ww \mid w \in \{a,b\}^*\}$, which is not even context-free.

Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; you just concatenate and/or intersect checking and consuming expressions and use the resulting automata. The idea is to check the look-ahead or look-behind expressions while you "consume" the input and store the result in a state.

When implementing regexps, you want to run the input through an automaton and get back start and end indices of matches. That is a very different task, so there is not really a construction for finite automata. You build your automaton as if the look-ahead or look-behind expression were consuming, and change your index storing resp. reporting accordingly.

Take, for instance, look-behinds. We can mimic the regexp semantics by executing the checking regexp concurrently to the implicitly consuming "match-all" regexp. only from states where the look-behind expression's automaton is in a final state can the automaton of the guarded expression be entered. For example, the regexp /(?=c)[ab]+/ (assuming $\{a,b,c\}$ is the full alphabet) -- note that it translates to the regular expression $\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$ -- could be matched by

[source]

and you would have to

store the current index as $i$ whenever you enter $q_2$ (initially or from $q_2$) and
report a (maximum) match from $i$ to the current index ($-1$) whenever you hit (leave) $q_2$.

Note how the left part of the automaton is the parallel automaton of the canonical automata for [abc]* and c (iterated), respectively.

Look-aheads can be dealt with similarly; you have to remember the index $i$ when you enter the "main" automaton, the index $j$ when you leave the main automaton and enter the look-ahead automaton and report a match from $i$ to $j$ only when you hit the look-ahead automaton's final state.

Note that non-determinism is inherent to this: main and look-ahead/-behind automaton might overlap, so you have to store all transitions between them in order to report the matching ones later, or backtrack.


Finding the number of iterations to a recurrence

Presumably the correct form of the recursive step is
$$ S_{k+1} \leq S_k - S_k \frac{\sigma}{1+\sigma} = \frac{S_k}{1+\sigma}. $$
Using induction, we can show that
$$ S_t \leq \frac{S}{(1+\sigma)^t}. $$
So the algorithm will end by the time $T$ satisfying
$$ \frac{S}{(1+\sigma)^T} < 1.$$
I'll let you solve this yourself.


Select at least one from each category to minimize union, NP-hard problem?

Nice question! Let us call this problem the minimum label-covering problem.
We will reduce the hitting set problem, a well-known $\mathsf{NP}$-hard problem to the minimum label-covering problem, thus proving it is also $\mathsf{NP}$-hard. Our strategy is simply translating "intersecting the $i$-th set" in the hitting set problem to "labelled with the $i$-th label" in the minimum label-covering problem.
Given $V=\{V_1, V_2,\cdots, V_m\}$, which is a collection of subsets of a finite set $U$ and a number $k$, the hitting set problem is to find the smallest subset of $U$ which intersects (hits) every set in $V$. Let $S$ be the disjoint union of $U$ and $\{l_1,l_2,\cdots, l_m\}$, a set of $m$ labels. Let $C$ be the set of all subsets of $S$ of the form $\{u, l_i\}$ where $u\in V_i$.  Let the label for $\{u, l_i\}$ be $l_i$. Suppose we have solved the minimum label-covering problem for $C$, $S$ and the specified labelling, that is, we have selected at least one set from each category such that their union is minimized. Let $U'$ be the set of all elements of $U$ that are members of the selected sets. It is easy to verify that $U'$ is the smallest subset of $U$ that hits every set in $V$. Our proof is done.
An exercise
Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category, the maximum label-covering problem is to select at most one $c$ from each category such that the size of their union is maximized. Show the maximum label-covering problem is $\mathsf{NP}$-hard.


Decide given complexity of given function

This answer assumes that $\log$ is to the base 2.

Consider $n = 2^{1000}$. Then
$$
f(n) = 2^{1000}, \quad g(n) = (\log_2 2^{1000})^{100} = (1000)^{100} < (1024)^{100} = (2^{10})^{100} = 2^{1000}.
$$
If you increase $n$ even more, you will see an even more dramatic difference between $f(n)$ and $g(n)$. You just have to consider large enough $n$, perhaps too large for your calculator.

What this example shows that even though $f(n)$ grows faster than $g(n)$, for values of $n$ encountered in practice the situation is very different, with $g(n)$ being much larger than $f(n)$. This shows the limits of asymptotic analysis – it is a natural and useful mathematical notion, but it isn't always a good model for reality.


Is it mandatory to define transitions on every possible alphabet in Deterministic Finite Automata?

Suppose a DFA was allowed to have missing transitions.  What happens if you encounter a symbol which has no transtion defined for it?  The result is undefined.  That would seem to violate the "deterministic" characteristic of a DFA.

However, it's trivial to transform such an incomplete DFA into a complete DFA.  Simply add a new state, illegal, and map any undefined transitions to the illegal state.  Finally, add transitions for every symbol from the illegal state back to itself. This illegal state is often called a sink state, because once data falls into the sink there's no way to get out.

So, from a practical perspective, it's kind of moot, as long as you have a well-defined way to handle missing transitions.


For $0 \leq i \leq pm+1$, define
$$
x_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor.
$$
We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) is
$$
x_i - x_{i-1} = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor - \left\lfloor (i-1) \frac{pn+1}{pm+1} \right\rfloor \in \left\{ \left\lfloor \frac{pn+1}{pm+1} \right\rfloor, \left\lceil \frac{pn+1}{pm+1} \right\rceil \right\},
$$
so your first condition is satisfied (the spaces are as equal to each other as possible).

For your second condition, we need to verify that $1 \leq x_1,\ldots,x_m \leq n$, $n+1 \leq x_{m+1},\ldots,x_{2m} \leq 2n$, and so on. It's clearly enough to verify that $x_{Cm} \leq Cn$ for $1 \leq C \leq p$ and that $x_{Cm+1} > Cn$ for $0 \leq C < p$. For the first condition, we have
$$
x_{Cm} = \left\lfloor Cm \frac{pn+1}{pm+1} \right\rfloor < Cm \frac{pn+1}{pm+1} + 1 = \frac{Cpmn + Cm + pm + 1}{pm+1} \\ < \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1,
$$
using your implicit assumption $m < n$. For the second condition,
$$
x_{Cm+1} = \left\lfloor (Cm+1) \frac{pn+1}{pm+1} \right\rfloor \geq (Cm+1) \frac{pn+1}{pm+1} = \frac{Cpmn + Cm + pn + 1}{pm+1} \\
\geq \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1,
$$
using $Cm + pn \geq Cn + pm$, which follows from $(p-C)(n-m) \geq 0$.


What you can do, is to employ a method called rejection sampling:

Flip the coin 3 times and interpret each flip as a bit (0 or 1).
Concatenate the 3 bits, giving a binary number in $[0,7]$.
If the number is in $[1,6]$, take it as a die roll.
Otherwise, i.e. if the result is $0$ or $7$, repeat the flips.

Since $\frac 68$ of the possible outcomes lead to termination in each set, the probability of needing more than $l$ sets of flips to get a die roll is $(1-\frac 68)^l = \dfrac 1{4^l}$. Hence, this method is efficient in practice.

Improvements:

@Angel's answer points out, that the number of coin flips in each set but the first can be reduced from 3 to 2, by using the distinction between a $0$ and a $7$ as the first bit for the next set.

@Emanuele Paolini explains, how you can reduce the number of rerolls, if you need multiple die rolls.


Pseudo-number generation compared to Blum-Micali

No, your algorithm is fundamentally different.  The resemblance is purely superficial.  The Blum-Micali generator is based on integers modulo a large prime number, and leverages deep number theoretic ideas.  Yours is based on the fractional part of real numbers (hence the "mod 1"), and is not based on number theory and not related to Blum-Micali.  Blum-Micali is cryptographically secure.  Your scheme seems unlikely to be.


The universe here is the set of all strings over the alphabet $\{a,b\}$ and is usually denoted by $\{a,b\}^*$.

You have way too many brackets.


is duality principle in boolean algebra is true for every expression

Negation gives you $\overline{A}=0,\overline{B}=0$, so everything is ok in "and".


Is a very long plain text password harder to crack than a short complicated password?

Usually when we talk about "hard to find" we are talking about brute force guessing. This is where the attacker just keeps trying different passwords till they find the right one. I'm going to assume we're talking about this model here and not talk about the real world with hashing and rainbow tables and so forth.

Now, there is nothing inherently different about trying a 5-character random string versus trying a 4-word password. They are both equally easy for a computer to plug in and see if they work. Instead, the question is how many guesses you need to find the password, i.e. how hard is it for an attacker to guess your password.

Now, an important question is what the attacker knows about your strategy of picking passwords.
We usually want to make the worst-case assumption that the attacker knows our method for picking passwords. Under this key assumption, we can compare the two methods.

If we pick a 5-character password uniformly at random from all strings containing a-z,A-Z,0-9,!@#\$%^&*()-_+={}[];:'"|\,<.>/? then we have something like $92^5 \approx 6.6$ billion possibilities. So the attacker has a one in $6.6$ billion chance of guessing it on the first try, and so on.

If we pick 4 random words uniformly from a set of say 500 words, then we have $500^4 = 62.5$ billion possibilities. So in this example, the attacker is worse off trying to guess a 4-word random passphrase than a 5-character random string. Notice that the example is really assuming that we do this random process for picking passwords, i.e. we run a computer program that takes a list of 500 words and (using good randomness!) spits out a sequence of 4 random words.

Also notice that both of these examples assumed that the attacker knows your strategy. If the attacker is first going to try all 4-word passphrases, and then all 5-character strings, then you would rather have a short random string because it will take longer for that attacker to guess. But since you don't know what the attacker knows, you're best off assuming they know what type of passwords you use, but they don't know which one you picked. And by "type" of password, I really mean a method of generating that password, like uniformly random 5-character strings. Thinking about this method, as we did above, tells you how random or hard-to-guess it is.


Algorithm for generating random incrementing numbers up to a limit

-- generate ALL sequences of n natural numbers with given sum
-- should be called with n<=sum
gen(n,sum):
  for i in 1..sum-n+1:
    -- next number in sequence is i
    gen(n-1,sum-i)  -- generate ALL possible sequences of remaining numbers


Do any programming languages use general recursive functions as their basis?

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons.

General recursive (i.e., $\mu$-recursive) functions are significantly less expressive than lambda calculi. Thus, they make a poor foundation for programming languages. You are also not correct that the TM is the basis of imperative PLs: in reality, good imperative programming languages are much closer to $\lambda$-calculus than they are to Turing machines.

In terms of computability, $\mu$-recursive functions, Turing machine, and the untyped $\lambda$-calculus are all equivalent. However, the untyped LC has good properties that none of the other two have. It is very simple (only 3 syntactic forms and 2 computational rules), is highly compositional, and can express programming constructs relatively easily. Moreover, equipped with a simple type system (e.g., System $F\omega$ extended with $\mathsf{fix}$), the $\lambda$-calculus can be extremely expressive in that it can express many complex programming constructs easily, correctly and compositionally. You can also extend the $\lambda$-calculus easily to include constructs that are not lambdas. None of the other computational models mentioned above give you those nice properties.

The Turing machine is neither compositional nor universal (you need to have a TM for each problem). There are no concepts of "functions", "variables" or "composition". It is also not exactly true that TMs are the basis of imperative PLs - FWIW, imperative PLs are much, much closer to lambda calculi with control operators than to Turing machines. See Peter J. Landin's "A Correspondence Between ALGOL 60 and Church's Lambda-Notation" for a detailed explanation. If you have programmed in Brainf**k (which actually implements a rather simple Turing machine), you will know that Turing machines are not a good idea for programming.

$\mu$-recursive functions are similar to TMs in this respect. They are compositional, but not nearly as compositional as the LC. You also just can't encode useful programming constructs in $\mu$-recursive functions. Moreover, the $\mu$-recursive functions only compute over $\mathbb{N}$, and to compute over anything else you'd need to encode your data into natural numbers using some sort of Gödel numbering, which is painful.

So, it is not a coincidence that most programming languages are somehow based off the $\lambda$-calculus! The $\lambda$-calculus has good properties: expressiveness, compositionality and extensibility, that other systems lack. However, Turing machines are good for studying computational complexity, and $\mu$-recursive functions are good for studying the logical notion of computability. They both have outstanding properties that the $\lambda$-calculus lacks, but in the field of programming $\lambda$-calculus clearly wins.

In fact, there are many, many more Turing complete systems out there, but they lack any outstanding property whatsoever. Conway's Game of Life, LaTeX macros, and even (some claim) DNA are all Turing complete, but no one programs (i.e. do serious programming) with Conway or studies computational complexity using LaTeX macros. They simply lack good properties. Turing complete per se is nearly meaningless when it comes to programming.

Also, many non-Turing complete computational systems are very useful when it comes to programming. Regular expressions and yacc are not Turing complete, but they are extremely powerful in solving a certain class of problems. Coq is also not Turing complete, but it is incredibly powerful (it's actually considered much more expressive than its Turing complete cousin, OCaml). When it comes to programming, Turing completeness is not the key, as many (close to) useless systems are uninterestingly Turing complete. You're not going to claim that Brainf**k or Whitespace are more powerful programming languages than Coq, are you? An expressive foundation is the key to powerful programming languages, and that's why modern programming languages are almost always based on the $\lambda$-calculus.


I'll start by giving an example which can be easily run in parallel: the elliptic curve method (ECM). In this method, we choose a random elliptic curve $E$, and run Pollard's $p-1$ method on this curve up to a certain point. The idea is that with probability $\alpha$, Pollard's $p-1$ method terminates within $T$ iterations. We optimize over $T/\alpha$, the end result being that $\alpha$ is quite small.

Here is how you would run ECM in parallel. Each processor (or core) runs the algorithm just described, until one of them succeeds in factoring the integer. Having $N \ll 1/\alpha$ processors (or cores) cuts the running time by a factor of $N$. An algorithm where a similar approach is possible is called embarrassingly parallel.

A slightly different example is the quadratic sieve. In this algorithm, we need to find a certain number of smooth integers and factor them. If we aim at finding $n$ such integers and there are $N$ processors available, we can assign each of them to find $n/N$ integers. A more complicated approach would be to have one central processor assign "jobs" (integers) to processors: each time a processor finishes factoring a smooth integer, it receives a new one. (In practice, since the algorithm sieve for smooth integers, each processor will get a range of potential smooth integers.) This scheme is also embarrassingly parallel.

In contrast, consider the simple Pollard's $p-1$ method. The algorithm is iterative in nature and there doesn't seem to be a simple way to run it in parallel; we can perhaps run the FFTs associated with modular exponentiation using a sophisticated parallel scheme, but this is no longer embarrassingly parallel.

At this point you should be able to answer the question on your own. The question is asking you to determine which of the algorithms are embarrassingly parallel.


What is this trapezoid-shaped logic component?

Looking at slide 5-43 "Data Path Revisited" these are MUX, multiplexors.

As such they are a "switch": When the red input is 1, we have immediate mode and the SEXT output is passed through unchanged. When it is 0 it needs to look up a value based on the SEXT value and some memory or register.

Also in the slides, a MUX is represented again at BR and JMP, slides 5-31 and 5-35, again without actually clearly defining the alternative scenarios, and the BR case confuses the issue a bit because it clearly calculates a relative jump previously.

I'd guess the red input is the result of the branch condition and if false the original PC is passed through, but if that was the case they might as well have connected up the lines in this diagram.

For the JMP it is currently showing an absolute jump and under a different red arrow input it could be an indirect jump, similar to the ADD case.

(My latter suggestions have not actually been reconsidered much after reviewing slide 5-43.)


Yes, Earley's algorithm can be parallelized, but not in the way that you are thinking.
Earley's Algorithm In Particular
You ask about Earley's algorithm specifically. Parallelizing the algorithm in the way you suggest is unlikely to be faster. Researchers Peter Ahrens, John Feser, and Robin Hui report:

We first tried to naively parallelize the Earley algorithm by processing the Earley items in each Earley set in parallel. We found that this approach does not produce any speedup, because the dependencies between Earley items force much of the work to be performed sequentially.

The reason Earley's algorithm in particular is difficult to parallelize is because of interdependencies within the computation. To answer how successfully Earley's algorithm parallelizes, we need to solve this  demarcation problem: What should be call Earley's algorithm? Seth Fowler and Joshua Paul explain:

There  are  several  published  algorithms  (see,  for  example, Hill and Wayne[6]) for parallelizing a variant of the  the  Earley  algorithm,  the  CYK  algorithm.   Unfortunately,  in  practice  CYK  has  a  much  longer  running time than Earley (even though it has the same worst-case complexity of $O(n^3)$), and so it is not typically used.

Most researcher's agree that there are few successful parallelizations of the algorithm, however. Fowler and Paul continue:

For  the  Earley  algorithm  itself,  there  are  very  few parallelization  methods  published  (though  there  are many  optimizations—see,  for  example,  Aycock  and Horspool [1]).   One  such  method  by  Chiang  and  Fu [3] uses  a  decomposition  similar  to  the  one  we  develop,but goes on develop the algorithm for use on a specialized VLSI. Similarly, Sandstrom[7] develops an algorithm based on a similar decomposition....

Nonetheless, there are parallel versions. Peter Ahrens, John Feser, and Robin Hui who we cited earlier present "the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism." The researchers claim a "120x speedup over the Earley algorithm on a natural language task."
Parallel parsing in general - usually impractical
Parallel parsing techniques have been studied for decades.  Other parsing algorithms are more amenable to parallelization, such as the CYK algorithm mentioned above. But parallelizing parsing is only rarely a practical strategy. Most parsing tasks you are likely to encounter are much more efficiently performed serially, that is, in the old fashioned single-threaded way.
The reason parallel parsing algorithms are generally impractical is because parallelism has a lot of overhead that needs to be recouped by the gain in speed, while most parsing tasks can be performed incredibly quickly. (See parallel slowdown.) Quoting from Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs:

From a practical point of view, parallel parsing is interesting only for problems big enough to require considerably more time than a fraction of a second on a single processor. There are three ways in which a parsing problem can be this big: the input is very long (millions of tokens); the grammar is very large (millions of rules); or there are millions of inputs to be parsed. The last problem can be solved trivially by distributing the inputs over multiple processors, where each processor processes a different input and runs an ordinary, sequential, parser. Examples of very long inputs requiring parsing are hard to find. All very long parsable sequences occurring in practice are likely to be regular: generating very long CF sequences would require a place to store the nesting information during sentence generation. ...
The situation is different for parsing with very large grammars. These are found most often in linguistics. They are especially bothersome there since most linguistic applications require general CF parsing techniques, the speed of which depends on the grammar size.

References
Seth Fowler and Joshua Paul. "Parallel Parsing: The Earley and Packrat Algorithms." (2009). Note that this is a student project report for an undergraduate course.
Peter Ahrens and John Feser and Robin Hui. "LATE Ain’T Earley: A Faster Parallel Earley Parser." (2018) The arXiv, 1807.05642.
Grune D., Jacobs C.J.H. (2008) Parallel Parsing. Parsing Techniques. Monographs in Computer Science. Springer, New York, NY.


An efficient algorithm to decide if a triangulation is 3-colourable

Let us assume that the dual graph is connected, which means that if you connect any two faces which share an edge, then you get a connected graph on the triangular faces.

Pick an arbitrary triangular face $F$ and color its 3 vertices with 3 distinct colors. If $F'$ shares an edge with $F$, then there is only one choice for the color of the remaining vertex of $F'$. Continuing in this way, attempt to color all vertices. If you're successful, the graph can be 3-colored. Otherwise, the graph cannot be 3-colored.

This algorithm is very similar to the one for deciding whether a given graph can be 2-colored.


Efficient algorithm for this optimization problem? Dynamic programming?

This is just an extension to @Sébastien Loisel's answer.

Notice minimize $(x_i-y_i)^2$ subject to $x_i-x_{i-1}\ge c_i$ is equivalent to minimize $(x_i-(y_i-c_i))^2$ subject to $x_i\geq x_{i-1}$. Let $a_i=y_i-c_i$, then this is precisely the isotonic regression problem. There exist a $O(n)$ time algorithm.


How are Signed integers different from unsigned integers once compiled

There is no way to tell if 8 bits in memory are a signed integer, an unsigned integer, a character, or part of a bigger data. The knowledge is put in the instructions.

As stated by David Richerby, two's complement makes signedness transparent in most operations (addition, substraction, multiplication), but some are different: the bitwise shift may preserve or ignore the sign bit. Some processors implement arithmetic shift to preserve sign bit (acting like a division, even on negative numbers) and logic shift (which is suitable for unsigned integers). When you compile your source code, the compiler knows the type of your data, and generate the program with the instruction that fit with your use-case.

Please note that some processors implement only one type of bit shifts. In such case, to keep the same behavior, the compiler will add some extra instructions to do the same work (based on the compiler's knowledge of the data types). Some languages may avoid such extra work on the compiler by stating something like

  The result of E1 >> E2 is E1 right-shifted E2 bit positions. [...] If E1 has a signed type and a negative value, the resulting value is implementation-defined.

Source : C language : ISO/IEC 9899:TC2 section 6.5.7 (Bitwise shift operators)

Type and signedness aren't part of the data itself. The knowledge was already used to generate the instructions that use the data according to their actual type. For dynamic type evaluation (at runtime, see dynamic programming language), some kind of tags (many implementations are possible) are added in the data structures to identify their type, and use the appropriate code to handle it.


Hint: The time hierarchy theorem implies that there is a function $g$ solvable in time $f(n) = n^{\log n}$ but not in time $o(f(n)/\log f(n)) = o(n^{\log n}/\log^2 n)$. In particular, $g$ cannot be solved in polynomial time.


Controlling overflow and loss of precision during floating point multiplication

Multiplication of floating point numbers is considered uncritical with respect to accuracy. If your input is only accurate to 6 digits, there is no point in computing the output to 60,000 digits. The expected relative error after 10,000 multiplications is $\sqrt{10,000}\epsilon=100\epsilon$ with $\epsilon<10^{-14}$ for double precision. This is more than enough precision for your case.

Overflow and underflow on the other hand can indeed happen during multiplication. In practice, I would prefer to work with numbers in a range where I know that this won't happen. However, this may not always be possible. One can use frexp to split floating-point numbers into significant and exponent, multiply the significants separately and add the exponents together, and use ldexp for putting the result back together. However, doing this naively by applying frexp for every number and multiplying all 10,000 significants together at once would be a bad idea, because it would be slow and nearly guarantee underflow. But if done intelligently (appropriate grouping), it will yield the correct result, and the speed difference will be almost unnoticeable.


Essentially, $\Gamma$ is a store that maps variables to types.

This rule says that we can deduce that a variable has a type in a context if that type is stored for our variable in the context.

The rule is deliberately simple, and is a base case for the inductive process that is type derivation.

In short, to check the type of a variable, just look it up in the environment.


Does CSL contain an empty string or not? Is empty string accepted by LBA or not?

Welcome to CS.SE!
I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions.
Ultimately this is done to have a nice definition in the sense that the class of context-sensitive languages forms a proper superset of the class of context-free languages.
Definitions excluding the empty string to be in context-sensitive languages are a little bit less nice, in that sense.
As you found out, definitions may vary between sources and are often chosen in order to state some property or result in a particularly nice manner.
This is common in mathematics and another example would be the question of including 0 in the natural numbers $\mathbb N$ or not.
The thing is that usually these little changes do not really matter in the end; they do not fundamentally change the mathematical nature of the thing defined, and this is also the case with the small differences between the definitions for context-sensitive languages you encountered.


A technical clarification on subgraph isomorhism

The subgraph isomorphism problem is "Is $G$ isomorphic to some subgraph of $H$?" so, yes, if $H$ contains a $k$-clique, that clique on its own has subgraphs isomorphic to any graph on $k$ or fewer vertices. Your "exact presence" version is the induced subgraph isomorphism problem: is $G$ isomorphic to some induced subgraph of $H$? Both versions are NP-complete.

You could have found this trivially by Googling for "subgraph isomorphism problem".


Not sure why I can't just comment.  All I want to do is share a link:

http://people.csail.mit.edu/bdean/6.046/dp/

Or better yet:  Deciding on Sub-Problems for Dynamic Programming

This is a duplicate.


Maximizing integer sets intersection (with integer delta)

You can compute the sumset (well, difference set) $X-Y$ using standard techniques (Computing Cardinality of Sumsets using Convolutions and FFT).

As an optimization, I suggest first replacing $X,Y$ with $X'=X \bmod p$, $Y'=Y \bmod p$ where $p$ is at least $n+m$ or so.  Then, enumerating through the elements of the multiset $X'-Y'$ by decreasing cardinality will give you good candidates for $\delta \bmod p$.  The running time to compute $X'-Y'$ will be $O((n+m)\log (n+m))$, and if the maximum value of $F(\delta)$ is sufficiently large, I expect you should be able to find the correct value for $\delta$ among the first few candidates.


How do I count the exact number of executed commands for a MIPS program?

There are two ways: You use a simulator and count the actual number of instructions (or do it manually), which of course only works for fixed input like your case here. Or you use mathematics to calculate the number of instructions, just as you did.

In general, mathematical analysis ranges from easy to hard to impossible for humans, so there is no general method.

Sometimes you’re lucky to get a result like “about 2.25 n^2”, or “$\Theta (n^2)$ or similar. How do you deal with it? You do your best.


Is there an official way to choose half of the clauses that satisfy the formula?

There is no official way. As noted by Juho, "any algorithm that you prove correct is acceptable". Moreover, you do not have to choose that half of the clauses explicitly.

Here is the simplest algorithm to decide $\text{HALF-2-SAT}$ that runs in polynomial time. In fact, it runs in constant time. (If the algorithm should verify the given input is valid, it runs in linear time.)

Input: $\varphi$ and $m$, where $\varphi$ is a 2-CNF formula with $m$ clauses.
Output: True if there is an assignment of the variables such that at least $m/2$ clauses become 1.
Procedure: Return true.

Why does the above algorithm work? Here is the reason.

Lemma. Let $\varphi$ be a 2-CNF formula. Then there exists an assignment that satisfies at least half of the clauses in $\varphi$.

Proof. Let $f_0$ assign 0 to all variables. Let $f_1$ assign 1 to all variables. Let $c$ be any one of the clauses in $\varphi$. Suppose variable $x$ appears in $c$.

the literal $x$ is in $c$. Then $c$ becomes 1 under $f_1$.
the literal $\neg{x}$ is in $c$. Then $c$ becomes 1 under $f_0$.

So every clause becomes 1 under $f_1$ or $f_0$.  So the number of clauses is not greater than the sum of the number of clauses that becomes 1 under $f_1$ and the number of clauses that becomes 1 under $f_0$. Hence, at least half of the clauses in $\varphi$ are satisfied under $f_1$ or $f_0$. QED.

Here are several exercises.

Exercises 1. Show the following language is in P:
$$\begin{align*}\text{3-SAT}_{\ge\frac12} = \{ \langle \varphi \rangle \mid \, &\text{$\varphi$ is a 3-CNF formula and there exists an assignment} \\
& \text{that satisfies at least half of the clauses} \}\end{align*}$$

Exercises 2. Show that the following problem is in P:
$$\begin{align*}\text{2-SAT}_{\le\frac34} = \{ \langle \varphi, f \rangle \mid \, &\text{$\varphi$ is a 2-CNF formula and $f$ is an assignment} \\
& \text{that satisfies at most three fourth of the clauses} \}\end{align*}$$

Exercises 3. Let $\varphi$ be a 2-CNF formula such that none of its clause involves only one variable. Then there exists an assignment that satisfies at least three fourth of the clauses in $\varphi$.


Gray-like code with maximum value <= maximum value of original symbol

Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two.  I'll describe how, below.

I will say that $a_0,\dots,a_{n-1}$ is a Gray code sequence for $0,1,\dots,n-1$ if each $a_i$ is in the range $0..n-1$, and if each $a_i$ differs from $a_{i-1}$ in a single bit position.  Note that this generalizes the usual notion of a Gray code, to the situation where the numbers are not a power of two.

Let $n = 2^t + u$, where $u \le 2^t$.  We'll use two steps:

First, recursively construct a Gray code sequence for the numbers $0..u-1$.  Suppose the sequence is $x_0,x_1,\dots,x_{u-1}$.  This means that each $x_i$ is in the range $0 \le x_i \le u-1$ (for each $i=0,1,\dots,u-1$), and each $x_i$ differs from $x_{i-1}$ in a single bit position (for $i=1,2,\dots,u-1$).  This in turn gives us a Gray code sequence for the numbers $2^t,2^t+1,2^t+2,\dots,2^t+u-1$ by just adding $2^t$ to each element in the sequence: specifically, $2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1}$.
Second, construct a Gray code sequence for the numbers $0..2^t-1$ that starts at the number $x_{u-1}$.  A cool fact about the standard Gray code construction (for a power of two) is that it is cyclic, i.e., you can start anywhere and get to all the numbers, from that starting point.  Let $y_0,y_1,\dots,y_{2^t-1}$ be this sequence.  As mentioned, we have $y_0 = x_{u-1}$.

Now if we just concatenate these two sequences, we get an ordering of $0..n-1$ where each number in the sequence differs from its previous number by a single bit.  In particular, the full sequence is

$$2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1},y_0,y_1,\dots,y_{2^t-1},$$

with the $x$'s and $y$'s defined as above.  This gives a simple and easy to implement construction for what you want.

Caution: Iterating through elements of the matrix in Gray code order will trash your cache.  Caches are optimized for sequential access.  You're doing random access (jumping around in the address space), so the caches will be useless and every memory access will be a miss in the cache.  As a result, performance might suffer.  Beware.


Keywords/terminology for using "extra" information in search problems?

Such search algorithms would generally be called informed search algorithms (or methods, techniques, etc.), or simply heuristic search algorithms. We might also call them guided search algorithms.

An example would be A* search, which uses precisely what you call "airplane distance" (more commonly referred to as the straight-line distance) as a heuristic.

Best-first search techniques would be somewhat closely-related, but they may have a slightly different meaning (they may, for example, use statistics / information gathered earlier during the same process for guidance during a later part of the search process, rather than heuristic domain knowledge given a priori).


Arbitrary depth nested for-loops without recursion

It is impossible to do this in $O(n \log m)$ space, by a counting argument. Fix $n = 2$ and consider the number of iterations for which the program must execute. There are $m$ nested loops, each with $2$ indices, so the inner statement executes exactly $2^m$ times and then the iteration terminates. But the configuration space of the program only has $2^{O(\log m)} = \operatorname{poly}(m)$ possible states. So as $m \rightarrow \infty$, by the pigeonhole principle some state must be visited twice during the iteration, which is impossible because it would result in an infinite loop.

On the other hand, you can easily do this in $O(\log(n^m)) = O(m \log n)$ space. (Note that this is reversed from what you wrote!) All you have to do is count in base $n$. That is, keep an array of integers of size $\log n$ and treat them as the base $n$ digits of a single number that you are incrementing. Or you can use an arbitrary precision integer data type and use division and modulo operators to extract the base $n$ digits. Either way, this is trivially equivalent to using a stack, but maybe it feels less "recursive" to you.


Is Newton's Method to compute the zeros of a function an algorithm?

It's pretty clearly an algorithm according to my definition in the linked question. I think your real question is "what is the problem, if any, for which this algorithm is correct?" The answer would be something like "given some stuff and a number of iterations, output a value satisfying some condition with an accuracy related to the iteration count."


Why is the object destructor paradigm in garbage collected languages pervasively absent?

The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories.  Let's not conflate destructors with finalizers - only one is related to garbage collection:

The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically.
Finalizers are called automatically before deallocation by a garbage collector.  The term applies if the garbage collection algorithm employed can determine object life cycles.

The destructor pattern: cleanup method declared automatically, defined by programmer, called automatically only sometimes.
Destructors can be called automatically for stack-allocated objects (because object lifetime is deterministic), but must be explicitly called on all possible execution paths for heap-allocated objects (because object lifetime is nondeterministic).

The disposer pattern: cleanup method declared, defined, and called by programmer.
Programmers make a disposal method and call it themselves - this is where your custom myObject.destroy() method falls.  If disposal is absolutely required, then disposers must be called on all possible execution paths.

Finalizers are the droids you're looking for.
The finalizer pattern (the pattern your question is asking about) is the mechanism for associating objects with system resources (sockets, file descriptors, etc.) for mutual reclamation by a garbage collector. But, finalizers are fundamentally at the mercy of the garbage collection algorithm in use.
Consider this assumption of yours:

Languages which offer automatic garbage collection ... know with 100% certainty when an object is no longer in use.

Technically false (thank you, @babou).  Garbage collection is fundamentally about memory, not objects.  If or when a collection algorithm realizes an object's memory is no longer in use depends on the algorithm and (possibly) how your objects refer to each other.  Let's talk about two types of runtime garbage collectors.  There are lots of ways to alter and augment these to basic techniques:

Tracing GC.  These trace memory, not objects.  Unless augmented to do so, they don't maintain back references to objects from memory.  Unless augmented, these GCs won't know when an object can be finalized, even if they know when its memory is unreachable.  Hence, finalizer calls aren't guaranteed.

Reference Counting GC. These use objects to track memory.  They model object reachability with a directed graph of references.  If there is a cycle in your object reference graph, then all objects in the cycle will never have their finalizer called (until program termination, obviously).  Again, finalizer calls are not guaranteed.

TLDR
Garbage collection is difficult and diverse.  A finalizer call cannot be guaranteed before program termination.


Polynomial time optimization problems belong to which complexity class?

Take a look at the FP complexity class.
Technically speaking, it is wrong. However, usually people don't make a huge difference between the two. Its usually clear from the context whether the problem is a decision or a search problem, hence its clear whether it should be in $P$ or $FP$.
So, writing that "Finding the shortest $(s,t)$ path in the graph $G$, is a $P$ problem" would actually mean: "Finding the shortest $(s,t)$ path in the graph $G$, is an $FP$ problem" (since the context is clear)