Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs

For item (b), the reduction does not work. To understand why, imagine a graph with all edges having the same weight. Then, the reduction has no effect: $G = G'$. Finding the shortest path from $u$ to $v$ consists in finding the path with fewer intermediate nodes, while finding the longest path, consists in finding the path with the highest number of intermediate nodes. The problems are not polynomially equivalent because the shortest path is in $P$ while longest path is in $NP$ (see here).
For item (c), the optimization problem for MAX CUT is NP-hard while for MIN CUT is polynomial. However, when you consider the version of these problems that allows both positive and negative weights they can be trivially converted to each other by flipping the sign in all weights.


What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

Where are you using that T(n) = c for n <= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N <= 10 is the base case.
Clearly T(n) = c for n <= 10, T(n) = c+3 if 10 < n <= 100, T(n) = c+6 if 100 < n <= 10,000, T(n) = c+9 if 10,000 < n <= 100,000,000 etc.
Let f(n) = log_10 (max (n, 10)) so for the four cases above we have f(n) = 1, 1 < f(n) <= 2, 2 < f(n) <= 4, 4 < f(n) <= 8 etc.
Let g(n) = ceil(log_2(f(n))), then g(n) = 0, 1, 2, 3 etc, and T(n) = c + 3 g(n).


For its complexity, note $N$ the sum of all your integers. Then, the number partitioning problem injects itself into your problem with $K=\frac{N}{2}$

I found this paper which deals with almost your problem. It aims to maximise the number of bins used, but instead of working with each partition must have a sum of at least $K$, you have each partition cannot be completed with another item.

Edit: Another user already asked almost the same question: https://scicomp.stackexchange.com/questions/8216/bin-packing-maximise-number-of-bins-fukubukuro-problem


What is partial expansion in Monte Carlo Tree Search?

Partial expansion is a pruning/reduction strategy. Instead of requiring all children to be explored in selection you could set a threshold like done in "Move Count Pruning" (MCP) based on only expanding the first 10 children only. Usually you call ucb_sample if all children are explored depending on your weights.

Another example could be based on the rollout. Even rollouts need full expansion and odd rollouts need only MCP. This way the tree gets explored in a different way.

Benefits usually come in reducing time and favouring early moves. Early moves get more time and those nodes get better statistics. With backpropogation grandchildren help update their parents because statistics exist.


Variation to spanning tree called Group Spanning Tree

A spanning tree connects all nodes, so in particular it connects nodes of each color.

Are you sure that is the problem you are facing?


The symbolic differentiation of univariate expressions

You might be looking for automatic differentiation, which is an entire field of research; many techniques are known.


Prove complexity bound without reduction?

As mentioned on Wikipedia, there is no known proof that breaking RSA is at least as difficult as prime factorization -- and there are reasons to believe it might not be.  In other words, we don't currently expect any such proof to exist.  See the reference listed in Wikipedia.


What is the most efficient algorithm to get percentile distribution from histogram distribution?

First, compute the cumulative distribution.  Suppose the input array is $A[0..n-1]$.  You can compute the cumulative distribution as follows:

Set $C[-1] := 0$.
For $i:=0,1,2,\dots,n-1$, do: set $C[i] := C[i-1] + A[i]$.

After this, $C[i]$ contains a count of the number of values in the underlying data set that are $\le i$.

Now you can compute percentiles directly from the cumulative distribution.  In particular, item $i$ is in the $\lfloor 100 C[i] / C[n-1] \rfloor$ percentile.  So, the output array can be computed as

Set $P[j] := 0$ for $j=:0,1,2,\dots,100$.
For $i:=0,1,\dots,n-1$, do:

Set $j := \lfloor 100 C[i] / C[n-1] \rfloor$, and set $P[j] := P[j] + A[i]$.

Now $P[j]$ contains the number of values from the underlying data set that fall into the $j$th percentile.  That was what you wanted to compute.

The running time is $O(n)$, where $n$ is the length of the input array.  It seems unlikely you can build anything that's any faster than that, as the problem seems to require reading the entire input.


Your problem sounds similar to one-shot (black) pebbling. Wu, Austrin, Pitassi, and Liu, in their paper titled Inapproximability of treewidth, one-shot pebbling, and related layout problems (J. Artificial Intelligence Res. 49 (2014), 569–600), show that it is (probably) hard to compute the optimal cost (which corresponds to your memory).


What is the time complexity of FC_MRV algorithm?

The worst case complexity of FC-MRV is $O(n^2 d^2)$ where $n$ is the number of variables and $d$ is the number of domain size.


Why is ARP needed in a host - router system if the router already has list of addresses it assigned using dhcp?

The fact that the router has the list does not help when computer A wants to talk to computer B, because neither of the two has the list.


How to model this constraint using integer linear programming?

Assuming $x_j$ are binary.

The additional binary variable $y_i$ equals one if and only if when all $j$ are 1.

$$
\sum\limits_{j=i}^{i+p-1}x_j - p+1 \leq y_i \leq \frac{1}{p}\sum\limits_{j=i}^{i+p-1}x_j
$$

Then to have a unique $y_i$ equals one you add
$$
x \leq \sum_{i=1}^n y_i \leq (n-1)(1-x)+1
$$


There is a formula for the PageRank which involves inverting an $n\times n$ matrix. When $n = 3$ this is not too hard. For inverting the matrix, use the formula given on Wikipedia, which is just a special case of the general formula involving the adjugate matrix.

That said, I see absolutely no reason why you would ever have to calculate PageRank by hand. That's what we have computers for. If you are given such an exercise in an exam, the matrix will probably have some very simple structure which will make it easier to handle by hand.


Efficient algorithm to compute the $n$th Fibonacci number

You can use matrix powering and the identity
$$
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}.
$$
In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.


what is the Recent Nature Inspired Algorithm for Optimization?

This paper[[1]] recommends the following Swarm Intelligence algorithms:

  Ant colony optimization
  Bat algorithm
  Cuckoo search
  Firefly algorithm
  Particle swarm optimization

[1]: "A Brief Review of Nature-Inspired Algorithms for Optimization"


Spanning tree in a graph of intersecting sets

Interesting question.
The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. I cannot prove that guideline is correct, however.
Instead, I will present one series of such examples. More specifically, from some $n$ (that can be arbitrary large), there are $n$ sets, each having $(n-1)/2$ elements drawn from a set of $n$ elements, such that the cardinality of the symmetric difference between any two sets is no less than $(n-1)/2$. So the weight of the minimum spanning tree is no less than $(n-1)^2/2=\mathcal\Theta(n^2)$.

Here is the construction, using quadratic residue.
Example. Let $n=p$ be an odd prime. Let $X_0$ be the set of all non-zero quadratic residues of $p$ between 0 and $p-1$ inclusive. In other words, $$X_0=\{0\le k\lt p: \left(\frac {k}p\right)=1\}$$ where $\left(\frac{\cdot}p\right)$ is the Legendre symbol. For $0\le i\lt p$, let $X_i$ be "$X_0$ plus $i$", i.e., $$X_i=\{0\le k\lt p: \left(\frac {k-i}p\right)=1\}.$$ Then $|X_i|=\frac{p-1}2$ for all $i$ and $|X_i \triangle X_j|\ge \frac{p-1}2$ for all $i\not=j$.
Proof: Since $\left(\frac{\cdot}p\right)$ is either $-1$, $0$, or $1$, we have $1+\left(\frac{\cdot}p\right)\ge0$. Hence,
$$\begin{aligned}
&\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&\ge\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&=\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}4\\
&=4\,|X_i\cap X_j|
\end{aligned}$$
On the other hand, we have
$$\begin{aligned}
&\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\
&=\sum_{0\le k\lt p}\left(1 + \left(\frac {k-i}p\right) + \left(\frac {k-j}p\right)+ \left(\frac {k-i}p\right)\left(\frac {k-j}p\right)\right)\\
&=p + 0 + 0 + \sum_{0\le k\lt p} \frac {k^2-(i+j)k+ij}p\\
&=p-1
\end{aligned}$$
Since $p\nmid(-(i+j))^2-4ij=(i-j)^2$, the last equality above comes from the case of $p\nmid b^2-4ac$, theorem 1 in the paper On Certain Sums with Quadratic Expressions Involving the Legendre Symbol. So we have $|X_i\cap X_j|\le \frac{p-1}4.$
Since $|X_i|=|X_j|=\frac{p-1}2$, $\ |X_i \triangle X_j|=|X_i|+|X_j|-2|X_i\cap X_j|\ge \frac{p-1}2.$ $\quad\checkmark$

For people who appreciate concrete examples, here are the sets when $n=17$, where $|X_i \triangle X_j|\ge 8$.
$$\begin{aligned}
X_{0}&=\{\phantom{1}1, \phantom{1}2, \phantom{1}4, \phantom{1}8, \phantom{1}9, 13, 15, 16 \}\\
X_{1}&=\{\phantom{1}2, \phantom{1}3, \phantom{1}5, \phantom{1}9, 10, 14, 16, \phantom{1}0 \}\\
X_{2}&=\{\phantom{1}3, \phantom{1}4, \phantom{1}6, 10, 11, 15, \phantom{1}0, \phantom{1}1 \}\\
X_{3}&=\{\phantom{1}4, \phantom{1}5, \phantom{1}7, 11, 12, 16, \phantom{1}1, \phantom{1}2 \}\\
X_{4}&=\{\phantom{1}5, \phantom{1}6, \phantom{1}8, 12, 13, \phantom{1}0, \phantom{1}2, \phantom{1}3 \}\\
X_{5}&=\{\phantom{1}6, \phantom{1}7, \phantom{1}9, 13, 14, \phantom{1}1, \phantom{1}3, \phantom{1}4 \}\\
X_{6}&=\{\phantom{1}7, \phantom{1}8, 10, 14, 15, \phantom{1}2, \phantom{1}4, \phantom{1}5 \}\\
X_{7}&=\{\phantom{1}8, \phantom{1}9, 11, 15, 16, \phantom{1}3, \phantom{1}5, \phantom{1}6 \}\\
X_{8}&=\{\phantom{1}9, 10, 12, 16, \phantom{1}0, \phantom{1}4, \phantom{1}6, \phantom{1}7 \}\\
X_{9}&=\{10, 11, 13, \phantom{1}0, \phantom{1}1, \phantom{1}5, \phantom{1}7, \phantom{1}8 \}\\
X_{10}&=\{11, 12, 14, \phantom{1}1, \phantom{1}2, \phantom{1}6, \phantom{1}8, \phantom{1}9 \}\\
X_{11}&=\{12, 13, 15, \phantom{1}2, \phantom{1}3, \phantom{1}7, \phantom{1}9, 10 \}\\
X_{12}&=\{13, 14, 16, \phantom{1}3, \phantom{1}4, \phantom{1}8, 10, 11 \}\\
X_{13}&=\{14, 15, \phantom{1}0, \phantom{1}4, \phantom{1}5, \phantom{1}9, 11, 12 \}\\
X_{14}&=\{15, 16, \phantom{1}1, \phantom{1}5, \phantom{1}6, 10, 12, 13 \}\\
X_{15}&=\{16, \phantom{1}0, \phantom{1}2, \phantom{1}6, \phantom{1}7, 11, 13, 14 \}\\
X_{16}&=\{\phantom{1}0, \phantom{1}1, \phantom{1}3, \phantom{1}7, \phantom{1}8, 12, 14, 15 \}\\
\end{aligned}$$


