Exact definition of average time complexity?

Here is the definition of average-case time complexity of an algorithm:

Let $T(x)$ be the running time of some algorithm $A$ on input $x$. For every $n$, let $\mu_n$ be a distribution on inputs of length $n$. The average-case or expected time complexity of $A$ on inputs of length $n$ is $$T_{\mathit{avg}}(n) := \mathbb{E}_{x \sim \mu_n} T(x). $$

As you can see, in order to talk about average-case complexity, you have to specify a distribution. In the definition above I have alluded to the common case in which the complexity is parameterized by input length, but we could also have more parameters, or no parameters at all.
For comparison-based sorting algorithms, we usually consider the following distribution $\mu_n$: the uniform distribution on all $n!$ permutations of $1,\ldots,n$. However, we would obtain exactly the same notion of average-case complexity (for comparison-based algorithms) if instead we pick any atom-less distribution $\mu$, and define $\mu_n$ to consist of $n$ iid copies of $\mu$.
Unfortunately, no distribution on the integers is atom-less. This creates a problem, since if we generate $n$ iid copies of a distribution $\mu$ with atoms, then there is positive probability that the generated elements are not distinct. While comparison-based sorting algorithms can certainly handle this case, the situation becomes much less clean since the average-case time complexity now depends on $\mu$.
Finally, you seem to be quoting a quite informal average-case complexity analysis of quicksort. You can find rigorous analysis of the average-case complexity of quicksort (in fact, two different ones) in lecture notes of Avrim Blum.


Is Weighted Averages the Best Method to Aggregate Information?

A weighted average might or might not be the best method.  This will depend on (a) the nature of the algorithms, and (b) what objective function you are trying to minimize.

Let me give you a sample set of assumptions.  Suppose we treat the predictions from the recommendation algorithms as independent random variables (e.g., because each recommendation algorithm was trained independently).  Also,  suppose we wish to minimize the variance of the final prediction.  In other words, our loss function is the $L_2$ loss: if our prediction was $Y$, and the correct value was $\tilde{Y}$, then the loss (penalty) is $(Y-\tilde{Y})^2$.

Then in this case we can find the optimal set of weights.  In particular, in this case, if we restrict ourselves to linear combinations, the optimal set of weights is inversely proportional to the variance of each estimator.  Suppose $X_1,\dots,X_n$ are the predictions from our $n$ recommendation algorithms.  Suppose that we have measured the accuracy of each recommendation algorithm by measuring its $L_2$ loss on a validation set; in other words, we know the variance $\text{Var}(X_i)$ for each $i$.  Here $\text{Var}(X_i)$ is a measure of the accuracy of the $i$th recommendation algorithm: the larger the variance, the larger the expected $L_2$ loss, and thus the less accurate the prediction is.  Then the optimal linear weighting is to select a final prediction $Y$ by

$$Y = c_1 X_1 + \dots + c_n X_n,$$

where we choose the weights

$$c_i = {a_i \over a_1 + \dots + a_n}$$

where

$$a_i = {1 \over \text{Var}(X_i)}.$$

Is a linear combination optimal (as opposed to other, nonlinear methods of combining the predictions)?  In this situation, if we additionally know that the errors made by each recommendation algorithm have a Gaussian distribution, then yes, a linear combination is optimal.  If the errors have a different distribution, then some other combination might be better.

As you can see, this will depend on the loss function we select, and on other assumptions.  That said, in practice, a linear combination (i.e., a weighted average) is often a reasonable choice.

There's lots written about this sort of thing in the statistics literature.  For instance, the above discussion is just a restatement of the fact that the average is the optimal estimator of the mean of a Gaussian distribution (i.e., it minimizes the mean squared error).  See, e.g., https://en.wikipedia.org/wiki/Estimator, https://en.wikipedia.org/wiki/Mean_squared_error, https://stats.stackexchange.com/q/81571/2921, https://stats.stackexchange.com/q/97765/2921, https://stats.stackexchange.com/q/48864/2921, https://math.stackexchange.com/q/9032/14578.


Here is an expanded version of Igor Shinkar's comment. The simplest way to simulate a non-deterministic machine running in time $f(n)$ and space $s(n) \leq f(n)$ uses $s(n) + 2f(n) + O(1)$ space. We enumerate over all possible coin tosses, simulating the original machine on each of them; this requires space $f(n)$ for storing the coin tosses, and $s(n)$ space for simulating the actual machine. There is a slight difficulty here: when the coin tosses are "read" by the (original) machine, we need to mark somehow where we are in the sequence of coin tosses; we can use an additional bit per coin toss. It is probably possible to optimize this even further.

If we're careful, we might be able to get something even better, since in each run of the program, the total number of coin tosses and the total space used add together to at most $f(n)$. I suspect it's possible to run the simulation in $(1+o(1))f(n)$ space. Perhaps we will need to assume something like $f(n) = \Omega(\log n)$ for that.

As Igor mentions, usually resource-bounded classes are only defined "up to big O", so that the result, which uses space $O(f(n))$, is still in $\mathrm{DSPACE}(f(n))$.


Time complexity of art gallery-like problem

Your problem is a special case of finding a dominating set of size at most $w$ for directed graphs $G$, where we require that there are no isolated vertices in $G=(V,E)$ and that $w\geq |V|/2$.

Unfortunately, this problem is still NP-hard, since there is a polynomial time reduction from the general directed dominating set problem:

