Are Java and C# also purely interpreted languages?

It depends on what you mean by "crucial", "feasible", and "interpreted."  Certainly applications which many people consider to be crucial are written in C# and Java, so in some sense the answer to your question must be "Yes."  But we can try to dig a little deeper.

While it is true that Java and C# are both compiled into byte code, in general the  byte code is not directly run by an interpreter.  Instead it is Just In Time compiled (jited).  This means that when you run a C# program, the byte code is compiled into native code and cached by the Common Language Runtime (CLR)  (See the documentation for the ngen program for more details).  Many times the compilation will remain in cache until the runtime is updated, so the compilation is only happening a single time, when the the app is started for the first time (its a bit more complicated in practice, but you get the idea.)

Theoretically this means that as new optimizations are added to the framework, or as new processor features become available, the application will be automatically re-jited into a "better" executable.  This means that, theoretically, the performance of a C# or Java program can be better than a C program compiled for a generic processor.

Typically the applications that C# and Java are unsuitable for are embedded applications and realtime applications.  However, this is mostly due to the way that the most common garbage collectors are non-deterministic, and does not have much at all to do with the way the languages are compiled.  Additionally, applications that need to use native libraries, or access memory in very specific ways, may encounter performance problems or other obstacles when implemented in C# or Java, due to auto-boxing, pinning, etc.  However this has more to do with "managed memory" and safety then with compilation.


Finite state automata, multiple completion states?

Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of course:

And yes, having multiple accept states is fine (in fact, some languages require it).


On what abstraction is a filesystem actually built on?

You usually have several layers. You will have a physical level, where complete sectors can be read or written - except on SSD drives, you can only write into an area that is zeroed, and you can only zero sectors 32 or 64 at a time. Much more interesting than a hard drive.

On top of that you have a level that is still in the hard drive. Caches on a hard drive, highly complex controllers on an SSD drive. SSD drives especially need to be handled right to get maximum performance, and that is built into the controller instead of the operating system.

On top of that you usually have one level handling partitioning, possibly one level handle fusioning of partitions on several drives, and a level handling full disk encryption. And you'll build your file system on the highest of those levels.


Extracting non-duplicate cells in a particular matrix with repeated entries

Choose a permutation $\pi$ uniformly at random, and let $P = \{ a_{i, \pi(i)} \mid i\in [n]\}$.  The set $P$ contains exactly one element in each row and each column of given the matrix $A$.

Now consider any pair of entries in $A$ with the same value.  If those two entries lie in the same row or the same column, they cannot both be in $P$.  If those two entries are in different rows and columns of $A$, then the probability that both entries lie in $P$ is exactly $1/n(n-1)$.

There are $n^2/2$ different values in the matrix.  So the expected number of values with both entries in $P$ is at most $n^2/2n(n-1) = n/2(n-1)$.  If $n\ge 4$, this expected value is less than $1$, which implies that the probability of choosing no matching pairs must be positive.


Heuristics for an Artificial Intelligence problem

All white tiles must be moved all the way to the left.  Call the left most position 0.  Then, in the final position, the sum of white distances from the axis is 0+1+...(N - 1).

Calculate this value, the "solution distance" of the tiles up front.  As a heuristic, add the zero-based positions of white tiles up, and subtract from this sum the "solution distance" calculated a priori.

This heuristic gives you a minimal cost of finding a solution (eg. it will cost at least that much to get all white tiles in the correct place).


Why don't they use all kinds of non-linear functions in Neural Network Activation Functions?

I am wondering why they choose functions that always go up and to the right? Why not use [...] ones that are directed down instead of up, etc.?

The activation function is applied to a weighted sum of the inputs of the neuron. Replacing a function that is "directed up" with one that is "directed down" is equivalent to changing the weights. There's no particular reason to prefer an increasing function to a decreasing one, it just happens to be the convention.

Why not use all kinds of crazy input functions, those that fluctuate up and down

In principle, you could. People are using the functions that work best. If somebody found a "crazy" activation function that yielded good results it would certainly get used. However, using a "crazy" activation function probably makes it much harder to train the network. Part of the reason why e.g. ReLU is popular is because its simplicity makes training easier.


"Equivalent device" for testing for NP and coNP?

I will not directly answer your questions, as this would result in explaining the definitions of $\mathsf{NP}$ and $\mathsf{coNP}$, which has been done before. However, using the following hint combined with the definition of the complexity classes indirectly answers your questions.

A modern computer with unlimited memory is equivalent to the concept of a register machine, which in turn is turing equivalent. Thus everything that can be computed on a modern computer with infinite memory can also be computed by a turing machine and vice-versa.

  A Turing Machine can't generate true (undeterministic) random numbers
  while on a computer you may use the noise of the microphone input...

A microphone, or any other hardware-based true random number generator, is an input of the computer. That means the values delivered by it are not computed by the computer itself. Note that you can also model random input by a two-tape turing machine, where one tape contains the random numbers.


Some intuition involves the notion of a convex function. You can look up the formal definition, or consider the quintessential example of a convex function, namely $x^2$. Minimizing a convex function is easy, since there is a unique minimum, and moreover if you start anywhere and keep going done, you will eventually reach the minimum. Maximizing a convex function is a different thing. Suppose for example that you want to maximize $x^2$ under the constraint $x \in [\alpha,\beta]$. In order to do that, you need to compute the function at both endpoints $\alpha,\beta$ and choose the maximum. Now imagine that you function is multivariate and has lots of inputs. Minimizing is still easy - there is a unique minimum that can be reached by descent - but maximizing is problematic, since there are many potential maxima.

MAX-CUT and MIN-CUT are related to the cut function, which gets as input a cut, and outputs the number of edges cut. This is a set function rather than a function on $\mathbb{R}^n$, but it has the property of submodularity, which is a form of convexity for set functions. Indeed, in general one can minimize submodular functions, but maximizing them is NP-hard.


Let's take the case $k = 1$. Consider the CNF $z_1 \land \lnot z_1$. You suggest replacing it by
$$
(z_1 \lor y_{1,1} \lor y_{1,2}) \land (\lnot z_1 \lor y_{2,1} \lor y_{2,2}).
$$
Hopefully you see the problem now.


Prove that the TM which would go over the leftmost position is not decidable

You can reduce the halting problem to your problem. Roughly speaking, the reduction goes along the following lines:

  Given a Turing machine $T$, construct a Turing machine $T'$ which simulates $T$ but never ventures to the left of the starting symbol. If $T$ halts, it then proceeds to go all the way to the left, until it goes beyond the starting symbol.

If you can do this, then you will have shown that LEFT is undecidable.

So how do you construct the machine $T'$? The difficult part is to somehow arrange that it never goes to the left of the starting symbol. Fortunately, this is essentially equivalent to showing that Turing machines with a one-sided infinite tape are equivalent to Turing machines with a two-sided infinite tape. You can look this up in many sources, or come up with a simulation of your own. There are many different ways to do it. Be creative!

One thing which might be unclear is what it means to simulate $T$ without going to the left of the starting symbol. What if $T$ wants to go to the left of the starting symbol? We are not looking for a literal simulation. Rather, we want to simulate each step of $T$ using a series of steps in $T'$, in such a way that the state of $T$ can be read from the state of $T'$. As a simple example, you can think of a Turing machine over the tape alphabet $\{0,1\}$ which simulates a Turing machine with tape alphabet $\{00,01,10,11\}$ by using two cells to store each symbol. We are looking for something similar: simulating a two-sided infinite tape using a one-sided infinite tape.


Assume that you are only given a source vertex and not given the whole adjacency list, then this method won't work.


Multiple choices for a single case in the recursive formula of a Dynamic Programming algorithm

If you want to have two values for each stage, one for $t_{i - 1} = app$ and one for $t_{i - 1} = int$, which are derived from three or two cases respectivelly then you will need to store two dynamic programming values for each stage. Let's name these values for the $i$-th stage $z_{app, i}$ and $z_{int, i}$ respectively. $z_{app, i}$ is the minimum additive value of your objective function for stages up to the $i$-th one if you used (app) in the $i$-th stage, while $z_{int, i}$ has a similar definition. Now let's see what the format of the dp recursion will look like:

$
z_{app, i} = min
\begin{cases}
z_{int, i - 1} + p + (app), & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (app), & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j) + (app), & \text{if } t_{i - 1} = app \wedge r(j) > p
\end{cases}
$

$
z_{int, i} = min
\begin{cases}
z_{int, i - 1} + p + (int), & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p + (int), & \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

Note that that $t_{i - 1} = int$ dictates the use of $z_{int, i - 1}$ which is the optimal value of the previous stage when (int) was used. The case when $t_{i - 1} = app$ is faced similarly by using $z_{app, i - 1}$. We have represented the optimal values of each stage using mutual recursion. Equivalently you can use the following recursion:

$
z_{app, i} = (app) + min
\begin{cases}
z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p\\
z_{app, i - 1} + r(j), & \text{if } t_{i - 1} = app \wedge r(j) > p
\end{cases}
$

$
z_{int, i} = (int) + min
\begin{cases}
z_{int, i - 1} + p, & \text{if } t_{i - 1} = int\\
z_{app, i - 1} + 2p, & \text{if } t_{i - 1} = app \wedge r(j) \leq p
\end{cases}
$

This way the dynamic programming calculations will speed up by a constant factor.


Narrowing the field of a combitorial game

You have discovered the Calkin–Wilf tree, which is the game tree of your game. There is a unique way to reach any pair of coprime positive integers. Given a pair of coprime positive integers, repeatedly subtract the smaller one from the larger one, and you will eventually reach $(1,1)$. Reversing your moves, you obtain the unique way to generate the given (ordered) pair.


Is an integer variable constant or logarithmic space?

The random-access machine is a common model of computation, which is the model of choice when analyzing algorithms. In this model, memory consists of words of length $\Theta(\log n)$ bits, where $n$ is the length of the input (in bits). Therefore both your lecturer and CLRS are right.


If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

Hint: If $A \leq_m B$ then there is a computable function $f$ such that $x \in A$ iff $f(x) \in B$ iff it is not the case that $f(x) \in \text{co-}B$. Can you use this to Turing-reduce $A$ to $\text{co-}B$?


NP-hard has all problems that can be reduced in polynomial time from an NP to them.

Not quite: NP-hard consists of all problems to which every NP problem reduces.

