BPP search: what does boosting correctness entail?

If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)$ to $2^{-\mathrm{poly}(n)}$.

Edit: if $R$ is in BPP rather than P, with constant error probability $\mu$, then this approach doesn't work. You can decide whether $x \in S$ or not using the usual majority trick, but if $x \in S$, it's not clear how you'd find a correct witness whp.


Merging sorted arrays and finding Big O bounds

In case the order of the elements does not matter:

I assume your arrays are not sorted and you don't care of the order of the elements when you merge them.

If you store your arrays as a linked list, then merging list1 and list2 takes $O(1)$ time: you just point list1's tail to list2's head or vice versa depending how you are going to merge. So for $x$ arrays it wil take $O(x)$ time.

If you initially store them as $x$ separate static arrays (by static I mean their size is fixed and the arrays do not grow) then at each step you will need to create a new array of larger size to combine two previous arrays by copying each element one-by-one. Thus, initially it will take $2n$ steps, then $3n$ an so on. Then the total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

If your array is dynamic, i.e., you can append one element to the end of the arrays in $O(1)$ time, then you just append all elements to the first array in $O(nx)$ time.

In case the arrays are sorted and the order of the elements does matter:

The underlying structure does not provide an advantage, whether it is a linked list or dynamic array. Again assume that elements are stored as $x$ separate static arrays. Then we merge two arrays like in the Merge sort algorithm. The total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

But you could use the same procedure exactly like in the Merge sort algorithm by pairwise merging arrays at each stage. This will take $O(nx\log_2{x})$ time.


Ford-Fulkerson algorithm with asymmetric adjacency matrix

The algorithm doesn't need a symmetric adjacency matrix. It needs to keep track of a flow and a residual network. Both are supported on the edges of $G$ and their inverses. You can store them in roughly the same way you store your graph $G$, using the same amount of space (up to a multiplicative constant).


Expressing conditional in linear program

If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/

In your case you need the following:

$0 \le -B + MA \le M-1$

assuming that $M$ is big enough.


Is there any data structure that can't be represented or described inside a computer?

There is a systematic way of computing datatype representations of mathematical objects: anything that can be described in higher-order intuitionistic logic has a representation as a datatype. Because we are talking about descriptions, and not about proofs of theorems, it does not even matter much that the logic is intuitionistic and not classical. Pretty much any mathematical object you encounter in practice can be represented. Some examples that can be done easily: real numbers, the space of square-integrable measurable functions $L^2[0,1]$ and other infinite-dimensional Hilbert spaces, Banach spaces, the space of compact subspaces of $\mathbb{R}^n$, etc.

Roughly, the process goes as follows. Take you favorite model of computation and build a realizability topos from it. Then take your description of the mathematical object and interpret it in the topos. It will tell you how to represent data, because the topos is built in such a way that every object is equipped with a data representation, and every statement is witnessed by a program. In most cases we do not actually need the entire topos, the much smaller and easier subcategory of modest sets suffices.

There is an important caveat: in intuitionistic logic an object may have several inequivalent descriptions which are classically equivalent. These will lead to different data representations (and this is good, as it means we can express more computational distinctions).

The process of interpretation is automatic. To make that point, Chris Stone and I wrote a tool rz which does this. You can feed it the definition of real numbers, or an infinitely dimensional Banach space, or anything like that, and it spits out a specification. (The software experienced bitrot, I should update it, but the paper has many examples.)

Let me also address the common misconception that "non-computable objects cannot be represented in a computer". There is a difference between non-computable and non-representable. For example, the digits of a real number may be written down on the tape of a Turing machine. It doesn't matter whether the real number in question is computable, it can be stored on the tape. The question of "who stored it onto the tape" is a separate concern. You may object that the tape is not infinite. Actually, it is infinite in most textbooks. But people like to press this point, to which I have two responses.

First, we may replace the infinite tape with a potentially infinite tape, i.e., think of the real number as a process which emits digits on demand. This can be some sort of a physical process, say a quantum-mechanics experiment that produces bits by making measurements. Would anyone like to presuppose that the real number so obtained is computable? In this case they have to produce some evidence for such a claim. Good luck with that. The moral here is that it is largely irrelevant whether "all reals in this universe are computable". What is important is that we can represent whatever reals there are, and that would by definition be all of them.

Second, we can study models of computation that have no infinite components, for example the $\lambda$-calculus. In such models infinite data, say a real number, is represented by a program that produces the data, say the digits of the real number. So obviously only computable reals may be represented. But this doesn't matter! The corresponding realizability topos still thinks there are uncountably many reals, and is a self-consistent world of mathematics.

For further explanation on how to represent uncountable data, I refer to my blog post Representations of uncomputable and uncountable sets. It's a bit of a rant, actually.

The takeaway is the motto from my PhD thesis:

  Data are continuous, programs are computable.


Why do Θ-bounds not survive taking differences?

The proof is by counterexample. Consider the following functions:

$$f_1(x) = 2x$$
$$f_2(x) = x+1$$
$$g_1(x) = x$$
$$g_2(x) = x$$

First, we can see that $f_1 = \Theta(f_2)$ and $g_1 = \Theta(g_2)$. Finding constants to prove the four big-Oh relationships involved is straightforward (in particular for $g_1$ and $g_2$).

Next, we can observe that $f_1 - g_1 = x \neq \Theta(1) = \Theta(f_2 - g_2)$.

Notice that the choice of $2$ and $1$ for the above functions is unimportant, so long as you choose them so that the difference between $f_1$ and $g_1$ is more than constant and the difference between $f_2$ and $g_2$ is constant.


How does FDS (flat datacenter storage) make optimizations around locality unnecessary?

The paper you cited is exploring the consequences of the question "what if datacenter network bandwidth was free?"  There are two reasons you might care about data locality.  One is latency and the other is bandwidth.  The workloads they are looking at (mostly) don't care about latency, and they've made bandwidth irrelevant, hence locality doesn't matter.  (Note however that at the end of Section 6.2 (on Page 12) they discuss how the inefficiency of non-local accesses forced them to use more compute nodes for their sorting algorithm.)

They also aren't completely eliminating locality optimizations.  Each compute node is still caching/buffering reads and writes in its local DRAM.  The rule of "avoid unnecessary I/O" still stands.  It's just that you don't make a distinction when you do a disk access of whether the disk is near or far from your compute node.  All disk accesses are assumed to include the extra latency of a round-trip network traversal.

Here's a picture to show the difference. The authors' "flat" storage model is on the left, the traditional "distributed" storage model is on the right:

In the distributed model (on the right) data is either on a local disk or a remote disk.  In the flat model (on the left) data is all remote.  But since the network bandwidth is (effectively) infinite, this doesn't reduce your maximum data bandwidth.


Computer Algebra: Algorithms for solving equations symbolically

The are some open source JAVA libraies with complete documentation for math/CAS like:

Jasymca, Java Algebra System and many more.

I think a good way is start with them and try to contribute more!


Understanding Randomized Select algorithm

The function Randomized-Partition accepts an array $A[p],\ldots,A[r]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A[p],\ldots,A[q-1] \leq A[q] \leq A[q+1],\ldots,A[r]$.

The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A[p],\ldots,A[r]$. To see this, let us assume from now on that all elements of $A$ are distinct (this will slightly simplify the arguments). Then the $q-p$ elements $A[p],\ldots,A[q-1]$ are smaller than $A[q]$, and the rest are larger than $A[q]$.

If $i = k$, then we are done. If $i < k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[p],\ldots,A[q-1]$ (since the $i$th smallest element is smaller than $A[q]$, which is the $k$th smallest element), and moreover, it is the $i$th smallest element in that subarray. If $i > k$, then the $i$th smallest element of $A[p],\ldots,A[r]$ belongs to the subarray $A[q+1],\ldots,A[r]$ (since the $i$th smallest element is larger than $A[q]$, which is the $k$th smallest element), and moreover, it is that $(i-k)$th smallest element in that subarray (since the $k$ elements $A[p],\ldots,A[q]$ are already smaller than it).


Let $\$$ be a symbol not in the alphabet, and let $\{ w_i \}_{i \in \mathbb{N}}$ be the strings you are searching from. Construct the string $S = w_1 \circ \$ \circ w_2 \circ \$ \circ \dots \circ w_n$ and use Ukkonen's algorithm to construct a suffix tree for $S$. You are now able to retrieve all $m$ occurrences of a pattern $P$ in time $\Theta(m + |P|)$, with $\sum_i|w_i|$ preprocessing time.


Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

The reason for why you are having problems is because your solution does not work. In particular, the problem is that your formula does not capture the VC problem statement. More precisely, the formula you build always has assignments satisfying $k$ clauses by just setting $k$ variables to true and the rest to false.
So let $G = (V, E)$ be a graph and $X \subseteq V$ be a VC in $G$.
Then for any edge $vw \in E$ we must have $v \in X$ or $w \in X$, giving us 3 mutually exclusive possibilities (by essentially rewriting $v \vee w$ in DNF):

$v \in X$ but $w \notin X$,
$v \notin X$ but $w \in X$
$v \in X$ and $w \in X$