Given an arbitrary directed graph $G=(V,E)$ and an integer $w$, construct the instance $(G',w)$ as follows:

Set $G_0 \leftarrow G$ and $w_0\leftarrow w$.
Remove all $i$ isolated vertices from $G_0$ and 'place guards on them': $w_0\leftarrow w_0 - i$. If $w_0\leq 0$, simply construct some instance that yields NO and we're done.
If $w_0\geq |V|/2$, we are done. Otherwise, 'add two guards' for every cycle we will introduce: $w'\leftarrow w_0+2\cdot(|V_0|-2w_0)$ and add $|V_0|-2w_0$ directed 3-cycles to $G_0$. Set $G'\leftarrow G_0$.

Observe that now $w'\geq |V|/2$, since if we have added the three-cycles, we get $2w'= 2w_0+4(|V_0|-2w_0) \geq |V_0| + 3(|V_0|-2w_0) = |V'|$. The reduced instance is a YES-instance if and only if the original instance is, since 'disconnected' components do not influence the rest of the graph and at least 2 guards are required to watch a 3-cycle.

So a polynomial time algorithm most likely doesn't exist, even for this special case.


Hardness of approximation statement clarification?

Since $1 + \log n = (1 + o(1)) \log n$, for every $\beta < \alpha$ you can find $N$ such that for $n \geq N$,
$$ (1-\alpha)(1 + \log n) \leq (1-\beta) \log n. $$
This suffices to reach a contradiction.


Hint:

There are countably many computable functions defined at zero, and countably many computable functions undefined at zero.
There are countably many natural numbers divisible by 2, and countably many natural numbers not divisible by 2.

Put the two facts together.


In a LP problem Ax = b, how to solve for A instead of x?

Let $a_{ij}$ represent member of matrix $A$. This can either be the constant $0$ if you want $a_{ij}$ to be $0$ in the solution matrix, or a variable for a linear programming problem. Then you want to add linear constraints:
\begin{alignat}{2}
&\!\min_{a}        &\qquad& \sum_{i} s_i\\
&\text{subject to} &      & \forall j \left(\sum_{i}a_{ij} \leq 1 + \epsilon \right),\\
&                  &      & \forall j \left(\sum_{i}a_{ij} \geq 1 - \epsilon \right),\\
&                  &      & \forall_i \left(\sum_{j}a_{ij}x_j \leq s_i\right),\\
&                  &      & \forall_i \left(\sum_{j}a_{ij}x_j \geq -s_i\right).
\end{alignat}
This finds the optimal matrix $A$, with the desired elements set to $0$, that has columns adding up to $1$ (within a certain precision) and minimizes $\left\lVert Ax\right\rVert_1$.


MTBF calculation with 2 units connected in series

If the MTBF of a device is $N$, then the probability that the device will fail in 1 time unit is $1/N$. With two devices in series with failure probabilities $p_1$ and $p_2$, the system will fail in one time unit if device 1 fails or if device 1 doesn't fail and device 2 fails. The probability of that happening is
$$
p_1 + (1-p_1)p_2=p_1+p_2-p_1p_2
$$
In your problem, $p_1=1/200, p_2=1/300$ so the probability that the system will fail in one time unit is
$$
(1/200)+(1/300)-(1/200)(1/300)=499/60000\approx0.00832
$$
and so the MTBF of the whole system is $1/0.00832\approx120.24$. Your friend is right: none of the proposed solutions are correct.


Context-free grammar of the concatenation of a string S and subsequence of reversed S

Let me start with a grammar for the language of words of the form $x\#x^R$:
$$
S \to aSa \mid bSb \mid \#
$$
This is our starting point. Now there are two interpretations of the term subsequence. Under the first interpretation, a subsequence is obtained by removing any number of symbols. This just means that we can omit the second side of each production of the form $S \to \sigma S \sigma$, resulting in the grammar
$$
S \to aSa \mid bSb \mid aS \mid bS \mid \#
$$
Under the second interpretation, the subsequence must be contiguous. Each derivation should therefore be in three steps: first only on the left side, then on both sides, then finally again only on the left side. This requires three nonterminals, and results in the following grammar:
$$
S \to aS \mid bS \mid T \\
T \to aTa \mid bTb \mid U \\
U \to aU \mid bU \mid \#
$$


What is the difference between regular trees and phylogenetic trees in terms of graph theory?

Phylogenetic trees are usually "full binary trees", that is rooted trees in which every internal node has exactly two children. A full binary tree having $n$ leaves has exactly $2n-1$ nodes.


Can a regular language have uncountably many strings?

No, there are only countably many finite strings over any finite alphabet.  Given an alphabet $\Sigma = \{s_0, \dots, s_d\}$, you can associate the string $w$ with the number $1w$ written in base-$d$, giving an injection from the natural numbers to $\Sigma^*$.  (The reason we use the number $1w$ rather than $w$ is to avoid problems with, e.g., $2$, $02$, $002$, etc. all mapping to the same number.)


Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points

Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same.

A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9299 http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A580FE7BF3251BC23DB793E3B1DFDF64?doi=10.1.1.21.9299&rep=rep1&type=pdf


NP-complete problems and sub-expenential sized circuits

If such an algorithm were found, it would violate the exponential time hypothesis.  See also, for example, Are there subexponential-time algorithms for NP-complete problems?.

And of course, if this were the best possible complexity for any algorithm for this problem, you would have shown that $P \ne NP$ (and in fact that $NP \ne P/\text{poly}$).  When you wrote that the problem has such-and-such circuit complexity, I don't know whether you meant (a) there exists an algorithm with that complexity, or (b) the problem has that complexity (which means there exists an algorithm of that complexity, and there is no better algorithm); this paragraph only applies if you meant (b).

Beyond that, I don't think there would be any other obvious consequences.  In particular, I don't know of any significant consequences if the ETH is violated (other than the obvious one, that the theorems of the form "if the ETH holds then..." become moot).


Practical application of Finite State Machines

Each time you do a search (particularly a "pattern search") in your favorite editor/tool, the pattern is translated into some form of finite state machine, which does the matching.

The lexical analysis part of your compiler/interpreter (yes, even your shell) is again a finite automaton which matches keywords and other tokens recognized by the language.

Any vending machine is a finite automaton which takes in coins of different denominations and recognizes when the correct amount has been entered (OK, today's vending machines probably have a small CPU inside doing the adding, but the end result is the same).


Implications of polynomial time reductions

Right, if you have an algorithm A that reduces $\Pi$ to $x$ in polytime, and you can solve $x$ is polytime using some algorithm B, then you can solve $\Pi$ in polytime by applying first A and then B.

Using polytime reductions on a problem in P however is rather boring, since you can solve the instance during the reduction and map every instance of $x$ to either a trivial yes or a trivial no answer. Normally you restrict yourself to logspace reductions for problems from P.


That is correct. An x-bit binary number can be expanded as "A number in the binary system that consists of x binary digits".


There's a problem with terminology here.  A walk in a graph is a sequence $v_1\dots v_k$ of vertices such that $v_1v_2, v_2v_3, \dots, v_{k-1}v_k$ are edges. A path is a walk that doesn't repeat vertices.  So, a graph with a positive-weight cycle contains no longest walk (you can always walk around the cycle one more time to get a longer one) but it does contain a longest path (paths can't go all the way around cycles).

Algorithms such as Bellman–Ford actually compute shortest walks between vertices and use the fact that, as long as the graph has no negative cycles, the shortest walk is also the shortest path.  (Any walk that isn't a path must contain a cycle and, if all cycles have positive weight, then the walk without that cycle is shorter.) The graph your algorithm generates contains negative-weight cycles, so Bellman–Ford will fail: it can't use its "the shortest walk is also the shortest path" rule because there is no shortest walk.


d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

The crux is right there in the first paragraph of the post.

  Let's say that Dijkstra’s algorithm with the priority queue using a $d$-ary heap. We can achieve the best runtimes for the algorithm with $d$ being $\sim |E|/|V|$.

As you have pointed out, the time-complexity of Dijkstra with $d$-ary heap is $O\left((|V|\cdot d+|E|)\dfrac{ \log|V|}{\log d}\right)$. Substituting $|E|/|V|$ for $d$, we see the best time-complexity of Dijikstra with d-ary heap is $O\left((2|E|)\dfrac{\log|V|}{\log|E|/|V| }\right)=O\left(\dfrac{|E|\log |V|}{\log |E|/|V|}\right)$.

In the case 1 where $|E|$ dominates, the ratio of the best time-complexity of Dijkstra with $d$-ary heap to $O(|E|)$, the time-complexity of Dijkstra with Fibonacci heap is $\dfrac{\log|V|}{\log |E|/|V|}$ (ignoring some constant factor), which takes its maximum value when $|E|$ takes its minimum value, $|V|\log |V|$. Hence we get the ratio $\dfrac{\log|V|}{\log\log|V|}$.


Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

I have a proposal for a proof that doesn't involve "coloring" since it sounds vague.
Let $T' = (V,F')$ be a spanning tree but not a MST of $G=(V,E)$. Let $T = (V,F)$ be a MST of $G$.

You already did the following:
Now go through all $e \in F-F'$ and add $e$ to $T'$. Resulting graph contains a cycle if there is another edge $e'$ on the cycle such that $e\neq e',w(e) < w(e')$ we are done because $T'$ could be augmented.

My approach for the rest using Kruskal's algorithm:
Otherwise we construct a graph $G' = (V,F'\cup (F-F')) = (V, F'\cup F)$.
For all $e \in F-F'$ and for all cycles $e$ lies on (in $G'$) $e$ is clearly one of the edges with the max weight.
Now run Kruskal's algorithm on $G'$ with a modified sorting procedure. Every edge is primarily sorted by its weight and secondary by the boolean if it belongs to $F'$ or not in such a way that for two edges with different weights the edge with the least weight comes first, but if two edges have the same weight the one belonging to $F'$ comes first (if both belong to $F'$ the order doesn't matter).
We are allowed to make this modification to the sorting procedure because Kruskal's algo doesn't care in which order edges with equal weight appear.
The algorithm proceeds to sort all edges in mentioned order. Thus for every cycle in $G'$ all edges in the cycle are considered before the an edge $e\in F- F'$ is considered. Since we know that Kruskal's algo connects two nodes always when they do not create a cycle and we know that edges $F-F'$ are considered last for every cycle the MST found by the algo is $T' = (V,F')$.
Contradiction:
But from our assumption we know that the weighted sum of $T$s edges is clearly lower than that of $T'$s edges and that $T$ is a spanning tree of $G'$. So actually $T$ is the MST of $G'$. Thus we have a contradiction and can conclude that there must be an $e \in F- F'$ such that it augments $T'$.


It is the turing machine that clones its input. If you want a description of this machine's operation, you may find this useful.


Is showing two different derivations enough to prove that a CFG is ambiguous?

As Rick says, this is very close. The key is to show that there are two different parse-trees for the same word in the grammar.

What you have is okay, but presenting it as a linear derivation isn't enough. For example, consider something similar to what you did, but slightly different:

$O \rightarrow OOs \rightarrow OsOOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

At face value, these are two different derivations. However, if you look closely, you see that they only differ in the order that we expand the different terminals of the same intermediate word. So this is NOT a valid proof that the grammar is ambiguous.

However, if we look at your original example using parse-trees, we can see that it still holds:

O
|
O--O--s
|  |
r  s--O--O
      |  r
      r

And the second tree:

O
|
O--s--O
|     |
r     O--O--s
      |  |
      r  r

This shows that these are actually different parses: we use a different production from the initial $O$ symbol, so we know that they are different.

An equivalent way to do this is to use the linear derivations like you do, but always put them in "left-derivative" form, where you only ever expand the left-most non-terminal. So your derivations would become:

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OsO \rightarrow rsO \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

In this case, there's a 1:1 correspondence between left-derivatives and parse trees, so if there are two distinct ones, you know the grammar is ambiguous.

For the "bad" example I gave, both derivations give the first parse tree, so it's not a valid proof that the grammar is ambiguous.


You can show that $\mathsf{NL}[2] \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}[2]$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ does is to guess the state $\sigma$ of $M'$ after it finishes reading the witness tape for the first time. It then simulates two copies of $M$, one starting at $M$'s initial state, and the other starting at $\sigma$. After going through the witness tape, it verifies that the first copy has reached $\sigma$, and that the second copy has reached an accepting state.

In this way you can show that $\mathsf{NL}[O(1)] = \mathsf{NL}$.


The solution in short. For each edge $e$ not in the tree, check the path between its endpoints in the tree. The weight of each edge on this path is upper-bounded buy the weight of $e$. Keep track of the smallest upper-bound for each edge on the tree while iterating over all edges not in the tree. Following is a sketch of the correctness.

Let us call an edge in a simple cycle Heavy for this cycle, if its weight is maximum among all edges in the cycle. We claim that each edge $e$ in $G\setminus T^*$ is Cycle heavy for some cycle in $G$.

Proof. By adding the edge $e$ to the tree, it constructs a cycle with a path in the tree between its endpoints. If there is an edge in the cycle with strictly heavier weight, we can remove this edge and keep $e$ constricting a lighter tree which contradicts the assumption that the given tree is minimum.

On the other hand, it is not hard to prove that an edge is in an MST of a given graph if it is not heavy for any simple cycle containing this edge. The correctness of the sketched algorithm follows directly from this statement.


How to implement random sampling with continuous variables?

One standard approach is to use inverse transform sampling: if $F$ is the cdf of the desired random variable and $U$ is uniformly distributed, then $F^{-1}(U)$ has the desired distribution.  There are more sophisticated methods for specific distributions; you can find references and links where you can learn more in the linked Wikipedia article.


Determining number of elements divisible by at least one prime of set

One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.


Complexity of recognizing whether two $\omega$-regular expressions represent the same language

It's quite easy to reduce the equivalence problem for regular expressions to the equivalence problem for $\omega$-regular expressions, so you have EXPSPACE hardness.

For EXPSPACE completeness, observe that given two $\omega$ regular expressions $r_1$ and $r_2$, you can translate them to equivalent NBWs $A_1,A_2$, where the size of $A_i$ is at most single-exponential in the size of $r_1$. Then, checking whether $L(A_1)=L(A_2)$ can be done in PSPACE (nontrivial, but well known).


Finding lowest "pass" between two points on a map?

A simple solution to this would be to implement it as any normal pathfinding algorithm (say, A*), but then render in your map any height over a threshold as impassable, and any height under the threshold as passable, and then continuously run the pathfinding algorithm for threshold heights between the minimum cell height and the maximum cell height. The first time you can path from start to end is the lowest possible height.

This has some performance implications for maps with a large difference between highest and lowest points, but you use a search algorithm other than a linear search to find the upper and lower bounds and close in on the boundary.

Many pathfinding algorithms are already generalised to n-dimensions, so to generalise this is simply the case of picking the correct dimension to use as the varying threshold. Essentially, for a map of n dimensions (say, a 2D map + height), you path find in that many dimensions with the height being made into a passable/impassable cost.


Prove that "Finishing the degree in three years" problem is NP-Complete

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "edge course") in $G$. Each edge course has two precondition vertex courses corresponding to its two endpoints. In addition, we set $m_1=k,m_2=+\infty, m_3=m-\binom{k}{2}$ where $m$ is the number of edges in $G$. Now we can see there is a clique of size $k$ in $G$ if and only if it is possible to finish the degree in three years.


How profiling is done in trace scheduling?

Yes, profiling is normally done by running the program.  Yes, running the program and then gathering information about execution frequencies is how this is normally done.  As Paul A. Clayton suggests, read more about profile-guided optimization to learn more about techniques commonly used in this field -- there's a rich literature on profile-guided optimization.

There are alternatives based on various heuristics or static analysis algorithms, but profiling normally implies running the program, and profiling will usually be considerably more accurate than any static technique.


Recursive-Descent Predictive Parser for $S \rightarrow 0S1\ |\ 01$

You may need to modify the grammar. In general this is not necessarily possible (not every CFG is an LL(k) grammar - the class suitable for recursive descent predictive parsing). In this case we can modify the grammar to:

$$\begin{align*}
  &\mathtt{1.} & S &\rightarrow 0SA \\
  &\mathtt{2.} & S &\rightarrow \varepsilon \\
  &\mathtt{3.} & A &\rightarrow  1 \\
\end{align*}$$

Then we have an unambiguous first and follow set for each combination of terminal and non-terminal. So the parsing table looks something like:

$$\begin{array}{l|l|l}
    & 0           &  1 \\ \hline
  S & \mathtt{1.} & \mathtt{2.} \\ \hline
  A &             & \mathtt{3.} \\
\end{array}$$

This gives an LL(1) grammar - one that can be parsed with one symbol of lookahead. It is possible to parse the original grammar without modification using 2 symbols of lookahead (making it an LL(2) grammar), Raphael explains that approach excellently in his answer.

The details are all in the dragon book of course (what isn't!), and better explained there than I can do here.


Converse proof for random coding capacity of AVC

A complete proof appears in Blackwell, Breiman and Thomasian, The Capacities of Certain Channel Classes Under Random Coding. This paper is linked from the Wikipedia article on AVCs.


"Coalescing" can also refer to coalescing memory access patterns. In this usage, coalescing is used to mean making sure that threads run simultaneously, try to access memory that is nearby. This is usually because:

Memory is usually retrieved in large blocks from RAM.
Some processing units will try to predict future memory accesses and cache ahead, while yet processing older parts of memory.
Memory is cached in a hierarchy of successively larger-but-slower caches.

Therefore, making programs that can use predictable memory patterns is important. It is even more important with a threaded program, so that the memory requests do not jump all over; otherwise the processing unit will be waiting for memory requests to be fulfilled.
Diagrams inspired by Introduction to Parallel Programming: Lesson 2 GPU Hardware and Parallel Communication Patterns:
Below: Four threads, with uniform memory access. The black dashed rectangle represents a single 4-word memory request.

The memory accesses are close, and can be retrieved in one go/block (or the least number of requests).
However, if we increase the "stride" of the access between the threads, it will require many more memory accesses. Below: four more threads, with a stride of two.

Here you can see that these 4 threads require 2 memory block requests. The smaller the stride the better. The wider the stride, the more requests are potentially required.
Of course, worse than a large memory stride is a random memory access pattern. These will be nearly impossible to pipeline, cache or predict.
TikZ sources:

Memory.Access.Coalescing.tex (writelatex)


A problem that is computable yet doesn't lie in NP?

The time hierarchy theorem says that, if you allow more time, you can solve more problems. It's normally stated for deterministic machines but it applies to nondeterministic ones, too. In particular, nondeterministic Turing machines running in exponential time can solve problems that no polynomial-time NTM can. NTMs running in doubly-exponential time can solve even more, and so on for triply-exponential, quadruply-exponential and so on.

So you need to investigate the class NEXP, and find some problems in there that are known not to be in NP.


Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?

You are making a classical mistake in applying the pumping lemma. The pumping lemma states that each word $w$ of length at least $N$ in the language (where $N$ is the number of states in the minimal DFA for the language) can be decomposed as $w = xyz$, where $|xy| \leq N$, $|y| \geq 1$, and $xy^i z$ is in the language for all $i$. You don't get to choose this partition! The lemma just states that there is some partition. Taking as an example your word $a^3 b^t$, since $N = 6$ (indeed, the minimal DFA for the language has $6$ states), we can always choose $x = a^3$ and $y = b$, and then $xy^i z = a^3 b^{t+i-1}$ which is always in the language (since $t \geq 3$).

When you use the pumping lemma to prove that a language is not regular, you don't know $N$, and so you have to start by taking $N$ to be arbitrary, and run the proof from there. What you are in effect showing is that for each $N$, there is no DFA accepting the language with at most $N$ states.


Prove that PP is closed under complement

$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that you accept can't be exactly 0.501. It's either 0 (you never accept), 1/4 (one coin flip combination leads to acceptance), 1/2 (two combinations make you accept), 3/4 or 1.

So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.


Two definitions of balanced binary trees

Definition 1. is also known as weight-balancedness¹ and definition 2. as height-balancedness.

Height-balancedness does not imply weight-balancedness; examples are both AVL- and Red-Black-Trees. See here and here for proofs, respectively.

Weight-balancedness does imply height-balancedness, though. This can be proven by showing the following stronger fact by induction (over height): a weight-balanced tree is complete on all levels but the deepest². The essential argument in the inductive step is that the subtrees can't have a height difference of more than one because -- both having the claimed property by induction hypothesis -- they would then not be weight-balanced.

The article gives a different, more general definition.
In other words, such a tree of height $k$ without the leaves at level $k$ is a perfect tree of height $k-1$.


There is no optimal scheme for encoding integers. To understand what this statement even means, we need a few definitions.

A codeword $w$ is a word over the alphabet $\{0,1\}$.

A sequence of codewords $w_0,w_1,w_2,\ldots$ is a code.

A code $w_0,w_1,w_2,\ldots$ is prefix-free if no $w_i$ is a prefix of any $w_j$ for $i \neq j$.

A code $w_0,w_1,w_2,\ldots$ is monotone if $|w_0| \leq |w_1| \leq |w_2| \leq \cdots$.

An integer encoding scheme is a monotone prefix-free code.

An integer encoding scheme $x_0,x_1,x_2,\ldots$ is better than an integer encoding scheme $y_0,y_1,y_2,\ldots$ if $|x_i| - |y_i| \to -\infty$.

The codes that you give are examples of integer encoding schemes which get progressively better.

Theorem. For any integer encoding scheme $y$ there is a better integer encoding scheme $x$.

In fact, the situation is even worse: there is no optimal sequence of codes:

Theorem. For any sequence $y_1,y_2,\ldots$ of integer encoding schemes there is an integer encoding scheme $x$ better than all of them.

For proofs see, for example, this paper.

Elias came up with a sequence of codes, including the gamma and delta codes, which are progressively better, culminating in the limiting omega code; but even this code isn't optimal.


There has been a lot of work in genetic programing (GP) in this vein. Automatically defined functions are a big deal in GP and figuring out how many and what kinds of ADF's you should have (the "Architecture") has been the subject of a lot of research as well. More generally some people have looked at how to use GP to create libraries that it can then work with to make new more complex functions.

GP can often create perfect solutions like reversing a list or sorting lists. More often how ever it generates approximate solutions. It is really clever what all it can do however. John Koza (a really big name in GP) used genetic programing to find entirely new circuits that had never been created before and were effectively open problems in electrical engineering. To do this he had it design everything from the ground up but it had many recognizable circuits as sub parts. One could imagine that it might have made these things faster if it had already had those designed parts in its library.


How to convert regular expression to CFG?

There is a simple algorithm to convert regular expressions to context-free grammars. It goes as follows.
Base cases:

$\emptyset$ corresponds to the empty grammar.
$\epsilon$ corresponds to the grammar $S \to \epsilon$.
$\sigma$ (where $\sigma \in \Sigma$) corresponds to the grammar $S \to \sigma$.

Inductive cases:

$r = r_1 + r_2$. Given CFGs for $r_1,r_2$ with disjoint nonterminals and starting symbols $S_1,S_2$, add rules $S \to S_1 \mid S_2$ and make $S$ the new starting symbols.
$r = r_1r_2$. Same, adding the rule $S \to S_1 S_2$ instead.
$r = r_1{}^*$. Same, adding the rules $S \to S S_1 \mid \epsilon$ instead.


Supervised learning with no prior information

I think that the success of a newborn child follows from the fact that the phenomena he's trying to learn is describable (or can be sufficiently approximated) by the hypothesis class generated by the learning algorithm which is going on in his brain.

This is of course, not formal in any way, but say a baby is equipped with some neural network (of fixed depth), and upon receiving new data, the weights are updated accordingly using some algorithm.

The choice of neural network doesn't really matter, simply imagine that you have carefully studied the processes going on inside the human brain, and found out that the human learning process is similar to using a neural net.

In that case, the image of the learning algorithm is some class $\mathcal{F}$, say functions expressible by some fixed depth nets, and the success of the baby in learning new things simply means that the phenomena he's trying to learn is captured by $\mathcal{F}$ (so nothing magical/contradicting what you quoted is going on).

To make sure this answer does more than just contain some of my random thoughts, I will add that if you truly know nothing, there is nothing you can hope to learn. The data you're receiving could always be generated from the uniform distribution, i.e. someone is tossing a coin and giving you the outcome. Obviously, in that case, you can not hope for a small generalization error.


The "go back to start" edge doesn't matter because of nondeterminism and the fact that you can read any string at all while staying in state $s$. Any string that the automaton accepts has an accepting run that doesn't use the "go back to start" edge.


Conceptual overview: Self-information, Mutual information, uncertainty, entropy

Trying to answer the question myself, with my textbook at hand. So far, I am here:

Self-information of an event: uncertainty of an event.
$$I(x_i) = \log \frac{1}{P(x_i)} = -\log P(x_i)$$
Self information of a vector event:
$$I(x_i y_i) = -\log P(x_i,~y_i)$$
Mutual information between two events: the information one event (experiment outcome) gives us about the other event:
$$I(x_i;y_i) = \log \frac{P(x_i,~y_i)}{P(x_i) P(y_i)}$$
$$I(x_i y_i) = I(x_i) + I(y_i) - I(x_i; y_i)$$
Uncertainty: the formula of it is the same as self-information of an event. So I'll assume they are the same.
Average mutual information: The information one gives about the other when observer the former. Clumsy notation:
$$I(X; Y) = E[I(x_i; y_i)]$$
Entropy: the average amount of information that is revealed by observing an event. (I know the relationship to Huffman coding here.) Clumsy notation:
$$H(X) = E[I(x_i)]$$
Conditional entropy: the amount of information (about $X$) that is left to be discovered after observing the given ($Y$).
$$H(X|Y) = H(X) - I(Y;Y)$$

\begin{align}
I(X; Y) &= H(X) - H(X | Y) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}

Conditional self-information: the information that is contained within the outcome of a certain event ($x_i$), after already knowing the outcome of another event ($y_i$).
$$I(x_i | y_i) = -\log P(x_i | y_i)$$
Relations:
$$I(x_i | y_i) = I(x_i) - I(x_i; y_i)$$
\begin{align}
I(x_i; y_i) &= I(x_i) - I(x_i | y_i) \\
\text{mutual} &= \text{a priori} - \text{a posteriori}
\end{align}


What is the regular expression to the given language?

Look at the three parts of your language:

For the $a^{3k-1}$ part, we have possibilities $a^2, a^5, a^8, \dots$. For this part we'll have any 2 $a$s plus a multiple of 3 $a$s. That's expressible as $aa(aaa)^*$.
The $b^n$ part is easy, it's just $b^+$, since you need $n>0$.
The $a^{2t}$ part is likewise easy. Since $t\ge 1$ we can express this as $(aa)^+$.

Now concatenate these three regular expressions.


Disk scheduling algorithm - SCAN and C-SCAN

Here are the examples of various disk scheduling algorithms.

Yes you are correct in both the case. The author here has made mistake.
For SCAN: The answer should be 236.
For C-SCAN: The answer should be 146+37=183.(Note: The head movement when its not servicing any requests is not counted.)
Refer the link, it gives a clear concept of how the different kinds of disk scheduling algorithms are used in practice.


What is the type theory judgement symbol?

It's called a "turnstile". See the Wikipedia article.


How can it be decidable whether $\pi$ has some sequence of digits?

There are only two possibilities to consider.

For every positive integer $n$, the string $0^n$ appears in the decimal representation of $\pi$.  In this case, the algorithm that always returns 1 is always correct.
There is a largest integer $N$ such that $0^N$ appears in the decimal representation of $\pi$.  In this case the following algorithm (with the value $N$ hard-coded) is always correct:

Zeros-in-pi(n):
 if (n > N) then return 0 else return 1

We have no idea which of these possibilities is correct, or what value of $N$ is the right one in the second case.  Nevertheless, one of these algorithms is guaranteed to be correct.  Thus, there is an algorithm to decide whether a string of $n$ zeros appears in $\pi$; the problem is decidable.

Note the subtle difference with the following proof sketch proposed by gallais:

  Take a random Turing machine and a random input.
  Either the computation will go on for ever or it will stop at some point and there is a (constant) computable function describing each one of these behaviors.
  ???
  Profit!

Alex ten Brink explains:

  watch out what the Halting theorem states: it says that there exists no single program that can decide whether a given program halts. You can easily make two programs such that either one computes whether a given program halts: the first always says 'it halts', the second 'it doesn't halt' - one program is always right, we just can't compute which one of them is!

sepp2k adds:

  In the case of Alex's example neither of the algorithms will return the right result for all inputs. In the case of this question one of them will. You can claim that the problem is decidable because you know that there is an algorithm that produces the right result for all inputs. It doesn't matter whether you know which one that algorithm is.
  10


Is "Feral Concurrency Control" a disparaging description?

Sorry for coming to this issue so late. For context, I am one of the coauthors of the paper. The term "feral concurrency control" in the paper was inspired by the common usage "feral database" (similarly "feral system") said by IT admin people, to refer to databases or systems that were run by staff outside the control of IT services. For example, a university department might keep a database of student information, separate from the centrally managed official student record system. See https://en.wikipedia.org/wiki/Feral_information_systems

The connotation is of something that has escaped from control and is acting wild (like a feral cat is a cat that is, or descends from one which, escaped from domestication and became wild)


Your coin flips form a one-dimensional random walk $X_0,X_1,\ldots$ starting at $X_0 = 0$, with $X_{i+1} = X_i \pm 1$, each of the options with probability $1/2$. Now $H_i = |X_i|$ and so $H_i^2 = X_i^2$. It is easy to calculate $E[X_i^2] = i$ (this is just the variance), and so $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ from convexity. We also know that $X_i$ is distributed roughly normal with zero mean and variance $i$, and so you can calculate $E[H_i] \approx \sqrt{(2/\pi)i}$.

As for $E[\max_{i \leq n} H_i]$, we have the law of the iterated logarithm, which (perhaps) leads us to expect something slightly larger than $\sqrt{n}$. If you are good with an upper bound of $\tilde{O}(\sqrt{n})$, you can use a large deviation bound for each $X_i$ and then the union bound, though that ignores the fact that the $X_i$ are related.

Edit: As it happens, $\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$ due to the reflection principle, see this question. So
$$
\begin{align*}
E[\max_{i \leq n} X_i] &= \sum_{k \geq 0} k(\Pr[X_n = k] + \Pr[X_n = k+1]) \\
&= \sum_{k \geq 1} (2k-1) \Pr[X_n = k] \\ &=
\sum_{k \geq 1} 2k \Pr[X_n = k] - \frac{1}{2} + \frac{1}{2}\Pr[X_n = 0] \\ &= E[H_n] + \Theta(1),
\end{align*}
$$
since $\Pr[H_n = k] = \Pr[X_n = k] + \Pr[X_n = -k] = 2\Pr[X_n = k]$. Now
$$ \frac{\max_{i \leq n} X_i + \max_{i \leq n} (-X_i)}{2} \leq \max_{i \leq n} H_i \leq \max_{i \leq n} X_i + \max_{i \leq n} (-X_i), $$
and therefore $E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$. The other direction is similar.


As you correctly noted, the case 1 of the Master theorem applies here. In other words, the case 1 applies if $f(n) = O(n^{\log_b a - \lambda})$ for some constant $\lambda > 0$.

Indeed, we will have to see if we can find some $\lambda > 0$ so that in this case, $\log n = O(n^{\log_4 2 - \lambda}) = O(n^{1/2-\lambda})$. Easy, we can pick any $\lambda < 1/2$. Finally, be careful what the Master theorem now tells you: the solution to the recurrence

$$T(n) = \Theta(n^{\log_4 2}) = \Theta(n^{1/2}) = \Theta(\sqrt n).$$


Question about the formal proof of the inorder traversing

It is definitely possible to analyze this algorithm using Hoare triples. The first step would be to replace the VISIT procedure calls with some more reasonable accounting mechanism, say a list that lists the visited nodes in order. You then define formally what a binary tree is and what an inorder traversal is, something along the following lines:

Tree = Leaf N | Node N LTree RTree
Inorder(Leaf N) = N
Inorder(Node N LTree RTree) = Inorder(LTree) || N || Inorder(RTree)

Here N is the "name" of the node, and || is list concatenation. Armed with these notions, it is an exercise to construct the required Hoare triples. You will probably need to come up with even more notions (for example, you will need to explain what the contents of the stack are when a node P is popped).

What do we gain from this exercise? Do we understand the algorithm any better? Probably not. But we understand how to reason precisely about algorithms, something which is useful if you plan on doing software verification or programming language theory, areas forming the so called "Theory B". If you're more of a "Theory A" type (algorithms and complexity) then, like me, you will find such exercises somewhat beside the point.


Optimization over convex combinations in a circle

A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms.

In particular, define parameters $\theta_1,\theta_2,\theta_3$, representing the angle from the horizontal of $D_1,D_2,D_3$, respectively.  Here each $\theta_i$ is in the range $[0,2\pi)$.  The locations of $D_1,D_2,D_3$ are completely determined by the value of $\theta_1,\theta_2,\theta_3$.  Therefore, we can express the value of $F$ as a function of $\theta_1,\theta_2,\theta_3$: let's write this as $F^*(\theta_1,\theta_2,\theta_3)$.  It's tedious but not too hard to write down an explicit expression for $F^*$.

The problem becomes: given an expression for $F^*$, find $\theta_1,\theta_2,\theta_3$ that maximize $F^*(\theta_1,\theta_2,\theta_3)$, subject to $0 \le \theta_1,\theta_2,\theta_3 < 2\pi$.  This is a mathematical optimization problem on a three-dimensional objective function $F^* : [0,2\pi)^3 \to \mathbb{R}_{\ge 0}$.  There are standard algorithms for maximizing such a function, e.g., using gradient descent or any number of other methods.  You can try applying any of them.

In practice, I suggest you run gradient descent, starting from an initial point (an initial assignment to $\theta_1,\theta_2,\theta_3$) chosen at random.  Run gradient descent until convergence.  This will give you a local maximum.  Repeat this 1000 times, with 1000 different randomly chosen starting values, and take the best solution found in any of these iterations.  While there are no guarantees, I expect this to work well.  Generally speaking, these methods tend to work very well when the number of dimensions is small, and in this case, you have only 3 variables and 3 dimensions, so I expect they'll work well.  In particular, I expect the function $F^*$ to be piecewise smooth, with only a small finite number of pieces, so this procedure will probably ensure that you have at least one starting point in each piece and thus that gradient descent finds the maximum within each piece, ensuring that you find the global maximum with high probability.

If you wanted to do a more careful analysis, you could probably work out analytically the boundaries of each piece (i.e., decompose the three-dimensional space $[0,2\pi)^3$ into a finite union of regions within which $F^*$ is continuous and differentiable) and then run one iteration of gradient descent per piece.  However, that sounds tedious, and it's probably easier to just slam the thing into an off-the-shelf optimization tool and let the computer do the grunt work for you.  Doing the delicate analysis might be important if you want a procedure that is guaranteed correct in all cases (e.g., long and skinny triangles, etc.), but if you just want something that'll probably work without working too hard, I suggest you spare yourself the headache and let the computer do the crunching.


How to calculate the number of tag, index and offset bits of different caches?

The question as stated is not quite answerable.  A word has been defined to be 32-bits.  We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.)  You need to know this to know what the lowest-order bit of an address is telling you.

Then you work from the bottom up.  Let's assume the system is byte addressable.

Then each cache block contains 8 words*(4 bytes/word)=32=25 bytes, so the offset is 5 bits.

The index for a direct mapped cache is the number of blocks in the cache (12 bits in this case, because 212=4096.)

Then the tag is all the bits that are left, as you have indicated.

As the cache gets more associative but stays the same size there are fewer index bits and more tag bits.


What is the difference between storage media and storage devices

Media is what holds the information, e.g. disk platen, CD, magnetic stripe.
Device is what uses the media and provides a physical interface.

For devices that have removable media, such as CD/DVD players the distinction is easy. For other devices where the media is an integral part of the device, the distinction is not so easy because the media is not designed to be removed, e.g. hard drive, thumb drive.


What is +1 in binary search time complexity

The exact number depends on your assumptions, so either is defensible.  If you assume that the number you're searching for is definitely in the list, and it's just a matter of finding it, then the number of comparisons needed can be as large as $\lceil \lg n \rceil$, and won't be any larger than that.  (Here $\lceil \cdot \rceil$ represents rounding up to the nearest integer.)  Since $\lceil \lg n \rceil \le 1 + \lg n$, it is not unreasonable to describe the worst-case number of comparisons needed as $1 + \lg n$.  Again, as a reminder, this assumes that the number you're searching for is definitely present.

That said, in theoretical analysis, we usually ignore constant factors.  So, we summarize the running time as $O(\lg n)$.  For these purposes, there is no difference between $\lg n$ or $\lg n+1$; they are both $O(\lg n)$.


On Tarjan's paper "Finding a Maximum Clique"