Input: 0^a 1^b 0^c with a + c >= b + 1

Output: 0^z 1^b 0 1^b with b + z + 1 = a + c

Strategy:

Move 1^b to the back of the tape
Copy 1^b immediately to the left
Clean up

States:

q0: scan left until you see 1; if beginning of tape, continue with state q3. Otherwise, change 1 to 0 and continue to q1
q1: scan right until blank or 1; then, move left and continue with state q2
q2: change 0 to 1, go left, and continue with q0
q3: scan right until you find 1; if you do, change 1 to 2, move left and continue with step q4; otherwise continue with state q6
q4: scan left until you find 0; then, move right and continue with state q5
q5: scan left until you find 0; when you do, change it to 2, move right, and continue with state q3
q6: scan left until you find a blank, changing all 2s to 1s along the way. then, halt-accept.

If you count halt-accept as its own state, this has 8 states, so it's at least one better than the one you gave (if this one works). Here's how I'd see it processing your example:

   0000001110: q0
-> 0000001101: q0, q1, q2, q0
-> 0000001011: q0, q1, q2, q0
-> 0000000111: q0, q1, q2, q0
-> 0000020211: q0, q3, q4, q5, q3
-> 0000220221: q3, q4, q5, q3
-> 0002220222: q3, q4, q5, q3
-> 0001110111: q3, q6, halt-accept


Enumerating programs as graphs, or executing graphs?

We can summarize your original findings as follows: there is an effective enumeration for programs and graphs. An effective enumeration of a countable set $S$ is a computable bijection between the natural numbers and $S$, that is, a program $P(n)$ such that $S = \{ P(n) : n \geq 0 \}$ and $P(n) \neq P(m)$ for $n \neq m$.

There are many countable sets which can be effectively enumerated – there is nothing special about programs and graphs. We can generalize and say that if $S_1,S_2$ can be effectively enumerated, then there is a computable bijection between $S_1$ and $S_2$ (why?), but this doesn't say much about any relation between $S_1$ and $S_2$.


Can I assume that a percentage of the time can be parallelized?

You can never assume anything.

There are plenty of cases where your work, or a percentage of your work, can be split up into k independent tasks. If you have k processors, then each one can handle one task. If you have k+1 processors, then one will be unused. So it's not just a matter of "percentage of work that can be parallelised", it's also a a matter of "how many parallel tasks can be performed".

There are plenty of cases where work can be parallelised, but work needs to be done to prepare for this. Let's say it takes time t to prepare for one parallel execution, independent of the amount of work. So with two processors, that preparation takes 2t. With 100 processors, it takes 100t. If the amount of work is fixed, there will be a point where more processors add more preparation time than the savings you get.

There are plenty of cases where there is a simple sequential solution, and a more complex and slower parallel solution. The total time using one processor and the sequential solution may be x. To use k processors may save y of the sequential time, but add f (k) sequential time for preparation, and use g (k, y) in total parallel time where g (k, y) >> y.


Does a never-halting machine always loop?

Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step.  This means that the TM never halts, since it always moves to the right, and never repeats a state, since after k steps the tape head is over the kth cell of the machine.  Consequently, each configuration of the machine is different from all others, and the machine always loops.

We could also nonconstructively show the existence of such machines.  Assume for contradiction that every TM that never halts eventually loops.  This means that if you start a TM $M$ on a string $w$, one of the following will eventually happen:

$M$ halts, or
$M$ repeats a configuration.

In this case, the halting problem would be decidable as follows.  Given a TM $M$ and string $w$, simulate $M$ on $w$, at each point writing out the contents of the tape, current state, and current tape position.  If this configuration is a duplicate, output "does not halt."  Otherwise, if $M$ halts on $w$, output "halts."  Since one of these is guaranteed to happen eventually, this process always terminates, so we would have an algorithm for the halting problem, which we know does not exist.

Hope this helps!


Find the closest string to a fixed set of strings

This is a nearest-neighbor problem, and there are a variety of algorithms for the problem.  The simplest is a k-d tree, and there are more sophisticated data structures as well.  Another approach is to use locality-sensitive hashing.

However, the effectiveness of these methods depends heavily on the dimension (i.e., on the length of the strings).  Practical experience is that for dimension $\le 10$, these are better than the naive linear-time search, but for very high dimension, usually they perform no better than the naive algorithm.  This occurs due to the curse of dimensionality.  In your context, that means that if the strings are short and $n$ is large, these data structures will probably be effective, but if the strings are long, I would not expect too much hope.

In the special case where strings are long and you expect the nearest neighbor to have very low Hamming distance, whereas the distance to most other strings will be very large, then there are techniques you can use.  For instance, you might look into shingling the strings into $n$-grams, storing the $n$-grams in a hashtable, and doing a lookup on each $n$-gram from the query string.  You can view this as a form of locality-sensitive hashing for the Hamming distance.  Another approach is to use bit sampling as a locality-sensitive hash; this should be easy to implement.

I also recommend taking a look at our questions in the nearest-neighbor topic, especially Why Is KD-Tree-based Nearest Neighbor Exponential in K?, Best data structure for high dimensional nearest neighbor search, Why is exact nearest neighbor search hard in high dimensional spaces?,
What is the state of the art for k nearest neighbour search?.

We also have questions here about the harder problem of finding the nearest string, where nearest is measured by Levenshtein edit distance (e.g., Find all pairs of strings in a set with Levenshtein distance < d, How to speed up process of finding duplicates/similar items in a large amount of strings?, How fast can we identifiy almost-duplicates in a list of strings?, Matching strings in one set to strings in another based on Levenshtein distance).


Closure Properties between different Language Classes

Yours is a correct intuition: $L_1 \cap L_2$ is indeed recognisable.

However, you can't say that such language is not decidable only because you failed to prove it decidable. In theory, there could be a more complex argument that you were not able to find, which could establish that $L_1 \cap L_2$ is actually decidable.

To prove it, you need a counterexample. It is usually helpful to try corner cases, first.

For instance if $L_1 = \Sigma^*$, which is regular, we get $L_1 \cap L_2 = L_2$ which is decidable only if $L_2$ is such. Hence, since recognizable but non decidable languages exist, we get a counterexample.

Further, note that if we took $L_1 = \emptyset$, which is regular, then $L_1 \cap L_2 = \emptyset$ which is decidable, whatever $L_2$ is.

Hence, from the given hypotheses, we can not conclude that $L_1 \cap L_2$ is decidable, nor that it is not. This is because we found counterexamples to both conjectures.


Example of a code that can be decoded using bounded distance decoder

The simplest example is a repetition code. You encode the bit 0 as 000 and the bit 1 as 111. The decoder outputs the majority bit, which is always at distance at most $t = 1$.

As another example, suppose we encode 0 as 0000 and 1 as 1111. We can still correct up to one error (by taking the majority), but we cannot accommodate $t = 2$, since given 0011 we can't tell whether it came from 0000 or from 1111. Therefore we need to declare failure.


Proving the correctness of a square summing algorithm

Assuming $n ≥ 0$,
let $$ P(n) \;≡\; ∀ a.\, sumHelper(n, a) = a + ∑_{i = 0}^n i² $$

Then we prove this is always true by induction on $n$.

The base case, n = 0:

  sumHelper(n, a)
={ Case n = 0 }
  sumHelper(0, a
={ Definition }
  a
={ Arithmetic }
  a + 0²
={ Arithmetic }
  a + ∑_{i = 0}^0 i²
={ Case n = 0 }
  a + ∑_{i = 0}^n i²

The induction step, assuming P(n) let us show P(n+1),

 sumHelper(n+1, a)
={ Definition }
  if   (n+1==0) a
  else sumHelper(n+1-1, a + (n+1)*(n+1))
={ Since we assumed n ≥ 0, we have n+1 ≠ 0.
   Hence we have the else-branch. }
  sumHelper(n+1-1, a + (n+1)*(n+1))
={ Arithmetic }
  sumHelper(n, a + (n+1)*(n+1))
={ Apply the inductive hypotheis with a ≔ a + (n+1)*(n+1) }
  (a + (n+1)*(n+1))) + ∑_{i = 0}^n i²
={ Arithmetic: Bringing the `n+1` term back into the sum }
  a + ∑_{i = 0}^{n+1} i²

We're done :-)


The pumping lemma says that you can split the word into $xyz$. It doesn't say that every such split works. For instance, if you take $|x|=1$ in your example, the pumping works up and down. This would be a "correct split" that makes the pumping lemma hold.

As a reference, recall the definition of the pumping language for regular languages (from Wikipedia):

  Let $L$ be a regular language. Then there exists an integer $p\ge  1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

  $|y| \ge 1$
  $|xy| \le p$ and
  for all $i \ge 0$, $xy^iz \in L$.
  $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).


Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

An obvious counter example is $g(n) = \sqrt{n}$. If $f(n) = \Theta(\sqrt{\log n})$, you can't conclude that $f(n) = \Theta(\log{\sqrt{n}}) = \Theta(\log{n})$.


Prove that $S_2$ is closed under union and complement

As you mention in your post, you can define a new verifier $V=V_A \vee V_B$ however, you missed the point that the input of $V$ need not be the input of $V_A$ or $V_B$: it can be the concatenation of their inputs

So the new $V$ can be written as
$$ V(x, y_A\circ y_B, z_A \circ z_B )$$
where it "runs" $V_A(x,y_A,z_A)$ and $V_A(x,y_B,z_B)$ and decides accordingly.

It then immediately follows that $q = p_a +p_b +1$  (the +1 is just to separate the prefix from the suffix, you can ignore it).


Proving NP hardness about graph creation problem with triangle number

This is just a begining of reflexion. I hope it will help. This is not a solution for the very general case but some points that can reduce the problem.

If you consider triangles as unique 3-cliques, you know how many triangles are provided by a k-clique:

3-clique : 1 triangle
4-clique : 4 triangles
5-clique : 10 triangles
k-clique : C(k, 3) triangles

Thus the number of triangles you have to provide is a combination of these numbers: N = 1*a + 4*b + 10*c ...

You also know that building a clique requires nodes with sufficient neighboors. A k-clique requires k nodes having k-1 edges. And any node with only one edge cannot create any triangle.

On a short example :
10 nodes with (5, 5, 4, 4, 3, 3, 2, 2, 1, 1) edges. A 5-clique is not possible. I think this can do up to 12 triangles with 3 different 4 cliques (5, 5, 4a, 4b), (5, 5, 4a, 3a), (5, 5, 4b, 3b). The remaining (2, 2, 1, 1) cannot provide any triangle.