Hence the edge $vw$ is covered by $X$ if and only if the formula $\psi(vw) = (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$ has exactly one satisfied clause (under the assignment corresponding to $X$).
Constructing such a formula for every edge and taking their disjunction, we get the DNF formula
$$\psi^\text{VC}(G) = \bigvee_{e \in E} \psi(e) = \bigvee_{vw \in E} (v \wedge w) \vee (\neg v \wedge w) \vee (v \wedge \neg w)$$
and any assignment satisfying exactly $|E|$ clauses must be a VC of $G$.
Now we need a way to encode the size of the VC into it all, for which we can reuse your idea.
Define
$$\psi(G) = \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$
and note that the number of satisfied clauses in the second part is just given by the size of the set of vertices we select, so the total number of satisfied clauses under the assignment corresponding to some VC $X$ in $G$ is $|E| + |X|$.
There is only one problem remaining here.
We could get an assignment not corresponding to a VC but including more vertices to satisfy the same number of clauses that a desired VC would.
As a remedy, we can repeat the first formula some $|V| + 1$ times such that no matter how many vertices you chose, the total number of satisfied clauses will always be too low.
Hence we obtain the final formula
$$\psi^\ast(G) = \bigvee_{i = 1}^{|V| + 1} \psi^\text{VC}(G) \vee \bigvee_{v \in V} v$$
and note that if $G$ has a VC $X$ then the corresponding assignment will satisfy exactly $(|V| + 1) \cdot |E| + |X|$ clauses of $\psi^\ast(G)$.
For the reverse direction, let $\alpha$ be some assignment satisfying $(|V| + 1) \cdot |E| + k$ clauses of $\psi^\ast(G)$.
Then $\alpha$ must represent a VC in G as otherwise, the number of satisfied clauses in the first part of $\psi^\ast(G)$ is at most $(|V| + 1) \cdot (|E| - 1) = |V| \cdot |E| + |E| - |V| - 1$ and as $\alpha$ can satisfy at most $|V|$ clauses in the second part, the total number of satisfied clauses will be at most
$$(|V| + 1) \cdot (|E| - 1) + |V| = |V| \cdot |E| + |E| - 1 < (|V| + 1) \cdot |E|$$
However, this implies that the total number of satisfied clauses in the first part must be exactly $(|V| + 1) \cdot |E|$ and thus exactly $k$ clauses of the second part are satisfied by $\alpha$, so $\alpha$ corresponds to a VC $X_\alpha$ of size $k$ in $G$.
Note that for clarity I did not specify a $3$-DNF formula. However, as all clauses in $\psi^\ast(G)$ are of size at most $2$ you can just add redundant literals to the clauses to blow them up to size $3$ if need be.
I am not sure that this is the best way to do this, but it should work out. I omitted some details for brevity, please feel free to ask for additional clarifications if something is not clear to you :)


ANN architectures that perform faster/efficient prediction over time?

The machine learning term for this is dimensionality reduction (see here for a survey), which is used in a more general context than just neural networks.

Dimensionality reduction can be both supervised and unsupervised. An example for unsupervised dim. reduction is PCA, in which a projection onto a lower-dimension space is found, in a way that preserves distances / structure as much as possible. In the case of supervised dimensionality reduction, the labels of the training set are also used in order to reduce the dimension. This is, however, a more advanced research area. This paper and references therein would be a good starting point.

Hope this helps.


This decision problem ("does this graph contain a tour of length at most this?") is NP-complete, so you won't find a polynomial-time algorithm most likely.

In addition to the brute-force method you describe, you can have a look at Held-Karp, which solves the problem in $O^*(2^n)$ time using dynamic programming. For an even more practical solution, you can have a look at the Concorde TSP solver, which has been successfully used to solve instances with tens of thousands of cities optimally.


Supplemental 2016-10-03: I mixed up induction-induction and induction-recursion (not the first time I did that!). My apologies for the mess. I updated the answer to cover both.

I find the explanations in the Forsberg & Setzer's paper A finite axiomatisation of inductive-inductive definitions illuminating.

Induction-recursion

An inductive-recursive definition is one in which we define a type $A$ and a type family $B : A \to \mathsf{Type}$ simultaneously in a special way:

$A$ is defined as an inductive type.
$B$ is defined by recursion on $A$.
Crucially, the definition of $A$ may use $B$.

Without the third requirement, we could first define $A$ and then separately $B$.

Here is a baby example. Define $A$ inductively to have the following constructors:

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

The type family $B$ is defined by

$B(a) = \mathtt{bool}$
$B(\ell(x, f)) = \mathtt{nat}$.

So, what is in $A$? First of all we have an element $$a : A.$$ Because of that, there is a type $B(a)$ which is defined to be $\mathtt{bool}$. Therefore, we can form two new elements $$\ell(a, \mathtt{false})$$ and $$\ell(a, \mathtt{true})$$ in $A$. Now we have $B(\ell(a, \mathtt{false})) = B(\ell(a, \mathtt{true})) = \mathtt{nat}$, so we can also form for every $n : \mathtt{nat}$ the elements
$$\ell(\ell(a, \mathtt{false}), n) :  A$$
and
$$\ell(\ell(a, \mathtt{true}), n) : A$$
We can keep going like this. The next stage will be that since
$$B(\ell(\ell(a, \mathtt{true}), n)) = \mathtt{nat}$$
there is for every $m : \mathtt{nat}$ the element
$$\ell(\ell(\ell(a, \mathtt{true}), n), m) : A$$
and the element
$$\ell(\ell(\ell(a, \mathtt{false}), n), m) : A$$
We can keep going.
A little bit of thinking reveals that $A$ is more or less two copies of lists of natural numbers, sharing a common empty list. I will leave it as an exercise to figure out why.

Induction-induction

An inductive-inductive definition also defines a type $A$ and simultaneously a type family $B : A \to \mathsf{Type}$:

$A$ is defined inductively
$B$ is defined inductively, and it may refer to $A$
Crucially, $A$ may refer to $B$.

It is important to understand the difference between induction-recursion and induction-induction. In induction-recursion we define $B$ by providing equations of the form
$$B(\mathsf{c}(\ldots)) = \cdots$$
where $\mathsf{c}(\ldots)$ is a constructor for $A$. In an inductive-inductive definition we define $B$ by providing constructors for forming the elements of $B$.

Let us reformulate our previous example as induction-induction. First we have the inductively given tpye $A$:

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

The type family $B$ is defined by the following constructors:

$\mathsf{Tru} : B(a)$
$\mathsf{Fal} : B(a)$
if $x : A$ and $y : B(x)$ then $\mathsf{Zer} : B(\ell(x,y))$
if $x : A$ and $y : B(x)$ and $z : B(\ell(x,y))$ then $\mathsf{Suc}(z) : B(\ell(x,y))$.

As you can see, we gave rules for generating the elements of $B$ which amount to saying that $B(a)$ is (isomoprhic to) the booleans, and $B(\ell(x,y))$ is (isomorphic to) the natural numbers.


Proving P = NP without mathematical statements / computer program

A Turing machine, it must be remembered, is a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to P versus NP, most computer scientists would try to find a formulation of it which did come as close as possible to a plain english description in order to get as strong an understanding of the solution as possible.

But there is a fundamental problem with the sort of question that you're asking. What does it mean for someone who would be able to solve P versus NP — and by showing that they are equal, no less — to not actually be either a computer scientist or a mathematician? Perhaps they are not employed professionally as a computer scientist or mathematician, but this is beside the point if they have the skill to solve what some (Scott Aaronson, for example) describe as the most important mathematical problem we've ever considered. If someone has the training (or has even self-taught) to successfully tackle the problem, and also to clearly communicate the solution to others by identifying the major sub-routines and their roles in solving e.g. SAT or HAMPATH, then whether they are employed or even have degrees is an irrelevant detail; they are nevertheless in that case a mathematician or a computer scientist. Better still if they can describe how their solutions overcome classic obstacles such as oracle results, such as oracles A for which PA ≠ NPA (or the opposite) by showing specifically what sorts of structure in the problem the algorithm takes advantage of, which would not be accessible in the oracle model. The problem, however, is that most people who dream of solving P versus NP as amateurs or outsiders seem to lack the communication skills to actually describe their work adequately, or (by virtue of not having read enough) they are unaware of results which would make their approach to solving the problem doomed from the start.

As with all dreams of glory these days, there is a basic problem with the fantasy of being the one to resolve P versus NP. The problem is that it's bound to be nearly impossible. Not actually impossible, mind you, or at least not necessarily impossible; just nearly so. As someone bright with ambition, it is possible  for one to lose sight of the fact that there are many other bright people: many of whom have also thought about the problem; and many of whom are brighter than oneself, even by a couple of orders of magnitude. And that there have been such bright people for as long as the problem has been around; and yet it remains unsolved. Yes, it's possible in principle that everyone is thinking about it the wrong way, and have been for decades. But is that really particularly likely? Nobody should expect themselves to be the one person who can spot the one sign-error that everyone else is making, because if everyone else is making that error then there must be something about the problem that will lead one to make the same mistake. Or — in the more likely event that the reason why the problem remains unsolved is not that people keep making simple mistakes or haven't yet thought of the one simple trick that dissolves the whole thing — what makes the problem fundamentally difficult is essentially an objective difficulty of the problem, and no clever dancing steps will allow one to simply waltz gracefully past all obstacles; that what is required is an approach which is not merely novel, but quite profound, identifying subtle structures that there was good reason for nobody to have seen before. The sort of structure which one is most likely to spot by thinking continuously about the problem for years.

If you want to be realistic about what it would take to solve the P versus NP problem, you might compare it to similarly famous breakthroughs in the past few decades, such as the proofs of the four-colour theorem, Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive). There's no particular reason to suspect that P versus NP will be different; so that if in the end it is resolved by an amateur, chances are extremely strong that it would be by someone with similar background knowledge and awareness of techniques of someone who is academically trained. Any realistic amateur who dreams of solving P versus NP would do well to keep that in mind.


This might be a language issue. In (mathematical) English, the statement all finite languages are regular means: if $L$ is a finite language then $L$ is regular. No implication in the other direction ("if a language is regular then it is finite") is implied.


Problems understanding proof of smn theorem using Church-Turing thesis

In books on computability theory it is common for the text to skip details on how a particular machine is to be constructed. The author of the computability book will mumble something about the Turing-Church thesis somewhere in the beginning. This is to be read as "you will have to do the missing parts yourself, or equip yourself with the same sense of inner feeling about computation as I did". Often the author will give you hints on how to construct a machine, and call them "pseudo-code", "effective procedure", "idea", or some such. The Church-Turing thesis is the social convention that such descriptions of machines suffice. (Of course, the social convention is not arbitrary but rather based on many years of experience on what is and is not computable.)