You definition of $A(C)$ is wrong. It is the set of vertices adjacent to all vertices in $C$:
$$
A(C) = \{ v \in V : \forall u \in C, (u,v) \in E \}.
$$
In particular, if $C = \emptyset$ then $A(C) = V$.
In your example, suppose that $S = \{v\}$. Let's see what $|C| + \|G_{A(C) \setminus S}\|$ amounts two for all choices of $C$:

If $C = \emptyset$, then $A(C) \setminus S = V \setminus \{v\}$, and so $|C| + \|G_{A(C)\setminus S}\|$ is the maximum size of a clique in $G$ that doesn't contain $v$.
If $C = \{v\}$, then $A(C) \setminus S = N(v)$, the set of neighbors of $v$. Therefore $|C| + \|G_{A(C) \setminus S}\|$ is the maximum size of a clique in $G$ that contains $v$.

So in this case, the formula is correct.
When $S = \emptyset$, the formula just states that $\|G\| = \|G\|$.


Equivalence of two context free grammars [for the given example]

Both grammars generate the language of words having an equal number of a's and b's. Here are some hints on how to prove that.

Grammar $G_1$: Prove by induction on derivation length that

Every word generated by $S$ has an equal number of a's and b's.
Every word generated by $A$ has one more a's than b's.
Every word generated by $B$ has one more b's than a's.

This shows that every word generated by $G_1$ has an equal number of a's and b's. For the other direction, prove by induction on word length that

Every word having an equal number of a's and b's can be generated by $S$.
Every word having one more a's than b's can be generated by $A$.
Every word having one more b's than a's can be generated by $B$.

This part is more complicated, though the different cases you have to consider follow closely the rules of the grammar.

Grammar $G_2$: Easy induction on derivation length shows that every word generated by $S$ has an equal number of a's and b's. For the other direction, prove by induction on the length of the word that every word which has an equal number of a's and b's can be generated by $S$, as follows.

Given a word $w$, consider the walk generated by $w$ starting at the origin in which $a$ corresponds to a step up and to the right and $b$ corresponds to a step down and to the right. The walk ends on the X axis (since the number of a's and b's is equal). Let $x$ be the prefix of $w$ corresponding to the first time in which $w$ reaches the X axis (after the empty prefix), and write $w = xy$. If $y$ is empty then $x$ must start and end with different letters, so the one of the productions $S\to aSb|bSa$ can be used, and otherwise the production $S\to SS$ can be used.


Resizing and aliasing in computer science

When you resize to a lower resolution, there are several ways to do
it. If you average values of the pixels that merge into a single one,
you simply have a loss of resolution, which amounts to keeping only
the lower spatial frequencies (counting frequencies relative to image
size, not to pixel size).  However, if you reduce resoution by
sampling, i.e. replacing a bunch of pixels by the value of one of
them, you may overplay high frequencies, not meaningful at the given sampling (spatial) frequency, leading to all kinds of
artefacts such as moiré effects for images.

When you recreate the image at former resolution, you cannot in
principle recreate
lost information. But you try to make educated guess as to the effect
most likely to occur or not to occur in most images. Hence, you apply
some reprocessing to the image so as to eliminate unlikely phenomena,
or play down phenomena that you know could not have survived the initial size
reduction (they may or may not have been there, but you know that
later presence is not due to original existence).

Typically, as you know that the image reduction has necessarily lost
some higher spatial frequencies, or distorted their role, you can
choose to eliminate or play doen those frequencies at the recreated higher
resolution, as they do not originate from the initial image.

For example, if you had a large geometric image, reduction and back
resizing will produce a staircase effect on most straight lines. These
abrupt changes correspond to high spatial bandwith. By removing these high
frequencies, you will recreate shaded areas that smooth down the staircase effect on the
straight lines.

Aliasing has to do with the artefact due to the combined effect of
sampling and reproducing back a sampled observation of a theoretically
continuous phenomenon (or considered as such because its initial resolution is
significantly greater than the sampling rate), may be an image, a
sound, a film,etc. As seen above, the sampling technique does matter.
Antialiasing consist of the techniques used to eliminate
artefacts known as likely to occur.  It cannot recreate lost
information unless you knew separately that the processed information
has to satisfy some constraints, which antialiasing can then use to
improve the image. For example, you may know that geometric images use
straight lines more often than small staircases.

Wikipedia has more technical information.


Why does the principle of locality of computation not relativize?

When you go into a special "oracle" step, the oracle reads the entire contents of the oracle tape and determines its output based on the entire tape. This is the non-local aspect of oracle computation.


It's not correct. The instruction that would determine the result of the condition is read at cycle x. The conditional branch is read at cycle x + k. k can be any value, depending on the code. For example I can have a comparison "compare x and 0", then half a dozen unrelated instructions, then an instruction "branch if the comparison result is 'greater'". You are saying the correct condition is determined at cycle x + 14. You lose 14 - k cycles.

You may find out 14 cycles later that the branch was predicted wrongly, or 8 cycles later, or in the next cycle. What is lost is the cycles between branch prediction and the point where the correct way became known, which is variable. In this situation, compilers will often try to issue the comparison as early as possible before the branch instruction, to minimise the penalty for an incorrect branch.

To clarify: If a compare instruction is read at cycle x, and the result of the comparison is available at cycle x+14, and a conditional branch instruction is read at cycle x + k, then it doesn't matter at which stage in the pipeline the incorrect branch is detected. What matters is the time from the start of the conditional branch, to the time of detection of the incorrect branch, and that time is variable. If the compare instruction is issued early enough then the branch isn't even predicted because the result of the compare instruction is known.


Simplify the definition of substitution in Lamdba calculus

Yes, there are several techniques, such as de Bruijn indices and explicit substitutions. Actual implementations, at least those that actually have to work efficiently, use such techniques and never implement substitution by renaming variables.


Meaning of type inference rule for abstraction in lambda-calculus

The problem is that whatever the context $\Gamma$ may imply about the
variable $x$ is irrelevant. This rule is intended to type a
$\lambda$-abstraction, and the variable $x$ may be changed to another
variable by $\alpha$-conversion, without changing the semantics of the
$\lambda$-abstraction,  and thus without changing its type.

By writing $\Gamma, x: \tau_1$, we are considering a context $\Gamma$
where the variable $x$ has type $\tau_1$, ignoring what the type of
$x$ may have been in context $\Gamma$ alone. If $x$ could be assigned
a type in the context $\Gamma$ alone, it would refer to some homonymous variable that is irrelevant to the abstraction, since its scope is shadowed in the abstraction by the local variable $x$. Indeed, an $\alpha$-conversion would make $x$ disappear from $e$ altogether.

In other words: $\Gamma \vdash x: \tau_1$ may or may not be true, but
it is simply irrelevant to typing the abstraction.

Then, it is possible that $\Gamma \vdash e: \tau_2$. But that is only
possible if the type of $x$ is irrelevant, for example when $x$ does
not actually occurs in $e$, as for the abstarction $\lambda x.42$,
Then $e=42$ which is indeed typable. But in general, you cannot type $e$ without having a type for $x$ (for the variable $x$ of the abstraction).

In other words, you expect the type of $e$ to be in general related to the type of $x$, and it is their relation that the rule is intended to express.

What the rule says is that, if by adding to the context $\Gamma$ that the new
variable $x$ has type $\tau_1$, you can infer then that $e$ has type
$\tau_2$ in this new environment, then the abstraction $\lambda x. e$
has type $\tau_1 \rightarrow \tau_2$ in the original environment
$\Gamma$.

It says that the type of $e$ is dependent on the type $x$ may have.

Then, wherever the abstraction is applied to another expression $e'$, the type of the application is whathever the type of $e$ should be when the type of $x$ is that of $e'$.  But that is another typing rule.


If you could accept an approximate solution for this problem, then the following approach would help you. Your cylinders are thin, so if two of them intersect, then their axial segments almost touch each other. If you project such a pair of almost touching segments on each of coordinate planes you'll see that their projections almost always intersect.

So - project your set of segments on three coordinate planes and apply the Bentley-Ottmann (or similar) algorithm three times to find all the intersections. Select pairs of segments, which intersect on all three planes, calculate distance between them and verify the cylinders intersection.

This method can give you false negatives - for example in the case, when two cylinders are collinear with small gap between them. However, this method won't give you false positives, because you explicitly verify each suspicious pair of cylinders.


Password authentication over an insecure connection

If you don't use a secure connection, it is vulnerable to man-in-the-middle attacks, so not secure.

If you do use a secure connection, then it is no better than sending the password directly.


You can get an unambiguous grammar by thinking of words in $L$ as walks that start and end on the Y axis; each $a$ corresponds to a move $\nearrow$, and each $b$ corresponds to a move $\searrow$. Each such walk can be decomposed into segments of the form $\nearrow \cdots \searrow$ and $\searrow \cdots \nearrow$ which only touch the Y axis at the endpoints. Moreover, this decomposition is unique.

In turn, in a walk of the form $\nearrow \cdots \searrow$, the $\cdots$ part is itself a concatenation of walks of the same form, and this decomposition is unique. Alternatively, if you convert $\nearrow \mapsto ($ and $\searrow \mapsto )$, then walks of the form $\nearrow \cdots \searrow$  become valid strings of balanced parenthesis, surrounded by a pair $()$.

Putting everything together, we get the following unambiguous grammar:
$$
\begin{align*}
&S \to AS \mid BS \mid \epsilon \\
&A \to a X b \\
&X \to AX \mid \epsilon \\
&B \to b Y a \\
&Y \to BY \mid \epsilon
\end{align*}
$$
Actually proving that this grammar generates $L$ and that it is unambiguous is tedious, and left to you.


How does this reduction to prove undecidability account for epsilon?

Let $x = \langle M, w \rangle \in H$, where $H$ is the usual haltingproblem. Then $\langle M_2 \rangle$ halts on every input, especially on $\varepsilon$ and by construction accepts every input, especially $\varepsilon$. Hence, $f(x) = \langle M_2 \rangle \in ES$.

Now assume $x = \langle M, w \rangle \notin H$, i.e. $M$ loops on $w$. Then $M_2$ loops on every input, especially $\varepsilon$ and thus, never accepts it. $\langle M_2 \rangle \notin ES$.


Your understanding is correct.

The key point about TSP is that we are given a distance between every pair of cities. In other words, formally speaking, TSP is the problem of finding a minimum-weight Hamiltonian path/cycle on a weighted complete graph, given the weight function.  This doesn't quite correspond to the standard intuition where a salesman is travelling around an actual road network and is forbidden from visiting the same city twice, for reasons nobody can really explain.

In graphic TSP, the distance function is defined in terms of some (possibly weighted, possibly directed) graph on the given vertices.  This is much closer to the usual intuition about what TSP is: driving from, say, Baltimore to New York by the fastest route might involve passing through Philadelphia but, even if we've already visited Philadelphia, we're allowed to pass through again without stopping.