Are there any programming languages which support user defined control structures?

There are two aspects to your question:

Can we arrange a convenient syntax to express one control structure in terms of another?
Can we actually define new control flow mechanisms.

For example, suppose we have a language which only has the if statements without else:

if A then B

Can we express if A then B else C somehow? Yes, like this:

a = A ;
if a then B ;
if not a then C

It would be even better if we could package up the above piece of code into convenient syntax so that we could write just if A then B else C.

Sometimes we can define new control structures using existing ones. For instance, a while loop

while A do B

can be replaced with a call to a recursive function (under some technical assumptions):

function whileLoop():
   if A then (B ; whileLoop ())

whileLoop();

This sort of transformation is a bit more involved because it requires that for each while loop we define a new recursive function. If we were to automate the process, we would have to worry about many details (how to invent unique names of generated functions, do the functions have access to the local variables, etc.) than when we're performing just a straightforward syntactic translation of one variant of loop to another.

On the other hand, there are control mechanism which simply are not expressible in a language, unless already supported. One such example would be continuations. You can't get these in C, for example, but they exist in Scheme.

Your question is about syntax: can we make a syntactic transformation that replaces one piece of syntax with another piece of syntax. Languages usually deal with this sort of thing through a macro mechanism or syntax extensions. Here are some examples:

C has macros which will get you some of the way
Scheme has a more elaborate macro system which gets you a lot further
Racket, a descendant of Scheme, has an elaborate multi-stage computation system which allows essentially arbitrary syntax extensions
OCaml has the camplp5 syntax extension tool which allows pretty much arbitrary syntax extensions
Template Haskell is an extension of Haskell which allows meta-level transformations of syntax.

I am sure there are many other languages with similar facilities that I am not familiar with.


Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

May be it helps you to see more easily the way to attack the problem.
The first that you could try  it's find or understand the recursive relation behind Floyd-Warshall Algorithm. As the next function $f$.

$$
f(u,v,k) = \begin{cases}
w_{u,v} & k = 0\\
\min\, (\ f(u,v, k-1),\ f(u,k,k-1) + f(k,v,k-1)) & \text{otherwise}
\end{cases}
$$

$w_{u,v}$ it's the weight of edge from $u$ to $v$ in the direct graph $G$. $\infty$ if that edge doesn't exist.
$f(u,v,k)$ is the weight of a shortest path from $u$ to $v$ if you consider the first $k$ vertices as intermediates.

To adapt the above function form for your problem, I'd sketched the essence of the  problem in the next graph:

$m_i\in E_0$
$l_i\in E_1$
The curly curve is the shortest path considering the first $k-1$ vertices.
You have a alternate path that consider the $k$ node when you see the pattern (normal-$k$-dashed) lines in the path, or with convention above: (dashed-$k$-normal) line or $(m_i, l_j)^*$ , $(l_i, m_j)^*$ pattern in general.

So the next step it's construct the recursive relation looking the connection between subproblems, and for that you could think for a moment that your function solve the problem for a small size of problem, or instances pattern (follow principle of optimality).

$$
f(u,v,k,i) = \begin{cases}
w_{u,v,i} & k = 0\\
\min\, (\ f(u,v, k-1,i),\ f(u,k,k-1,~i) + f(k,v,k-1,i)) & \text{otherwise}
\end{cases}
$$

$w_{u,v,i}$ is the weight for the edge in $E_i$  (Note that I change enumeration of $E$ for convenience). $\infty$ if that edge doesn't exist.
$f(u,v,k,i)$ is the weight of a shortest path that ended up with a edge in $E_i$ that consider  the first $k$ vertices as intermediates like the graph above.
$~i = 0$ if $i = 1$ or $1$ if $i = 0$.

So, the weight of the shortest alternate path from $u$ to $v$ is
$$\min \,(\, f(u, v, |V|, 0),\ f(u, v, |V|, 1) )$$
where $|V|$ is the number of vertices.

Of course, after some work, you could notice that:

It's possible delete parameter $k$
you could implement iterative version or use a memorization technique.
Other details, that I'm forgiving. It's late.

I'd wrote a python code/ and input test file if you can play with that. But, Here, it's not important.


Average case complexity of bubble sort vs insertion sort

There is a big difference between the first answer you quote, on this site, and the second answer you quote, on stackoverflow: while the answer on cs.se contains an argument, the answer on stackoverflow just states the result without any explanation. This means that you can verify the answer on cs.se: you can check whether the proof is correct, and whether the result answers your question. In contrast, there is no way to know whether the answer on stackoverflow is correct or not, apart from trusting its poster.

This highlights a general difference between programmers and computer scientists. Programmers just want to know the answer, and generally don't care whether it's correct or not. Computer scientists, in contrast, want to see some evidence: a proof if one is available, or results of experiments (or both, in some communities).

Two more proofs of the formula $\frac{n(n-1)}{4}$ can be found on math.se and on cs.se. See if any of these convince you of this formula. You have to check both the statement (whether you are counting the correct expectation) and the proof.

Another thing you can do is experimentally determine the veracity of these proofs. This would entail programming both algorithms, and running them on many different arrays of length $n$ for various values of $n$, thus estimating the number of swaps.

A user on stackoverflow did a simpler experiment which suggests that the number of swaps is the same in bubble sort and inversion sort (at least for the user's version of these algorithms, quoted in the question). This would imply, of course, that the average number of swaps is the same in both algorithms.


graph theory conventions, difference between a PATH and a GRAPH?

Your algorithm returns a cycle rather than a path.

Here is a cycle:

Here is a path:

(Both images taken from Wikipedia.)

To get a path from the cycle, simply remove one edge (this is my best guess for what return a path of that cycle means).

Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.


Given an array arr[] of N integers. Do the following operation n-1 times

It seems some kind of problem with mathematical solution (try to find the position with a closed math formula). However, here is an algorithmic approach that runs in $O(n \log^2 n)$.

Using segment tree / Fenwick tree, you can find the number of removed elements in a range (using prefix sums). Keep track of the offset (imagine having a pointer on the first element (imagine a cyclic arry and in each step we push it one element to the left instead of rotating right). Using binary search on the Fenwick tree, you can find the index of element having the distance you are looking for the offset element. Nite that after deleting half of the elements $k$ will be greater than the size and hence you can directly output the first unremoved element before the offset.


Is the length of the shortest quine in a programming language computable?

You need to formally define the computational problem. It appears that the input is "a programming language" and the output is the length of the shortest quine in that language. But how is the programming language specified? The only way I can think of is to specify it by giving the encoding of a Turing machine that interprets the language. So, then, our input is $\langle M\rangle$ and our output is $\min\,\{|x|\mid M(x)=x\}$. This is uncomputable: it's uncomputable even whether $M(0)=0$


I'm lookin for a method to construct a particular grammar?

it is not clear what you mean by "words which have multiple identical symbols". it sounds like you mean certain symbols are interchangeable. in that case, just replace all cases of an interchangeable symbol with a single representative symbol.

as to the more general question, there is an area of CS not-so-widely studied, called grammar based codes which is, roughly, focused on the idea of creating compressions of strings based on grammar expansions. in this way classic compression algorithms such as eg Lempel Ziv can be regarded as special cases of grammar compressions.

your problem is not so well defined unless you specify the type of grammar also, eg say CFG. if the grammar is generated by a recursive machine, then this problem is actually similar or almost identical to finding the Kolmogorov complexity of a string, which is undecidable in general.


For A* to get the optimal path it requires that $f(n) \leq g(goal)$. In other words that the heuristic underestimates the cost from the node to the goal.

Multiplying a valid hueristic with $0 \lt\alpha\lt 1$ will not violate this requirement.

Multiplying $g(n)$ is not allowed because you can end up with $f(goal) = \alpha g(goal) < f(n)$ which would violate the requirement for getting the optimal path.


Confusion about the definition of the average-case running time of algorithms

The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as
$$
\newcommand{\Tavg}{T_{\mathit{avg}}}
\newcommand{\EE}{\mathbb{E}}
\Tavg(n) = \sideset{\EE}{}{}_{X \sim \mu_n} [T(X)].
$$
Usually $\mu_n$ is supported on inputs of "length" $n$, though length is not necessarily measured in bits or in machine words.

When analyzing comparison-based sorting algorithms, usually $\mu_n$ is chosen as the uniform distribution over all permutations of the array $1,2,\ldots,n$ (or any other array consisting of $n$ distinct comparable elements). The analysis of quicksort uses these distributions.

Now regarding the recursive formula you mention. Given an input array $X$, let $I$ be the rank of the pivot; if $X$ is a random variable, then so is $I$. The formula in Wikipedia is
$$
\Tavg(n) = \sum_{i=0}^{n-1} \Pr[I=i] \EE[T(X)|I=i] = \sum_{i=0}^{n-1} \frac{1}{n} \left[n-1 + \Tavg(i) + \Tavg(n-1-i)\right].
$$
Rearranging gives you the quoted formula.


How to determine if a regular language L* exists

$L^*$ always exists. ${}^*$ is an operation on languages, just like ${}^2$ is an operation on numbers – whenever you have a number $x$, there is a number $x^2$ and, similarly, whenever you have a language $L$, there is a language $L^*$.  Specifically, $L^*$ is the language of all strings that can be made by concatenating zero or more strings from $L$.  That's well-defined for any language $L$.

What you've observed is that $L^*$ might have different properties from $L$.  If we take your example of $L = \{y,yx,xy\}$, we see that no string in $L$ has $xx$ as a substring ($L$ is not the only language with this property but that's beside the point).  On the other hand, $L^*$ includes the string $yxxy$, which does have $xx$ as a substring. That doesn't mean that $L^*$ doesn't exist; it just means that it doesn't have some property that $L$ has. Well, that's no surprise because $L$ and $L^*$ are often different languages, in which case they can't have exactly the same properties.


For every choice of $\alpha > 0$, Moshkovitz shows that approximating set cover on instances with $n^{C_\alpha}$, where $C_\alpha$ is some constant depending only on $\alpha$, better than $(1-\alpha) \log n$ is NP-hard. Since $\log m \leq C_\alpha \log n$, it is NP-hard to approximate set cover better than $\frac{1-\alpha}{C_\alpha} \log m$. I'm not sure what is $\sup_{\alpha\to 1} \frac{1-\alpha}{C_\alpha}$, but it can probably be gleaned from the paper. At any rate, all three results you mention are correct, and the first can be strengthened by replacing $c$ with $1-\alpha$ for any $\alpha > 0$.


No, the Bombe was not doing brute-force search over all possible internal settings of the Enigma machine.  Read the Wikipedia article on the Bombe, which has a detailed explanation of the techniques used by the Bombe: https://en.wikipedia.org/wiki/Bombe.


The answer is yes. Suppose $A=(Q,q_0,F,\delta)$ is a deterministic finite automaton (with set of states $Q$, initial state $q_0$, set of final states $F$, and transition function $\delta$) recognizing the original language $L$. Then you can construct a nondeterministic automaton for $L'$ as follows:

For each state $q$ of $A$ create a separate copy of $A$, add $\epsilon$-transitions from its accepting states to the initial state, and then make $q$ the initial and (unique) accepting state. This gives you an NFA $A_q=(Q,q,\{q\},T)$, with transition relation $T=\{r,a,\delta(r,a)|r\in Q,a\in\Sigma\}\cup\{(r,\epsilon,q_0)|r\in F\}$. This NFA accepts a word $w$ if and only if there is a decomposition $w=uv$ such that $\delta(q,u)\in F$ and $\delta(q_0,v)=q$, which implies $vu\in L$.

Let $A'$ be the union of all the $A_q$. Then for any $uv\in L$, $vu$ is accepted by $A_q$ for $q=\delta(q_0,u)$, and therefore by $A$.


How to convert a centralized algorithm to a distributed algorithm?

Sure.  If you have a distributed system with N machines, you can always run the centralized algorithm on machine 1 and let machines 2..N sit idle.

If you're asking whether all sequential algorithms can be parallelized, that's an open question, but it's believed that the answer is no: see the NC complexity class.  As Wikipedia states,

  there are probably some tractable problems that are "inherently sequential" and cannot significantly be sped up by using parallelism.

P-complete problems are good candidates for problems that are likely not amenable to speedup by parallelism.

If you're asking whether all algorithms can be made reliable in a distributed system, that is a subtle question that depends on what kinds of failures you are considering.  You might look into consensus protocols, state machine replication, and the CAP theorem.


EVEN-CFL Decidable / Undecidable - Rice-Theorem

The property of being EVEN-CFL of c.e. languages is not trivial, by Rice's theorem this is not decidable.


The first step is to show that
$$
L \cap (aac)^*aabb^* = \{ (aac)^n aab b^n : n \geq 0 \}.
$$
Given that, you argue as follows: If $L$ were regular, then $L \cap (aac)^*aabb^*$ would also be regular. You can show in various ways that $\{ (aac)^n aab b^n : n \geq 0 \}$ isn't regular. It follows that $L$ isn't regular.


Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?

It looks like the comparison in the question is wrong.

$$\begin{aligned}
\lim_{n -> \infty} \frac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } &= \lim_{n -> \infty} \frac{n^{\delta} }{2^{\sqrt{\log n}}}=\lim_{n -> \infty} \frac{2^{\delta\log n} }{2^{\sqrt{\log n}}}\\
&=\lim_{n -> \infty} 2^{\delta\log n-\sqrt{\log n}}=\lim_{m -> \infty}2^{\delta m-\sqrt{m}}\\
&=\lim_{m -> \infty}2^{\sqrt m(\delta\sqrt{m} -1)}\\
&=2^{+\infty}=+\infty.\\
\end{aligned}$$