I am not saying that this is a bad idea, I am just telling you honestly what is going on. Books on analysis skip $\epsilon\delta$-proofs, books on category theory don't verify every naturality square, books on topology rely on geometric intuitions of the readers, etc.

There are standard tricks on how to read computability theory. If the book says "there exists $X$", then that usually means "$X$ can be computed from whatever our current parameters are". If they want to emphasize that whatever they are doing can be computed as a function of a parameter $p$, they will say "whatever we are doing, uniformly in $p$". And obviously, if they say "non-uniformly in $p$", they are emphasizing that whatever they are doing is not computable as a function of $p$.

In Barry's text, he could have emphasized the computability bit by writing "there exists an index $e_{x_0}$, uniformly in $x_0$, such that ..." But since this is an introductory text, sticking in the word "uniformly" will just confuse a good part of the readership. So what are we supposed to do? We certainly do not want to write out detailed constructions of machines, because then students will end up thinking that's what computability theory is about. It isn't. Computability theory is about contemplating what machines we could construct if we wanted to, but we don't. As usual, the best path to wisdom is to pass through a phase of confusion.


Is equivalence of CFGs decidable for finite sets of grammars?

A problem is decidable if there is a TM which decides instances of the problem.

Given two arbitrary CFGs $G_1$ and $G_2$, we know this for certain: either $L(G_1) = L(G_2)$, or $L(G_1) \neq L(G_2)$. Consider the first case: a TM that accepts on the input $(G_1, G_2)$ correctly decides this problem. Consider the second case: a TM that rejects on the input $(G_1, G_2)$ would be correct in that case.

Now, consider a finite set of grammars $\{G_1, G_2, ..., G_n\}$. For any two grammars $G_i$ and $G_j$ in this set, we know that either $L(G_i) = L(G_j)$ or $L(G_i) \neq L(G_j)$.

Consider the following TMs:

TM #1:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then accept

TM #2:

if input is (G_1, G_1) then accept
if input is (G_1, G_2) then accept
...
if input is (G_n, G_n) then reject

...

TM #N

if input is (G_1, G_1) then reject
if input is (G_1, G_2) then reject
...
if input is (G_n, G_n) then reject

Each TM can either accept or reject for each of the $n^2$ (ordered) inputs; so there are $N = 2^{n^2}$ different TMs (as many as binary strings of length $n^2$).

One of these TMs is guaranteed to correctly decide your problem. I can't tell you which one, but one of these gives all the correct answers. Since there is a TM for your problem, it's decidable.


Randomness is a philosophical concept (though there are several mathematical definitions as well). There are two aspect to randomness generated by a computer, unpredictability and pseudorandomness, which correspond to two different demands from a randomness source:

Data produced by the randomness source should be unpredictable, even in principle.
Data produced by the randomness source should "behave" as a truly random source.

The approach taken by computers to generate randomness is a combination of both of these flavors. Randomness is generate using a pseudorandom number generator, which is an algorithm designed to churned up numbers which "look random", in the sense that any program employing a randomness source will behave the same regardless of it being given a truly random source or the output of the pseudorandom number generator. ARC4 (usually known as RC4) is such an algorithm, though the first few random bits are known to be somewhat problematic.

A pseudorandom number generator (PRNG) is seeded by initial randomness, known as either a seed or a key. Sometimes we want to fix this initial randomness, for example when debugging a program which uses the PRNG. Other times, it is important that this initial randomness be unpredictable - this is the case in cryptographic applications. It used to be the case that PRNGs are seeded using the exact time-of-day as kept by the computer clock. Nowadays systems are more sophisticated, and harvest random bits from other sources such as keystrokes, CPU, internal devices and network usage, commonly known as an entropy pool. Therefore modern systems are capable of producing unpredictable random numbers.

If it is important to generate truly random numbers (or rather, numbers which are even less predictable), one can resort to hardware number generators, which usually measure thermal noise generated by electric components such as diodes (in the form of voltage or current fluctuations). However even this random output needs to be filtered (through a randomness extractor) to result in a sequence of independent fair coin flips.


Proving NP completness without reductions

To prove that a problem is NP-complete, you must show that it's in NP and that every problem in NP reduces to it.  As far as I'm aware, there are only really two ways of doing the latter:

show that some problem already known to be NP-complete reduces to your problem;
show directly that every problem in NP reduces to your problem by showing that your problem can essentially simulate a nondeterministic polynomial-time Turing machine.


Does every language in BPP have a mapping reduction to ATM?

Yes.

Every decidable language reduces to $A_{\mathrm{TM}}$.

Every language in BPP is decidable because the definition requires that every execution of the probabilistic machine halts in polynomial time. So you can just simulate out all the possibilities and compute the probability that the machine accepts.


Sure, just sample $n$ bits, concatenate them, and output the result.


Given RSA, why do we not know if public-key cryptography is possible?

We don't know for sure that RSA is safe. It could be that RSA can be broken in polynomial time, for example if factoring can be done efficiently. What is open is the existence of a a provably secure public-key cryptosystem. We don't know for sure that such a cryptosystem exists at all; for all we know, every cryptosystem could be broken efficiently.

A different, unrelated problem with RSA is that it can be broken by quantum computers. This is an unrelated problem since the definition of a secure public-key cryptosystem only requires that the cryptosystem not be breakable by classical (non-quantum) computers.

Practically speaking, though, RSA seems secure, and it is used all the time. This is due to the gap between theory and practice. While theoretically we don't know for sure that RSA is secure, practically speaking we have to use some public-key cryptosystem, and RSA is a good choice since people have tried to break it and failed. Generally speaking, a known cryptosystem that people care about is more secure than an obscure one, since it has resisted the attempts of cryptographers. This doesn't constitute a proof that it is secure – it might well not be – but it's the best we can do.


How to implement insertion sort on linked list with best case performance O(n)?

Best case performance is attained when only one element is not in place. Assume the following list

1->2->3->4->0

You can easily show that it takes you $O(n)$ to sort via insertion sort: The inner while loop will run $n$ times when the outer loop reaches node 0. Otherwise, it will never be executed.


Optimize binary search on Segment Tree by storing past result

There turns out to be a very simple way to do this in $\mathcal{O}(\lg n)$:

Restrict the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$
If $r≥\sum_{k=1}^{d-1}A_k$, add $A_d$ to $r$.
Search using the original method.

Finding $\sum_{k=1}^{d-1}A_k$ is $\mathcal{O}(\lg n)$ time, finding $A_d$ from $S$ is $\Theta(\lg n)$ time, and the binary search is $\Theta(\lg n)$ time.


Are there specific rules for programming languages applicable to Quantum Computers?

We probably don't yet know enough about the landscape of practical quantum computing devices to lay down the kinds of concrete specifications you're asking for. It also seems to me that there's a big gap between what Assembly Languages and a formalism like CSP brings to the table. So, this question probably has different answers at different levels of hardware and software abstraction.

What all that being said, "A Layered Software Architecture for Quantum Computing Design Tools" by Svore et. al lays out a framework that I believe cuts across what you're getting it.  It's simply a proposal though, not a specification per se.  The authors do lay out some of the challenges faced when designing quantum computing design tools and programming languages and I think address what you're looking for.  The previously mentioned Liquid language seems to be an an attempt and working off this framework.

From what I've seen, quantum programming systems typically to work by providing a universal set of elementary gates for quantum circuits and possibly some higher-level primitives for common quantum algorithm components like the Quantum Fourier Transform.  I believe Svore,  et. al. refer to this layer as Quantum Assembly. For example, the two-qubit CNot gate and arbitrary single qubit unitaries are universal for quantum computation. The ability to lay out circuits from these primitives would provide you with the ability to express an arbitrary quantum computation.

I'd hesitate to call this assembly in the sense that we know it from classical computing as it corresponds to a set of primitives from a low-level abstract model of quantum computation and not to an abstract or concrete instruction set.  Going back to my first comment, it's not clear that we're even sure what kind of quantum instruction set is best at this point.


No.

In the modal logic K, the formula □(p → q) implies □p → □q (by the distribution axiom) but it is not equivalent to it.

A possible intuition is as follows. Read □(p → q) as: every time it rains, my umbrella is open. Read □p → □q as: if it rains everyday, my umbrella is open everyday. In those worlds in which it rains sometimes but not always, the first formula implies that my umbrella is open on those days, the latter does not since its premise requires rain on all days.


Prim's algorithm: difference between brute force and PQ approaches

First, the psuedo-code given is not intended for brute force Prim's algorithm. It is a meta-algorithm for MST. Quoted from the beginning of Section 5.1.5 of "Algorithms":

  What the cut property tells us in most general terms is that any algorithm conforming to the following greedy schema is guaranteed to work.

Both Kruskal's algorithm based on disjoint sets and Prim's algorithm based on priority queues are instances of the meta-algorithm.

As for your other questions:

  "If we use a brute force approach, running time is O(|V|⋅|E|)."

It does not make much sense to discuss about the time complexity of a meta-algorithm.

  "Anyway I think that this more than just optimization, since solution with this last approach is built incrementally."

The greedy meta-algorithm for MST is incremental. And both Kruskal's algorithm and Prim's algorithm are incremental.


Finding an element in a infinite unsorted doubly linked list

Infinite/unbounded in both directions?
Zig-zag.


Is the language with decreasing numbers of a, b and c context-free by pumping lemma?

If your language is context free, so is its intersection with the regular language $a^* b^* c^*$. And your proof in the answer that this isn't context free does go through. Your proof omits the cases where one of the strings straddles the $a/b$ or $b/c$ boundaries.


The algorithm works by choosing the number of buckets and the boundaries of the buckets such that in expectation the number of elements that land in a bucket is constant. The analysis is particularly simple for a uniform distribution, because uniformly sized buckets work.

For more complicated distributions you have to choose your bucket size more cleverly, but there is nothing stopping you from looking hard at the probability density function and creating more buckets in regions where you'd expect many elements to occur.


Algorithm for Dynamic Client Side Throttling