Dijkstra to favor solution with smallest number of edges if several paths have same weight

Given a graph $G = (V,E,w)$, we define $G'=(V,E,w')$ with $w'(e) = aw(e) + 1$ where $a = |E| + \varepsilon$ for some $\varepsilon \geq 0$ as proposed in the comments of the question.

  Lemma
  Let $P$ a path in $G$ with cost $C$, i.e. $w(P)=C$. Then, $P$ has cost $aC + |P|$ in $G'$, i.e. $w'(P) = aC + |P|$.

The lemma follows directly from the definition of $w'$.

Call the result of Dijkstra on $G'$ $P$, which is a shortest path in $G'$. Assume $P$ was not a shortest path with fewest edges (among all shortest paths) in $G$. This can happen in one of two ways.

$P$ is not a shortest path in $G$.
Then, there is a path $P'$ with $w(P') < w(P)$. As $|P|,|P'| \leq |E| \leq a$, this implies that also $w'(P') < w'(P)$ with above lemma¹. This contradicts that $P$ was chosen as shortest path in $G'$.
$P$ is a shortest path but there is a shortest path with fewer edges.
Then, there is another shortest path $P'$ -- i.e. $w(P) = w(P')$ -- with $|P'| < |P|$. This implies that $w'(P') < w'(P)$ by above lemma, which again contradicts that $P$ is a shortest path in $G'$.

As both cases have led to a contradiction, $P$ is indeed a shortest path with fewest edges in $G$.

That covers one half of the proposition. What about $a < |E|$, i.e. $a = |E| - \varepsilon$ with $\varepsilon \in (0,|E|)$?

Actually, we also need that $a$ or all weights in $G$ are integers. Otherwise, $w(P') < w(P)$ does not cause the weights in $G'$ to be at least $|E|$ apart. This is not a restriction, though; we can always scale $w$ with a constant factor so that all weights are integer, assuming we start with rational weights.


Construct a DAG from given multiple topological orderings

Approach 1
For example, consider the two orders: 1, 2, 3, 4, 5 and 2, 4, 1, 5, 3.
According to your approach, we will get a cycle 1->2->3->4->1. We then remove 3->4 and 4->1, and obtain a graph:
     ______
    /      \
1->2->4->5->3
 \______/

Now 5->3 and 1->2 respectively violate the first and the second orders, so we remove them, and get
     ______
    /      \
1  2->4->5  3
 \______/

Now node 2 has 2 outgoing edges. Removing either one makes a final graph where 3 nodes (1, 2, 3 or 1, 2, 4) have in-degree 0.
However, there exists a graph
1->3 2->4->5

where both orders are satisfied but only 2 nodes have in-degree 0.
So Approach 1 is incorrect.
Approach 2
Consider an optimal solution. Every edge in this optimal solution must be the form $(a_i,a_j)$ where $i<j$ in each order. This means all edges in the optimal solution are contained in the intermediate graph. So if you then remove the outgoing edges such that the number of nodes having in-degree 0 is minimum, you will get a correct optimal solution.
However, your approach that trying to make the number of nodes having in-degree 0 minimum is incorrect.
For example, consider the three orders:
\begin{align}
1, 2, 3, 4, 5, 6, 7, 8 \\
5, 1, 6, 3, 8, 2, 4, 7 \\
2, 7, 3, 8, 1, 4, 5, 6
\end{align}
First we can obtain the following intermediate graph:
    _____
   / ____\__
  / / ____\_\__
 / / /     \ \ \
1 2 3->4 5->6 7 8
 \ \__/
  \__/

Applying your approach, we will remove 1->4, 2->4 and 3->4 (or 3->8), and there are 5 nodes with in-degree 0: 1, 2, 3, 4 (or 8), 5. However, the optimal solution would be
     _______
    / ____ _\__
   / /       \ \
1 2 3 4 5->6 7 8
 \___/

where only 4 nodes have in-degree 0: 1, 2, 3, 5.


Prove that $L = \{ xy \in \{a , b \}\textbf{*} \mid |x|_a = 2|y|_b \}$ is not regular

Here are several routes to proving this:

Intersect with $a^*b^*$ and apply an appropriate inverse homomorphism to reduce to the language $\{a^nb^n : n \ge 0 \}$, which you know isn't regular.
Use Myhill–Nerode theory: the words $\{a^n : n \geq 0\}$ are pairwise inequivalent.
Use the pumping lemma on the word $a^{2p} b^p$, where $p$ is the pumping constant.


Understanding NFA (nondeterministic finite automaton) with a null transition

If a run of an automaton reaches a state where it has no legal transitions for the next input character, that run rejects immediately.

So, in your example, if the automaton makes the null transition, it can read $bb$ while staying in state $2$.  But when it reads the $a$, it has no legal transition so that run rejects.  Any run that stays in states $0$ and $1$ must also reject, because those two states are rejecting states. Therefore, the automaton does indeed reject all strings containing $bba$.


Solving the recurrence of recursive insertion sort

Why do u need to guess?
T(n) = T(n-1) + cn  {c is a const}
T(n) = T(n-2) +c(n-1) +cn
     = T(n-3) +c*[(n-2)+ (n-1) + n]
.....

Keep going this way till u reach the arithmetic sequence  (2+...+(n-1)+n]. So,

T(n) = T(1) + c* n(n-1)/2 = O(n2)

You may check any Algorithms book or lecture notes on solving recursive equations; we don't usually guess, there r rules and this one is trivial.


Is there a designation for this not-quite-exponential time?

Two useful classes are sub-exponential, $c^{n^\epsilon}$ for $\epsilon \in (0,1)$, and quasi-polynomial, $c^{\log^k n}$ for $k > 1$. (In both cases, $c > 1$.)

The terms themselves sometimes have different meanings. For example, in some contexts "sub-exponential" means $2^{(1-\epsilon)n}$ for some $\epsilon > 0$, and in others it means $2^{o(n)}$.

Since the term "sub-exponential" is loaded, it is better to mention what you mean by it whenever you use it.


Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

What's the smallest possible j, and which i goes with it (to allow j < i < 2j). So that's the minimum number of a's and b'. Beyond that, you need one or two a's for every additional b.
That should be enough to find a grammar.


Modifying Floyd–Warshall Algorithm for Vertex Weights

"I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work."

Yes, your cool idea works! In fact, other people have found the same cool technique of including vertex weight in the new edge weight. By the way, I would not say you have modified the Floyd-Warshall algorithm. It is better to say that you have adapted the problem brilliantly so that Floyd-Warshall algorithm can be applied flawlessly.

"If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful"

It looks like there is little chance for you to become thankful by that cause.


Metaheuristic for NP-complete problem without exact algorithms other than brute-force

Thanks to user AdrianN (see comments) I was able to find a paper which presents a Mixed 0-1 Linear Program to find all Pure Nash Equilibria in n-player games. The method is an exact method and the authors provide performance results.

Zhengtian Wu et al. “A Mixed 0-1 Linear Programming Approach to the Computation of All Pure-Strategy Nash Equilibria of a Finite n-Person Game in Normal Form”

This, however, only answers half the question.
This question remains:

  Is it useful to design metaheuristic algorithms for a problem like
  this when its performance can not be shown by comparing it to other
  (exact) algorithms?

I realize this is a subjective question as, I think, D.W. tried to point out. I would like to answer this question myself by agreeing to D.W. and saying: It might be, it depends.

As a lot of references on metaheuristics will point out, it is important to be fully aware of the state-of-the-art before trying to design one. Metaheuristics tend to perform better than alternatives in certain (preferably interesting) situations, which should be shown by comparing them to said alternatives. Even if there is only a brute-force algorithm, it is likely that the brute-force algorithm will perform better in certain (interesting) situations and your metaheuristic will perform preferably much better in other situations. As D.W. said: "It depends what you're looking for, but sure, [metaheuristics] might be (useful), if you can accept the limitations."


Self-balancing BST supporting in-order-sequential multi-insertions / multi-deletions in logn+klogk time?

This can be solved with split and join operations, both achievable in $\mathcal{O}(\log n)$ for Red-Black and AVL trees.
For Red-Black Trees this is doable either leveraging finger trees or via extending a regular Red-Black Tree as in Ron Wein's "Efficient Implementation of Red-Black Trees with Split and Catenate Operations" implemented in CGAL with criticisms mentioned in https://stackoverflow.com/questions/29029894/red-black-tree-split-concatenate-in-logn-time (Tarjan might have a better paper).
For AVL trees this is doable according to Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory".
InsertInOrderSequentialBatch is expressable as a split followed by 2 joins. DeleteRange is 2 splits followed by 1 join.


Sorting algorithm which sorts half the possible inputs in linear time

Suppose that a comparison-based sorting algorithm sorts the set of permutations $\Pi$ correctly. Construct the comparison decision tree underlying the algorithm, with permutations as leaves. Each permutation in $\Pi$ must appear as a leaf (why?), hence the tree must have depth at least $\log_2 |\Pi|$ (why?).


Confusion about example in Raft consensus paper

Server 1 does not immediately know the term when it starts up. Terms and other state such as commit indexes are (normally) held in memory and shared only via RPCs. Therefore, even though server 1 died when it was the leader for term 2, it won't even know about term 2 when it starts back up, let alone term 4.

The way server 1 will learn the term is via AppendEntries and RequestVote RPCs. When server 1 starts, it will initialize its term to 1. If it receives a heartbeat from node 5 before it dies, the heartbeat (an AppendEntries RPC) will contain server 5's term: 3. Given that information, when server 5 dies and server 1's election times out, it will transition to candidate, increment its term to 4, and start the election. This is the likely way in which this scenario might occur since server 2 could also win an election with or without server 1 being alive.

The reason server 1 would need to have been alive for some period of time prior to server 5 crashing is because of server 1 starts a new election immediately after it starts (without having communicated with any other node) it will lose the election since its term (1) will be less than the term of all other servers. In that scenario, server 2 would also start an election and ultimately win before server 1 can update its term and start another election.


Space Complexity of Bottom-Up Merge Sort

Yes, an auxiliary array is required for the merge operation.  The space complexity would be $\Theta(n)$, where $n$ is the size of the input.

The merge subroutine can create a temporary array to store the result of the merge operation and its contents can then be copied into the input array.  Or, an array having the same size as input can be created in the beginning and passed as an extra argument to the merge subroutine.


tillz is broadly correct, however there is one more detail of many modern systems which you should be aware of.

On some modern CPUs, when the power is first turned on and the CPU transfers control to firmware, almost all of the hardware needs to be initialised before it's used. This includes the hardware which arbitrates between cores in a multicore machine. One upshot of this is that main memory may not be available.

So some CPUs (notably Intel-esque machines) do support a mode where cache can be used as if it were RAM. Intel calls this "no-fill mode", and AMD calls it "cache-as-RAM mode". This is handled by the same mechanism that the CPU uses to implement non-cached memory (e.g. memory-mapped I/O).

On most modern CPUs, L1 cache split in two: an instruction cache, which is read-only, and the data cache, which is read-write. It does this so that the CPU pipeline can maintain the illusion of a Harvard architecture on top of a von Neumann architecture: the L1 instruction cache is "program memory" and the L1 data cache is "data memory", and they sit on top of a combined lower-level (probably L2) cache. "Combined" here means "both instructions and data", that is, it implements the von Neumann memory model.

Because the L1 instruction cache is read-only, the only way you can get anything in it is by filling from somewhere, and that somewhere is the next-level cache. So it's actually the lower-level cache which is acting as RAM, not the L1 cache.


Complexity of finding the largest $m$ numbers in an array of size $n$

Here is an $O(n)$ algorithm solving the problem.

Use the worst-case $O(n)$ selection algorithm to determine the $n-m+1$-th order statistics. Let $k$ be this number, which is the smallest of the $m$ largest numbers we are trying to determine.
Now partition the array around the pivot $k$ using the QuickSort partition function. This step takes $O(n)$ too.
Output the $m$ largest numbers: these are given by $k$ and all of the numbers in the upper subarray generated by partition in step 2.


The main idea is that $a^x \cdot a^x = a^{2x}$.

Now, in order to get, say, $a^{10}$ you can do $res = res * a$ for 10 times.
On the other hand you can do compute $a^2=a\cdot a$, then $a^4=a^2\cdot a^2$, then $a^8 = a^4 \cdot a^4$, and get the final result by multiplying $a^8$ with $a^2$. That is, we "break" the computation in a similar way to the binary representation of the exponent.

Let me give  do the example in more details, and then give the general statement.
note that $10 = 1010_{(2)}$, and can think of each '1' bit as an element we need to multiply in order to get the final answer (here $a^8$ for the 4th bit, and $a^2$ for the 2nd lsb bit. The power is the same as the "value" of that bit in binary..).

Generaly, in order to compute $a^{exp}$, consider $exp_{(2)}$: the MSB is always 1, and you will have to compute the element $a^{2^{\lfloor \log exp \rfloor}}$, which will take you $\log exp$ (modular) multiplications, and generate
$a^2, a^4, a^8, a^{16}, ..., a^{2^{\lfloor \log exp \rfloor}}$. Finally, with another up to $\log exp$ multiplication you will multiply all the elements that correspond to a '1' bit in the binary representation of $exp$.


This can be reduced to the following problem.

APPROXIMATE ROUNDING:
Input: real numbers $c_1,\dots,c_m \in \mathbb{R}$, an integer $d \in \mathbb{N}$
Goal: find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize
$\sum_i (x_i - c_i)^2$, subject to the requirement $\sum_i x_i = d$.

The reduction: define $S = \{i : H_i > 0\}$, $x_i = Q_i - 1$ for $i \in S$, $d=2^n-1-|S|$, and

$$c_i = -1 + (2^n-1) H_i / \sum_j H_j.$$

Now the optimal solution to APPROXIMATE ROUNDING immediately yields the optimal solution to your problem, by setting $Q_i = x_i + 1$ for each $i \in S$ and $Q_i=0$ for each $i \notin S$.

Can we solve APPROXIMATE ROUNDING efficiently?  I don't know.  I conjecture there exists $t \in \mathbb{R}$ such that the optimal solution is $x_i = \lfloor t c_i \rceil$ for all $i$ (i.e., $x_i$ is $tc_i$ rounded to the nearest integer).  If this is true, we can use binary search to find $t$ such that $\sum_{i \in S} \lfloor t c_i \rceil = d$, and thereby solve APPROXIMATE ROUNDING efficiently.  However, I have no proof that this works.

Erwin Kalvelagen over on Math.SE has suggested that APPROXIMATE ROUNDING can be solved using a MIQP solver.


Efficiency of 0-1 linear programming w.r.t. number of binary variables

If the other variables are integer variables

This is still NP-hard, even when $k=0$, for the same reason that integer programming is hard.

As for whether lowering the number of binary constraints will help in practice, that depends, and usually the only way to know is to try it.  It will depend on what the price of doing that is, as well as depend on the behavior of your ILP solver (which can sometimes be hard to predict).

I would expect that binary variables are harder to deal with than integer variables with a larger range.  In particular, if we have an integer variable whose values are in the range $\{0,1,2,\dots,r\}$, then I would expect that the smaller $r$ is, the harder the problem is.  Heuristically, the larger the value of the integer variable is, the better it can be approximated with a continuous variable (not restricted to integers), so the closer it comes to linear programming.  A standard strategy for ILP solvers is to solve the linear program without the integer constraints, then fine-tune the solution somehow to make everything an integer (e.g., round to the nearest integer).  We might hope that the larger the integers, the less error this process will introduce.  So, binary variables might be a lot harder than integer variables whose value will be large and whose range of plausible values is large.  This is not a hard-and-fast rule; just a rule of thumb to help you think about formulating your problem as an integer problem.

As always, the ultimate answer is to try it and see.

See also https://cstheory.stackexchange.com/q/16530/5038 and https://cstheory.stackexchange.com/q/29317/5038.  The operations research community studies what properties of ILP problems tend to be solvable more efficiently with existing ILP solvers (as "rules of thumb" and heuristics).

If the other variables are continuous variables

Then yes, the fewer binary constraints, the faster the ILP solver probably will be.  With no binary constraints (or integrality constraints), this becomes linear programming, which can be solved in polynomial time and for which there are efficient algorithms.  It's the binary constraints that make the problem hard.  The more binary constraints you have, the harder things can get.


Find a polynomial in two or three queries

You can determine the polynomial using two queries. First query the polynomial at $x=1$ to get an upper bound $M$ on the value of the coefficients. Now query the polynomial at $x > M$ of your choice and read off the coefficients from the base $x$ expansion.

Curiously, if you allow the coefficients to be negative then you cannot do better than $d$ queries. Indeed, I can always answer your $d-1$ queries $x_1,\ldots,x_{d-1}$ by zero, and this does not fix the value of the polynomial since all polynomials of the form $(x-x_1)\cdots(x-x_{d-1})(x-x_d)$ are consistent with my answers.


What is the worst case running time for an algorithm that combines insertionsort and mergesort?

In fact, the running time of mergesort for large $n$ doesn't depend on what happens for small $n$. Recall the recurrence for mergesort:

$$ T(n) = 2T(n/2) + O(n), \qquad T(1) = O(1). $$

This recurrence holds even if you run insertion sort for $n < 100$, since the running time of insertion sort on at most 100 elements can be swallowed in the big O constants. Even if you use exhaustive search on all $n!$ permutations for $n < 100$, mergesort will still run in time $O(n\log n)$; the only change is that the big O constant would be rather huge.


Calculating the end-to-end delay of a message sent over a network

In this case the propagation delay is more than the transmission delay, the propagation delay acts as a bottleneck for the whole network therefore the total time depend on it.

Consider a pizza shop, it takes 10 min to prepare pizza but 5 min to transport it, having infinite labour to transport, calculate how much time will it take to finsh job for 100 pizza.

Your ans might be correct but equation is wrong, you should draw the transmission diagram for better understanding.


Group time series events into minimal amount of buckets

The first event at time $t_0$ needs to be in a bucket. We can safely choose the bucket $[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at $t>t_0+30$ (earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that repeating this strategy until all events are covered is optimal (you can do it by induction).
This procedure runs in $O(n)$ time if your events are sorted, $O(n\log(n))$ if you need to sort them first.


Finding duplicate in immutable array in linear time and constant space

Let us denote the array by $a_1,\ldots,a_{n+1}$. Define a function from $\{1,\ldots,n+1\}$ to itself as follows: $f(i) = a_i$. The graph of the function is a directed graph in which each node has outdegree 1. Since $n+1$ has indegree 0, the connected component of $n+1$ has a node with indegree 2, which corresponds to a duplicate entry. This node can be found using a cycle detection algorithm in linear time and constant space.


What is the difference between Boolean Algebra and Boolean Lattice?

According to Wikipedia, these are two names for the same concept. You can differentiate them by stating that Boolean algebra is an algebraic structure having operations $\land,\lor,\lnot$ satisfying certain axioms, and in contrast a Boolean lattice is a lattice having certain properties; but the two definitions are equivalent. Sometimes Boolean algebra and Boolean lattice refer to specific constructions (subsets of a set), but according to Stone's representation theorem these two definitions are also equivalent.


How to implement graph search to solve Sudoku puzzle

A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a vertex is a board configuration and an edge from configuration $a$ to configuration $b$ exists if $b$ is obtained from $a$ by inserting a number in an empty cell of $a$. There are $(9^2)^9$ possible configurations; searching this graph for a solution will take a lot of time but you will find one eventually. Many of the configurations are invalid Sudoku grids so you can eliminate lots of them.

A typical Sudoku solver would search an implicit graph: the solver is not given a graph as input but it is given a procedure to generate candidate configurations given some configuration. One such procedure may be described as:

generate_candidates(config) {
  candidates = [] is a list of configs
  for every empty cell (call it C) in config
    for every number in [1..9]
      C = number
        if config is a valid grid
          add copy of config to candidates
}

In the implicit graph, the edges are the ones that look like 'config $\to$ candidate' where config is the input to generate_candidates and candidate is a configuration generated by generate_candidates. Of course you have to generate new candidates from the ones just generated; you keep growing that list of candidates until no more can be generated or you've found a solution.


First, the one-move shift is definitely NOT standard, but, as far as I understand, it only strengthens the result in that article. If a machine with the special operation can be simulated, then of course a machine without that operation can as well.
Second, here are some papers by Hans-Jörg Stoß dealing with multi-head machines. No one-move shifts here.

k-Band-Simulation von k-Kopf-Turing-Maschinen (1970) - establishes that $k$-head and $k$-tape can simulate each other without changing computation time.
Zwei-Band Simulation von Turingmaschinen (1971) - simulates a machine with $k$ heads on an $m$-dimensional tape by a machine with 1 normal tape plus 1 stack, establishing a rather precise time bound.
Linear-Time Simulation of Multihead Turing Machines (1989) - linearly simulates a machine with $k$-heads on a $d$-dimensional tape by a machine with $k$ separate $d$-dimensional tapes plus 1 normal tape.

Unfortunately, the first two are, as far as I know, only in German. The full text of the third one (translated) is here: doi.org/10.1016/0890-5401(89)90037-0


Dynamic changes to classes or context activation -- how to treat existing objects in a consistent way?

A recent paper on this topic that I stumbled upon is
Incremental Dynamic Updates
with First-class Contexts by
Erwann Wernli, Mircea Lungu, and Oscar Nierstrasz. The approach taken in the paper is not based on global updates. Rather, multiple versions of a system run simultaneously in what is called a context. Objects are gradually migrated from one context to another, at which time an update is performed. Bidirectional transformations are used to maintain consistency between old an new contexts.

In general, I think you need to have a pair of update functions for any update, one for updating classes, the other for updating objects. The real issue is when/how do you apply the update functions to objects. In any case, you will often have multiple versions of classes around at the same time. UpgradeJ (by Biermann, Parkinson and Noble) is one programming language that deals with multiple versions of a class in a type safe fashion.

The bibliography of these papers provides a few leads that you could follow. Also look on google scholar to see what paper build on these.


Consider the string $w= abba $.
$w$ clearly belongs to $L$ as $|a|=|b|$ but there's no derivation which allows you to generate $w$ given your CFG.

In practice, your rules only deal with the imbalance in the number of $a$'s and $b$'s.
 You need to make sure to generate every string $w \in (a+b)^*$ with the same number of $a$'s and $b$'s.

A CFG grammar for your language can be the following:

$S \rightarrow \epsilon\ |\ aSbS \ | \ bSaS $


A variant of hitting set problem? Is this also a NP-hard problem?

The special case of your variant where every set $S_i$ contains only single-element sets are exactly the standard hitting set problem, so this variant is at least harder than the standard hitting set problem, thus is NP-hard.


Which time series prediction techniques are useful given harmonic properties?

I would suggest to make the correlation plot and observe the dependencies. Yes, ARIMA, is so far the best forecasting model for time series and it should work in this data set too.
For the implementation, in R, there is auto ARIMA, which automatically takes the best suited valued for the parameters(
    p: The number of lag observations included in the model, also called the lag order.
    d: The number of times that the raw observations are differenced, also called the degree of differencing.
    q: The size of the moving average window, also called the order of moving average.)

But as far as I am concerned, in Python, you have to manually tune the parameters by yourself by analyzing the correlation plot. This is a very well explained beginner level tutorial for the implementation in Python.
Let me know in the comments if it works (or not).


What is the fastest online sorting algorithm?

I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion).
In that case you can access sorted structure at any time.

If inputs comes in batches, sort batch (with any fast algoritm) and then merge.

Other algorithms will also suffer from divided input, but insertion sort is poor even if input is available at once.

Natural split into sorted parts occurs in Mergesort and Timsort. But overall performance should be adjusted to needs: if data comes one at the time, but there is no need to retreive sorted version, it would be nice to keep smaller sorted buffers.
When length of array is known in advance and distribution the set it is possible to do distribution based sort, it spares some empty cells for incomming data.
If data could be divided into ranges, this would enable partitioning of data as it arrives.


Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ doesn't contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^*1^*$ is employed, to not bother with these words.
The demonstration is then possible because intersection and complementation are closed properties on the regular language. So if $\overline{L} \cap L(0^*1^*)$ is not regular, we know that $\overline{L}$ must not be regular, so its complement, $L$, must not be regular.


Why does using unary in subset sum problem result polynomial time complexity?

Consider the following (silly) function cow, which accepts a number $n$:

def cow(n):
   k = 0
   for i in range(0, n):
       k =  k + 1
   return k

The loop takes $n$ steps, so the time needed for the function to complete on input $n$ is $\Theta(n)$.

However, the size of the input is not $n$ but rather $\log_2 n$ because computers represent numbers in binary. That is, if $b =
\log_2 n$ is the size of the input, then the complexity is $\Theta(2^b)$ (because $n = 2^{\log_2 n}$), which is an exponential algorithm when measured in size of the input $b$. If we measure in terms of $n$ then it is a linear algorithm.

If we represented numbers in unary then we would have $b = n$, i.e., it would take $n$ "units" (not "bits" anymore) to represent $n$. In this case the complexity would be $\Theta(b)$, a linear algorithm.


Most frequently tools or programming language for implementation text processing and nlp algorithms in academic papers and journals

My personnal opinion is that such comparisons usually make little
sense because they can be too dependent on hidden specificity of tools
or programming languages, or programming style and its interaction
with those specificities.

In my opinion, the only proper way to compare techniques is by a precise knowledge of
the interpretation machines. If you are comparing different algorithms
intended to achieve the same purpose, you want to run them on some
kind of unbiased abstract machine, providing some application
meaningful primitives than can be used to implement on the same
footing all the algorithmic variations.

Then you can actually count elementary computation costs over some
chosen benchmark.

For example, I have seen this type of work done for various parsing
algorithms, using a standardized PDA definition.

Making a slightly better tool than what exist for problem X in
language Y is seldom worth publishing, unless there is some more
abstract consideration of some theoretical work that shows that you
are bringing something to the field, rather than just being a better
hacker. And then the tool or language support does not matter so much,
as long as you can compare with some known work, and explain credibly
why your version works better.

Of course, if you actually manage to get major improvements, undisputable ones, then you have a much better chance of being published. But the the technical support you use will matter even less.


Can a schedule be conflict serializable but not serializable?

NO. As you can see in the following picture, conflict serializable schedules are a subset of serializable schedules, therefore all of them are serializable.


How do I call a system like a grammar, but where a rule has to be applied to all matches at once?

Usually, grammar systems where the rules have to be applied in parallel, are called L systems, after the theoretical biologist Aristid Lindenmayer who observed that development in plants must change cells in parallel.

The first example at wikipedia has rules : (A → AB), (B → A), and the string (= line of cells) develop as follows: A →
AB → ABA
 → ABAAB
 → ABAABABA →  ...

Note that in replacing the letters we actually apply a string homomorphism. I think that formally such a system is called D0L-system, with 0 (for zero) to indicate the rules are applied in a context-free manner, i.e., without looking at the neighbours, and D for determinism, in the sense that the mapping applied is a homomorphism, and not a finite substitution.

If one wants to choose between different homomorphisms at various steps of the derivation, we can choose between different homomorphisms. Such a system is usually called DT0L-system, where the T is for tabled: each homomorphism is a table to choose from.

The first DT0L example I could online find, is from the article L Systems by Kari, Rozenberg and Salomaa. Its tables are Td = [a → b, b → bb, c → a] and Tn = [a → c, b → ac, c → c]. In each step we can choose between the two tables.

Starting with a we get b (in both cases) then bb or ac, then bbbb, acac, ba, cc, then b$^8$, acacacac, baba, cccc, bbb, acc, aa and then cc (but that was already generated). Und so weiter und so fort.

PS. An homomorphism (in language theory) is specified as a letter to string mapping, like [a → c, b → ac, c → bb], and then extended to strings, following the mapping letter-by-letter, so aabac → ccaccbb. A finite substitution axtends this by allowing choice in each of the images of the letters, then a letter (and consequently a string) is mapped to a set of strings. Example [a → aa,c ; b → ε,ac,bb]. Now aba maps to the set aaaa, aac, caa, cc, aaacaa, aaacc, cacaa, cacc, aaabba, aabbc, cbbaa, cbbc. I think.


What is the best Approximation algorithm to schedule a task graph?

You get a $2-\frac1m$-approximation (where $m$ is the number of machines), by greedily scheduling tasks as they become available, and this is essentially the best we can do at the moment. Improving this is actually a major open problem in scheduling (see e.g. this ).


Expanding on Pål GD's hint, you can reduced from the normal, unweighted version of VERTEX COVER.

  VERTEX COVER
  Input: A graph $G$ and an integer $k$.
  Question: Does $G$ have a vertex cover of size at most $k$?

So in this case, you're just counting the number of vertices in the cover. Now to transform this to the weighted version, we just need to add weights to all the vertices such that we can recover the size of the vertex cover from the weight of the vertex cover.

Bigger hint under the spoiler tag, don't mouse over unless you're really stuck.

   What happens if we assign each vertex the same weight (doesn't really matter what it is, as long as they're all the same)? If each vertex has weight $c>1$, what's the weight of a vertex cover of size $k$? What's the size of a vertex cover of weight $T$?


How to express a structure of a 5-colorable graph in logic

General ideas:

Require that each vertex ($\forall x \ldots$) satisfies at least one color predicate (Use $\lor$ among five color predicates).
Also require that no vertex ($\lnot\exists x \ldots$) has two distinct colors (you can enumerate all the ten distinct pairs: $\lnot({\sf red}(x)\land{\sf blue}(x))\land \lnot(\ldots)\land \cdots$).
For each color (repeat this axiom five times, once for each color), require that if $x$ has that color and $R(x,y)$ then $y$ has not that color (e.g. $\forall x y.\ {\sf red}(x)\land R(x,y) \implies \lnot{\sf red}(y)$).


Complexity of the algorithm to find occurences of a given number in a given array

If we retain only the references to i and j, the code reduces to

i = 1
j = 1
while i < |A|
    j = j + 1
    if j > |A|
        i = i + 1
        j = i

This is equivalent to

for i in [1 |A|]
    for j in [i |A|]

... which is gone through about ${|A|^2 \over 2}$ times. So it is $\Theta(n^2)$: both $O(n^2)$ and $\Omega(n^2)$.

The algorithm appears to be looking for the maximum number of replicates in the array. There are faster ways to do so. A good hash map has (average) constant time access/update. So you can count how many of each thing are in the array in $\Theta(n)$ time. You can then find the maximum in $\Theta(n)$ time too.

So the problem admits a $\Theta(n)$ solution, but what you have been offered isn't it.


How to prove NP-completeness of this mail-problem?

Given an instance of partition $X=\{x_1, x_2, \dots, x_n\}$ you can build the graph $G=(V,E)$ where $V=\{0, 1, \dots, n\}$ and, for any pair of indices $i$, $j$ with $0 \le i<j \le n$, there is an edge $(i,j) \in E$ of weight $x_i$. Additionally, $E$ contains all edges $(i,0)$ for $1 \le i \le n$ with weight $0$.
The deposit will be vertex $0$. If you are able to find two cycles $C_1$, $C_2$ of the same length then the sets $\{x_i : i \ge 1 \wedge i \in C_1\}$ and $\{x_i : i \ge 1 \wedge i \in C_2\}$ will be a partition of $X$.
Similarly, a partition of $X$ induces two cycles of the same length in $G$.
This shows that the problem is $\mathsf{NP}$-hard even with just $2$ postmen.
You can generalize this reduction to any number $k$ of cycles by adding $k-2$ additional vertices $y_1, \dots, y_{k-2}$ along with all edges $(0, y_i)$ of weight $\frac{1}{2}\sum_{i=1}^n x_i$ and $(y_i, 0)$ of weight $0$.