Here $\log n$ is understood as $\log_2n$. Since $\log_a n=\log_a2\cdot\log_2n$, the limit above will still be infinity if the base of $\log$ is switched to any number greater than 1.

In fact, for any constant $c>0$, however smaller it is and any constant $\delta>0$, however small it is, we still have, by similar argument,

$$\lim_{n \to \infty}\frac{\frac{n^3}{2^{c\sqrt{\log n}}}}{\ \ \ {n^{3-\delta}\ \ \ }} =+\infty.$$

  I compare between $\lim_{n -> \infty} \frac{ \frac{n^3}{2^{\sqrt{\log n}}}}{\ \ \ n^{3-\delta}\ \ } = 0 $ So, $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ is better than the other one, so why it doesn't mean that we refute the conjecture.

To be more careful, there is another mistake in the above reasoning. Even if $\lim_{n -> \infty} \dfrac{\frac{n^3}{2^{\sqrt{\log n}}}}{\ \ n^{3-\delta}\ \ } = 0 $, it does not imply it will refute the conjecture. The point is, "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" might be true because it can be solved in time $\frac{n^3}{2^{0.01\sqrt{\log n\ \ }}}$, not because it can be solved in time $\frac{n^3}{2^{\sqrt{\log n\ \ }}}$". If you want to use the fact that "APSP can be solved in time $\dfrac{n^3}{2^{\Omega(\sqrt{\log n\ })}}$" to refute the conjecture, you have to show that

$$O(n^{3-\delta}) \cap \frac{n^3}{2^{\Omega(\sqrt{\log n})}} = \emptyset,$$
or, in plain words, there is no function $f\in \Omega(\sqrt{\log n})$ such that $\dfrac{n^3}f\in O(n^{3-\delta})$.

Well, in fact, the other extreme is true. $\dfrac{n^3}f\in O(n^{3-\delta})$ for all $f\in \Omega(\sqrt{\log n})$.


Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

Simply put, even a weaker claim of $\mathrm{NP}^\mathrm{SAT}=\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{P}^\mathrm{SAT}=\mathrm{P}^\mathrm{NP}$ would imply PH collapse to the second level (so even the consequence is a little bit weaker, you can adapt to your case).

We have $\mathrm{P}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. So, from the assumption, we deduce that $\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. As a result, PH collapse to the second level.


Algorithm for distributing members over activites (with individual preferences)

Here is partly a solution, partly an approximation:

Let $T$ denote set of time blocks.
Let $C$ denote set of children.
Let $A$ denote set of activities.

Let $T_i$, $C_i$, $A_i$ denote $i$-the time block, child, activity.
Let $S_{ij}$ denote the satisfaction for child $i$ from activity $j$.
Let $M_j$ denote maximum number of pupils that can participate in $j$-th activity.

Create a bipartite graph where pupils are on the left side and activities are on the right.
For each pupil $C_i$ and activity $A_j$ create an edge with capacity equal to 1 and cost equal to $-S_{ij}$.
Create a source and connect it to all $C_i$, capacity equal to $|T|$.
Create a sink and connect all $A_j$ to sink, with capacity equal to $M_j * |T|$.
Find minimum cost maximum flow on this graph.
Now for each pupil you have assigned number of activities equal to the number of time blocks. If there exists a valid assignment of activities to pupils, the algorithm above will surely find some (not necessarily valid) assignment.

Let $P_j$ denote number of pupils that were assigned to $j$-th activity after the algorithm above.

Now, for the approximation part:

Let's create a grid of $|T|$ rows and $|A|$ columns, $i$-th row denoting all activities that will happen during $i$-th time interval.
Let's fill in our table. We will loop through it's columns, and for a column, we will loop from top to the bottom of the row. In parallel let's loop through all activities in some order. For activity $j$ let's put into the next cell of the table $j$ activity and move to the next cell, total of $P_j$ times for $j$ activity.
Since $P_j \le M_j * |T|$, in each row of the table there will be at most $M_j$ entries of $j$-th activity, satisfying the condition that during one time interval only $M_j$ persons can participate in $j-th$ activity.
Each row should have some permutation of pupils. Let's for each for find maximum matching between pupils and and activities in some row. Two problematic situations might occur:

Pupil is assigned to the same activities in different time blocks. We can overcome this in two possible ways:

a. Once pupil was assigned to some activity in one row, don't connect the appropriate pupil vertex to the appropriate activity vertex in the following rows.

b. Who ever said that satisfaction decreases if you participate in your favorite activity again? ;)
For some rows, we may not find perfect matching. Well, this is why it is an approximation, not a solution. since it is maximum matching, we will still find for many pupils their preferred activities from first part. For others, we can match them with other activities in a row.

Possible heuristics:

Match pupils in a row not using bipartite matching, but using Hungarian algorithm (for perfect maximum weighted matching, with weights equal to $S_{ij}$, where $j$ is activity in the appropriate cell in a row.

Try different orderings when creating a grid. For example, we may try to use simulated annealing based on the permutation of order, in which we put activities to the grid, and transition between steps that results in a swap of neighboring / any two elements in this permutation.


PRNG bad seeding and von Neumann unbiasing

Von Neumann unbiasing only works if the random source consists of independent samples. Otherwise it is not guaranteed to produce random bits. More generally, in theoretical computer science there exist objects called (randomness) extractors whose job is to extract random bits out of imperfect random sources. Usually they need access to a small number of "high quality" random bits.

In practice, seeding a PRNG is not difficult. There are many legitimate sources of randomness, and using an extractor such as a hash function, you can take a decently sized sample and extract a decently random seed. Once you have a handful of high quality random bits, you can use a PRNG to quickly extract many more seemingly random bits.


Why is Quicksort described as "in-place" if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented.

In an in-place implementation, instead the sort function is not called recursively on newly constructed arrays that become smaller and smaller, but on bounds that become closer and closer.

def sort(array, start, end):
    if end >= start: return
    pivot = array[start]
    middle = start + 1
    for i in range(start+1, end):
        if array[i] >= array[middle]:
            tmp = array[i]
            array[i] = array[middle]
            array[middle] = tmp
            middle += 1
    sort(array, start, middle)
    sort(array, middle, end)

(Beware of this code, I have only typed it, not proved it. Any off-by-one errors are yours to fix. Real-world implementations would use a different algorithm for small sizes but this doesn't affect asymptotic behavior. Real-world implementations would choose a better pivot but I won't get into that here as it doesn't really for this question.)

The Wikipedia page presents both a non-in-place and an in-place version of the algorithm.

Quicksort as written here requires $O(d) + s$ extra storage, where $d$ is the depth of the recursion (which depends on the pivot quality) and $s$ is the element size. The stack size requirement can be improved: there are two recursive calls, and we can make the second one a tail call (which consumes no stack). If we always do the recursive call on the smaller half first, then the maximum stack size for array lengths up to $n$ satisfies $\hat S(n) \le \hat S(m)$ with $m \le n/2 \le \hat S(n/2)$, so $\hat S(n) \le \lg_2(n) \hat S(1)$. Thus we can achieve $O(\log n) + s$ extra storage requirement, regardless of the pivot choice.

There are plenty of other sorting algorithms that can be implemented in-place, including insertion sort, selection sort and heap sort. The simple form of merge sort isn't in-place, but there is a more sophisticated variant which is.

 Thanks to Aryabhata for pointing out that Quicksort can always be done in $\lg(n)$ stack and that there is a variant of merge sort with both $O(1)$ additional storage and $O(n \log(n))$ runtime.


Computing a boolean function with a small formula

Something has gone wrong in the way you applied Adleman's theorem: it has led you to try to prove something that isn't actually true.

The statement the book asks you to prove is true.  There is a good deterministic algorithm for $f$.  Adleman's theorem, applied properly, immediately gives you a good deterministic algorithm for $f$.  Just make sure you pick the definition of "good point" correctly.  Hint: A good point for $a$ is a value $y$ such that $F(a,y)=f(a)$.  What can you conclude about $f(a)$, if you observe a point $y$ such that $F(a,y)=1$?  Now an application of Adleman's theorem immediately leads to a simple deterministic algorithm for computing $f$ and a small boolean formula for $f$.  In particular, we get the following boolean formula for $f$:

$$f(x) = F(x,s_1) \lor F(x,s_2) \lor \dots \lor F(x,s_n).$$

Why does this work?  Well, if $f(x)=0$, then we're guaranteed that $F(x,y)=0$ for all $y$ (this comes directly from the exercise in your book), so in particular every term of the above disjunction is 0, so this formula gives the correct answer for $f(x)$.  On the other hand, if $f(x)=1$, then Adleman's theorem guarantees that there exists at least one $s_i \in S$ that's a good point for $x$, i.e., at least one $s_i$ such that $F(x,s_i)=f(x)=1$, which means that the above disjunction is 1, so this formula gives the correct answer for $f(x)$ in this case, too.

In contrast, the claim you're trying to prove isn't true.  Here's an explicit counterexample.  Let $F(x,s)=s$ (so $m=1$), $s_0=0$, $s_1=1$ (so $S=\{0,1,\dots\}$), and let $f$ be any function with no small formula.  Then it is easy to verify that for all $x$ there exists $s \in S$ such that $F(x,s)=f(x)$: in particular, you can take  $s=f(x)$.  Notice that we didn't use anything about $f$, so we were free to choose $f$ any way we want.  It is also easy to see that $F$ has a small formula, for this choice of $F$.  Therefore, this choice of $F,S,f$ satisfies all the preconditions of your claim.  However, (by assumption) $f$ doesn't have a small formula, so this is a counterexample for your claim.

There's a crucial difference between "there exists at least one $s$ for which (blah) is true" vs "(blah) is true for a large fraction of $s$".

I don't know how you got to your claim or what went wrong in your translation from the book's exercise to your claim, but I suspect you didn't apply Adleman's theorem quite right, or the way you applied it didn't give you strong enough conclusions/assumptions about the properties that $F$ has.


Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

This is not the answer to your question, but maybe you can use some elements of it.
For $i<j$, let us denote $X_{ij}$ the random variable:
$$X_{ij} = \left\{\begin{array}{rl}1 & \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$
and $A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}$.
Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:
$$\mathbb{P}(X_{ij} = 1) = \mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) + \mathbb{P}(S_{(j)} \text{ first pivot in }A_{ij})$$
This is also due to the fact that if another element of $A_{ij}$ is chosen as first pivot, $S_{(i)}$ and $S_{(j)}$ will be put in two different parts of the partition.
Since the choice of the pivot is uniform, we get $\mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) = \frac{1}{|A_{ij}|}$ and finaly $\mathbb{P}(X_{ij} = 1)  = \frac{2}{j - i +1}$.
Now, the expected number of comparisons where $S_{(i)}$ is involved is:
$$\begin{array}{rcl}
\displaystyle\mathbb{E}\left(\sum\limits_{j=1,j\neq i}^nX_{ij}\right) & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{E}(X_{ij})\\
& = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{P}(X_{ij} = 1)\\
& = & \displaystyle\sum\limits_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\
& = & \displaystyle\sum\limits_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits_{j=i+1}^{n}\frac{2}{j - i +1}\\
& = & \displaystyle\sum\limits_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits_{k=1}^{n-i}\frac{2}{k +1}\\
\end{array}$$
This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is:
$$\displaystyle\mathbb{P}\left(\sum\limits_{j = 1, j\neq i}^n X_{ij} = k\right)$$
Also it is not so clear that for $j\neq j'$, $X_{ij}$ and $X_{ij'}$ are independant (since for example $X_{ij}$, $X_{ij'}$ and $X_{jj'}$ are not independant because at most two of the three could be $1$).