this is a fairly basic problem in control theory and there are "design patterns" in this area to handle this type of system, and think there is probably an example right out of a control theory book very close to your question. basically the theory involves a concept somewhat like the way a thermostat regulates temperature in a house. if the house is too hot, the heater shuts off, if is too cool, it turns on. you want something like the opposite where more delay ("throttling") is applied when there is greater load, however the principle is the same.

a basic solution is something like this. keep track of the minimum response time, this is a "baseline". now measure the current instantaneous difference between the minimum response time and current response time, this is roughly proportional to "load". now one does not one long-past load to influence current load readings. but neither does one want a large current spike in load to effect the throttling too much. the immediate idea here is to use a exponential running/ moving average of the load measurements to determine the throttling (this metric is used a lot in stock trading algorithms). exponential averages have a tunable continuous parameter (0..1) that basically weights between current and past values, at one end the past values are weighted lighter, at the other end the current value is weighted heavier.

my suggestion is to try this algorithm for different weighting values and then graph the results. notice a lot of web load problems vary over daily rates where midday or midweek have highest load. in that case a changing weight value might be more optimal. a basic strategy to figure out the general trend of cycles in input load would be to have no throttling and then just look at daily or weekly loads.

note that some round-robin routers are automatically doing something like basic load balancing because they do not route to already busy connections.


a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph

One unclear point about the question is the meaning of "connected". If we interpret it as weakly connected, then the orientation of the DAG is no longer important, and we could have worked with an undirected graphs in the first place. We should also not interpret it as strongly connected, since a DAG has no strongly connected subsets.

So we are probably interested in the subgraph reachable from a node in $a$. I looks like we can just work with the set of edges contained the graphs from $A'$. But then we end up with a problem which belongs to both 2-SAT and HORNSAT, and the unit-propagation algorithm for HORNSAT will solve it in linear time. As the problems also belongs to 2-SAT, we know that it is not P-complete.


Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph?

$G=(V,E)$ is the graph we work on.

Problem 2: $\Diamond_F(reverse(G))=\Diamond_J(G)$, where $reverse(G)$ reverses all the edges of G.

Problem 3:
This can be solved in $O(nm)$ time. For each vertex $s$, find all the pairs $(s,v)\in \Diamond$ in $O(m)$ time. To do this and split every outgoing edge $(s,v)$ with a new vertex $v'$. Namely, delete edge $(s,v)$, and replace it with $(s,v')$ and $(v',v)$. Find the dominator tree with source $s$ in the new graph, which can be done in linear time for dags.

$(s,v)\in \Diamond$ iff $v$ is the children of $s$ in the dominator tree and $v\in V$.


Is mutual inductive type definition essential in coq core language?

It is always possible, as you noted, to translate a mutual inductive family into a non-mutual family, in much the same way as you described.
A couple of difficulties though:

If your mutual inductives are not parametrized, say you have

Inductive Foo := foo : Bar -> Foo
with Bar := bar : Foo -> Bar

(with some constants if you want to make the types non-empty)
Then you have 2 non-dependent types, for which induction, recursion and pattern matching are rather straightforward. But the translation you suggest involve creating a FooBar : bool -> Type which now needs dependent pattern matching everywhere. It's not impossible to cope with this as well, but it makes the elaborator quite a bit more involved.

Even worse are mutual inductives with different parameters: Imagine now

Inductive Foo : nat -> Type := ...
with Bar : bool -> Type := ...

Now we need to define a type FooBar : forall b : bool, I b -> Type where I true = nat and I false = nat. I'll let you imagine the case of multiple, possibly dependent parameters.
All these complications add up to a system that is quite complicated: I think it's a reasonable decision to add special support in the core to handle mutually inductive families, and it's the decision the Coq developers have made.
The Lean developers originally made a different decision, see here for instance.
However my understanding is that the complexities outlined above, along with the difficulty of hiding all this to the user, has made them re-think their position (I believe, but at the moment I can't find the reference of how things are in Lean 4).


How do computers *really* work? (at the most basic level)

This is a complex matter. To begin with, when you move your mouse, there is so much going on at once, that I cannot even begin to explain everything here. So, I will focus on the most fundamental thing: How does the computer actually compute?
As you are probably familiar with, computers have memory called RAM, and a CPU that is able to execute "commands". Commands, are essentially some form of data, that allows the computer to decide which logic gates to pass the input to.
At its core, this is the work of the ALU in the CPU. ALU stands for Arithmetic Logic Unit, and it had three inputs, contrary to what you may think. The first two inputs are normal inputs for the operations, for example: two numbers $a,b$ that we want to sum up. The third input, decides what operation to do on them. For example, you can encode that "0001" means we want to sum the two numbers, while "0010" might mean multiplication and "0011" is division. This ALU does this magic!
This "magic" that decides based on the third input which operation to do, is done via applying a multiplexer circuit to take the output from the correct series of logic gates in the ALU.
Basically, an $n$-to-$1$ multiplexer is given $n$ "normal" inputs, and one "special" input that decides which of the $n$ inputs to output. Yes, it simply outputs one of its inputs without changing anything. Basically, if we think of its inputs as an list $inp$, and the "special" input is called $s$, then the output is $inp[s]$.
The ALU takes this, and gives to it as the $inp$ the list of all possible operations on the two numbers $a,b$, and thats how the ALU knows which operation to apply when.


If your ASTs have a small number of conditions, then you can use the following naive approach.

1) Convert your ASTs to a CSOP (Canonical Sum Of Products) expression.
     From your example, lets convert each condition to a boolean variable and express $A$ and $B$ as boolean expressions in the following variables

$p: (x ==1)$
$q: (y==5)$
$r: (b == 2)$
$s: (c == d)$

Now
$ A: \space p \cdot (r + s)$
$B: p \cdot q \cdot (r + s)$
Normalising $A$ and $B$ yields
$A: p \cdot \lnot q \cdot r \cdot \lnot s +
   p \cdot \lnot q \cdot r \cdot s +
   p \cdot q \cdot r \cdot \lnot s +
   p \cdot q \cdot r \cdot s +
   p \cdot \lnot q \cdot \lnot r \cdot s +
   p \cdot q \cdot \lnot r \cdot s
$
$B: p \cdot q \cdot r \cdot \lnot s +
   p \cdot q \cdot \lnot r \cdot s +
   p \cdot q \cdot r \cdot s
$

2) Check if $ B \subseteq A$. In the above example it is true. This implies $B$ is stricter than $A$. If thought logically, all conditions in $B$ are fulfilled by $A$, but $A$ also satisfies other conditions not in $B$.
Hence, $B$ is stricter compared to $A$.

Note: Expanding boolean expressions to normal forms requires exponential space. The algorithm might need some optimisation tweaks for larger expressions.


Recalculating shortest path after changing the weights

The standard term for this kind of problem is "dynamic shortest paths" or "shortest paths in a dynamic graph".  Here "dynamic" refers to the fact that the graph might be updated, and you want to update the shortest-paths information (hopefully more efficiently than re-computing it from scratch).  There are many kinds of updates to the graph one can consider: deleting a vertex, inserting a vertex, deleting an edge, inserting an edge, increasing the length of an edge, decreasing the length of an edge.  Your problem is the special case where we only have to deal with decreases to edge weights.

So, I suggest you search the research literature (e.g., using Google Scholar).  You should find a bunch of papers that discuss algorithms for this situation.


Do you >have< to define the upper and lower bound? (context: traveling salesman)

If you want to compute X (whatever X is), then you just need to compute X, and whatever intermediate results are required by your method for computing X.  If your method doesn't need upper and lower bounds, there's no need to compute them.

The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and they may be enough to answer your question. For example, as a typical student, you don't need to know the exact price of a helicopter to know that you can't afford one: helicopters surely cost at least \$100,000 and you don't have \$100000. Conversely, if you're a millionaire, you don't need to know the exact price of a chocolate bar to know that you can afford to buy one: surely a chocolate bar doesn't cost more than \$100 and you definitely have \$100.

  Can we say for sure that the cost of the optimal route is a number in the interval [between the lower bound and upper bound]?

Yes. That's what "upper bound" and "lower bound" mean.

  Is it possible to find a route whose cost is not within the interval?

Again, by definition of "lower bound" and "optimal", no route can be shorter than any lower bound on the length of an optimal route. Depending on what upper bound you use, it might be possible to find a route that is longer than an upper bound on the optimal route. For example, on upper bound on the length of a TSP route is to say that, since the optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex. But, if you think about it, that's actually an upper bound on any route, whether the route is optimal or not. So it's not possible to exceed this upper bound. However, it's possible that you could come up with a smarter upper bound such that the optimal route is definitely not longer than your bound, but suboptimal routes might be.


Break an authentication protocol based on a pre-shared symmetric key

This protocol seems to be insecure due to the fact that Bob sends $E(R_A,K)$. This can be used by Trudy to "generate" encryptions of $E(\langle R_A+1,P_T\rangle , K)$ that will later be used to complete the authentication protocol.

Specifically, consider the following attack:

Trudy picks random $R_1$ and runs the protocol with Bob in the following manner:
$$ \begin{align*}
 T \to B: &\quad \text{“I'm Alice”}, \langle R_1+1,P_T \rangle \\
 B \to T: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K)} \\
\end{align*} $$
and then Trudy cuts the protocol in the middle (since she doesn't know how to reply). We assume both Trudy and Bob abort.

Now Trudy starts another instance of the protocol:
$$ \begin{align*}
 T \to B: &\quad \text{“I'm Alice”}, R_1 \\
 B \to T: &\quad E(R_1, K) \\
 T \to B: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K) }
\end{align*} $$
How did Trudy complete the protocol this time without knowing $K$? it's easy! Bob actually performed the encryption for her in the first instance.

Lesson learned: in a cryptographic protocol, it's good for each message or separable fragment to contain a unique tag that prevents its reuse as some other message in the protocol. If Bob's reply was $E(\langle 1, R_A\rangle)$ and the third message was $E(\langle 2, R_A+1, P\rangle)$, this attack would not work.