Suppose $X\in \mathsf{P}$. If $\mathsf{P}\not=\mathsf{NP}$, then $SAT$ (for example) is not reducible to $X$. So $X$ is not $\mathsf{NP}$-hard: there are some problems in $\mathsf{NP}$ which do not reduce to $X$.

Note that the class of problems to which some problem in $\mathsf{NP}$ reduces is ... the class of all problems whatsoever! This is because (as you observe) once we discard the "edge cases" $\emptyset$ and $\mathbb{N}$, every problem in $\mathsf{P}$ is also in $\mathsf{NP}$, and problems in $\mathsf{P}$ are trivially reducible$^1$ to everything.

$^1$With respect to polynomial-time many-one reducibility. Change the reducibility, and you potentially change the situation. E.g. $\mathsf{P}$ is $\mathsf{NP}$-hard with respect to exponential-time many-one reducibility, since with respect to this reducibility all problems in $\mathsf{NP}$ are trivial.

The "many-one" bit is why $\emptyset$ and $\mathbb{N}$ are problematic: no nonempty set is many-one reducible to $\emptyset$, and dually no no set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$. This annoyance goes away with more intricate reducibilities, like (variations of) Turing reducibility: literally every problem in $\mathsf{P}$ is reducible to everything with respect to polynomial-time Turing reducibility.

In complexity theory, the default reducibility notion is polynomial-time many-one reducibility. So if we just say "$\mathsf{NP}$-hard" we mean with respect to that reducibility - in which case "there is an $\mathsf{NP}$-hard problem in $\mathsf{P}$" is equivalent to $\mathsf{P=NP}$.


How to find the angle of an arc to draw graphic

I think you have to determine the center C of your circle first. From your drawing, I suppose you want the last black segment to be tangeantial to the circle. Let say this last segment coordinates are P0 (x0, y0) and P1 (x1, y1).

Then the vector is:

vy = y1-y0
vx = x1-x0
with norm vr = sqrt(vy²+vx²)

And the vector vc from P1 to C is (2 choices depending on orientation):

vcy = +R*vx/vr or -R*vx/vr
vcx = -R*vy/vr or +R*vy/vr

then you obtain C coordinates (cx, cy) applying vc to P1. Now, your rotation angle phi must be expressed in the Cxy frame whatever the curve equation you use. The translation from (X, Y) in Cxy to (x, y) in Oxy is:

y = Y+cy
x = X+cx

Now about Bezier cubic curves, the equations you give assume you are starting at theta0=0 which is not the case on your figure. You can compute the starting angle with arctan2 (implemented on most of languages):

theta0 = arctan(-vcy, -vcx)

Then to plot a large angle arc with Bezier you actually have to cut it in small angle curves (let's say 30° max). So cut the (theta0, theta0+phi) angle into several (a, b) angles. NB: phi is negative on your figure (clockwise).

For every (a, b) angle, your Bezier cubic curve equation in Oxy frame is then:

K= 4/3 * tan( (b-a)/ 4)

start : y = cy+R*sin(a)
        x = cx+R*cos(a)

cp1 : y = cy+R*(sin(a)+K*cos(a))
      x = cx+R*(cos(a)-K*sin(a))

cp2 : y = cy+R*sin(b)- K*cos(b))
      x = cx+R*cos(b)+ K*sin(b))

end : y = cy+R*sin(b)
      x = cx+R*cos(b)

I did not not check these equations, I hope there is no mistake in.


is this language regular and why pumping lemma doesn't work?

It's a "trick" question. The language is regular because
\begin{align*}
\{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\}
    &= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\}
       \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\
    &= \{0,1\}^*
       \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\
    &= \{0,1\}^*\,.
\end{align*}


When $c > \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$).

When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a complement of an independent set. (You might need to add a few isolated vertices as well.)


Summary: An algorithm of linear time in $|E|$ can be given by an implementation of Prim's algorithm where its priority queue is $|F|$ queues of equal-weight edges, assuming $|F|$ is a constant.

We will explicitly let $k=|F|$ be a constant. This constantness is indicated by "in such a case we can sort the edges in linear time.". It is then superfluous to "assume that |V|>>k, i.e. the number of vertices is much larger than k", since the complexity analysis by the big $O$-notations is about the behaviour of the algorithm when the input size increases to infinity, skipping the cases when the input size is not big enough.

Let us sort $F$ by constant time. To each edge with weight $w$ that is the $i$-th smallest in $F$ for some $1\le i\le k$, we will reassign weight $i$. Since comparison compatible weights of edges will lead to the same set of MSTs, this weight reassignment, which is done in linear time of $|E|$, does not affect the correctness of all later arguments. So, we will assume, furthermore, $F=\{1, 2, \cdots, k\}$. (We can, alternatively, add this step to the algorithm below.)

Here is the description of a wanted algorithm in detail (given an undirected connected graph $G=(V,E)$ and a weight function $w:E→F=\{1, 2, \cdots, k\}$). For brevity let us call the algorithm Prim's algorithm with constant queues (PAWCQ). PAWCQ is, most probably, more or less the "approach that uses $|F|$ queues" that is mentioned by the OP.

Create $R$ as an empty list of edges.
Mark all vertices as unvisited.
Create $k$ empty lists of edges $L_1, L_2, \cdots, L_k$.
Select an arbitrary vertex $v_0$. Iterate through all edges incident to $v_0$, putting an edge in $L_i$ if its weight is $i$. Mark $v_0$ as visited.
Repeat the following steps until all $k$ lists are empty:

Find the non-empty list with lowest subscript.
Remove an element from the list just found. Name that element $e$.
If both vertices of $e$ are marked visited, do nothing. Otherwise, let $u$ be the vertex marked unvisited. (The other vertex must be marked visited). Iterate through all edges incident to $u$, putting an edge in $L_i$ if its weight is $i$. Mark $u$ as visited. Add $e$ to $R$.

return $R$.

We can see that PAWCQ is indeed a variation of Prim's algorithm. In particular, it will always terminate in finitely many steps to return an MST of $G$.

The time complexity of PAWCQ is asymptotically  linear in $|E|$ when $G$ is given by its adjacency list (in the usual computation models), since both the insertion of an edge into the constant queues and the removal of an edge from the contant queues take constant time and each edge is inserted once and removed once.

Note that the order in which we remove an element in step $5.2$ does not affect the correctness of the algorithm. We can implement each list as, for example, a FIFO queue or a FILO stack.

Note that we can speedup the algorithm in several places for better performance, such as ending the algorithm as soon as we have collected $|V|-1$ edges. However, none of them will improve the big $O$ complexity since $O(|E|)$ is the best possible.


Question about growth rates of functions involving n and logn

There exists some $n_0 > 0$ such that $\log n \le n^{0.0001}$ for all $n \ge n_0$.
This can be seen, e.g., by taking the limit:
$$
\lim_{n \to \infty} \frac{\log n}{n^{0.0001}} =
\lim_{n \to \infty} \frac{10000}{ n^{0.0001}} = 0.
$$

This means that, for $n \ge n_0$,
$$
f(n) = \log^{100} n + n^{0.01} \le  \left( n^{0.0001} \right)^{100} + n^{0.01} = 2n^{0.01}.
$$

Therefore, using the fact that $g(n) \ge n^{0.05}$:
$$
\lim_{n \to \infty} \frac{f(n)}{g(n)} \le
\lim_{n \to \infty} \frac{2n^{0.01}}{n^{0.05}} =
\lim_{n \to \infty} \frac{2}{n^{0.04}} =
0,
$$
implying that $f(n)=o(g(n)).$


Lambda calculus : what about the bound variables in substituting expression?

$x$, $y$, and $v$ are variables not (arbitrary) terms. To the extent that it makes sense to say so, the only variable free in $v$ is $v$. There could still be an issue with, say, $M = \lambda v.x$, i.e. $[v/x]\lambda v.x$, but, by assumption, $v$ is not bound in $M$, so this is not a valid case; $v$ is clearly free in $vPQ$.


Time complexity for balancing an unbalanced binary tree

Do an inorder traversal of the BST...and store it in an array
the array will be sorted.
next construct a balanced binary search tree from this array.
1) Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
    a) Get the middle of left half and make it left child of the root
          created in step 1.
    b) Get the middle of right half and make it right child of the
          root created in step 1.

Time Complexity of both inorder traversal and AVL tree construction is O(n).


For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy.  The intuition is that these hash functions are designed to "have no structure", so they don't admit anything like this.

In technical terms, modern cryptographic hash functions behave "like a random oracle".  For a random oracle, there is no such closeness predicate: the best you can do appears to be to invert the hash function and then enumerate all close strings and hash them.  As a result, there's no way to do this for modern cryptographic hash functions.

Heuristically, it does possible to design a custom hash function which does admit an efficiently closeness predicate, and which is (roughly) "as secure as possible" given this fact.  Let's assume the strings we are going to hash are of fixed length.  Suppose we have a good error-correcting code, and let $D$ be the decoding algorithm (so it maps a bit-string to a nearby codeword, if it can).

To get a simple but imperfect scheme, imagine defining $h(x) = \text{SHA256}(D(x))$.  If $x,y$ are two random strings that are sufficiently close, then there is a decent chance that $h(x)=h(y)$.  If $x,y$ are not close, then $h(x)$ will look nothing like $h(y)$, and we'll get no information beyond the fact that $x,y$ are not close.  This is simple.  However, it is also imperfect.  There are many pairs $x,y$ that are close but where we can't detect this fact from $h(x),h(y)$ (e.g., because the decoding function $D$ fails).

Heuristically, it looks possible to improve this construction.  At design time, choose random bit-strings $r_1,\dots,r_k$.  Now, define the following hash function:

$$h(x) = (\text{SHA256}(D(x \oplus r_1), \dots, \text{SHA256}(D(x \oplus r_k)).$$

Now if $x,y$ are sufficiently close, it is likely that there exists $i$ such that $D(x \oplus r_i) = D(y \oplus r_i)$, and thus $h(x)_i = h(y)_i$.  This immediately suggests a closeness predicate: if $h(x)$ matches $h(y)$ in any of its $k$ components, then $x,y$ are close; otherwise, infer that they are not close.

If you additionally want collision resistance, a simple construction is the following: let $h_1(\cdot)$ be a hash function with a closeness predicate; then $h(x) = (h_1(x), \text{SHA256}(x))$ is collision-resistant (any collision for this is also a collision for SHA256) and has a closeness predicate (simply use the closeness predicate for $h_1$).  You can let $h_1(\cdot)$ be the hash function defined above.

This is all for Hamming distance.  Edit distance is probably significantly harder.

In coming up with the above construction, I was inspired by the following paper:

Ari Juels, Martin Wattenberg.  A Fuzzy Commitment Scheme.

Ari Juels, Madhi Sudhan.  A Fuzzy Vault Scheme.  Designs, Codes, and Cryptography 38(2): 237-257, 2006.

Incidentally: in cryptography, hash functions are unkeyed.  If you wanted a keyed thing, you might want to take a look at pseudorandom functions.


Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?

At a broad level, there are two types of optimization: continuous optimization, and discrete optimization.  They tend to use different techniques.

Continuous optimization deals with problems where the parameters are continuous; methods include gradient descent, Newton's method, and other iterative methods, linear programming, and more.

Discrete optimization, or combinatorial optimization, deals with problems where the parameters come from a finite site; methods include integer linear programming, SAT, simulated annealing, particle swarm optimization, and more.

Genetic algorithms are another technique.  However, my experience is that they are rarely the best one; other methods often beat genetic programming and evolutionary optimization methods.  Your experience may vary.


Deciding which logical proposition is stronger

The notion of strength of a proposition comes from its power to constrain the model. For instance the proposition $P1 : x = 2$ is stronger than $P2 : x \geq 2$ in Arithmetic. And in propositional notation this can be written as $P1 \Rightarrow P2 $.

The stronger the proposition the harder it usually is to prove. On the other hand, if proven it provides more corollaries.

For instance for a signature with 2 propositional symbols $P$ and $Q$ we have the following partial diagram for the Strength relation.

Now to your examples. $\textrm{False}$ happens to be an extreme case. It can never be satisfied. If you are using propositions to constrain your search space for an answer, then $\textrm{False}$ says: "Call off the search and start again". The other extreme is the proposition $\textrm{True}$. It is trivial. It gives absolutely no information on where to look for the answer.

Now we shall use this intuition to tackle your questions:

1) True, False

Since $\textrm{True}$ is a trivial constraint, you would not be able to derive anything non-trivial out of it, this certainly means that you would not be able to derive the extreme constraint $\textrm{False}$.

  $\not\vdash \textrm{True} \Rightarrow \textrm{False}$

2) True, True

The propositions have exactly the same strength, they are equivalent

  $\vdash \textrm{True} \Rightarrow \textrm{True}$

3) False, False

The propositions have exactly the same strength, they are equivalent

  $\vdash \textrm{False} \Rightarrow \textrm{False}$

And an extra case

4) False, True

  $\vdash \textrm{False} \Rightarrow \textrm{True}$

Note: there is an issue with saying that proposition $P$ is stronger than $Q$ if $P \Rightarrow Q$ is a tautology since intuitively the relation of being stronger is strict. It would better align with the intuition if we were to say that proposition $P$ is stronger than $Q$ or of equal strength if and only if $P\Rightarrow Q$.


Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)

It certainly depends on the data structure used to represent the DAG.

We will use a data structure that I am going to call the characteristic-hash-vector (CHV). Given a graph $G$ of size $n$, and a subgraph $S \subseteq G$, the characteristic vector $X_S$ is the vector of size $n$ that has a 1 for each node in $S$ and a 0 for all other elements. The CHV is a way of representing the characteristic vector using a hashmap. Given a subset $S$, each node $v$ in $G$ is mapped to $X_S(v)$.

Let's try representing the DAG as a set of nodes, and with each node $x$, maintain a CHV for incoming nodes $y$ (there exists a directed edge from $y$ to $x$) and a CHV for outgoing nodes $w$ (there exists a directed edge from $x$ to $w$). Then, it is easy to find a node with no incoming edges. Start with any arbitrary node, and then pick any arbitrary node from its incoming CHV, and so on, until we reach a node with an empty incoming CHV. By the proof the earlier in the section, we know that this search will terminate in $O(n)$ time.

Then, we go to each node in this final node's outgoing CHV, and remove the final node from its incoming CHV (this is where we use the constant-time properties of hashmaps/CHVs). This process also takes $O(n)$ time.

Thus, we have a runtime of $O(n)$ for each iteration of the loop in the algorithm to compute a topological order for a DAG.


How does a compiler give an immediate compilation error?

I'll talk about relatively simple (for the sake of analysis) languages, like C#/Java. There may be different approaches aside from want I describe here.
What IDE does during analysis is not compilation
The primary goal of IDE is not compilation, it's to assist you with code writing/analysis. For example, IDE helps you with auto-completion, refactorings (renames, indentation, dead code removal, simplifying the code), navigation (go to definition, find usages), code generation (overriding equals()/hashCode(), creating constructors, properties generation), and many, many other tasks. On the other hand, it doesn't care about resulting code efficiency, linking, and other compilation-related stuff, but e.g. it cares about preserving comments and spaces (compilers can simply throw them away). It means that IDE can (and will) use completely different structures to work with.
Code analysis
The code analysis can usually be split into three steps, in this order (for C++ these steps are mixed, which makes it a hard language):

Lexical analysis: the input is split into a sequence of tokens. E.g. a + b becomes [IDENT(a), PLUS, IDENT(b)].
Syntax analysis (or parsing; they are not exactly the same, but doesn't matter now): builds a syntax tree. E.g. a + b can be parsed as PlusExpr(left=IDENT(a), PLUS, right=IDENT(b)). c = a + b; can be parsed as AssignmentStatement(left=IDENT(c), EQ, right=PlusExpr(...), SEMICOLON).
Semantic analysis. Surely a huge field, with a lot of tasks, but for now let's only care about name resolution (finding declarations) and type checking.

Error detection
Errors types detected by IDE correspond to code analysis steps outlined above.

Lexical errors: e.g. you use some invalid token (e.g. 0gda) or you didn't close a string literal (e.g. "abc<EOF>). Usually, lexical analysis is lightning fast, and such errors are trivial to detect. To continue lexical analysis (to detect more errors and allow syntax analysis), bad literals can be ignored or fixed (e.g. the analysis can treat "abc as "abc").
Syntax errors: e.g. you forgot a semicolon c = a+b<EOF>, closing parenthesis c = (a+b;, etc. Detecting the errors is simple. A tricky part is to recover from the errors. E.g. in c = (a+b; you can assume that there should be ) before ;, report error, and continue parsing. Anyway, while error recovering is nontrivial (and often requires manual handling), it's usually performed reasonably well.
Semantic errors. I'll talk about errors like "Undefined identifier" and "wrong type" next.

Name/Type errors
In Java, there are no identifiers that come from nowhere (this is one of the reasons why Java is a relatively simple language for analysis). The sources are (as I recall):

import statements.
Identifiers declared in the same scope. E.g. when you define class A at the top level of the file, this class can be used anywhere in the file; when you write for (int i; ..., i can be used in the body of the loop.
With qualifiers. E.g. if you have an object a, which has a method b, you can write a.b.

These lead to the following structures:

For import statements, you have a global structure that analyses all source files and all linked libraries. This structure is a trie which represents a global name hierarchy. So if you've written import java.util.*, it follows the path <root>->java->util and includes all identifiers in the found node into the current file scope.

For scopes. Consider an example:
class A {
    int f() {
        if () {
            print(a);
        }
    }
}

In this example, when we try to resolve a, we try to find a declaration (in this order): 1) inside if-block, 2) inside f(), 3) inside class A, 4) in the file scope (i.e. because of imports). When the name is found, the search is done.
Therefore, for scopes, it suffices to maintain a stack-like structure: each level of the stack represents a scope and has all the names defined in this scope. When trying to find a declaration, you process the stack layer-by-layer.

For qualifiers: for a.b, when resolving b, you assume that you've already resolved a (using the above rules). Moreover, you assume that you know the type of a; it means that the above structures should maintain the types of all identifiers (which is easy to do by looking at the type at the declaration; this is another aspect that makes Java simple). Now, you simply check whether the type has a member b and which type it has.

With the above analysis, the type analysis is simple: for each identifier you know its type, and you know which type you expect: e.g. in f(x,y), if you know (after resolution) that f is a function (int, int) -> int, you know that x and y should have type int.
Why it can be done fast
All these structures can be maintained on-the-fly. In the hierarchy trie, the only modified nodes are the nodes corresponding to the current file. The scope stack and access with qualified correspond only to the current file (so you simply need to re-analyze the file).
Also, some optimizations may be used to re-analyze only a portion of the file (e.g., if you make edits inside some function, there is a chance that you need to re-analyse only this function).
Actually, the slowest operations are the following:

Building the hierarchy when the project is first opened.
Loading the hierarchy when the project is reopened. This is indeed an issue, and a lot of efforts may be required to make this efficient.
Rebuilding the hierarchy when a lot of files change simultaneously (e.g. because of git pull).