What does an admissible numbering of computable functions look like?

The encodings you mention are admissible. Why do you think they need to be bijections?
In fact, there is no admissible numbering of partial computable maps that is a bijection. If there were one, we could decide equality if partial computable maps, which would allow us to implement the Halting oracle.


Two Generals problem - what if we set boundary conditions, and then layer redundant messages once they've been met?

Realize first that if General $X$ doesn't receive message $X_k$, then General $X$ must assume that General $Y$ didn't receive message $Y_{k-1}$.

Suppose that General $B$ does not receive the final message $B_n$.  An important question is: Why is that?

In General $B$s mind, General $A$ didn't necessarily receive $A_{n-1}$.  And that would be bad.

Suppose in this hypothetical scenario that $B$ believes that $A$ didn't receive $A_{n-1}$.  That could be due to $B$ not receiving $B_{n-2}$.  But why didn't $B$ in this scenario receive $B_{n-2}$.  Well, possibly because $A$ didn't receive $A_{n-3}$.

That means that if $B$ doesn't receive $B_n$, $B$ must assume that $A$ assumes that $B$ assumes that $A$ didn't receive $A_{n-3}$ ... ad infinitum.

The problem here is that after $A$ and $B$ split, there is no more new common knowledge.  A nice way of modeling this situation is with the use of possible worlds.


You can use the idea of the Master Theorem and apply it to these occurrences. That is what I have done here, I would recommend looking at that answer because it will answer your question.

Basically we can look at the fractional terms inside the recurrence calls. If the sum to less than $n$, then the "conquer" part of "divide-and-conquer" will dominate the "divide" part.

For your example we have the fractions: $\frac{n}{5} + \frac{7n}{10} = \frac{9n}{10} < n$. Therefore the $O(n)$ term will dominate and the overall time complexity will be $\Theta(n)$. This is an idea of the Master Theorem, figuring out which dominates: "divide" or "conquer". Again, I highly suggest looking at this answer for a more in-depth proof.


Choosing spanning trees to maximise node connectivity

My suggestion would be to try simulated annealing.  This looks like a good candidate for that heuristic.  It sounds like you have some idea what the objective function you want to minimize is (that's good; you need one).

I would suggest that you use simulated annealing as follows:

A state is a possible graph (a set of edges).
The cost function for a state might be your objective function plus some penalty for the number of $C_i$'s that aren't fully connected.
To transition between states, you might randomly choose among the following options:

Add an edge chosen at random (or: choose a $C_i$ that isn't fully connected, and add a randomly chosen edge between some pair of variables $C_i$ that aren't currently in the same connected component)
Delete an edge chosen at random
Pick an existing edge $(u,v)$, delete the edge, then randomly choose some other variable $w$ that is in the same connected component as $v$ and add the edge $(u,w)$.

but of course you can play around with it and try different variations to see which works the best.  This might just give you some reasonable solutions.

You could also try formulating this as a SAT or ILP instance, but my sense is that I would try simulated annealing first.  If you're lucky, it just might work well enough that you don't need to bother with anything else.


In general, it is not: see Summation of asymptotic notation, Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?.
But if each $O(f(k))$ term uses the same hidden constant, then it follows by expanding the sum: see  https://en.wikipedia.org/wiki/Big_O_notation#Sum, Summing big-O-notation, and then apply them repeatedly.


What are the definitions for "hard problem" and "easy problem"?

They're not technical terms, so they don't have precise definitions. A problem is "hard" if it requires (or we think it requires) "large" computational resources to solve, and "easy" if it doesn't. "Large" depends on context but, in most contexts, a problem that can be solved in polynomial time is considered "easy".


Proof that the language $ww^R$ is not regular without using the pumping lemma

Let

$$ L_1 = \{\ \omega\omega^r \ | \ \omega \in \Sigma^* \} $$
$$ L_2 = \{\ a^nb^n \ | \ n \in \mathbb{N}\ \}$$

Because $\Sigma = \{a, b, c\}$ is finite, $\Sigma^*$ must be countable.

This means we can define a function $f : \Sigma^* \rightarrow \mathbb{N}$ which returns the position of a word $\omega \in \Sigma^*$ in an arbitrary ordering defined by $f$. $f$ is invertible, we define $f^{-1} : \mathbb{N} \rightarrow \Sigma^*$, which returns the word $\omega$ at position $n$ in the enumeration of $\Sigma^*$ as defined by $f$.

Now, since every word $\omega$ is uniquely defined by a natural number $n$, and every word $\omega$ has exactly one unique reverse $\omega^r$, we can define an isomorphism between $L_1$ and $L_2$:

$$ g \colon\  L_1 \rightarrow L_2; \quad \omega\omega^r \mapsto a^{f(\omega)}b^{f(\omega)} $$

$$ g^{-1} \colon \ L_2 \rightarrow L_1; \quad a^nb^n \mapsto f^{-1}(n) f^{-1}(n)^r $$

Since $L_2$ is not regular and we have a bijection between $L_1$ and $L_2$, $L_1$ must not be regular.

This proof works for any finite alphabet $\Sigma$ because the transitive closure of a finite alphabet is always countable.


How do I prove all constants to some exponential power belong to little-o of some function

Try proving that $5^{2n} = o((\lg \lg n)^n)$.  Write out the proof in detail, and make sure you  understand every step.

Then, try replacing the $5$ in the base with an arbitrary constant $c$.  Does every step still go through?  Hint: you should be able to extend the argument to handle an arbitrary constant $c$, with very little change.

If you're still stuck, edit the question to show us what you've tried, including showing us your proof that $5^{2n} = o((\lg \lg n)^n)$ and your reasoning about which steps are still valid when you replace $5$ with an arbitrary constant $c$.


Is there a method to generate the complement of a context-free grammar?

If $L_0$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language
$$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}.$$
This language is context-free, but is complement (with respect to $\{a,b,c\}$) is not.
Another way to formulate your question is as follows: given a context-free grammar for a language $L$, is there an algorithm that either constructs a context-free grammar for the complement of $L$, or determines that the complement of $L$ is not regular? Such an algorithm can be used to decide whether the complement of $L$ is context-free. However, this is undecidable, as we now show following Hendrik Jan's notes.
Recall that given a grammar $G$ over an alphabet $\Sigma$, it is undecidable whether $L(G) = \Sigma^*$. Let $\#$ be a new symbol, and construct a grammar for the language
$$ L = L_0 \# \Sigma^* \cup \Sigma^* \# L(G), $$
where $L_0$ is a context-free language whose complement is not context-free (if $|\Sigma| \geq 3$, we can use the one above, and if $|\Sigma| = 2$, we can encode $a,b,c$ as $a,ba,bba$; if $|\Sigma| = 1$ then it is easy to check whether $L(G) = \Sigma^*$). If $L(G) = \Sigma^*$ then $L=\Sigma^*\#\Sigma^*$, and so the complement of $L$ is context-free. Otherwise, suppose that $w \notin L(G)$. Then
$$ \overline{L} \cap \Sigma^* \# w = (\Sigma^* \setminus L_0) \# w, $$
which is not context-free, and so $\overline{L}$ itself is not context-free (since the context-free languages are closed under intersection with a regular language). This shows that $\overline{L}$ is context-free iff $L(G) = \Sigma^*$.
The problem of deciding whether $L(G) = \Sigma^*$ is actually not recursively enumerable. This means that there is no algorithm which, on input $G$, halts iff $L(G) = \Sigma^*$ (however, there is a simple algorithm that halts iff $L(G) \neq \Sigma^*$, namely go over all words in $\Sigma^*$ in parallel, and check whether each of them belongs to $L(G)$). Therefore there is no algorithm that, given a context-free grammar for a language $L$, halts iff the complement of $L$ is context-free.
In other words, even the following solution to your problem does not exist: an algorithm that attempts to construct a context-free grammar for the complement of the given context-free language, and either halts with the grammar, or never halts (if the complement is not context-free).


Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".
That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.