$$\begin{align*}
55 = 1 + 2 + \dots + 10 &= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\
&\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\
&= (10/2)(10/2) = 25\,.\end{align*}$$

If you're wondering how to come up with such substitutions, there's no general method: this is one of the creative things you have to do to produce mathematical proofs.


This is a very easy question, assuming all scores are integers.

Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 zeros. For each score s, we will add 1 to count[s]. To produce the wanted sorted scores, we will output count[1] 1s, count[2] 2s, ..., and finally count[100] 100s.

This kind of sorting algorithm is called counting sort.

The case of more than $N>10000$ test scores that are between 1 and 100 is a prime usage of counting sort. The time complexity is $O(N)$ and the space complexity  is bounded by some small constant multiple of 100.

You may want to check counting sort for more information.


Let $N(p,q)$ be the number of sequences containing $p$ many A's and $q$ many B's, such that in every non-empty prefix, the number of A's strictly exceeds the number of B's. Clearly $N(p,q) = 0$ if $q \geq p$ and $q > 0$. When $p = q = 0$ there are no non-empty prefixes, and so $N(p,q) = 1$.

Suppose therefore that $p > q$, and consider any sequence satisfying the condition. If we remove the last element, we still get a sequence satisfying the condition. Conversely, whatever element we add, the resulting sequence will satisfy the condition, since $p > q$. We conclude that
$$
N(p,q) = \begin{cases}
1 & \text{ if } p=q=0, \\
0 & \text{ if } q \geq p \text{ and } q > 0, \\
N(p-1,q) + N(p,q-1) & \text{ if } p > q > 0, \\
N(p-1,q) & \text{ if } p > q = 0.
\end{cases}
$$


Apparently, the best you can do is write something on the lines of "the number of result sets is exponential in the number of input input elements". This is better than simply saying "the data grows exponentially" since such growth must happen with respect to some quantity. It also might be a good idea to state the value $2^n$ somewhere (in the more technical sections) so it is clear it is a precise and not an asymptotic estimate.

It is unfortunate you cannot estimate the size of each result set. Are you sure not even very conservative or even empirical estimates are possible? (If that is the case, then consider adding at least one of those.)


Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups

The solution and the analysis is given in Section 6.2.1 and 6.3 of the Book: Probability and Computing
Randomized Algorithms and Probabilistic Analysis
Sometimes it is better to refer to a book rather than formulating an answer by ourselves :)


You need to provide a linking page table which links the page number (logical address) to the frame number (physical address) and vice versa.


Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?

Let’s prove this by contradiction. Say $T_a$ is not an MST of $G_a$, that means there is some cheaper MST $T_a^*$. However, if that were true, then by reconnecting $T_a^*$ to $T_b$ we would obtain a tree that spans $G_a$ that has a lower weight than the MST $T$, which is a contradiction.


Why isn't the class of Turing-Recognizable languages closed under Complement?

Hint:
Suppose it was.  Let $L$ be a recognizable language and let $\overline{L}$ be its complement.  If $\overline{L}$ was recognizable as well, let $M_1$ and $M_2$ be recognizers of $L$ and $\overline{L}$, respectively.

Can you now use $M_1$ and $M_2$ to construct a decider for $L$?  What does this mean for undecidable and recognizable problems like the halting problem?


Approximating maximal independent set with a minimal vertex cover approximation

No, unfortunately this doesn't work. Denote by $\newcommand{\VC}{\mathrm{VC}}\VC$ the size of a minimum vertex cover and by $\newcommand{\IS}{\mathrm{IS}}\IS$ the size of a maximum independent set, so that $\VC+\IS=n$. The approximation algorithm for $\VC$ produces a vertex cover $C$ whose size satisfies $|C| \leq 2\VC$. The complement of $C$ is an independent set $I$ whose size satisfies
$$
|I| = n-|C| \geq n-2\VC.
$$
Unfortunately, $n-2\VC$ can be much smaller than $n-\VC$, and there's no constant lower bound on the ratio $$ \frac{n-2\VC}{n-\VC}. $$

As an example, let's see how the algorithm which picks a maximal matching fares on a graph consisting of a matching on $n$ vertices. The minimum vertex cover has size $n/2$, and so the maximum independent set has size $n/2$. The maximal matching algorithm picks all edges in the graph and then all vertices contained in them – in other words, it picks all vertices. It thus gives a vertex cover of size $n$, which corresponds to an independent set of size 0.

This difference between vertex cover and independent set is reflected in the fact that it is NP-hard to approximate independent set to within $n^{1-\epsilon}$, for any $\epsilon > 0$.


Bellman Ford facts and specific question

The claim is true. Any correct implementation of Bellman-Ford must guarantee this. Think about an arbitrary shortest path from $s$ to $v$. Besides being a shortest path with regard to the total weight, it must also satisfy another property: the path must be also shortest with regard to the number of edges used. In other words, the algorithm wants to determine shortest paths that are also simple paths (no vertices are repeated, i.e., all of the vertices in the path are distinct).
Why there is a need to ask for shortest and simple paths? Because there are obviously shortest paths with regard to the total weight that are not simple, e.g. there can be zero weight cycles. Bellman-Ford assumes that there are no negative weight cycles (the algorithm is able to detect a negative weight cycle) but there can be zero weight cycles, since they are actually allowed by the definitions. The problem caused by a zero weight cycle is that you can use it to arbitrarily augment the number of edges of a shortest path, by putting it somewhere in the middle of a shortest path. The total weight will remain the same, so the path will be a shortest path with regard to the weight, but not with regard to the number od edges composing it. This is the reason why you want shortest paths which are simple as well. The algorithm rules out zero weight cycles, throwing them away.
Now, everything follows immediately. A simple path can not have more than $|V| - 1$ edges: that is exactly the number of passes done by Bellman-Ford (since we assume no negative weight cycles, a shortest path can visit each vertex at most only once). Given a path $v_0 = s$ -> $v_1$->...->$v_k=v$ during the $i$th iteration the algorithm relaxes all of the edges; in particular, during iteration $i$ it relaxes the edge $(v_{i-1}, v_i)$. Therefore, after $i$ iterations the algorithm has correctly set the distance of vertex $v_i$ from $s$. And we know that the input graph does not contain negative weight cycles, that the path is simple and that a longest simple path may have at most  $|V|$ -1 edges. So, the algorithm is correct.


How to predict the next image in a sequence, or predict the deblurring of an image?

No.  You can't create information out of nothing.  There's no magic.  There's not enough information in the three lower-res to uniquely determine the high-res image.

Of course, you can always upscale an image, but that won't make it any higher quality or sharper than what you started with.

Note that "4K" is a marketing term, not a precise specification of an image resolution.  There are multiple different resolutions that are all marketed as "4K".  See https://en.wikipedia.org/wiki/4K_resolution.


Semantic information collections on the web. (Semantic Wikipedia)

DBpedia provides structured information from Wikipedia.

It uses RDF, and is one of the most known Linked Data datasets.

Also of interest (but not using information from Wikipedia) may be Freebase and OpenCyc.


What Fiorini et al. show is the following:

The TSP polytope $P_n$ over $n$ points is a polytope in $\binom{n}{2}$ dimensions whose vertices correspond to all Hamiltonian cycles in $K_n$ (the complete graph on $n$ vertices). (That is, it is the convex hull of the indicator vectors of all Hamiltonian cycles.)
Suppose that $X_n$ is a polytope whose projection over the first $\binom{n}{2}$ dimensions is $P_n$, and let $d_n$ be the number of constraints needed to define $X_n$ (i.e., the number of facets of codimension 1). Then $d_n \geq f(n)$ for some function $f(n) = 2^{\Omega(\sqrt{n})}$.

In other words, they show that TSP cannot be solved using LPs in one particular way. There could be some other way of using LPs to solve TSP which isn't ruled out by their result.
For example, perhaps you could use iterative rounding to solve TSP, at each step solving an LP. This is consistent with the result of Fiorini et al.
The method in your argument is likewise not ruled out by Fiorini et al.


Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length

PCP is undecidable essentially because, if there is a match, it could be arbitrarily long. But, here, the question specifically excludes any string longer than $k$ characters. There are only about $2^{k+1}$ possible strings of length at most $k$ over alphabet $\{a,b\}$. Does that help you find an algorithm?


How can I convert a list with duplicates into a set for a reduction to the set cover problem?

There are several possible interpretations of the problem:

The alphabet size could be fixed or unbounded.
Words could be repeated or not.
The input histogram (how many letters of each type) could be encoded in unary (e.g., the letters are "aabcccccc") or in binary (e.g. $a\times 2, b\times 1, c \times 4$).

Here is the complexity of some of these variants.

Fixed alphabet, words may not be repeated, histogram is encoded in unary. Use dynamic programming. Given the list of words $w_1,\ldots,w_n$, compute inductively all possible histograms of all possible subsets of $w_1,\ldots,w_i$ which are "within budget". If the budget is $b_1,\ldots,b_m$ (so the alphabet size is $m$), then the number of such histograms is at most $(b_1+1)\cdots(b_m+1) \leq (2\max b_j)^m$, which is polynomial in the input size. Check whether the budget is one of these possible histograms.

Fixed alphabet, words may be repeated, histogram is encoded in unary. A similar strategy works, using a fixpoint iteration. Maintain a list of reachable histogram. At each round, add all words to all reachable histograms under budget, and update the list. Stop when the list stabilizes. Check whether the input histogram is one of them.

Unbounded alphabet. NP-complete, by reduction from 1-in-3 SAT. There is one letter per variable and clause, and one word per variable truth assignment. The word contains the variable symbol as well as the clauses satisfied by the assignment. All budgets are $1$.


In type systems, is there a name for SQL's way of cutting and combining record types into new types?

I think what you are looking for is type inference for record types.  Let me give you a bit of an overview on each of those; but those keywords should help you find a lot more on those topics.

Type inference means that you don't need to declare the type of everything.  Instead, the compiler figures out the types where it can, from context.  For instance if you write a function

function f(x,y):
    return (x+y)/2