Solution-wide analysis
I was talking about finding errors in the current file.
However, editing the current file may break something else: e.g. if you remove a method from a class, all files using this method will break (the above structures can't detect it unless you open the affected file). This requires a Solution-wide analysis, which, well, analyses your entire project in real-time.
This analysis requires much more resources though (at the very least, you need to track all usages of all identifiers, and I believe there is a lot of other stuff going on there), not every machine can handle it on a large project, and it may take some time (few seconds, as I recall) for errors to be detected.


Finding the number of intersections of $n$ line segments with endpoints on two parallel lines

Since all points are distinct, this is a version of the Counting Inversions problem. First, sort the points $p_1, \dots, p_n$ in order of increasing $x$ coordinate to obtain an ordered list $p[1],p[2], \dots, p[n]$. We now relabel the points $q_1, \dots, q_n$ with respect to this new ordering of the $p$'s such that $p[i]$ and $q[i]$ are endpoints of a line segment, for all $1 \leq i \leq n$. Altogether, these steps take $O(n \log n)$ time.

Now, we want to count the number of inversions in $q[1], \dots, q[n]$; an inversion is a situation where $i < j$ and $q[i] > q[j]$ (we compare the points by their $x$ coordinates). This is because $i < j$ implies $p[i] < p[j]$ by construction, and $p[i] < p[j]$ and $q[i] > q[j]$ if and only if the line segments $(p[i], q[i])$ and $(p[j], q[j])$ intersect. Hence, the number of line segment intersections is precisely the number of inversions in $q[1], \dots, q[n]$.

There is a well known divide and conquer approach for counting these inversions. Can you take it from here?


Not understand exchanging argument proof for optimal prefix code

What Kleinberg and Tardos show is that given a tree $T$ containing a node with a single child, they can come up with a strictly better tree $T'$, showing that $T$ isn't optimal. Therefore an optimal tree cannot have a node with a single child. Whether this qualifies as an exchange argument or not is not so important.

More generally, the form of the argument is "if X doesn't satisfy P then X is not optimal; hence any optimal X satisfies P". In order to show that X not satisfying P cannot be optimal, they modify X to obtain a better X'. This is a common enough pattern which doesn't usually have a name attached to it.


If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?

Let $D(i)$ denote the number of descendants of the $i$th node.  In a min-heap, all $D(i)$ nodes below node $i$ must have a larger value than node $i$.  Hence, the $n-D(i)$ largest values $n-D(i)+1,\ldots,n$ cannot be put in node $i$.  It turns out that $n-D(i)$ can be put in node $i$, and so the maximum possible value for node $i$ is $n-D(i)$.  To see how this can be achieved, fill in the descendants of node $i$ by $n-D(i)+1,\ldots,n$, and fill in the remaining nodes in any way so that the min-heap property is satisfied.  The integers available for the parents of node $i$ are all less than $n-D(i)$ and so the min-heap property can be satisfied.  The sibling  of node $i$, the siblings of the ancestors of node $i$, and the descendants of these siblings, all necessarily contain values smaller than node $i$ because the values larger than $n-D(i)$ have been used up, and this is fine because we want node $i$ to have the largest possible value. There is no violation of the min-heap property, which only concerns relations between a node and its parent (and therefore all its ancestors) or its children.

To obtain the smallest possible value for node $i$, let $A(i)$ denote the number of ancestors of node $i$.  This value is the number of nodes in the unique path from the root to node $i$ (including the root node but not including node $i$).  These $A(i)$ nodes must have values less than node $i$, and so the smallest possible value for node is at least $A(i)+1$.  Is this bound achievable?  Yes, put values $1,2,\ldots,A(i)+1$ as the values on the path from the root node to node $i$ (where node $i$ takes value $A(i)+1$).  Observe that the remaining nodes can be filled in with the remaining values in such a way that the min-heap property is satisfied.  The sibling of node $i$, the siblings of the ancestors of node $i$, and the descendants of all these siblings, as well as the descendants of node $i$, will all have a larger value than $A(i)+1$, and this doesn't violate the min-heap property.


Finding the base case for T(n) = T(n - a) + T(a) + cn

Every $0\le k\le a$ yields the base case $T(k)$.
If you are trying to solve the big-O of the recurrence, then you may as well assume that there is some $c$ where $T(k)\le c$ for every base case $k$. It will help making the computation a bit easier


How to evaluate recommendation engine without ground truth?

One of the best ways to benchmark such big systems is to use a service like Amazon Mechanical Turk (AMT). First you implement a user interface for everyday users where they could specify whether or not the recommendations are relevant. Then you submit this to Amazon Turk and let many people try it out.

You could further process the results of an Amazon Turk to really benchmark your system and obtain quantification of accuracy of it.

Team of Fei Fei Li used similar technique for benchmarking their Fine Grained segmentation algorithm. The paper is here: http://vision.stanford.edu/pdf/DengKrauseFei-Fei_CVPR2013.pdf

Naturally using AMT won't give you a realtime solution, where you get a benchmark everytime a recommendation occurs, however you can prepare a subset of your dataset and let AMT guys evaluate the system using GUI you provide. Again, a sample data collection system is described here: http://ai.stanford.edu/~jkrause/papers/fgvc13.pdf

I have no intention of advertising it but AMT is also an economical workaround.


Computing exam averages in less than linear time

To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this for, this problem should take at least $\Omega(c \cdot r)$ time.


A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.

A straight-line program for a finite group $G$ is a straight-line program in a very simple language with an unlimited number of registers $r_1,r_2,r_3,\dots$ and with only two legal operations:

$r_i := \text{inverse}(r_j)$
$r_i := \text{multiply}(r_j,r_k)$

You specify $i,j,k$ for each line of the program; those are constants.  Each register holds a group element.

For instance, the following is a straight-line program that computes the cube of the element in $r_1$ and stores the result in $r_3$:

$r_2 := \text{multiply}(r_1, r_1)$
$r_3 := \text{multiply}(r_1, r_2)$

Here is another program that computes the same thing, but in a different way:

$r_2 := \text{multiply}(r_1, r_1)$
$r_4 := \text{multiply}(r_2, r_2)$
$r_5 := \text{inverse}(r_1)$
$r_3 := \text{multiply}(r_4, r_5)$


Does indirect diagonalization a relativize technique?

Buss and Williams codified the technique in their paper Limits on alternation-trading proofs for time-space lower bounds, and showed that the best bound that it can give is that SAT cannot be solved in time $n^{2\cos(\pi/7)}$ and space $n^{o(1)}$. This bound had been achieved earlier by Williams in his paper Alternation-Trading Proofs, Linear Programming,
and Lower Bounds.


Given two DFA's accepting the same language, does one have to refine the other?

For an integer $n$, consider the following DFA $A_n$ on the alphabet $\{a\}$. The set of states is $\{q_0,\ldots,q_{n-1}\}$. The initial state is $q_0$. All states are accepting. The transition function is $\delta(q_i,a) = q_{i+1}$, where we identify $q_n$ with $q_0$.
Do the relations of $A_2$ and $A_3$ refine each other?


Why should an average programmer learn automata theory?

Automata theory is rarely used by practicing programmers today.  It is in principle useful for building compilers and parsers (though most developers don't need to do that today, and often use tools to help them).  Some of the concepts can be useful for building state-machine based systems, which are widespread (including, e.g., embedded systems), though it's not clear you need to know all the ideas from automata theory to be successful at that.  Also, many people study theory even if there is not a direct practical application.


Error correction code without error detection

You might be interested in the binary erasure channel, in which each symbol is erased with probability $p$. The capacity of this channel is $1-p$, and there are practical erasure codes that achieve it.
In the second scenario you describe, some symbols are erased, and some are received with error. This is known as the binary symmetric error channel, and there is some work on it.
Finally, if each symbol is associated with a confidence, then the corresponding notion of decoding is soft decoding.


If R is a regular language, is $R^3= R \circ R \circ R$ also regular?

'$R$'
 is not used in the literature to indicate languages ... generally we use $L$.
Anyway, the "$\circ$" operator indicates the concatenation of two or more languages. Keep in mind that the concatenation of regular languages is also regular: you can proove this by 'linking' the NFA's/DFA's thath recognize them.
In this case you are concatenating a regular language with itself, so the resulting language is also regular.

NB:
The opposite is not always true: if the concatenation of two languages is regular, this does not mean that the languages themselves are necessarily regular.


Check the definitions (as commonly used in Computer Science, mostly for run time or other resource consumption):

$f(n) = O(g(n))$ if there is a constant $c_1 > 0$ so that for some $N_1$ we have for $n \ge N_1$ that $f(n) \le c_1 g(n)$

$f(n) = \Omega(g(n))$ if there is a constant $c_2 > 0$ so that for some $N_2$ we have for $n \ge N_2$ that $f(n) \ge c_2 g(n)$

$f(n) = \Theta(g(n))$ if both $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$

$f(n) = o(g(n))$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 0$

$f(n) \sim g(n)$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 1$

$f(n) = \omega(g(n))$ if $\lim_{n \to \infty} \dfrac{f(n)}{g(n)} = \infty$

You see that $f(n) = \Omega(g(n))$ (one part of $f(n) = \Theta(g(n))$) and $f(n) = o(g(n))$ can't be true simultaneously (check the definition of the limit).


There is no general way to do this. The "space of algorithms" is not a nice one, with a natural metric or other nice properties, unlike e.g. the real numbers. Note that even in the case of trying to solve $f(x)=0$, where your search space is $\mathbb{R}$, most algorithms work under several assumptions on $f$, e.g. continuity (there is no algorithm which can solve/approximate $f(x)=0$ for an arbitrary $f:\mathbb{R}\rightarrow\mathbb{R}$).

See the answers here, and also here for simple impossibility results regarding a general approach for optimizing the running time of an algorithm.


A variant of job assignment (scheduling) problem with variable time span

I searched for "job shop scheduling uncertain processing times" and came up with this: http://www.waset.org/journals/waset/v64/v64-190.pdf.  I hope it helps.

I think you will find that the best approximation algorithm is going to depend on the probability distribution of completion times.  An algorithm for exponentially distributed times might be very different than an algorithm for a uniform distribution.

I think you will also need to trade off expected completion time vs. variance.  With known completion times a decent approximation algorithm is Coffman's list scheduling algorithm: sort the jobs by length (longest to shortest) and then schedule greedily (next job starts as soon as a machine is free.)  With uniform completion times you might try sorting by best-case completion times, expected completion times or worst-case completion times, and you would be getting different answers.


Finding optimal multiplication order and optimal binary tree

This is the classic problem of matrix chain multiplication.

Here is the pseudocode in Java from Wikipedia, which computes, for each $2 \le k \le n$, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It runs in $O(n^3)$, where $n$ is is the number of matrices, assuming the number of rows and columns in all matrices are bounded by a constant.

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// The first index for dims is 0 and the first index for m and s is 1.
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}

You can check that Wikipedia page for more information. In particular, there is a ready-make java implementation. There is also explanation to a much more complicated algorithm that runs in $O(n\log n)$ time.


Choosing error rates for probabilistic algorithms

This is the arithmetic for Juho's answer.  (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability).

Suppose it takes time $t$ seconds to perform one computation, and thus time $kt$ to get the algorithm error probability down to $2^{-k}$.

Suppose that the hardware probability of failure per second is $p$.  Then the probability of a hardware failure is approximately $ktp$ (see lemma below).  So you want the $k$ that is the solution to

$$ \frac{1}{2^k} = ktp. $$

Lemma

Assume a memoryless failure process with a failure rate per time period of $p$.  Let $P=1/p$ (makes the arithmetic easier).  Then for very small $p$ (large $P$) the probability of success in $k$ time periods is

$$ 1 - (\frac{P-1}{P})^k = \frac{P^k - (P-1)^k}{P^k}.$$

By the binomial theorem this is

$$ \frac{P^k - P^k +kP^{k-1} + \frac{k(k-1)}{2}P^{k-2} + \cdots }{P^k} \approx \frac{k}{P} = kp.$$

Value of $p$

Also assuming memorylessness and independence and all that good stuff, the numbers in the paper that Juho provided give a failure rate (memory, disk and cpu) of about $1/180$ in 5 days, which is 432000 seconds, so the probability of failure in 1 second is something like $p = 1/77543800 \approx 2^{-26}$, but you want a lower probability than that, so you should probably use $2^{-27}.$

Thus you want k such that

$$ 2^{27-k} \lt kt$$
$$ 27-k \lt \log_2 k + \log_2 t $$
$$ 27 - \log_2 k - \log_2 t \lt k.$$

But for $k > 1$, $\log_2 k > 0$ so choose

$$ k > 27 - \log_2 t.  $$


Non-uniform random distribution: How do I get a random between 100 and 180 that is on average close to 120? (like in a Gaussian distribution)

Your problem is rather vague: "bell curve" and "centered around i" are not well defined.

One possible recipe is to generate a truncated gaussian: define s= min(b-i,i-a)/c where c is a free parameter (suggested values:  [1,3] range), generate a gaussian with mean i and standard deviation s  - and round it to the nearest integer. If the value falls outside the [a,b] range, try again.

Related.


The following algorithm should work.

The algorithm proceeds in several rounds. At each round, let $m'$ be the number of remaining items to take. Take one item per key, up to $m'$ items, and remove these items. If we took $m'$ items, the algorithm terminates. Otherwise, continue to the next round.

We leave the correctness proof (or a counterexample) to the reader.


Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

The Wikipedia page on König's theorem gives an algorithm that converts a maximum matching to a minimum vertex cover. I'm not sure that an algorithm for finding maximum matching can be tweaked to an algorithm for finding minimum vertex cover in any other way, though it's perfectly possible.


What are the conditions that make the A* algorithm optimal over the other unidirectional search algorithms

This is a nice question! Indeed, A* is known to be asymptotically optimal in the number of expansions. This is usually understood by saying that any algorithm solving the same problem should expand the same set of nodes at least. A unique property of A* with regard to its asymptotical behaviour is that, in addition, it never re-expands any nodes ---in contraposition with other algorithms such as IDA* and RBFS.

But first things first. Before addressing why A* is asymptotically optimal let me note in passing that A* is a suitable algorithm not only for the shortest path problem but those problems that actually verify the suboptimal structure, this is, that all the subpaths in the solution are solutions also between their respective start and end nodes. Additionally, A* is asymptotically optimal not only with regard to evaluation functions $f()$ which are scalar values but, in general, with any that verify the so called cost algebras.

In the following I address the question by mentioning the two contributions of A* that address its asymptotically optimal behaviour and also the role played by the heuristic function $h(n)$.

From the preceding paragraph, the first condition is that $f()$ should be non decreasing, i.e., $f(n) \leq f(n')$ where $n'$ is a descendant of $n$. This property is exploited by Raphael, Hart and Nilsson (the authors of A*) to create a CLOSED list that stores all nodes that have been previously expanded: if a node which is about to be expanded is found in CLOSED, then it is not expanded again even if its $f$-value is larger. The reason is simple: If that node was already expanded, a shortest path cannot go through a more expansive subpath (hope you see here how the principle of suboptimal structure applies). The second contribution of A* is that all newly generated nodes are inserted in an OPEN list and they are sorted in increasing order of their $f$-value. This guarantees that no node with a $f$-value strictly larger than the cost of the optimal solution is ever expanded.

In general, both conditions are also satisfied by Dijkstra's algorithm and, from here, by any of the so called Best-first search algorithms. A* is different from those however in the design of the $f$ evaluation function which is defined as $f(n)=g(n)+h(n)$. Now, if $h(n)$ is admissible, i.e., it never overestimates the effort to reach the goal then it is non-decreasing and, from here, optimality of the solutions found can be guaranteed.

Note, however, that some nodes with a $f$-value equal to the optimal cost might be expanded by A* whereas they are not needed at all. Some works, such as EPEA tried to address this issue with the design of specific operator tables.

Hope this helps,


I think proper here just means that the IP address in CIDR notation is the first address in the range specified by the IP address and its prefix.

This is the case for 192.168.23.0/24 and 10.57.13.64/28 and not the case for 193.205.16.132/26 (whose first address in the network range is 193.205.16.128) and 172.16.4.0/20 (whose first address is 172.16.0.0).


Binary Search Tree – Number of comparisons when element is not found

There are only 4 comparisons: the element 6 is compared to the elements 9,7,4,5.


Numerical Accuracy & Sorting Algorithms?

I'll give you a simple example.

Suppose you have some floating-point numbers to add together. We'll assume they're all non-negative so that cancellation isn't an issue.

For the purpose of this example, I'm going to use decimal with four significant digits of precision just to illustrate the point.

The numbers are:

1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e-4
1.000e+0

That is, ten copies of 1e-4 and one copy of 1.

This sum can be perfectly represented in our toy floating-point format:

1.001e+0

But the answer that you get depends on what order you do the additions! If you start at the top of the list and work your way down, the partial sums are:

1.000e-4
2.000e-4
3.000e-4
4.000e-4
5.000e-4
6.000e-4
7.000e-4
8.000e-4
9.000e-4
1.000e-3
1.001e+0

But if you start at the bottom and work your way to the top, the partial sums are:

1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0
1.000e+0

Clearly, you need to add the small numbers first. So here are two possible algorithms.

Sort the numbers into ascending order, then sum them in that order.
Insert the numbers into a priority queue. Remove the two smallest numbers, add them, and insert the sum back into the priority queue. Repeat until there is one number left.

Exercises:

Is there a set of numbers for which these two algorithms return different answers?
Is one of these algorithms better than the other, in the sense of always returning a more accurate final answer?
Can we do even better?


Is finding a solution of a satisfiability problem harder than deciding satisfiability?

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment.  This is because all NP-complete problems are downward self-reducible.

From Wikipedia:

Self-reducibility

The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula $Φ$. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula $Φ$$\{x_1=TRUE\}$, i.e. $Φ$ with the first variable $x_1$ replaced by $TRUE$, and simplified accordingly. If the answer is "yes", then $x_1=TRUE$, otherwise $x_1=FALSE$. Values of other variables can be found subsequently in the same way. In total, $n+1$ runs of the algorithm are required, where $n$ is the number of distinct variables in $Φ$.


Proof required for edges in a minimum spanning tree

Hint: Assume the contrary, that is, there exists at least one MST that contains the heaviest edge of some cycle in G. What happens if you remove that edge from MST? May it be the case that another edge in the cycle can play the 'role' of e in MST?


Based on the following observation, you can derive a $O(\sqrt{n})$ time algorithm ( by computing the sum on the right-hand side naively in a $O(\sqrt{n})$-sized loop): (For $n=10^{12}$ this yields $n=10^{6}$ which is enough for say competitive programming sites which usually allow ~10^8 operations)

For any positive integer $n$, Let $k=\lfloor\sqrt{n}\rfloor$:
$$
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor = 2\sum_{i=1}^k  \left\lfloor\frac{n}{i}\right\rfloor - k^2
$$

This post on Math StackExchange provides a clear visual proof of the equality above.
The following is a proof for the equality above that does not depend on a graph.
All variables below stand for positive integers. Let us fix $n$ and $k=\lfloor\sqrt{n}\rfloor$. For all $i, j\le n$, let
$\delta(i,j)=1$ if $i\cdot j\le n$. $\delta(i,j)=0$ otherwise. In particular,

$\delta(i,j) = 1$ if $i,j\le k$.
$\delta(i,j) = 0$ if $i,j\ge k+1$.

Proposition. $\left\lfloor\dfrac{n}{i}\right\rfloor = \displaystyle\sum_{j=1}^n \delta(i,j) $ for all $i$.
Proof. Both sides count the number of positive multiples of $i$ that are smaller than or equal to $n$. $\ \checkmark$
$$\begin{aligned}
\sum_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \left\lfloor\frac{n}{i}\right\rfloor \\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \sum_{j=1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{i=k+1}^n \sum_{j=1}^k \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{j=1}^k \sum_{i=k+1}^n \delta(i,j)\\
&= \sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 + \sum_{j=1}^k\left(\sum_{i=1}^n \delta(i,j)-\sum_{i=1}^k \delta(i,j)\right)\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 - \sum_{j=1}^k\sum_{i=1}^k \delta(i,j))\\
&= 2\sum_{i=1}^k \left\lfloor\frac{n}{i}\right\rfloor
 - k^2 \quad \checkmark \\
\end{aligned}$$
The proof above is, basically, a direct translation of the visual proof.


How to deal with questions having two or more asymptotic notations

No, this is not the right way to think about this question. To get you on the right track notice that $f(n) \in \Theta(f(n))$ no matter what. This should give you the right intuition. However, you can't prove equality with just one function taken from $\Theta(f(n))$ you have to consider an arbitrary function.

If you work through carefully (I won't give you the step-by-step since active learning is important), you will see that $\Omega(\Theta(f(n))) = \Omega(f(n))$. To test your understanding after you figure this out, make sure that you can also show that $\Omega(O(f(n))) \neq \Omega(f(n))$.

The intuition you should keep in mind (that you have to make rigorous by carefully understanding this table) is that $\Omega$ is kind of like $\geq$, $O$ is kind of like $\leq$ (for lower case of both, make them strict inequalities), and $\Theta$ is kind of like $=$. But this is only heuristic intuition. Make it precise on your own, and see if you can find any weird functions that might serve as counter-examples.


They second quote from Wikipedia has lost its context. Here it is complete, with emphasis added:

Another special type of linear grammar is the following:

linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

A linear grammar has at most one non-terminal on the right-hand side of any rule, as per Linz' definition.
But any linear grammar can be transformed into an equivalent linear grammar of that special type, simply by adding a new non-terminal. Wikipedia goes on to show an example of this transformation. So it is possible to assume wolog that a linear grammar is in that form, if it turns out to be helpful.


Shortest path in a weighted graph with coloured edges

Replace each vertex $x$ by $C$ vertices $(x,c)$, where $C$ is the number of colors (actually you only need the colors that appear in edges adjacent to $x$), and connect these vertices by edges of weight $K$. Replace an edge $(x,y)$ of weight $w$ and color $c$ by an edge $((x,c),(y,c))$ of weight $w$.

You can now solve your problem by running Dijkstra's algorithm on the new graph $C^2$ times. You can optimize this approach so that you only need to run Dijkstra's algorithm once by adding two new vertices $A,B$ and connecting $A$ to the vertices $(A,c)$ with directed edges, and similarly connecting the vertices $(B,c)$ to $B$ with directed edges.


Two Generals Problems - What's wrong with my approach?

New answer
After thinking some more and searching around for a bit I beleive both of your approaches are already implemented in TCP, as can be seen here:

[...] Acknowledgements (ACKs) are sent with a sequence number by the receiver of data to tell the sender that data has been received to the specified byte. [...]
Reliability is achieved by the sender detecting lost data and retransmitting it. TCP uses two primary techniques to identify loss. Retransmission timeout (abbreviated as RTO) and duplicate cumulative acknowledgements (DupAcks).
Timeout-based retransmission
Whenever a packet is sent, the sender sets a timer that is a conservative estimate of when that packet will be acked. If the sender does not receive an ACK by then, it transmits that packet again. [...]
Dupack-based retransmission
If a single packet (say packet 100) in a stream is lost, then [...] the receiver acknowledges packet 99 again on the receipt of another data packet. [...] if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. [...]

Retransmission timeout
Retransmission timeout is similar to your first approach: if general A did not receive the confirmation, he will send the same message again.
Duplicate cumulative acknowledgements
First we need to understand the steps taken in each algorithm.
TCP

The sender did not receive an acknowledgement so it sends the same message again.
The receiver notices that the same message is being sent again so it sends the same acknowledgement it sent previously for this message.
Only when the sender receives this acknowledgement it will send the next message. Only when the sender sends a new message will the receiver know that the confirmation has been received.

Your special case

General A did not receive an acknwoledgement so he sends the same message again.
General B notices that the same message is being sent again so he sends the same confirmation he sent previously for this message.
Only when general A receives this acknowledgement he will send the next message. Only when general A sends a new message will general B know that the confirmation has been received.

We can see that both algorithms are the same, except for their terminology. So there isn't any problem with your approaches.

Old, wrong answer
The problem with your Special Case approach is that B cannot do anything until new communication is sent. Because this can happen after the attack time has passed, this is not a functional approach.
Translated to real life networking, this means that the message has to sit in the buffer until the next message is received. This is not a usable strategy in most applications.


What is the size of the Perfect binary tree with n nodes in last level

A perfect (binary) tree of depth $k$ has exactly $2^{k+1}−1$ nodes.

There are probably several ways to prove it. A simple way is by induction.
Each level has twice as many nodes as the previous level (since each node has exactly 2 children in a binary tree). The base level - the root - has 1 nodes. Note that the root is depth 0, not 1.

Let's denote the number of nodes in level $i$ by $N_i$. We know,

$N_0 =1$
$N_i = 2N_{i-1} = 2^{i}$

The total amount of nodes (of tree of depth $k$) is $S_k \equiv N_1 + N_2 + \cdots + N_k$, that is,

$$ S_k = 1 + 2 + 4 + 8 + \ldots +2^{k}.$$
This is a geometric series, whose sum is $S_k = 2^{k+1}-1$.

Now for your question:
We are given a perfect (binary) tree with $n$ nodes at the last level, how many nodes does it have overall?
We are given that at the last level (call it level $k$) we have $N_k=2^k=n$ nodes. Then $k=\log_2 n$ and we get that $S_k=2^{k+1}-1=2n-1$; Yes, each level has one more node than the entire tree above it.

A related question:
we are given a perfect (binary) tree with $n$ nodes, what is its depth?
Now we are given that the total number of nodes is $S_k = 2^{k+1}-1 = n$, thus $k=\log_2 (n+1)-1$ (again, the root is considered depth 0 here).


Is there any development in continuous-value computers?

Since you asked about computability and computational complexity for computers working on continuous values, you might be interested in research on computational complexity for the reals.  In particular, there is a great deal of research on computational complexity for computations that work with real numbers ($\mathbb{R}$).

Normally, we think of algorithms as operating on discrete values (which can be expressed using bits).  However, one can also study algorithms that work with real numbers, where the algorithm can use standard operations on real numbers: addition, multiplication, comparison, etc.  Imagine that each basic operation on real numbers takes $O(1)$ time.  Now we can talk about the running time of algorithms that use these basic operations, and talk about the class of polynomial-time algorithms.  We can also look at a computational task, and ask about its complexity: about the running time of the best algorithm for that task.  For example, a task might be something like: given a polynomial $p(x)$ with real-valued coefficients, determine whether it has a real root or not.

One can then define an analog of P, namely, $P_\mathbb{R}$ -- the class of problems that have a polynomial-time algorithm, where the algorithm is allowed to do basic operations on real numbers.  One can also define an analog of NP, namely, $NP_\mathbb{R}$.  This lets one ask interesting questions, like whether $P_\mathbb{R} = NP_\mathbb{R}$.  Anyway, there is a rich literature on this, pioneered by Blum, Cucker, Shub, Smale, and others.  It is known as complexity and real computation, and sometimes known as the BSS model.  If you search the research literature, you'll find lots of work in this area.

The BSS model does have significant limitations.  It assumes that all computations on real numbers can be done in $O(1)$ time, to infinite precision, with no error.  Real analog computers won't have that property.  But it's still a useful and interesting theory, nonetheless.

To learn more, you can look at https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine and https://cstheory.stackexchange.com/q/2119/5038 and https://cstheory.stackexchange.com/a/2062/5038 and https://cstheory.stackexchange.com/q/31626/5038 and https://cstheory.stackexchange.com/q/27508/5038.


The notation means:

For any $(s_i,o_j) \neq (s,o)$, $A'[s_i,o_j] = A[s_i,o_j]$.

The correct symbol seems to be $\neq$, "not equal", rather than what you wrote.
The symbol $\forall$ means "for all".
The notation $s_i$ just means "element number $i$ in the set of rows", and $o_j$ is similarly "element number $j$ in the set of columns". You could just as well have replaced $s_i,o_j$ with any two other symbols (other than $s,o$).


Constrainted Optimization Problem in Matrix Entropy

Edit: A colleague informed me that my method below is an instance of the general method in the following paper, when specialized to the entropy function,

  Overton, Michael L., and Robert S. Womersley. "Second derivatives for optimizing eigenvalues of symmetric matrices." SIAM Journal on Matrix Analysis and Applications 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Overview

In this post I show that the optimization problem is well posed and that the inequality constraints are inactive at the solution, then compute first and second Frechet derivatives of the entropy function, then propose Newton's method on the problem with the equality constraint eliminated. Finally, Matlab code and numerical results are presented.

Well posedness of the optimization problem

First, the sum of positive definite matrices is positive definite, so for $c_i > 0$, the sum of rank-1 matrices
$$A(c):=\sum_{i=1}^N c_i v_i v_i^T$$
is positive definite. If the set of $v_i$ is full rank, then eigenvalues of $A$ are positive, so the logarithms of the eigenvalues can be taken. Thus the objective function is well-defined on the interior of the feasible set.

Second, as any $c_i \rightarrow 0$, $A$ loses rank so smallest eigenvalue of $A$ goes to zero. Ie, $\sigma_{min}(A(c)) \rightarrow 0$ as $c_i \rightarrow 0$. Since the derivative of $-\sigma \log(\sigma)$ blows up as $\sigma \rightarrow 0$, one cannot have a sequence of successively better and better points approaching the boundary of the feasible set. Thus the problem is well-defined and furthermore the inequality constraints $c_i \ge 0$ are inactive.

Frechet derivatives of the entropy function

In the interior of the feasible region the entropy function is Frechet differentiable everywhere, and twice Frechet differentiable wherever the eigenvalues are not repeated. To do Newton's method, we need to compute derivatives of the matrix entropy, which depends on the matrix's eigenvalues. This requires computing sensitivities of the eigenvalue decomposition of a matrix with respect to changes in the matrix.

Recall that for a matrix $A$ with eigenvalue decomposition $A = U \Lambda U^T$, the derivative of the eigenvalue matrix with respect to changes in the original matrix is,
$$d\Lambda = I \circ (U^T dA U),$$
and the derivative of the eigenvector matrix is,
$$dU = UC(dA),$$
where $\circ$ is the Hadamard product, with the coefficient matrix
$$C = \begin{cases}
\frac{u_i^T dA u_j}{\lambda_j - \lambda_i}, & i=j \\
0, &i=j
\end{cases}$$

Such formulas are derived by differentiating the eigenvalue equation $AU=\Lambda U$, and the formulas hold whenever the eigenvalues are distinct. When the there are repeated eigenvalues, the formula for $d\Lambda$ has a removable discontinuity that can be extended so long as the nonunique eigenvectors are chosen carefully. For details about this, see the following presentation and paper.

The second derivative is then found by differentiating again,
\begin{align}
d^2 \Lambda &= d(I \circ (U^T dA_1U)) \\
&= I \circ (dU_2^T dA_1 U + U^T dA_1 dU_2) \\
&= 2 I \circ (dU_2^T dA_1 U).
\end{align}

While the first derivative of the eigenvalue matrix could be made continuous at repeated eigenvalues, the second derivative cannot since $d^2 \Lambda$ depends on $dU_2$, which depends on $C$, which blows up as the eigenvalues degenerate towards one another. However, so long as the true solution does not have repeated eigenvalues, then it is OK. Numerical experiments suggest this is the case for generic $v_i$, though I don't have a proof at this point. This is really important to understand, as maximizing entropy generally would try to make eigenvalues closer together if possible.

Eliminating the equality constraint

We can eliminate the constraint $\sum_{i=1}^N c_i = 1$ by working on only the first $N-1$ coefficients and setting the last one to
$$c_N = 1-\sum_{i=1}^{N-1} c_i.$$

Overall, after about 4 pages of matrix calculations, the reduced first and second derivatives of the objective function with respect to changes in the first $N-1$ coefficients are given by,
$$df = dC_1^T M^T [I \circ (V^T U B U^T V)]$$
$$ddf = dC_1^T M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)],$$
where
$$M = \begin{bmatrix}
1 & \\
& 1 & \\
&&\ddots& \\
&&&1\\
-1 & -1 & \dots & -1
\end{bmatrix},$$

$$B_a = \mathrm{diag}(1+\log \lambda_1, 1 + \log \lambda_2, \ldots, 1 + \log \lambda_N),$$

$$B_b = \mathrm{diag}(\frac{d_2\lambda_1}{\lambda_1},\ldots,\frac{d_2\lambda_N}{\lambda_N}).$$

Newton's method after eliminating the constraint

Since the inequality constraints are inactive, we simply start in the feasible set and run trust-region or line-search inexact newton-CG for quadratic convergence to the interior maxima.

The method is as follows, (not including trust-region/line search details)

Start at $\tilde{c} = [1/N,1/N,\ldots,1/N]$.
Construct the last coefficient, $c = [\tilde{c},1 - \sum_{i=1}^{N-1} c_i]$.
Construct $A = \sum_i c_i v_i v_i^T$.
Find the eigenvectors $U$ and eigenvalues $\Lambda$ of $A$.
Construct gradient $G = M^T [I \circ (V^T U B U^T V)]$.
Solve $H G = p$ for $p$ via conjugate gradient (only the ability to apply $H$ is needed, not the actual entries). $H$ is applied to vector $\delta \tilde{c}$ by finding $dU_2$, $B_a$, and $B_b$ and then plugging into the formula,
$$M^T [I \circ (V^T[2dU_2 B_a U^T + U B_b U^T]V)]$$
Set $\tilde{c} \leftarrow \tilde{c} - p$.
Goto 2.

Results

For random $v_i$, with linesearch for steplength the method converges very quickly. For example, the following results with $N=100$ (100 $v_i$) are typical - the method converges quadratically.

>> N = 100;
>> V = randn(N,N);
>> for k=1:N V(:,k)=V(:,k)/norm(V(:,k)); end
>> maxEntropyMatrix(V);
Newton iteration= 1, norm(grad f)= 0.67748
Newton iteration= 2, norm(grad f)= 0.03644
Newton iteration= 3, norm(grad f)= 0.0012167
Newton iteration= 4, norm(grad f)= 1.3239e-06
Newton iteration= 5, norm(grad f)= 7.7114e-13

To see that the computed optimal point is in fact the maximum, here is a graph of how the entropy changes when the optimal point is perturbed randomly. All perturbations make the entropy decrease.

Matlab code

All in 1 function to minimize the entropy (newly added to this post):
https://github.com/NickAlger/various_scripts/blob/master/maxEntropyMatrix.m


Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?

A language $\mathcal L$ is recursive if there exists a Turing machine $\mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $\mathcal L$ (i.e. $\forall w, \mathcal M$ accepts $w\iff w\in\mathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.

However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*

Moreover, classes of languages are often included in each others. By instance, if a language $\mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $\mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $\mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$\mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.

As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $\mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.

(*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$\cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability


Colour a binary tree to be a red-black tree

If for each node of a tree, the longest path from it to a leaf node is no more than twice longer than the shortest one, the tree has a red-black coloring.

Here's an algorithm to figure out the color of any node n

if n is root,
    n.color = black
    n.black-quota = height n / 2, rounded up.

else if n.parent is red,
    n.color = black
    n.black-quota = n.parent.black-quota.

else (n.parent is black)
    if n.min-height < n.parent.black-quota, then
        error "shortest path was too short"
    else if n.min-height = n.parent.black-quota then
        n.color = black
    else (n.min-height > n.parent.black-quota)
        n.color = red
    either way,
        n.black-quota = n.parent.black-quota - 1

Here n.black-quota is the number of black nodes you expect to see going to a leaf, from node n and n.min-height is the distance to the nearest leaf.

For brevity of notation, let $b(n) = $ n.black-quota, $h(n) = $ n.height and $m(n) = $ n.min-height.

Theorem: Fix a binary tree $T$. If for every node $n \in T$, $h(n) \leq 2m(n)$ and for node $r = \text{root}(T)$, $b(r) \in [\frac{1}{2}h(r), m(r)]$ then $T$ has a red-black coloring with exactly $b(r)$ black nodes on every path from root to leaf.

Proof: Induction over $b(n)$.

Verify that all four trees of height one or two satisfy the theorem with $b(n) = 1$.

By definition of red-black tree, root is black. Let $n$ be a node with a black parent $p$ such that $b(p) \in [\frac{1}{2}h(p), m(p)]$. Then $b(n) = b(p) -1$, $h(n) = h(p)-1$ and $h(n) \geq m(n) \geq m(p)-1$.

Assume the theorem holds for all trees with root $r$, $b(r) < b(q)$.

If $b(n) = m(n)$, then $n$ can be red-black colored by the inductive assumption.

If $b(p) = \frac{1}{2}h(p)$ then $b(n) = \lceil \frac{1}{2}h(n) \rceil - 1$. $n$ does not satisfy the inductive assumption and thus must be red. Let $c$ be a child of $n$. $h(c) = h(p)-2$ and  $b(c) = b(p)-1 = \frac{1}{2}h(p)-1 = \frac{1}{2}h(c)$. Then $c$ can be red-black colored by the inductive assumption.

Note that, by the same reasoning, if $b(n) \in (\frac{1}{2}h(r), m(r))$, then both $n$ and a child of $n$ satisfy the inductive assumption. Therefore $n$ could have any color.


If $g ∘ f$ is primitive recursive, are $f$ and $g$, too?

Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.


How to prove this obvious theorem in type theory (LEAN prover)

If you used Type instead of Prop in the definition of P, then you could easily extract from axiom a1 a function f such that ∀b:B, P b (f b). However, there would be no guarantee that this function would satisfy f b = a for any given a and b that satisfy P b a. Given a decidable equality on B, you could turn the function that a1 gives you into your desired function via λ bb:B, if bb == b then a else fst (a1 bb). Without decidable equality, it's not clear how you would construct a function that you could prove would give a when given b.

As far as your informal argument, the problem is "picking" from the equivalence class. Constructive logic/type theory is compatible with everything being computable. (Formally, this is usually expressed via realizability.) To say that you can "pick" from an equivalence class subject to some constraints means you are providing an algorithm that can somehow "search" through (some representation of) the equivalence class and find an element that satisfies your constraints. However, you don't even know these types are computably enumerable. At any rate, "picking" is rarely "simple".

I'd have to look at the rules of LEAN to be sure, but with P going to Prop, you need the (real) Axiom of Choice to even get the function f at all before you ever got around to constraints. In fact, while I haven't thought about it too much, I believe the statement you give is equivalent to the (real) Axiom of Choice.


How does conversion from fixed-point to floating-point happen?

Your code converts a fixed-point number into its value. It also works for converting a fixed-point number to a rational number, for example.

A fixed-point number of the form $16.16$ consists of 32 binary digits, the first 16 to the left of the decimal dot, the second 16 to its right. When you insert the decimal dot, you are dividing by $2^{16} = 65536$.

Here is a decimal example. Consider a number stored in decimal fixed-point $2.2$. What is the value of the number stored as $1234$? It is $12.34 = 1234/100$.


Which type compilers report if they cannot infer a precise type?

It is important to keep in mind that this is a question about human-computer interaction and not about compilers. As far as the machine is concerned, the constraints are the constraints, and the obvious thing to do is just to show all the constraints to the user. However, when the user is a human, they may find the constraints too complex to process, and so the machine needs to dumb down the information for the cognitively handicapped user. This is in fact what happens, see for instance Pretnar's paper on inference for effects where he discusses what to show the user (that's just the first paper that came to my mind, and is by no means the only one or the first one).

As you notice, showing just the lower bounds may be useless. Symetrically, showing just the upper bound may be useless as well. However, in many situations one has either useful lower bounds or useful upper bounds, in which case you just show the useful part (and you need to indicate whether you're showing the lower or the upper bound). Other than that, people try various strategies. A common one is to simplify the constraints in the hope that we won't lose much information, and then show those to the user. Simplification can also be useful to control the size of constraints, which can easily grow so much that the whole system becomes useless.


Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which is large enough, then the Akra–Bazzi formula gives you $\Theta(n\log\log n)$ as wanted.


How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?

Yato and Seta show that for every constant $m$, given $m$ solutions to a Sudoku puzzle, it is NP-complete to determine whether there is another solution. They show that the same property is satisfied by other puzzles as well.


What does it mean that a let-binding can be treated polymorphically, only if its right-hand side is a syntactic value?

You seem to have been confounded by many related and similar but crucially different concepts! Let me attempt to explain them one at a time.

Parametric polymorphism is the ability to write types that quantify universally over type variables using the $\forall$ quantifier. It is similar to template polymorphism in C++, or generics in Java. For example, the type $\forall \alpha . \alpha  \rightarrow \alpha$ means "for each and every type $\alpha$, given an expression of type $\alpha$, this function returns an expression of type $\alpha$. This is (almost) equivalent to writing the Java method signature public <T> T foo(T bar).

Parametric polymorphism is parametric in that for each and every possible type $\alpha$, the function behaves in the same way. This gives us powerful free theorems about the behavior of a function, e.g., a function with type $\forall \alpha . \alpha  \rightarrow \alpha$ could only be the identity function, as you were given something of an unknown type, the only thing that you could do with it is to return it unchanged (unless you cheat by non-termination).

Hindley-Milner is a special and restricted form of parametric polymorphism, in that it only allows $\forall$ to appear at the beginning of a type. That is, you cannot have types like $\forall \alpha . (\forall \beta . \beta \rightarrow \beta) \rightarrow \alpha$. The reason why people love Hindley-Milner is that type reconstruction (or type inference), or reconstructing the type of an expression without type annotations, is always deciable and principal (meaning that the type reconstructed is always the most general type possible).

The value restriction is a restriction in programming languges with both Hindley-Milner type systems and mutable storage. With the value restriction, a polymorphic type would only be inferred for a definition if the right-hand side of the definition is a syntactic value. The idea is to prevent problems with mutable store:

Consider the following ML program:

let r = ref []
r := [3]; r
let l = List.map (function true -> 1 | false -> 2) !r

Without the value restriction, the type 'a list ref would be inferred for r. However, the second line makes the contents of r have the type int list, nevertheless r still keeps the (incorrectly) polymorphic type 'a list ref and the third line would result in an uncaught type error!

The value restriction prohibits definitions whose right-hand side is not a syntactic value from being inferred a polymorphic type. In the program above, r would no longer have a polymorphic type since ref [] is not a syntactic value. The second line will fix the type to r to int list ref, causing the third line to correctly report a type error.

For more about value restriction, the first and second part of Jacques Garrigue's paper Relaxing the Value Restriction explains it rather concisely. There is also Andrew Wright and Matthias Felleisen's paper A Syntactic Approach to Type Soundness in which the value restriction was first invented.


How to calculate the efficiency of an algorithm?

The best way (The way I was taught at least) is to look for a basic operation. That's the operation that most significantly impacts the performance of an algorithm. In your case it looks like if T[j] < minX then would be your basic operation as it's performed the most times, where the statements inside of the if check are only performed if the condition is true. The fact you have two for loops going from 1 to n-1 tell me that you're working with quadratic time. You're going to be doing your basic operation at minimum n^2 or n operations n times. This should tell you that your algorithm performs in O(n^2) timing.


Algorithm to find the shortest walk with k leaf nodes on a tree

This can be solved by a fairly standard dynamic programming algorithm. For a given node $v$, let $C(v,k)$ be the minimum length of a (closed) walk through the subtree rooted at $v$ passing through exactly $k$ leaf nodes ($C(v,k)=\infty$ if there is no such walk).

If a node $v$ has children $c_1,\ldots c_m$, then $C(v,k) = min_{k=a_1 + \ldots + a_m} \Sigma_{\{i:a_i\not = 0\}} 2 + C(c_i, a_i)$ (i.e. taking the minimum over all ways to split up $k$ over the children of the node).

With some modification, this can be made to run in $O(n^3)$.


The answer seems to be simple:

First, we XOR the two least significant bits (LSB) to get the most significant bit. The two LSB are obtained by right-shifting. So, calculating in this way, we get the sequence 110, 111, 011, 001, 100, 010, 101.


How to solve the feasibility problem in 0-1 integer programs?

The fundamental misconception seems to be: you seem to expect there to be some good way to solve NP-hard problems.  But the whole point of NP-hard problems is that there is (most likely) no good, general way to find optimal solutions to NP-hard problems in a reasonable amount of time.  So, you seem to be asking for something that (most likely) doesn't exist.

To answer your specific questions:

  [Here's an example where the grey first-fit algorithm doesn't find the optimal solution to a bin-packing problem.]  How to solve this issue with the greedy first-fit algorithm?

You can't.  The greedy first-fit algorithm isn't guaranteed to find an optimal solution (and often won't).  Morever, as you said, it's NP-hard even to find a feasible solution -- therefore, you shouldn't expect the greedy first-fit algorithm to be guaranteed to find a feasible solution, either.  It's no surprise that it fails to find a feasible solution to a NP-hard problem.  And there is (most likely) no way to fix it, while still having an efficient running time.

  In general, if I have a 0-1 integer program that is hard to check its feasibility, how to design an algorithm that makes few errors?

In general, there may be no way.

  Any suggestions where to find solutions to feasibility of 0-1 integer programs?

There's lots of literature on methods for solving integer linear programming (ILP).  None of them are guaranteed to find feasible solutions within a polynomial running time (after all, the problem of finding a feasible solution is NP-hard), though some of them might work well enough on some problems that you run into in practice.  Rather than study the literature and try to implement the known methods, you're probably better off using an off-the-shelf ILP solver -- the developers who implemented the ILP solver did that for you.


If you do not want a more complicated (non-context-free) grammar, you cannot coordinate the two steps. The trick is to work the other way around: generate the two "side strings" from one central non-terminal and put the $111$ in the end.

Further problems with your grammar are:

you miss $111$,
since your intention is to generate 2 symbols both at the front and at the end, you would add 4 instead of 2 and thus miss every second odd number.

I propose the grammar
$$[ \{0,1\}, \{S\}, R, S]$$
where $R$ has the rules
$S\rightarrow 0S0\ |\  1S1\  |\  0S1\  |\  1S0\  |\  111$.


Are there any proofs of exponential lower bound time complexity

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ and then show that it cannot be decided substantially faster than $f(n)$, in a very similar way to showing that "does this Turing machine halt in finite time" cannot be decided (in finite time).

In the case of generalized board games (e.g., Chess), these are often $EXPTIME$-complete. This means any problem in $EXPTIME$ can be reduced in polynomial time to it. Since (by the Time Hierarchy Theorem) there are problems in $EXPTIME$ that cannot be solved in subexponential time, neither can Chess (or any other $EXPTIME$-complete problem).

Your other example (shuffling bits to get a prime number) probably doesn't require exponential time. The chance that a random permutation of the bits results in a prime is quite high, and only a polynomial number of guesses would be required to find a prime. The problem is in $NP$, so a proof that it requires exponential time would be a somewhat significant breakthrough.


The question in the given situation is equivalent to the question: is it possible to create or to design a system such that m processes sharing n resources of the same type may enter a deadlock state subject to the following: each process needs less than or equal to n resources, and the total number of needed resources is less than or equal to m+n (“For a given certain situation”, 2015)?

Assumptions. Processes run on a single processor. The processor can execute a statement from one and only one process at a time. In other words every statement in a process is an atomic operation. After ending a statement and before executing the next statement of a process, the processor can switch to another process and execute the other process’ next statement.

Consider using a Petri Net for the system design. In terms of Petri Nets a deadlock is a situation when no transition is enabled. Figure 1 is an example of a system that may enter a deadlock state. In this example, m=2 and n=2.
For the same number of processes and resource needs per process (m=2 and n=2), it is also possible to create a system that does not enter a deadlock state. Each of Figure 2 and Figure 3 is an example of two systems that will never reach a deadlock state.

Figure 1: A System with Deadlock

Figure 2: A System without Deadlock

Figure 3: Another System without Deadlock

Notes

For Figure 1, the transitions related to Process 1 (Process 2) are:

T0 (T4) – get 1 resource unit.
T1 (T5) – get 1 resource unit.
T2 (T6) – process critical section.
T3 (T7) – return 2 resource units.

For Figure 2, the transitions related to Process 1 (Process 2) are:

T0 (T4) – get 1 resource unit.
T1 (T5) – get 1 resource unit.
T2 (T6) – process critical section.
T3 (T7) – return 2 resource units.
T8 (T9) – return 1 resource unit.

For Figure 3, the transitions related to Process 1 (Process 2) are:

T0 (T3) – get 2 resource units.
T1 (T4) – process critical section.
T2 (T5) – return 2 resource units.

For the PDF version of this reply, Figure 1, Figure 2 and Figure 3 are interactive, dynamic diagrams.

References

Chionglo, J. F (2015). "A Reply to "For a given certain situation how to prove that the system will never get into the state of deadlock" at Computer Science Stack Exchange". Available at http://www.aespen.ca/AEnswers/OnMWQ1449933168.pdf

“For a given certain situation how to prove that the system will never get into the state of Deadlock” (2015). Mathematics Stack Exchange. Retrieved on Dec. 2, 2015 at For a given certain situation how to prove that the system will never get into the state of Deadlock.


Flip-based algorithm for Delaunay triangulation in expected or average-case O(nlogn)

The proof that edge flipping is expected to perform well goes back to this paper below as well as a couple related one around the same time-frame:

Guibas, Leonidas J., Donald E. Knuth, and Micha Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica 7.1-6 (1992): 381-413.

A relatively concise algorithm and proof is given in the paper below by Edelsbrunner and Shah which describes a flip-based algorithm that runs in expected O(n log n) time.

Edelsbrunner, Herbert, and Nimish R. Shah. "Incremental topological flipping works for regular triangulations." Algorithmica 15.3 (1996): 223-241.

The algorithm involves adding points to the triangulation one at a time and using some history of the construction process to locate the new points. The paper is slightly more general, dealing with regular triangulations for which the Delaunay triangulation is a special case.


Do you have any sort of distance-heuristic?  If not, then yes, BFS is likely your best choice.


Let $CON(F)$ denote the sentence: "F is consistent".

You can prove $CON(F)\rightarrow \text{ MF does not halt}$, since if MF halts you have $F\vdash G(F)$ and thus by soundness $F\not\vdash G(F)$.

You cannot however, prove this unconditionally (unless your system is inconsistent), since this would mean $F\not\vdash G(F)$ which implies consistency (why?).


Solving distance-d independent set in a simple way

I'm sorry although I prefer to think of simple answers, ur Q triggers in my mind addressing other problems (a level of a research topic not an under graduate task)

Anyways, here is what popped up in my mind just incase u find something inspiring in them

-About the Kth Largest Subset problem http://dx.doi.org/10.1016/j.ipl.2015.09.015

-About Goemetric Set Packing problem
(I myself didn't study it a lot, but read some papers about it when someone suggested it to me. I did not use it in my work, but the way u r trying to describe ur problem tells it has a Goemetric landscape nature so maybe it will be useful for u)

https://www.sciencedirect.com/science/article/pii/S0925772112000740

https://slideplayer.com/slide/4514539/

I have more resources if u need so

.

Finally, u may search for exact MWIS algorithms and u'll find a lot. Here is one paper
"Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs", Sebastian Lamm
, Christian Schulz, Darren Strash, Robert Williger, Huashuo Zhangk.
arXiv:1810.10834v1 [cs.DS] 25 Oct 2018


Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?

No such bound is known; for all we know, it may be possible to solve it in linear time. In fact, for all we know, there might be an algorithm for it that uses $O(\log(n))$ space on its work tape.

We know one thing: There is not an algorithm which uses both linear time and logarithmic space. That is, there is a time-space lower bound! A Subset Sum instance of size $n$ can be reduced to a 3SAT instance of size $O(n^2)$ (perhaps there is a better reduction), and for 3SAT, we know that, if $t(t+s)<2$, then

$$3SAT \not\in TiSp\left(n^{t},n^{s}\right) $$

With $TiSp(t(n),s(n))$ the class of problems solvable in $O(t(n))$ time and $O(s(n))$ space. This is not the strictest bound, see Computational Complexity: A Modern Approach for more details.

But that still leaves open whether there is an algorithm which uses $O(n)$ time and $O(n)$ space. (Of course, the non-deterministic time hierarchy theorem tells us that for every $t(n)\in poly(n)$, there is a problem $L\in NP$ which provably requires $\Omega(t(n))$ time, the question is whether the subset sum problem is one of them.)

So yeah, that bound is not great. It's not the bound we deserve, but it is the bound we have right now.


Prove a language is not recursive enumerable

Yes it's okay to use Rice's extended theorem.

To clarify, the theorem states: "if $C$ is some set of languages, and $C\neq\emptyset\wedge\Sigma^*\notin C$, then $\{<M>|L(M)\in C\}\notin RE$."

So, let us define $C=\{L((01)^*)\}$. Notice that our $L$ in the question is exaclty $\{<M>|L(M)\in C\}$, and then since $C\neq\emptyset$ and $\Sigma^*\notin C$ $[$as the only language in $C$ is $L((01)^*)\space]$, we have by the extended theorem that $L\notin RE$.