We do not speak of "an improper subset", most of the time if not ever.
Why?
Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. If, furthermore, $A$ is not $B$, then we say $A$ is a proper (or strict) subset of $B$.
If we want to mention "an improper subset" of $B$, what would it mean?

It should mean $B$ itself. That is how I would understand that phrase upon first reading. Then, why do we want to say "an improper subset of $B$", a pretty long phrase, when we can just say "$B$", which is concise? The phrase "an improper subset" seems implying there are more-than-one such subsets for a given set, which is simply wrong.

It could just means "subset" when it is used in distinction to "proper subset" (which sounds unnatural to me, but maybe that is only me). Again, why not just use "subset", which is concise?


Matching/finding mathematical plot images

A natural approach is to first scrape the data from each plot; then come up with a distance measure to compare the similarity of the data from two plots; then given a template plot, loop over all plots in the database, compute the distance, and find the most similar one.

There are many tools for scraping plots (i.e., given an image that contains a plot, extract the underlying data).  See, e.g., https://academia.stackexchange.com/q/7671/705, https://stats.stackexchange.com/q/14437/2921, etc.

You'll have to choose the distance measure yourself.  You haven't answered questions about what notion of similarity you want to use, and we can't tell you what to use.  You could, for instance, rescale the data so that the x-axis and y-axis both vary across the range [0,1] (so all plots share the same scale), then use the $L_2$ distance (Euclidean norm) between the two time series represented on the plots.  That might or might not suit your needs.

I don't expect deep learning to be particularly useful here.  I would try more direct methods first.


Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Here is the general idea:

Sort all the strings according to their first character (refer to each string using an index to save time).
Partition the strings according to their first character, and run recursively on each part (deleting in your mind the first character).

I'll let you work out the details.


Another version of the 3-coloring decision problem?

Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time.
If $k$ is part of the input, then your problem is harder than the NP-complete vertex-deletion graph bipartization problem. The later problem is defined as follows. Given a graph $G$ and an integer $k\geq 0$, find a subset of at most $k$ vertices such that removing these vertices results in a bipartite graph.
To see why your problem is harder, assume that you have indeed succeeded in coloring a graph with $c_1, c_2$ and $c_3$, where at most $k$ vertices are colored with $c_1$. Then, removing the vertices that are colored with $c_1$ leaves us with a subgraph colored with $c_2$ and $c_3$, and thus the remaining subgraph has to be bipartite as two vertices with same color cannot be neighbors.
The vertex-deletion graph bipartization problem is known to be NP-complete even when restricted to planar graphs. See here.


Interesting problems that can be solved with algorithms

Depending on the level of sophistication of your intended audience, a simple canonical example is testing whether an input number $n$ is prime.

A brute force approach is to test, for all $d$ in the range $2,\dotsc n-1$ whether $d$ divides $n$. If you find a $d$ that divides $n$ you can stop and assert that $n$ isn't prime; if you don't find any such $d$, you can assert that $n$ is prime. That'll take about $n$ divisions if $n$ is prime.

An improvement is to try just those $d\le\sqrt{n}$ (rounding up), since it's easy to see that if $n$ has any divisors, there must be one in that range. This is a big improvement, since it reduces the number of divisions from $n$ to $\sqrt{n}$, more or less.

If you want to expand this, there are even faster ways to test for primality and if your audience is sophisticated enough, you might want to try one or more of them.


Search algorithm to find integer input that produces the first 'True' (bool: 1) occurence of a computationally expensive boolean function

Use binary search.

You know that the correct value is somewhere in the range $[n_\min,n_\max]$, so pick $t = \lfloor (n_\min+n_\max)/2 \rfloor$ (the point halfway in the middle), and evaluate $f(t)$.  This will either tell you that $n^*$ is in $[n_\min,t]$ or that $n^*$ is in $[t+1,n_\max]$.  Now you can repeat on the smaller interval.  Each time, the width of the interval decreases by a factor of two, so after $\lg (n_\max-n_\min)$ iterations, you will find the correct value of $n^*$.  This is much faster than trying all $n_\max-n_\min$ possible values of $n^*$.


Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

Given an instance $\langle \{s_1,\ldots,s_n\}, T \rangle$ of subset sum, construct the following weighted graph. The vertices are
$$ v_0,v_1,\ldots,v_n,u_1,\ldots,u_n. $$
Connect $v_{i-1}$ and $v_i$ with an edge of weight $s_i$. Connect $v_{i-1}$ to $v_i$ via $u_i$ (i.e., add the edges $\{v_{i-1},u_i\},\{u_i,v_i\}$) with zero weight edges. There is a simple path of total cost $T$ iff there is a subset of $\{s_1,\ldots,s_n\}$ summing to $T$. This shows that your problem is NP-hard, and in fact NP-complete, since it's clearly in NP.


Can we enumerate finite sequences which have no halting continuation?

Not an answer, but too long to be a comment:

  Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia's "Every syntactically consistent, countable first-order theory has a finite or countable model.")

I'm not a logician so I don't know if the latter statement is true, but it's definitely not a restatement of the first statement.

The statement you quoted from Wikipedia says if you have countably many axioms and they're consistent then there exists at least one model of the theory with countably many elements.

What Godel's completeness theorem says that if a statement is true then it has a proof.

What you're missing to bridge the two is "a statement true in every countable model is true in every model."  I don't know if this is true or not (logicians would probably know off the tops of their heads).


Confusion in CLRS's version of Prim's algorithm

Question 1: However still I think that according to the line 8 in algorithm, all adjacent vertices of $a$ not in the tree must be added first to the tree. Thus $h$ should also get added immediately after $b$, before $c$.

You are confusing the resulting MST tree (denoted $T$) with the intermediate priority queue $Q$.

All the vertices are already in $Q$ at the end of initialization (Lines 1 ~ 5). However, $T = \emptyset$ at this time point.
A vertex $u$ is extracted from $Q$ and becomes a member of tree $T$ at line 7.
In the loop starting from Line 8, vertice $v$ satisfying the requirements of Line 9 are not inserted into the tree $T$; instead their keys in the priority queue $Q$ are changed (in fact, decreased).

  Question 2: "My point is when the line 8 says "for each adjacent vertex $v$ of $u$", why only adjacent node $b$ of $a$ is considered, but not $h$ (which is also adjacent to $a$)."

Yes, $h$ is also considered, but in the way different from what you describe. In the iteration for $a$, both $b$ and $h$ are considered (satisfying Line 8 and Line 9): their keys are updated (i.e., decreased) in the priority queue $Q$ (Line 11) and their parents are updated accordingly (Line 10). (Note that these updates are not finalized and may be updated again during the algorithm.)

The key point is: neither $b$ nor $h$ has been added into the resulting MST tree $T$. Vertex $b$ will be extracted from $Q$ and added into $T$ in the next iteration at Line 7 (shown in step (b)).

Also note that the figure in CLRS only shows the changes on $T$; it does not show the states of $Q$.


First, to get some idea add code to your program that counts the operations and prints the total, then try with n=1, 10, 100 and 1000.  That’s not exactly scientific but is a hint about the correct answer. If n= 1000 takes too long, try 200, 300, 400.

Now: How many steps does the innermost loop perform at most, depending on I? And for a given I, how often is the whole loop performed? And how many values of i are there? That together gives you an upper bound, and guess what - it looks like O(n^4) to me.

I’ve just typed this on my phone, so you do it much more carefully and you may show be able to show your professor that you are indeed right. If the code is exactly what you wrote.

A bit more precise: The inner loop for k has j iterations. j % i == 0 is true when j is a multiple of i, that is j = i, j = 2i, j = 3i, ..., j = (i-1) i. So for a given i, the executions of the inner loop are i, multiplied by the sum over j for 1 ≤ j ≤ i-1. That sum is (i-1)(i-2) / 2, so the inner loop executes i (i-1) (i-2) / 2 times, which is quite exactly $(i-1)^3 / 2$ times.

We have 0 ≤ i ≤ n-1. Ignoring i = 0 and i = 1, 1 ≤ i-1 ≤ n-2. So the number of executions of the inner loop is about $((n-3)(n-2))^2 / 8$.


Types of reductions and associated definitions of hardness

Your definition of parsimonious reductions is incorrect. You are confusing it with polynomial-time one-one reductions which is a special case of Karp reductions. They don't preserve the number of "solutions". Please see this answer for more about reductions considering the number of certificates.

The rest seems fine although it is usually better to view them in a two dimensional chart:

the complexity of reduction: computable, polynomial time, logarithmic space, etc.
type of access: Turing, many-one, one-one, etc.

  Are NP-complete problems defined with respect Cook reduction or parsimonious reduction?

$\mathsf{NP}$ hardness and completeness are defined w.r.t. Karp reductions (polytime many-one), not Cook nor parsimonious reductions.

  Can anyone kindly give an example of a problem that is NP-complete under Cook and not under parsimonious reduction.

Take the complement of SAT, it is complete for $\mathsf{NP}$ under Cook reductions, it is not believed to be complete for $\mathsf{NP}$ under Karp reductions. Karp reductions include polytime one-one reductions.

  the class #P-Complete is defined with respect to Karp reductions