the compiler can figure out that f is a function that accepts two ints and returns an int.  (How?  It knows that 2 is an int, and that both operands to the / operator must have the same type.  Therefore, the type of (x+y) must be int.  That in turn means that both x and y must have type int.  And so on.)

You want type inference, so you don't need to explicitly declare the type of the result of the select and join operations.

A record type is basically just a fancy name for a struct.

A record is an object that has a list of fields; each field has a name and a type.  For instance, to invent some example syntax: {height: 69, weight: 152, name: "Bob"} might be a record with three fields; if r is a variable holding this record, then you might be able to use syntax like r.height to access the height field.

You might notice that a record is a lot like a tuple, except that the elements of a tuple do not have names (you just access the first element, second element, third element, etc. of a tuple), whereas the elements of a record do have names.  The ability to provide names is convenient.

Others have suggested you want anonymous record types, meaning you don't have to explicitly declare the record type.  That might be relevant, too.

With those concepts, here's what I think you want from a language.  First, I think you want your language to support records.  Second, assuming you want a statically typed language, it sounds like you want your language to support type inference, so that the compiler can infer the types of records where possible.  (In a dynamically typed language, you might not need the type inference part.)  Third, you want your language to provide select and join operations that operate on records and return records, and (assuming you want a statically typed language) you want the type inference operation to be able to infer the types on their result based on the types of what they're operating on.

There are some questions you'll need to decide.  Will select and join be built into the language?  Or do you want to enable them to be implemented as libraries or user-defined functions?

You'll also need to make some decisions about your type system.  Do you want to alow subtyping on records?  Do you want to allow functions in your language to be polymorphic over records?  For instance, consider the following function:

function g(r):
    return (r.weight + 10) / r.height

Do you want your type inference routine to infer that g is polymorphic in the sense that it can accept any record containing width and height fields that are both ints?  Do you want to allow first-class field names?  For instance, consider the following function:

function extract(r,f):
    return r.f

r = {height: 69, weight: 152, name: "Bob"}
extract(r, #weight)

In other words, do you want to be able to pass the name of a field as a first-class value?

There's lots of work on type systems for this sort of stuff, in the programming languages community -- and especially in functional languages.  I believe that F# and ML support sophisticated record types.  Here are two samples:

A proposal for records in Haskell.   Simon Peyton Jones and Greg Morrisett, 2003.
Record Polymorphism in SML#. Atsushi Ohori, Katsuhiro Ueno, 2012.

For experience about how to integrate SQL-like database queries directly into the programming language, take a look at LINQ, which provides support for SQL queries directly in .NET / C#.  There are both academic papers on LINQ and lots of documentation for developers.  It looks very close to what you are looking for.


How to create a LR(k) grammar for an arbitrary k

Here's one pattern for an LR(k) grammar which is not LR(k-1).
I didn't fill in the definition of $A$; there's nothing particularly special about it. It might have an empty right-hand side, or it might match any LR(k) subgrammar. $a^k$ represents $k$ instances of $a$.

$$
\begin{align}S&\to B a^{k-1} b\\
S&\to C a^{k-1} c\\
B&\to A\\
C&\to A\\
A&\to \text{see above}
\end{align}
$$

Clearly, it is not possible to determine whether $A$ should be reduced to $B$ or to $C$ without knowing what the $k$ following token is. So the grammar is not LR(i) for any $i \lt k$. The reduction can be determined using $k$ lookahead tokens, so the grammar is LR(k) provided that $A$ is.


Post Correspondence problem provable instance

The smallest solution is

  0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101

generated by the string

  bdcddbabdcdcddcddbaddbacdaacdddbabaaacdcdabaddbadaacdaacaacabadaac

where $a = (001,0)$, $b=(01,011)$, $c=(01,101)$, $d=(10,001)$.

This solution can be found by a simple pruning procedure:

Start with the list $L$ which contains a pair of empty strings.
At each iteration, attempt to add each of the four "pieces" to each of the pairs in $L$, and remove any pair for which no string is a prefix of the other.

Eventually $L$ will contain a pair of equal strings, in this case after 66 iterations.

As an example, here is the contents of $L$ in the first few iterations:

Iteration 1: (001,0), (01,011)
Iteration 2: (001001,00), (0110,011001)
Iteration 3: (011001,011001011), (011001,011001101)
Iteration 4: (01100101,011001011011), (01100101,011001011101), (01100110,011001101001)

The number of pairs of strings at every iteration fluctuates but generally increases, and after 66 iterations reaches 12081, one of which is the solution given above.


Bayesian updating for multivariate Gaussian

Prior:

$$p_0(\theta_a) \varpropto \text{exp}(-\frac{1}{2}\theta_{a}^{T} (\lambda I_d)^{-1} \theta_a) = \text{exp}(-\frac{1}{2} \frac{1}{\lambda}\theta_{a}^{T} \theta_a)$$

MLE:
\begin{align*}
p(y_{t,a} | \theta_a) &= (2 \pi)^{\frac{n_{t,a}}{2}} |\sum|^{\frac{1}{2}} \text{exp}(-\frac{1}{2} (y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a)) \\
& \varpropto \text{exp}(-\frac{1}{2}(y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a))
\end{align*}

Hence,
\begin{align*}
p_{t,a}(\theta_a) &\varpropto \text{exp}(-\frac{1}{2} \frac{1}{\lambda} \theta_{a}^{T} \theta_a) ~ \text{exp}(-\frac{1}{2}(y_{t,a} - D_{t,a} \theta_{a})^{T} I_{n_{t,a}}^{-1} (y_{t,a} - D_{t,a} \theta_a)) \\
                  &\varpropto \text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a))
\end{align*}

By definition, we also have
\begin{align*}
p_{t,a}(\theta_a) &\varpropto \text{exp}(-\frac{1}{2}(\theta_a - \hat{\theta_{a}})^{T} A_{t,a} (\theta_a - \hat{\theta_a})) \\
                  &\varpropto \text{exp}(-\frac{1}{2}(\theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta}))
\end{align*}

And so we have
\begin{align*}
\text{exp}(-\frac{1}{2} (\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a)) &= \text{exp}(-\frac{1}{2}(\theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta})) \\
\frac{1}{\lambda} \theta_{a}^{T} \theta_a + y_{t,a}^{T} y_{t,a} - y_{t,a}^{T} D_{t,a} \theta_a - \theta_{a}^{T} D_{t,a}^{T} y_{t,a} + \theta_{a}^{T} D_{t,a}^{T} D_{t,a} \theta_a &= \theta_a^T A_{t,a} \theta_a - \theta_a^T A_{t,a} \hat{\theta_a} - \hat{\theta_a}^T A_{t,a} \theta_a + \hat{\theta}^T A_{t,a} \hat{\theta}
\end{align*}

Equating the "second coefficient" of $\theta_a$
 $$\theta_a^{T} (\frac{1}{\lambda} I_d)\theta_a + \theta_a^T D_{t,a}^T D_{t,a} \theta_a = \theta_a^T A_{t,a} \theta_a$$
Hence $A_{t,a} = D_{t,a}^T D_{t,a} + \frac{1}{\lambda} I_d$,

Similarly, equating the "first coefficient" of $\theta_a$, we have $$\hat{\theta_a}^T = A_{t,a}^{-1} b_{t,a}$$


I got the answer with a bit of reverse engineering.

1) 0111 is 7 in denary so the exponent is power(2,7)

2) convert 10101000 to a positive number using twos comp

3) you  you get: 010110000 which is 1/2 + 1/ 8 + 1/16 using the powers of 2 after the radix point

4) this is 11/16 but we no it is negative from step 2 so it is -11/16!


Combinations of elements with mutual relationships

The relevant branch of mathematics is graph theory.

Your elements are the vertices of the graph and the relationships between them are the edges. The triples you're looking for are known as triangles: sets of three vertices with all possible edges between them.

I'm not quite sure what you're looking for in your question. If you just want a list of all the triangles in the graph, that can be done naively just by trying all the triples. If you have $n$ vertices in your graph, that takes about $n^3$ tests. More advanced algorithms turn out to be closely related to matrix multiplication, which can be done a little faster – roughly $n^{2.5}$ steps.  That might still be rather slow for half a million vertices. If you want to go faster, you'll have to either use approximations (if you're happy with finding most but not necessarily all of the triangles). Alternatively, the particular graph you're interested in might have properties that make it easier to find triangles, for example by ruling out a lot of the possibilities.

Your Google search term is "enumerating triangles in graphs".


Yes, there are efficient algorithms for this problem, using standard data structures for storing two-dimensional data.

Here is a simple approach.  Store all of the colored pixels in a quadtree.  Next, for each sub-circle, compute it bounding box, so now you have a square instead of a circle.  Query the quadtree data structure to find all points contained within that square.  For each such point, test whether it falls within the sub-circle.  If it does, mark that point as associated with that sub-circle, unless it is already associated with a smaller sub-circle.

I expect the running time of this approach will be approximately $O(n+m)$ where $n$ is the number of colored points and $m$ is the number of sub-circles (assuming there is not too much overlap among the sub-circles, which seems likely to be the case for the parameter settings you listed).  Thus, it should be very efficient.

You can alternatively replace the quadtree with any other data structure for 2D data, such as a k-d tree, though for the parameter sizes you mention, I expect that anything will already be quite fast and so it probably won't be necessary to worry too much about optimizing this as much as possible.


Subset Sum algorithm, why not split by 3+?

First of all, let me mention that the algorithm you mention is attributed to Horowitz and Sahni (1974), whose algorithm achieves time $O(2^{n/2})$ and space $O(2^{n/2})$. A major improvement due to Schroeppel and Shamir (1981) reduces memory consumption to $O(2^{n/4})$ while keeping the same running time; this algorithm divides the input into four sets.

The topic is of interest to cryptographers, and there has been a recent line of improvements: Howgrave-Graham and Joux (2010), Becker, Coron and Joux (2011), Dinur, Dunkelman, Keller and Shamir (2012) and Austrin, Kaski, Koivisto and Määttä (2013), which seems to be the latest word on the subject; the authors of the last paper are actually not cryptographers.