Note that $\mathsf{\#P}$ is not class of decisions problems, it is a class of function computation problems. Its hardness and completeness are usually defined w.r.t. Cook reductions (polytime Turing). See e.g. Arora and Barak, page 346.


There is no one universally accepted lexographical ordering. Any author is free to introduce their own ordering, as long as it is consistent within their scope of discussion.

It's just like binary tree traversing algorithms like preoder, inorder or postorder traversal. There is no one correct traversal, its upto the author to decide which one to use, and stick with it throughout their discussion about the topic.


is L = { | M is a tm such that t(n) = O(n^2) } in R? RE? CO-RE? CO-RE / RE?

This problem is not in RE nor in coRE.

First, your intuition that it's not in RE is correct, although note that very crucially - it's just an intuition, and not a direction for a proof!
However, your intuition breaks down for co-RE due to the specification being $O(n^2)$ and not $n^2$ exactly.

Let's start by proving that the language is not in coRE, by a reduction from $HALT_{TM}=\{\langle M,w \rangle: M$ halts on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle D \rangle$, where $D$ is a TM that given input $x$, ignores it and simulates $M$ on $w$. I'll leave it to you to prove correctness, but note that if $M$ halts on $w$, then it does so in constant time (i.e. independent of $x$, of course). Use this and the asymptotic notation $O(n^2)$ to conclude correctness.

Proving that the language is not in RE is a bit trickier. The reduction itself is quite standard. We reduce from $HALT_{\overline{TM}}=\{\langle M,w \rangle: M$ does not halt on $w\}$.

Given input $\langle M,w \rangle$, the reduction outputs $\langle K \rangle$, where $K$ is a TM that given input $x$, computes the length $|x|$, and then simulates the run of $M$ on $w$ for $|x|$ steps. If $M$ halts on $w$ during this time, $K$ goes into a non-halting loop. Otherwise, $K$ halts.

The correctness of this reduction is based on the observation that computing $n=|x|$ can be done in time $O(n\log n)$, and that simulating $M$ on $w$ for $n$ steps also takes $O(n\log n)$ time. This is not trivial, and follows by a clever use of a universal TM.


Proving program termination in the $\lambda$-calculus

This may take the form of a quantity which is asserted to decrease continually and vanish when the machine stops.

Lambda calculus evaluation is a sequence of beta reduction steps. So for the lambda calculus (with or without types: types don't affect evaluation), you want a quantity (a positive integer) that decreases at each reduction step.
Such a quantity exists if and only if the lambda-term is normalizable (according to a chosen reduction strategy $\to$). Proof: suppose there is a function $f : \mathbf{\Lambda}(M_0) \to \mathbb{N}$ where $\mathbf{\Lambda}(M_0)$ is the set of lambda-terms $M$ such that $M_0 \to^\star M$, such that if $M \to M'$ then $f(M) \lt f(M')$. Then the length of a reduction chain from $M_0$ is bounded by $f(M_0)$ and in particular cannot be infinite, so $M_0$ is strongly normalizable. Conversely, if $M_0$ is strongly normalizable, define $f(M)$ as the length of the longest reduction starting at $M$.


Small space hash functions that are weakly but not strongly universal

Let $H$ be a family of strongly universal hash functions from $U$ to $[m]$.
Construct a new family of hash functions from $U \cup \{x\} \to [m]$ by extending all functions $h \in H$ with $h(x) = 1$. The family is weakly universal since $h(u)$ is distributed uniformly for every $u \in U$, but it is clearly not strongly universal.


Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

As I understand, you are asking two questions. Let me address them separately:

You don't. Your assumption on $M$ did not require anything more than $L(M) = A$, which is too weak for such a proof. You need to use $A \in \textbf{PSPACE}$ and require the existence of a polynomial $p:  \mathbb{N} \to \mathbb{N}$ such that $M$ uses at most space $p(n)$ for any input of length $n$.Incidentally, you also need this to know what $k$ should be. In your proof, you give no explicit way of computing $k$ other than simulating $M'$, but you do not state why this could ever be done in poly-time. (In fact, this could only ever work for arbitrary $M$ if $\textbf{P} = \textbf{PSPACE}$.)
The description of $M$ remains constant as the length of the input $x$ increases, so it is negligible, asymptotically speaking.

The real issue

It appears your approach is based on fixing $A$ and $x$ and then constructing an LBA $M''$ to simulate $M$ on $x$. This is not how reductions work. $A$ and $M$ should be fixed, but you need to keep $x$ arbitrary, otherwise the proof is quite incorrect (since the result of running $M$ on $x$ could be simply hardcoded into a TM which produces the result immediately upon reading $x$ as input; this proves absolutely nothing).


This question is very natural since most if not all common functions that appear in the runtime-analysis of algorithms form a totally ordered set in terms of little $o$-notation or big $\Omega$-notation such as shown in this answer by Robert S. Barnes or this answer by Kelalaka.

However, there is no such totally-ordered set of representative functions for all positive increasing functions.

The basic reason is the first property, when applied to $F$, does not define a total-order.

Define two strictly increasing $f_1(n)$ and $f_2(n)$ from $\Bbb N$ to $\Bbb N$.

$$f_1(n)=2^{(2\lceil\frac {n+1}2\rceil)^2+n}$$
$$f_2(n)=2^{(2\lfloor\frac {n}2\rfloor+1)^2+n}$$

Then
$$\sup\lim _{n\to\infty}\frac {f_1(n)}{f_2(n)}
\ge \lim_{n=2i+1\to\infty}\frac {f_1(n)}{f_2(n)}
=\lim_{i\to\infty}\frac {2^{(2(i+1))^2+2i+1}}{2^{(2i+1)^2+2i+1}}
=\lim_{i\to\infty}2^{4i+3}=\infty$$

$$\sup\lim _{n\to\infty}\frac {f_2(n)}{f_1(n)}
\ge \lim_{n=2i\to\infty}\frac {f_2(n)}{f_1(n)}
=\lim_{i\to\infty}\frac {2^{(2i+1)^2+2i}}{2^{(2i)^2+2i}}
=\lim_{i\to\infty}2^{4i+1}
=\infty$$

In plain words, neither of $f_1(n)$ and $f_2(n)$ grows asymptotically the same or faster than the other one ignoring a constant factor.

Let $F$ and $G$ be defined as in the question. Suppose $G$ exists. Then there is $g_1, g_2\in G$ such that $g_1(n)=\Theta(f_1(n))$ and $g_2(n)=\Theta(f_2(n))$. Then $g_1(n)>c_1(f_1(n))$ for some constant $c_1>0$ and $g_2(n)<d_2(f_2(n))$ for some constant $d_2$. (In usual cases, we have to say "for $n$ large enough". However, that clause can be omitted since all values here are positive. Anyway, we can add that clause as well.)

$$\sup\lim _{n\to\infty}\frac {g_1(n)}{g_2(n)}
\ge \sup\lim_{n\to\infty}\frac {c_1f_1(n)}{d_2f_2(n)}
\ge \frac{c_1}{d_2}\sup\lim_{n\to\infty}\frac {f_1(n)}{f_2(n)}
=\infty
$$

Symmetrically, $\sup\lim_{n\to\infty}\dfrac {g_2(n)}{g_1(n)}=\infty$. We see that $g_1\not=g_2$ but neither $g_1(n) = o(g_2(n))$ nor $g_2(n) = o(g_1(n))$. This contradition shows $G$ does not exist.

How about if we drop the first requirement so that the functions in $G$ are not required to dominate each other?

Then this question becomes closely related to the question Big O notation and the maximal set of comparable functions as found by OP, where a couple of enlightening answers explain the situation pretty well, indicating there is hardly any hope for a nice positive answer. Even countably-infinitely real parameters cannot parametrize continuously a set of representative functions in the equivalence classes of increasing functions where two functions are in the same equivalence class if they are related by $\Theta$ and each function only uses finitely-many parameters.

Explicit rigorous answers to the following exercises might be long. However, the ideas should be simple for experienced users.

(Exercise 1.) For any given positive integer $n$, construct $n$ increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 2.) Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(f_2)$ nor $f_2=O(f_1)$.

(Exercise 3.) Let $h(n)$ be a given function from $\Bbb N$ to $\Bbb N$. Construct a set of infinitely many increasing functions from $\Bbb N$ to $\Bbb N$ such that for any two of them, $f_1$ and $f_2$, neither $f_1=O(h\ f_2)$ nor $f_2=O(h\ f_1)$.


From where does the Fetch Unit get its instructions?

The instructions come from some part of memory, pointed to by the Program Counter (PC) aka Instruction Pointer (IP).

In modern computers, instructions tend to share the same RAM used for everything else (with protections in place to keep things sane), but especially in older or special-purpose machines it's not uncommon for instructions to be baked into ROM instead.


Closure of context-free languages under "removal of a regular language from the right"

Let me prove that if $L$ is regular then so is $P$. The proof in your case is similar. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$ be a copy of the alphabet $\Sigma$. Let $s$ be the $\Sigma$-substitution $s(\sigma) = \{\sigma,\sigma'\}$, let $t$ be the $\Sigma$-homomorphism $t(\sigma) = \sigma'$, and let $d$ be the $\Sigma \cup \Sigma'$-homomorphism $d(\sigma) = \sigma$, $d(\sigma') = \epsilon$. Then
$$
P = d(s(L) \cap \Sigma^* t(R)).
$$

As an aside, the class of languages obtained by dividing a context-free language by a context-free language consists of all r.e. languages. See for example The family of one-counter languages is closed under quotient by     Latteux, Leguy and Ratoandromanana.


What happens when we increase or decrease capacities in the minimum flow?

Case 1, increase the weight.  Consider a path on at least three vertices with capacity 1 for every edge.  Max-flow is 1, min-cut is 1.  Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false.
Case 2, let $C$ be a minimum cut with cost $w(C)$.  Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(C)$.  Since $C$ is still a cut in the graph, but $w'(C)$ is smaller than any other minimum cut, the claim is true.


Let me break up several possible interpretations of your question:

What is the purpose of learning compilation?

There are several possible answers:

So that you know how to build a compiler should you have to. This is not a good answer nowadays.
Part of the goal of the computer science curriculum is to explain to you how a computer works, stopping at the hardware. This includes the operating system, file systems, the compiler, the network stack, and more.
As a programmer, you will be using compilers. Sometimes it will be useful to know what happens under the hood. For example, understanding garbage collection will help you choose which language to use in embedded applications.
Compilation is part of the standard curriculum, so you might get asked about it in interviews.

Why are they teaching me compilation?

Apart from the reasons listed above, there is an additional one: universities are very conservative. In the past it used to be more important to understand how compilers work. Nowadays this is less important, but change is slow, so material
that made sense 10 years ago is still being taught today.

That said, some universities might reform their compilation curriculum, for example by de-emphasizing parsing, concentrating on more exciting aspects such as optimization, memory management, dynamic and static analysis, and the like.

Why am I studying compilation?

As an aspiring programmer, your university training contains lots of apparently useless classes, for example calculus. People choose to go to university for various reasons - it's a rite of passage, an opportunity for socialization and finding a partner, and it might help you get a job; or even just family or peer pressure.

Some people do away with university training, preferring other formal training, or even self-training. Some of these people are very successful.
For whatever reason, you chose to attend university rather than any of these alternative routes. You should accept that university training is rather theoretical, and try to make the most out of it.


NP completeness proof of a spanning tree problem

In short, your guesses are correct.  For the purpose of this answer, let’s call the three problems in question as follows:

Equality version: Given a graph $G = (V, E)$ and a set $S \subseteq V$, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is equal to $S$.  As you stated, this is NP-complete by a reduction from the Hamiltonian path problem.
Subset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a subset of $S$.
Superset version: Given $G$ and $S$ as above, decide whether $G$ has a spanning tree $T$ such that the set of leaves in $T$ is a superset of $S$.

To prove that the subset version is NP-complete, you can still reduce the Hamitonian path problem to it.  Try to modify the proof of the NP-completeness of the equality version.

To prove that the superset version can be solved in polynomial time, try to find a necessary and sufficient condition for such a tree $T$ to exist.

Both versions (as well as some other problems about spanning trees) are studied in [SK05].  But I guess that it is better if you try to solve the problems by yourself before looking at the proofs in the paper, because looking at the paper can be a big spoiler.  Unfortunately I had looked at the paper before trying to find a polynomial-time algorithm for the superset version!

[SK05] Mohammad Sohel Rahman and Mohammad Kaykobad.  Complexities of some interesting problems on spanning trees.  Information Processing Letters, 94(2):93–97, April 2005.  [doi] [author copy]