Find an element in sorted 2D-array (matrix)

(Copied from a post on StackOverflow)

Here's a simple approach:

Start at the bottom-left corner.
If the target is less than that value, it must be above us, so move up one.
Otherwise we know that the target can't be in that column, so move right one.
Goto 2.

For an NxM array, this runs in O(N+M).  I think it would be difficult to do better.  :)

Edit: Lots of good discussion.  I was talking about the general case above; clearly, if N or M  are small, you could use a binary search approach to do this in something approaching logarithmic time.

Here are some details, for those who are curious:

History

This simple algorithm is called a Saddleback Search. It's been around for a while, and it is optimal when N == M.  Some references:

David Gries, The Science of Programming. Springer-Verlag, 1989.
Edsgar Dijkstra, The Saddleback Search. Note EWD-934, 1985.

However, when N < M, intuition suggests that binary search should be able to do better than O(N+M): For example, when N == 1, a pure binary search will run in logarithmic rather than linear time.

Worst-case bound

Richard Bird examined this intuition that binary search could improve the Saddleback algorithm in a 2006 paper:

Richard S. Bird, Improving Saddleback Search: A Lesson in Algorithm Design, in Mathematics of Program Construction, pp. 82--89, volume 4014, 2006.

Using a rather unusual conversational technique, Bird shows us that for N <= M, this problem has a lower bound of Ω(N * log(M/N)).  This bound make sense, as it gives us linear performance when N == M and logarithmic performance when N == 1.

Algorithms for rectangular arrays

One approach that uses a row-by-row binary search looks like this:

Start with a rectangular array where N < M.  Let's say N is rows and M is columns.
Do a binary search on the middle row for value.  If we find it, we're done.
Otherwise we've found an adjacent pair of numbers s and g, where s < value < g.
The rectangle of numbers above and to the left of s is less than value, so we can eliminate it.
The rectangle below and to the right of g is greater than value, so we can eliminate it.
Go to step (2) for each of the two remaining rectangles.

In terms of worst-case complexity, this algorithm does log(M) work to eliminate half the possible solutions, and then recursively calls itself twice on two smaller problems.  We do have to repeat a smaller version of that log(M) work for every row, but if the number of rows is small compared to the number of columns, then being able to eliminate all of those columns in logarithmic time starts to become worthwhile.

This gives the algorithm a complexity of T(N,M) = log(M) + 2 * T(M/2, N/2), which Bird shows to be O(N * log(M/N)).

Another approach posted by Craig Gidney describes an algorithm similar the approach above: it examines a row at a time using a step size of M/N.  His analysis shows that this results in O(N * log(M/N)) performance as well.

Performance Comparison

Big-O analysis is all well and good, but how well do these approaches work in practice?  The chart below examines four algorithms for increasingly "square" arrays:

(The "naive" algorithm simply searches every element of the array.  The "recursive" algorithm is described above.  The "hybrid" algorithm is an implementation of Gidney's algorithm. For each array size, performance was measured by timing each algorithm over fixed set of 1,000,000 randomly-generated arrays.)

Some notable points:

As expected, the "binary search" algorithms offer the best performance on rectangular arrays and the Saddleback algorithm works the best on square arrays.
The Saddleback algorithm performs worse than the "naive" algorithm for 1-d arrays, presumably because it does multiple comparisons on each item.
The performance hit that the "binary search" algorithms take on square arrays is presumably due to the overhead of running repeated binary searches.

Summary

Clever use of binary search can provide O(N * log(M/N) performance for both rectangular and square arrays.  The O(N + M) "saddleback" algorithm is much simpler, but suffers from performance degradation as arrays become increasingly rectangular.


Meaning of # in descriptions of languages

It's just a symbol in the alphabet, so the alphabet is $\{a,b,\#\}$ and the language is the set of strings that:

contain exactly two $\#$'s and
the string after the second $\#$ is the reverse of the string between the two $\#$'s.


What is the difference between apprenticeship and imitation learning?

In general, yes, they are the same thing, which means to learn from demonstration (LfD). But, usually, apprenticeship learning is mentioned in the context of "Apprenticeship learning via inverse reinforcement learning" (IRL).
Both methods learn from demonstration, but they learn different things:

Imitation learning (a.k.a. behavioral cloning) will try to copy the teacher. This can be achieved by supervised learning alone. The AI will try to copy even irrelevant actions such as blinking or scratching, for instance, or even mistakes. You could use RL here too, but only if you have a reward function.
Apprenticeship learning via inverse reinforcement learning will try to infer the goal of the teacher. In other words, it will learn a reward function from observation, which can then be used in reinforcement learning. If it discovers that the goal is to hit a nail with a hammer, it will ignore blinks and scratches from the teacher, as they are irrelevant to the goal.


What is the 1's and 2's complement of 0.01101?

One's and two's complement apply to (fixed-point) encodings of integers.  They don't apply to floating-point numbers.  Floating point is different.


What are logical addresses and where do they actually reside?

Well, this is the entire point of "virtual memory".

When your program runs, the OS makes it believe it has all the memory just for itself. That is, addresses 1 to 10,000 (say), are all empty and ready for this program to use. If you run two programs, each one of them gets its own space - each one can access address 1 to 10,000 without any interference between the programs.

Obviously, for this to work, the OS must perform some clever bookkeeping, mapping the programs' "virtual memory" into places in the real memory (or hard disk). That is, when the first program access cell 200, the information needs not be in cell number 200 in the real memory. It may be somewhere else, but the OS is responsible of converting the (virtual/logical address) "200" of the first program to some (real) address X, as well as the virtual "200" address of the second program, to some other (real) address Y.


Can a deterministic finite automaton ever go into an infinite loop?

A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.


"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:

Writing proofs about physical wires and switches is extremely difficult.
Writing proofs about Turing machines is (relatively) easy.
Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).

But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.


No, the converse direction does not hold:

Pick some non-c.e. set $B \subseteq \mathbb{N}$. Now consider $\Gamma = \{A \ c.e. \mid A \cap B \neq \emptyset\}$. By construction, $\Gamma$ satisfies the conclusion of Rice-Shapiro (it suffices to consider singleton sets rather than all finite sets). However, for the resulting index set $I$ we find that $B \leq_m I$, so $I$ cannot be c.e..

Essentially, Rice-Shapiro says that the Markov-effectively open subsets of the subspace of ce subsets of $P(\omega)$ (with the Scott topology) are open, but for already for cardinality reasons alone, not all open subsets can be Markov-effectively open.


Your operation is multiplication of polynomials over $GF(2)$, i.e., multiplication in the polynomial ring $GF(2)[x]$.

For instance, if $p=101$ and $q=1101$, you can represent them as $p(x)=x^2+1$, $q(x)=x^3+x^2+1$, and their product as polynomials is $p(x) \times q(x) = x^5+x^4+x^3+1$, so $p \otimes q = 111001$.

If $p,q$ are $r$ bits long, this polynomial multiplication operation can be computed in $O(r \lg r)$ time using FFT techniques, but in practice this may not be a win unless your polynomial is extremely large. There is also a Karatsuba-style algorithm, whose complexity is something like $O(r^{1.6})$, as well as other options.  The situation is somewhat analogous to integer multiplication, in that many of the same fast algorithms can be applied, but not identical.

See, e.g.,

Wikipedia on Fast multiplication algorithms for large inputs.  These methods are described in terms of multiplying two integers, but they can be transposed to apply to polynomial multiplication.
Polynomial Multiplication, Karatsuba and Fast Fourier Transform
When is FFT multiplication of arbitrary-precision polynomials practical?.  Richard Fateman, March 14, 2006.
Can you save time in multiplying polynomials by encoding them as integers?.  Richard Fateman, January 15, 2005.


If an operation, any operation, has an amortised cost of O(1), then performing it n times has cost O(n), by definition of “amortised cost”. Either your amortised cost is wrong, or your total cost is (assuming you change “O(n log n)” to “not O(n)”, to be a bit pedantic).


Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on?

An algorithm solves a problem. Let’s assume that our algorithm is made to solve problem A.

The TM which implements this algorithm should halt and accept on all solutions to problem A. Due to the fact that the algorithm solves A.

Let’s now define L2 as the set of all inputs that the TM halts and accepts on. This will be the set of solutions to problem A.

If we define L1 as the set of all solutions to problem A.

Then in this sense, L1 and L2 should be the same.

I imagine that your confusion is when to use one or the other when defining the language. I am
not sure when you should use each one, however I usually note that if the Turing Machine recognises a language L which is the solution set to a problem A, then this TM can solve problem A.

Remember recognises means it halts and accepts on L.


optimal flow for index multiple source and destination in directed graph

This is an instance of a multi-commodity flow problem.  Unfortunately the problem is NP-hard (even when all edge capacities are 1).


How do I prove that SAT in coNP implies NP=coNP?

If SAT is in coNP then since coSAT is coNP-complete, SAT can be reduced to coSAT in polytime. The same reduction also reduces coSAT to SAT. Since coSAT is coNP-complete, every problem in coNP can be reduced in polytime to coSAT, and so to SAT. This shows that SAT is coNP-complete.


Explanation of Summations for Algorithm Analysis

I will answer each of your questions as follows

Why are the lower and upper bounds 0 and n/2, respectively?

For the lower bound: we can see that at the first recursive call, the running time is $n^2$ so $n^2 = (n - 2i)^2$ when $i = 0$
For the upper bound: we can see that when a base case is given say $T(1) = a$, ($a$ can be some constant that for the purpose of calculating the upper bound, we don't really care) then to reach to the base case, you will need to apply the recurrence formula $x$ times which means you need to solve for $x$ the equation $((n - 2) - 2) .. -2) = 1$. This equation is $n - 2x = 1$ which will give you $x = \frac{n-1}{2}$. To make things easier for readers, someone might consider the base case is $T(0)$. In this case you will instead
solve $n-2x=0$ giving $x=\frac{n}{2}$. This is your convenient upper bound $\frac{n}{2}$.

What do I do with the summation notation to get a final answer?

A good way to solve summation like the one you give for the purpose of asymptotic bounding (such as $O$, $\Omega$, $\Theta$) is using integration. Let's look at the following graph, so you can easily visualize the approach and main idea.

Let's look at the interval where the terms in your summation are monotonic.
In your particular case, the terms in your summation decreases as $i$ increases in the interval of $[0, \frac{n}{2})$. This is because the each of the terms is a parabola on variable $i$, and this parabola has a single minima at $i = n/2$. As $i$ increases, the parabola decreases until $i$ reaches $n/2$ then the parabola start increasing.

Let's not worry too much about the actual value on the y-axis, but focus on the fact that your summation can be view as the summation of all the cyan blocks having width 1. As the terms monotonically decrease, you have $(n - 2i)^2 < (n - 2(i-1))^2$. Then you choose the function $f(x)$ using the right hand side replacing the variable $i$ with the variable $x$ which is the red line in the graph. $f(x)= (n - 2(x-1))^2$ thus you have $\sum\limits_{i=0}^{n/2} (n - 2i)^2 < \int\limits_{0}^{n/2} (n - 2(x-1))^2dx$

Now you solve the right hand side of the above inequality. This will give you $-\frac{1}{2}\frac{1}{3} (n - 2(x-1))^3 \Big|_{0}^{n/2} = -\frac{8}{6} - (- \frac{1}{2}\frac{1}{3}(n+2)^3) = \frac{(n+2)^3 - 8}{6} \in O(n^3)$. So you have $T(n) \in O(n^3)$

If you want to find the bound for $\Omega$, then you will do similarly. The difference now is that you choose $f(x) = (n - 2(x+1))^2$ because the terms in the summation are greater than the next term $(n - 2i)^2 > (n - 2(i+1))^2$. Your summation now can be seen as the bigger cyan plus blue (and purple) blocks. In other words, $\sum\limits_{i=0}^{n/2} (n - 2i)^2 > \int\limits_{0}^{\frac{n}{2}-1} (n - 2(x+1))^2dx$. Note that I have changed the upper bound on integration because getting over $\frac{n}{2}-1$ the terms change direction. But that is ok, because we still have the bound on $>$ sign

Solving the integration will give you a polynomial of degree 3 so you have $T(n) \in \Omega(n^3)$.

So now you can conclude that $T(n) \in \Theta(n^3)$

Extra: Back up image in case the graph above is no longer viewable:
Summation bound


Try the following grammar (which can be transformed into a regular grammar):

$S \rightarrow A \mid E \mid I \mid O\mid U$
$A \rightarrow aA \mid bA \mid cA \mid \dots \mid zA \mid \epsilon$ (all consonants and only 'a')
$E \rightarrow eE \mid bE \mid cE \mid \dots \mid zE \mid \epsilon$ (all consonants and only 'e')
$I \rightarrow iI \mid bI \mid cI \mid \dots \mid zI \mid \epsilon$ (all consonants and only 'i')
$O \rightarrow oO \mid bO \mid cO \mid \dots \mid zO \mid \epsilon$ (all consonants and only 'o')
$U \rightarrow uU \mid bU \mid cU \mid \dots \mid zU \mid \epsilon$ (all consonants and only 'u')

Example 1: $S \Rightarrow A \Rightarrow aA \Rightarrow anA \Rightarrow annA \Rightarrow annaA \Rightarrow anna$

Example 2: $S \Rightarrow E \Rightarrow sE \Rightarrow seE \Rightarrow sepE \Rightarrow septE \Rightarrow septeE \Rightarrow septemE \Rightarrow$ $septembE \Rightarrow septembeE \Rightarrow septemberE \Rightarrow september$

Warning: do not expect that this grammar generates only English dictionary words. For example it does generate a nonsense such as 'aagfdadgsa'.


Till which layer does the loopback packet goes?

When you say "layer", you are probably thinking of the OSI model, also known as the seven-layer model.

However, real TCP/IP implementations don't actually fit the OSI model very well.  The OSI model was designed by a standards committee 30 or 40 years ago, based on how the committee members thought network stacks ought to be designed -- but that was before the Internet and without the advantage of the experience we have today.

127.0.0.1 is an IP address, and the loopback functionality of 127.0.0.1 is associated with the IP protocol.  The IP protocol can be thought of as most closely associated with the "network layer" (in the OSI model).  So, you could say that the answer is "the network layer".

But, it's important to realize that this is a bit of a lie.  In real operating systems, there's not necessarily a clean separation between the TCP stack and the IP stack; the two are closely hooked together.  So, it's doesn't make sense to ask "the code that does loopback processing -- what layer is it at?".  The code that does loopback processing could plausibly be considered part of the TCP/IP stack, and the TCP/IP stack combines elements of the network layer, the transport layer, and the session layer.  Loopback processing might also be performed in a separate device driver that, from the operating system's perspective, looks like another device (just like another Ethernet card, but different), so one could even make an argument that the code is really part of the data link layer or physical layer.  See how the seven-layer OSI model isn't really adding much insight here?  The code is what the code is; trying to attach a label based on one of those seven layers is a human construct, one that in this case isn't a very good match to reality.

It's probably better to think of the OSI model as a plausible vocabulary for talking about network protocols, but it's less helpful when talking about the structure of networking code: the structure of the code doesn't necessarily correlate well to the seven layers of the OSI model.

TL;DR: the OSI model is a lie.


Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

Yup.  Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search.  This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time.  Note that the average case only applies if you make a particular assumption about the distribution of values in the array.


Why vertices of directed acyclic graph are considered strongly-connected components?

This has to do with the definition of Strongly Connected Component in graph theory.

  A graph to be said to be Strongly Connected if every vertex is
  reachable from every other vertex.

The smallest possible graph of any type consists of a single vertex.
Since that vertex can reach itself (since it is itself), the graph therefore meets the criteria, and can be considered Strongly Connected.

In this image, the nodes at the bottom right, and the top middle are examples of smallest possible strongly connected components:


Why is it so difficult to eliminate dead loops?

The conceptual problem here is that dead code elimination is not computable. That is, we know that there is no algorithm that can remove all instances of dead code.

Of course, tools can be created that recognize some instances of dead code and remove them. Which patterns to look for is a matter of taste and skill of the tool creator; it's better to be conservative and err on the site of not breaking things. Language semantics play a huge role as well. I don't think there are overarching conceptual issues there, but I could be wrong.

There may be language-specific subtleties at work that prevent elimination of apparently dead code. For instance, a Java compiler can never remove a private method that is never called from within the class -- it can be executed using reflection. Such special cases are beyond the scope of this site, and best discussed one by one on Stack Overflow.

In the end, I expect there to be trade-offs (as there always are): how much time do you spend on developing the optimizer, how much time do you spend during compilation, for what gain? Maybe an optimization that often creates more efficient code occasionally creates some dead code, which you are willing to accept.


Compression algorithm using key value mapping

All of your doubts are correct.
What you're describing is called static-dictionary compression. It works well for short text strings (see smaz, for example, though I doubt that its fixed dictionary was obtained by machine learning).
It would probably not accomplish much when applied to zip files because deflate doesn't tend to produce common bit sequences that are long enough to be further compressed – because eliminating those sorts of sequences is essentially its job.
A weakness of deflate is that its maximum copy length is 258, which means that long repeating sequences of bytes will tend to produce repeating (offset,length) pairs in the output, which can be further compressed by another pass. But the encoding of the repeated (offset,length) pair varies from file to file (even the length part, because the bit pattern used to represent a length of 258 isn't fixed), so you would need a dynamic dictionary to benefit from this.


Who converts binary/machine code to electrical signals and how?

In old computer you actually had a row of switches on the front panel
that would allow entering 1s and 0s directly by hand in the registers
of the machines. But this is no longer done.

You never have 1s and 0s, unless you ask the machine to print its
internal information as a sequence of 1s and 0s. All information is
already in the machine encoded as voltage, or magnetic orientation, or
hole in a physical substrate, or some other physical form. Various
devices can perform the translation between these form: magnetic
heads, laser beams, electro-mechanical devices, electronic
circuits,etc.

Some form are better adapted at memorizing or transmission by various
means, while other (electrical signal notably) are better adapted at
processing, usually by complex systems of logical gates (and, or, not,
xor ...) and micro-memories (registers).

In general, binary/machine code is no longer entered by human beings,
but produced by a program (usually a compiler) by the computer itself,
or by another computer and then imported on some memory support or by
network. However, human beings can ask to have it printed as 1s and 0s
to check what the computer is using or producing. However this
requires transforming the single bit 0 or 1 in the computer as a
stream of bits to be interpreted by the printer as a request to print
an actual drawing (on screen or paper) od the symbol representing a 0
or a 1.

It is hard to give more details without your being more specific
regarding the source form and target form of the conversion. But it is
most often from binary to binary, with a different physical
representation.


Lamport Timestamps: When to Update Counters

Considering that any local action (e.g. increasing a counter) done by a process is an event, the Wikipedia sentence

  "A process increments its counter before each event in that process."

does not make any sense to me. Let me try to answer your questions:

  Should we increment the counter before sending a message, as the sending of a message is itself an event. This incremented timestamp is the value that is sent with the message.

Both actions (i.e. increasing the counter and sending the message) happen atomically in the same event. The same is true when a message is received: The receive event already includes the counter update.

  When a message is received by process Pi Lamport states that Pi logical clock should be set to max(Tm+1,Ci). However, the Wikipedia article says that this should be max(Tm,Ci)+1. Is Wikipedia wrong?

Note that, according to Lamport's paper, the logical clocks must satisfy the following property:

  If $a$ happens before $b$ then $C(a) < C(b)$.

In particular, this means that clock values (of events) at the same process must be strictly increasing.
Therefore, the correct update rule is $\max(Tm,Ci)+1$, as otherwise two subsequent events at the same process might have the same value.