How to prove or disprove that f is computable?

Define the function $f: \mathbb{N} \to \{0,1\}$ as follows.  Let $f(x) = 1$ if turing machine $x$ halts on itself as input and $f(x) = 0$ otherwise.  Then for all $x$, we have that $f(x) \leq 1$.  Yet, if $f$ is computable, then the Halting problem should be decidable.


Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

A recurrence of the form
$$
T(n) = 2T(n/2) + \Theta(n)
$$
is really a shorthand for a recurrence of the form
$$
T(n) = 2T(n/2) + f(n), \text{ where } f(n) = \Theta(n).
$$

Let us consider a recurrence of this form, and let us suppose that $an \leq f(n) \leq bn$, where $a,b > 0$. Consider the more general recurrence
$$
T_c(n) = 2T_c(n/2) + cn,
$$
with the same initial values as the $T(n)$ recurrence. You can prove by induction on $n$ that
$$
T_a(n) \leq T(n) \leq T_b(n).
$$
Therefore, if you can show that $T_c(n) = \Theta(n\log n)$ for all $c$ (where the hidden constant could depend on $c$), then it would follow that also $T(n) = \Theta(n\log n)$.


Question about Prims algorithm where weights are between 1 and some constant W

The solution is to preprocess the adjacency matrix so that each vertex now has a list of adjacent vertices. When decreasing keys, you address each edge at most twice, so this part of the algorithm runs in $O(E)$.

The basic observation here is that you can implement a priority queue in $O(W)$ if the number of different weights is $W$. You have to be careful to maintain an array mapping the vertices to their current location in the priority queue, but then all operations are indeed $O(W)$.


An inversion is a pair of indices $(i, j)$, with $i < j$ and $a_i > a_j$.
If you separated the array into two halves, then the inversions fall into three categories:

both indices of an inversion appear in the left half -> we count those in the first recursive call
both indices of an inversion appear in the right half -> we count those in the second recursive call
$i$ is in the left half, and $j$ is in the right half.

So in the merge step, we need to make sure that we only count those inversions of the third type.

By taking the definition of inversion, this translates as follows:
For each element in the left half ($a_i$), count how many elements in the right side are smaller ($a_j$). It should be obvious, that this really counts all inversions of the third category, and that it only counts these.
This translation also gives a very native $O(n^2)$ implementation of this step.

To make this more efficient, we can use the fact that both halves are sorted after the recursive calls, and we can use two pointers so that we can accomplish this step in $O(n)$. The pointers point to the first unprocessed element in each half. Then we take the smaller one of the two unprocessed elements, and put it in our merged array. If this one is of the first half, then we can count in constant time how many were smaller than it in the second half (by looking at the index of the second pointer).


Is there a term for "delegate" function in CS?

I cannot know all the parochial terminologies and concepts used by the
great variety of the many - sometimes disputable - language designs
available in computer science. Some design choices may be motivated by
issues that are only remotely connected with science. But there is
also some more or less established terminology.

When a function A takes a function B as parameter, that is simply
called a functional parameter.

A function can be seen as composed of a control part (the code or
instructions) and of an environment of entities used by the control.
This environment comprises usually two kinds of program entities:

local entities that are normally intended to be used during the
lifetime of a call to the function, that have distict instances for
distinct calls, and are visible only to other entities created (declared)
in the body of the function. They come into existence at each function call, usually only for the duration of that call
global entities that are defined (declared) in some (usually) enclosing structure
(function, method, class instance ...)  containing the function
declaration, hence also visible and usable by the function. They are the same for each call of the function value created by the same declaration instance.

The function code together with its associated global environment is called a
closure. The term is about 50 years old. But a closure is
essentially a functional value.

Often the conceptual closure structure can be ignored as everything
works naturally as one would hope, since a function declared in some environment usually ceases to be
accessible, thus to be used, when this environment is exited. Hence it
will no longer need what it was using there. It is however possible that a
functional value $\gamma$ leaves the environment where its has been declared, and
has to survive the disappearance of this environment where it uses some global entities. This happens mostly when another function returns $\gamma$ as a functional
result.

If function G and variable X are declared in function F,
then G can use X as a global. It may happen that the functional
value $\gamma$ of G is returned by a call to F. This is no problem
because that functional value $\gamma$ can be stored in a functional
variable (some would probably say pointer) and just used from
there. The difficulty comes from the fact that when this functional
value $\gamma$ is called, it may use the variable X of the call to
F that created $\gamma$, and terminated returning it. So special steps must be taken to preserve
X for the closure, even after the call to F has terminated, and
the corresponding environment should be no longer otherwise needed.

Actually, this occurs often in object oriented programming, for
essentially the same reason. Object orientation can be implemented in
a language that does not have it precisely by declaring an object constructor
function with local variables (the state variables of the object constructed) that
return tuples of functional values (the methods of the object class) accessing these variables.
Thus the closure concept is just a very intentional and frequent
occurrence in OO programming. Every method is essentially a closure on
the environment implementing the state of an object. At each call to the constructor, a new tuple of closures is created for the new object, corresponding to function code that does not change, but which is closed on a new environment, the local environment of the constructor call that creates the object.

As said above, a closure is just a pair composed of a function and its
globals. It is not mutable: the pair is essentially fixed when the
function is created. However, the adress of such a pair is just a
pointer to a closure, and can be stored in a variable. It can be
dereferenced and called (no big mystery). But I do not know whether
that is what C++ calls a pointer to a function, though I would hope it
is.

You may note that creation of a closure has nothing to do with caller
or callee. It has to do with the function that declares the closure,
and with the function that returns it out of the environment
where its globals are defined.

I am not experienced with C# delegates (so double check me), but they
seem just to be functional types, that can have functions, closures,
or methods as instances. This typing ensures that instances are not
misused, as might happen with untyped pointers to functions.  It is
not clear to me whether C# allows changing the closure associated with
a delegate instance, i.e. whether delegate instances are to be
considered functional variables or functional constants. From what I read, it seems to be the former, hence the comparison with function pointer. Why that is necessary to pass functions or methods as parameter is apparently due to specific features of C#. Other languages do not need anything special for that: they just declare the parameter like any other, but with a functional type (i.e. a signature).

I suggest you read the wikipedia articles on closure and possibly scoping
(though I have not read them in enough detail to vouch for their
accuracy).


Why does backtracking work the way it does?

for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly?

You have already tested that 1 and 2 are placed correctly, otherwise you wouldn't call backtrack(3).

Recall that sol[i] = j means that the queen in column $i$ is put at row $j$.  By calling backtrack(k+1) you have already verified that every queen in $1 \dots k$ are placed correctly (non-colliding).


Proof that there is unambigous grammar for every regular language

Something like this might work. First, note that every regular language is accepted by some minimal DFA. Call such a DFA $M$. Next, describe how you could construct a right-regular grammar that accepts the same language as $M$. Take as your set of nonterminal symbols the set $Q$ of states of $M$. Form the set of productions as follows: the smallest set of productions such that if $M$ has a transition from $q_1$ to $q_2$ on $\sigma$,  then there is a production $q_1 \rightarrow \sigma q_2$, and also a production $q_1 \rightarrow \sigma$ if $q_2$ is an accepting state. (You'll also need to add the production $q_0 \rightarrow \epsilon$ if the empty string is in the language).

Now, if this grammar is ambiguous, there are two different derivations for some string. This would imply that, at some point, more than one transition was available in the minimal DFA (since each production corresponds to some transition). This is a contradiction, since there cannot be more than one valid transition at any time while a DFA processes input.

Basically, while you're very right that right-regular grammars can be ambiguous, you can actually construct a specific right-regular grammar that must be unambiguous. All you have to do is describe the method of construction and produce a valid argument why it's right-regular and why it can't be ambiguous.


Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

It is context Free.

You can see it as a union of two languages:
$L_1$ where $j>2i$ and $L_2$ which is very similar to the one of this question.

More information you can find in this question.


Let $A$ be the array; by hypothesis there exists a unique permutation $\pi : A \rightarrow A$ such that $\pi(A)$ is sorted. The minimum number of swaps required to sort $A$ is the minimum $h$ such that there exists a decomposition of $\pi$ in $h$ transpositions.

Certainly $\pi$ can be broken down in at most $n-k$ transpositions where $k$ is the number of cycles in the unique cycle decomposition of $\pi$: it is sufficient to observe that a cycle $(c_1, c_2, \dots, c_l)$ can be rewritten as $(c_1, c_l)(c_1, c_{l-1})\dots(c_1, c_2)$.

It can also be shown that $n-k$ is the minimum, the proof isn't straightforward but it's a known result that you can easily find in literature should you be interested.

As for your multi-dimensional case, the same idea should work, but you should be more specific about what you mean for a multi-dimensional array to be sorted.


Offline scheduling fully determined arbitrary jobs in multiprocessor setting

I think it is going to be tough to find a more efficient algorithm than the one you already have.  You are getting close to requiring an online algorithm.

I think a lot is known about the online version of this problem.  Take a look at:

  Dertouzos and Mok: Multiprocessor On-Line Scheduing of Hard-Real-Time Tasks, IEEE T. Software Eng., 15(12):1497-1506, 1979.

It is known that least laxity first (also known as least slack first) scheduling is an optimal on-line greedy scheduling algorithm for the multiprocessor case only when all the $a_i$ are the same (basically: all the tasks arrive at the same time, but they have different execution times and deadlines.)  Dertouzos and Mok show there is no online algorithm for the case that the $a_i$ are not known a-priori.

What I don't know is whether there is some least-slack-first algorithm similar to list scheduling.  There must be a reference about this, but I haven't found it in the small amount I've looked just now.  Slack is a dynamic quantity.  At any time $t$ for any job $i$ it is the difference between $d_i -t$ and however much work is remaining to be done on job $i$.  The slack of a job starts at the value $(d_i - a_i) - r_i$ and must be monotonically non-increasing.  On imagines that one could take all the jobs, sort them by their initial slack value, and then greedily schedule them in that order, and that (for the case where the processors are identical, there are no precedence constraints, the jobs are all single-threaded, and arbitrary preemption and job migration are permitted and have no cost) you might be able to prove something concrete about it.


Range majority queries - most freqent element in range

If the $N$ items are in ascending sorted order and stored into an array, you can determine a majority candidate in $O(1)$ time for a specified range by returning the item whose index is the range median. Therefore, this will require $O(M)$ time in the worst case for $M$ range queries. Note that the item returned in each query is a candidate: you need to verify if the item actually is a majority element in the range. And, verification is linear in the number of items in the range.

EDIT: explained tradeoff between space and time

If the items are not in sorted order, than finding a candidate element requires in the worst case time linear  in the number of items in the range, using the Boyer-Moore algorithm and constant space (one counter). You can not determine a candidate element in time logarithmic in the number of items in the range while using constant space. However, if you trade space for time, you can determine a majority element in $O(1)$ time at the cost of using linear space.