Suppose that your problem is a minimization problem: on instance $I$, you output a solution $O$ which should minimize some function $f(O)$. We say that an algorithm is a $(1+\epsilon)$-approximation if on instance $I$ it outputs a solution $S$ which satisfies
$$ f(S) \leq (1+\epsilon) f(O) $$
for an optimal solution $O$. We also say that $S$ is a $(1+\epsilon)$-approximate solution.

An FPTAS is an algorithm that gets as input an instance of size $n$ and a number $\epsilon>0$ (let's not worry about how $\epsilon$ is represented), returns a $(1+\epsilon)$-approximate solution, and runs in time $O(n^C (1/\epsilon)^D)$ for some constants $C,D>0$.

Given an FPTAS, you can extract a polynomial time $(1+\epsilon)$-approximation algorithm for any $\epsilon > 0$; furthermore, the dependence of the running time on $\epsilon$ is polynomial (in $1/\epsilon$).

A PTAS, in contrast, is an algorithm gets as input an instance of size $n$ and a number $\epsilon>0$, returns a $(1+\epsilon)$-approximate solution, and for any fixed $\epsilon > 0$, runs in polynomial time. That is, for every $\epsilon > 0$ there exist constants $A_\epsilon,C_\epsilon$ such that the running time of the algorithm is at most $A_\epsilon n^{C_\epsilon}$.

Again, given a PTAS, for any $\epsilon > 0$ we can extract a polynomial time $(1+\epsilon)$-approximation algorithm. This time, however, the dependence of the running time on $\epsilon$ can be arbitrary.


Decidability of Turing machines and misconceptions on the halting problem

The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable.
If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$).
As an example in which this problem is decidable consider the trivial Turing machine $T$ that immediately halts.
As an example in which this problem is undecidable consider an universal Turing machine $T$ in which $w$ encodes a pair $\langle M, w'\rangle$ where $M$ is some other Turing machine, and $w'$ is $M$'s input. The machine $T$ simply simulates $M'$ on $w'$. Clearly if we could solve the halting problem for this fixed $T$ and any $w$, we could also solve it in the general case.
If a word $w$ is fixed but the machine $T$ is part of the input of the problem, then the problem is undecidable regardless of $w$.
Suppose towards a contradiction that this problem was decidable, then given a Turing machine $M$ and a word $w'$ as input, you could decide whether $M(w')$ halts. To do so you construct a new Turing machine $M'$ that clears its tape, writes $w'$, and then simulates $M$ (an encoding of such a machine $M'$ is computable given $M$ and $w$). Clearly $M'(x)$ halts iff $M(w')$ halts, regardless of $x$. In particular, for $x=w$,  $M'(w)$ halts iff $M(w')$ halts. It then suffices to decide whether $M'(w)$ halts, which we can do by our hypothesis.
If both a Turing machine $T$ and a word $w$ are fixed, then the problem does not make much sense since you do not have a class of instances anymore... Notice that, in this case, either $T(w)$ halts or it does not, meaning that one of the following two Turing machines must answer correctly: 1) Always halt and accept. 2) Always halt and reject.


Why are long block lengths commonly assumed/used in channel coding proofs?

One reason is that this allows a small fixed overhead per block.  With a sufficiently large block, the effect of this becomes minimal (it's amortized out over the length of the block).


Why is $AF \phi \lor \varphi$ not equivalent to $AF \phi \lor AF \varphi$?

You also need to argue the other way around. "Each path has either $\psi$ or $\varphi$" is not the same as "either each path has $\psi$ or each path has $\varphi$".


Trying to understand the proof of the halting problem presented in Sipser textbook

The first misconception is that $A_{TM}$ is a Turing Macahine. $A_{TM}$ isn't a machine, it's a language, $H$ is the machine that decides the language $A_{TM}$. So you give $H$ a string that consists of two parts, a string $M$ that describes a Turing machine, and another string $w$, which can be anything.

This leads us to the second part, $w$ can be any string - it's the theoretical input to $M$ that you want to know whether $M$ would accept or not. So $H$ should accept if $M$ would accept $w$, and reject otherwise (i.e. when $M$ doesn't accept, which could be by rejecting or never halting). $\langle M \rangle$ is just a string, it happens to coincidentally be a description of a Turing Machine, but it is still just a string. So there's no reason we can't ask "does $M$ accept the string which is its own description?"


Suppose you had a problem such that for any $x \in L$, there was a verifier $v$ such that $v$ could be checked against $x$ by a nondeterministic polynomial time algorithm. For a valid $(x, v)$ pair, there is some verifier $v'$ such that it takes polynomial time to check $((x, v), v')$ is a correct verification.

But then, you could simply combine $(v, v')$ into a single witness, and run the check in deterministic polynomial time.

Thus, the class ${\bf N(NP)}$ you describe is really just equal to ${\bf NP}$.


Order-of-growth of selection sort is quadratic, it takes 2secs to sort 100 elements, what will be the expected completion time to sort 200 elements?

First off, that's a less than wonderful question.

Second: If the running time is indeed quadratic (with no linear term), the best answer is 8 seconds, not 4 seconds.  Suppose the running time is $T(n) = c \cdot n^2$ for some constant $c$.  Then we know $T(100) = $ 2 seconds.  One can show that

$$T(200) = c \cdot 200^2 = c \cdot 4 \cdot 100^2 = 4 \times T(100),$$

so it follows that $T(200) =$ 8 seconds.

That said, I still don't like the question very much.  Usually when we say that an algorithm has quadratic running time, we mean that its running time is in $\Theta(n^2)$.  That means the running time could be something like $T(n) = c_1 \cdot n^2 + c_2 \cdot n$.  If the running time looks like that, then we don't have enough information to conclude what the running time will be for $n=200$.


This looks like a typo in your source, and your derivation looks correct. So the corrected statement should be:

  $S \models  S' \iff S \land \neg S'$ is unsatisfiable

or

  $S \models  S' \iff {\boldsymbol \neg} (S \land \neg S')$ is satisfiable


Tasks in which recursion is either the fastest or only way to produce a result

There are no questions which can only be solved with recursion. This is because they can be solved with Turing machines, which don't use recursion.

The set of problems which can be solved with a TM are exactly the same as the ones which can be solved with recursion (or its formal model, the Lambda Calculus).

In particular, if you want to simulate recursion iteratively, the way to do this is to use a data structure called a stack (which simulates the call stack for functions).

As for algorithms that can be solved better using recursion, there are tons. I'm surprised that your recursive versions were longer, as recursion usually leads to less code. This is one of the reasons haskell is gaining popularity.

Consider the algorithm quicksort, for sorting lists. In rough pseudocode, it's as follows:

function quicksort(list)
    if length(list) <= 1
        return list
    pivot = first element of list
    lessList = []
    equalList = []
    greaterList = []
    for each element in list:
        if element < pivot, add to lessList
        if element == pivot, add to equalList
        if element > pivot, add to greater list
   sortedLess = quicksort(lessList)
   sortedGreater = quicksort(greaterList)
   return sortedLess ++ equalList ++ sortedGreater

where ++ means concatenation.

The code isn't purely functional, but by dividing the list into different parts, and sorting each sublist recursively, we get a very short $O(n\log n)$ sort.

Recursion is also very useful for recursive data structures. Often times you'll have a traversal on trees, of the following form:

function traverseTree(tree)
    if (tree is a single node)
        do something to that node
    else, for each child of tree:
         traverseTree(child)


Inorder tree tranversal on binary search tree doesn't give the elements in order?

This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree.


If $B$ is neither empty nor the universal set, then the reduction can be performed and is trivial.

You need to have two strings $w_1 \in B$ and $w_2 \notin B$. In the reduction of membership problem $(A,x)$, we trivially solve the membership in $A$ in polynomial time: if $x \in A$ then return $w_1$ else $w_2$.


Producing a total or partial order from an inconsistent relation

It's hard to say without more context and more modelling.  It will require some assumptions on how the results of the comparison function relate to the (hidden) desired total order.
It's possible you might want the Bradley-Terry-Luce model.  If so, there are many standard algorithms.  See also https://cs.stackexchange.com/a/85204/755.
It's possible you might want some ranking system, like Elo, etc.
It's possible you might want a ranked voting system, such as IRV, Condorcet method, Borda count, or any of many others.  They all have various flaws and tradeoffs.  There is a proof that no system will have all the properties we might want -- see, e.g., Arrow's theorem and the problem of non-transitivity (that even if each of your friend's individual preferences is transitive, i.e., a total order, then there is no guarantee that there exists a global total order that is consistent with all of them).


Minimum-cut with minimum number of edges

Those answers assume that all edge capacities are integers.  Assuming they are, this works.

Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut.  Note that if you consider any cut in the original graph with larger capacity, its original capacity will be $x+1$ or more, so its total capacity in the transformed graph will be $(x+1)(|E|+1)+k'$ for some $k'$ in the range $0 \le k' \le |E|$.  Now

$$\begin{align*}
(x+1)(|E|+1)+k'
&= x(|E|+1)+|E|+1+k'\\
&> x(|E|+1)+|E|\\
&\ge x(|E|+1)+k,
\end{align*}$$

so any cut in the original graph that isn't a min-cut won't be a min-cut in the transformed graph, either.

In other words, any min-cut of the transformed graph will be a min-cut of the original graph.

Moreover, out of all of the min-cuts in the original graph, the one whose cut set is smallest is the one that will have lowest capacity in the transformed graph (since the transformation adds one for each edge in the cut set).  So, the min-cut in the tranformed graph will be a min-cut in the original graph, and it will break ties by choosing the one with smaller cut set.


How do you swap consecutive boxes on a Turing Machine tape?

Here is a possible set of transition to do one move, as you request.
Note that $x$ is to be replaced by $0$ and by $1$, so that each
transition with $x$ is actually a pattern to be replaced by 2
transitions, one with $0$ and the other with $1$, instead of $x$ (so you really have 5 transitions below)
And of course $q_{2,x}$ stands for two states: $q_{2,0}$ and
$q_{2,1}$.

I present things that way so that you know what to do if you can have
more than two disctinct symbols to deal with.

The $*$ is just a wild card, indicating that the content of the tape
does not matter.

This will do the required  exchange, with $0$ or $1$. You end up in
state $q_2$, still pointing to the $a$

$\begin{align}
q_1, a&\to q_{1,a},a,R\\
q_{1,a},x&\to q_{2,x},a,L\\
q_{2,x},*&\to q_2,x,R
\end{align}$

I hope this is clear.

What it does is to note $a$ in the finite state control, by going in state $q_{1,a}$, and then moving Right. There it notes in the finite state control whatever $x$ is found there, a $0$ or a $1$, thus going in state $q_{2,x}$, and write down the $a$ (so it can forget it), and moves back Left.
Back on the left square, there is still an $a$, it does not matter, it can write down the $x$ it memorized in the finite state control, and move Right again, in state $q_2$, so that it is pointing to the $a$ that was moved.

Note that the $*$ could be replaced by $a$. The $*$ is a convenient notation to say that it does not matter, as you could have several symbols other than $a$ to be moved in this way.

$q_2$ is whatever state you need to be in after performing one such permutation.


The complexity of an algorithm is defined in the size of input. You can talk about the running time of algorithm in other parameters but the classic complexity classes like $\mathsf{P}$ and $\mathsf{NP}$ are defined in the size of input (in Turing machine model).

For an algorithm to read $N$ numbers in $O(N)$ time it needs to be able to read a number in constant time. This might seem OK at first but it is not. The time that it takes to read a number depends on the number of bits needed to store it. If you want to read a number which has $2$ bits and a number which has $2^{100}$ bits to see even on an actual computer it really depends on the number of bits.

This confusion about reading a number in constant time comes because in programming languages the data types for numbers has a maximum number of bits. For example, in many programming languages an integer variable cannot store a number more than 64 bits. So it always reads 64 bits and therefore seems constant time. But if you don't have an upper bound on the size of numbers that you might read it can take arbitrary large amount of time.

Therefore we cannot bound the running time of an algorithm reading $N$ numbers simply in $N$, it depends on how large those numbers are.

OK, so does this mean we shouldn't use the RAM model based analysis for algorithms since it hides these issues? Well, we can use them, and it is usually much easier to use them. But one should be careful about these issues. That is the reason we put emphasis on what is the size of the input for a problem when teaching data structures and algorithms.

But it is not just the input. Take for example the following program:

Input: n
x = 2
for i from 0 to n
  x = x*x
return x

At first glance this looks like to be a polynomial time algorithm. We have a loop that is executed $n$ times and inside the loop we perform a single simple multiplication. So this is polynomial time?

No, it is not. The size of input is $\lg n$ (the number of bits used to give $n$) so this the loop is executed exponentially many times. But that is not the only problem. Let's look at

Input: n
x = 2
for i from 0 to log n
  x = x*x
return x

Is this one polynomial time?

It is not. Although the loop is executed only a linear number of times in the input length the number $x$ grows and it grows it takes more time to multiply it. To see this ask we can look at the number of bits $x$ the algorithm returns. Surely an algorithm running in polynomial time cannot return exponentially many bits, right?

$$
(0,2)\\
(1,4)\\
(2,16)\\
(3,256)
.\\
.\\
.\\
(i, 2^{2^{i}})
$$

So the output is $2^{2^{\lg n}}$ which has $2^{\lg n}$ bits, exponentially more than the number of bits in input.

Now why this algorithm is not polynomial time? Well, multiplying two numbers is not constant time, and as $x$ grows the multiplication will take longer and longer time,
and the amount of time it takes to multiply two numbers grows with the number of bits they have.

In a language like C you will quickly overflow if you define $x$ to be of the standard data types for storing integers.

OK, so why people use the RAM model for algorithms analysis then? Because it is much easier to analyze algorithms in the RAM model and if one is careful the result is correct. for example, if you only use operations which are polynomial time in the size of their input (like multiplication) and during the execution you only store and use objects which are of polynomial size in the size of input then if your algorithm executes a polynomially many operations then your algorithm is actually polynomial time.

Now, returning to the dynamic programming algorithm for the Knapsack problem. The space complexity of the algorithm is roughly $w^2n$ and the number of operations executed by the algorithm is $wn$. The size of input is something between $n+\lg w$ and $n\lg w + \lg w$ since we can assume all numbers are at most $w$ (otherwise we can ignore them). The exact size of input depends on the size of the numbers given to use. So it is not going to be polynomial time in general.

However, when $w$ is exponentially small relative to $n$, i.e. $w \approx \lg n$ the size of input becomes roughly something between $2n$ and $n^2$ and the running time becomes roughly $n^2$. In this case the running time is going to be bounded by a polynomial in the size of input.

When $w \approx \lg n$, it means that the numbers are so small that you can encode them in unary in place of binary with a at most polynomial increase in the size. This is why people sometimes say that Knapsack is polynomial time when the input numbers are encoded in unary. That is essentially the same as saying $w \approx \lg n$.

Note that if we encoded the numbers in the input in unary, the size of input would be between $n+w$ and $nw+w$ and then the algorithm is polynomial time in the size of the input.

In short, dynamic programming for Knapsack is polynomial time when the number $w$ is at most a polynomial in the total length of the input. This can be phrased in different ways but that is what essentially pseudo-polynomial means.

I think these confusion happen partly because people forget to emphasis the encoding used for input and output and without fixing those encodings the computational problem is not completely defined. All objects whether numbers, graphs, strings, etc. should be encoded with the basic objects that the machine deals with, which is usually bits. And there are many different ways of encoding other objects with bits, this is particularly important in practice when dealing with graphs. Some graph problems can be solved faster using adjacency matrix, other graph problems can be solved faster using adjacency lists, etc. and until the encodings are not fixed the complexity of the graph problem is not well defined.


NP-hardness for one-dimensional facility location problem with entrance fee for each customer

$\require{cancel}$
The answer shows a reduction to the rainbow path problem and thus doesn't prove anything about the complexity of the given problem. See this paper which contains hardness results for related problems (theorem 2.3 states that rainbow s-t path is hard).
The problem is $\cancel{\text{still polynomial}}$, as it can still be reduced to some version of shortest path. Observe that there always exists an optimal solution where the facilities are a subset of $\{x_1,...,x_n\}$ (given an optimal solution and a facility $y_j$ in it, let $A_j$ denote the set of clients attending $y_j$, then replacing $y_j$ with the median of $A_j$ does not increase the value of the solution). Now construct a directed graph whose vertices are $V=\{s,t, v_{il}| i\in[n], l\in[m] \}$ and whose edges are given by:
$$E=\{(v_{il},v_{jk})| i<j\in[n], \text{and } l,k\in[m]\}\cup\{(s,v_{il})|i\in[n],l\in[m]\}\\\cup\{(v_{n,l},t) |l\in[m]\}$$
Interpret the edge $(v_{il},v_{jk})$ as choosing a solution where the clients $x_{i+1},...,x_j$ are members of the facility $y_k$. With this in mind, we set the weights of the edges to be:
$$
w(v_{il},v_{jk})=\sum\limits_{q=i+1}^j |x_q-m_{ij}|+(j-i)f_k\\
w(s,v_{il})=\sum\limits_{q=1}^i|x_q-m_{0,i}|+if_l\\
w(v_{n,l},t)=0, \text{ for all $l\in[m]$}
$$
Where $m_{ij}$ is the median of $x_{i+1},...,x_j$. An optimal solution for your problem is the weight of the lightest path from $s$ to $t$ of length $\le m$ which uses at most one edge from the set $E_i=\left\{(v,v_{l,i})|v\in V, l\in [n]\right\}$ for every $i\in[m]$ (this implies that we do not use the same facility twice). This version of shortest (lightest) path can be solved in polynomial time (think of it as having $m$ different color edges, and we want a path that does not use the same color twice, I believe that a sort of modified Dijkstra should work).


How do I check if two if-stmt blocks are the same?

(Here, I am assuming that the statements are taken from a Turing-equivalent programming language, since this is the common case in practice.)

In the general case, we know this is not feasible. That is, we know that there exists no algorithm (not even an inefficient one!) that, given two statements, can always output whether they are equivalent.

This is one of the standard results that can be proved using computability theory. A short proof is that, if $equiv(s_1,s_2)$ were decidable, then we can choose any  statement $s_{\sf fixed}$ and obtain that the set $A = \{\langle s1 \rangle \ | \ equiv(s_1,s_{\sf fixed}\}$ is decidable. Indeed, to decide that, we can simply use a decider for $equiv(-,-)$ fixing its second argument to $s_{\sf fixed}$. However, Rice's theorem proves that $A$ is not decidable.

This can also proved without Rice, e.g. using the fact that the halting problem is not decidable, and constructing a suitable reduction.


Prove correctness of recursive multiplication algorithm

You need to do a proof by induction on $n + r$. Let $P(m)$ be the statement "for any $n,r \geq 1$ satisfying $n+r = m$, $\mathrm{multiply}(n,r) = nr$. The proof by induction goes along the following lines.

Base case: $m=2$, so $n=r=1$. By inspection, $\mathrm{multiply}(1,1)=1$.

Induction step: suppose $P(m)$ is true for some $m \geq 2$, and let $n,r\geq 1$ satisfy $n+r = m+1$. If $n=1$ or $r=1$ then $\mathrm{multiply}(n,r)=nr$ by inspection. Otherwise, by $P(m)$, $\mathrm{multiply}(n-1,r)=(n-1)r$ (since $n-1+r = m$), so $\mathrm{multiply}(n,r) = r+\mathrm{multiply}(n-1,r) = r+(n-1)r = nr$.

By the principle of mathematical induction, $P(m)$ is true for all $m$, and so for any $n,r\geq 1$, $\mathrm{multiply}(n,r)=nr$.


Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Technically it is $O(n\log n)$, since big-O is an upper bound only, but your tighter bound of $O(n)$ is also correct.  (Without loss of generality, it suffices to restrict $n$ to powers of two; then the proof is easy.)


What is the standard notation for introducing syntactical formalism in a paper

There is no general standard way. It depends to some extent on what is
customary in the community you are addressing, on the size and
syntactic complexity of the language you are defining, on the amount
of formality required, and on whether the formalism is intended for
practical use or only for theoretical work.

Typically, if you are defining a programming language, You are likely
to decompose the presentation into a lexical and syntactic part. The
lexical part defines elements of your language such as identifiers and
literals (numbers, strings, or other), usually by means of regular expressions. The syntactic part defines the
various constructs of your language, often with a Context-Free grammar. In the case of programming languages, the most common way of defining a context-free syntax is with the Backus-Naur Form (BNF) which is a metalanguage for syntax definition.

I you a creating a shell command for the Unix system, you will use a
presentation that is quite close to your example.

If you are defining an algebraic formalism, you may define a tree
syntax, or possibly a string syntax based on a context-free formalism,
possibly not caring for syntactic ambiguity issues.

It is up to you to be knowledgeable enough to determine what is
appropriate in your specific case. Existing similar literature should
help you.

Two questions you want to ask yourself when choosing a notation are:

what is sufficient to convey my intent with enough precision, given the purpose and use of the language?
Will it be clear for my readers, given the kind of experience and knowledge they are supposed to have.

Your specific example of being the first to introduce XML syntax, is difficult to answer because the is not really a first. The XML formalism was derived from predecessors such as HTML and SGML, and probably other mark-up languages. One is seldom first, and it is usually wise to restart from the shoulders of those who came before. This applies both to what we define, and to the definitional tools. However, the intended community of users may change, and choices that may be best for a very general public may not be so good for computer specialists, or for theoretical work, the converse being also true. On the other hand, people prefer things close to what they already know.

If you want to introduce a syntax near or derived from XML, the above applies, and you should probably use the same definitional tools But you should probably make sure that your variations are necessary. In such a case, you may also rely on what people may already know of XML, which is fairly widely known, and insist on the differences, on the ways your language departs from XML.


Term for a graph decomposition based on a maximum matching

Looking at the image in the question, I get the impression that $X_L\cup Y_S$ is a minimal vertex cover of the graph $G$. (This is not fully true: If $X$ contains isolated vertices, then those would be part of $X_L$, but not of a minimal vertex cover.) Good, but there can be many vertex covers of a graph, so this does not yet fully characterize that specific decomposition. So let us look at the construction in more detail: Any minimal vertex cover must contain at least one vertex from every matched edge. Since the vertices in $X_0$ don't belong to any matched edge, covering the edges incident to $X_0$ by vertices (from $Y$) belonging to matched edges is the best we can do. So $Y_S$ turns out to be the biggest subset of $Y$ belonging to every mimimal vertex cover of $G$. (So it is the intersection of the $Y$ part of all minimal vertex covers). And $X_L$ is the unique subset of $X$ covering the remaining edges (+ the isolated vertices of $X$).

OK, so how is this related to the Dulmage-Mendelsohn decomposition? (set $U=X$ and $V=Y$).

  ..., let $D$ be the set of vertices in $G$ that are not matched in at least one maximum matching

I guess the neighbors of $D\cap X$ belong to any minimal vertex cover, and the neighbors of $D\cap Y$ also belong to any minimal vertex cover. So $Y_S$ is also part of (or at least easily defined) for the Dulmage-Mendelsohn decomposition. Can we also define $X_L$ in terms of the Dulmage-Mendelsohn decomposition? Well, it is easier to define $X_S$, it should be just $D\cap X$.

This all sounds much more complicated than it actually is. If you look at the possible alternating paths for the given maximum matching, it should be easy to see the relation between the minimal vertex cover and the set $D$ used to define the Dulmage-Mendelsohn decomposition.


Checking acceptance of a word vs finding an accepted word

The two problems are Turing equivalent: one is undecidable for Turing machines iff the other is.

Deciding whether a Turing machine (TM) $M$ halts on a specific input $x$ is the Halting problem for Turing machines.

Given a TM $M$, we want to know whether it halts on some word. From
$M$ we build a TM $M^*$ that, independently of its input, dovetails the computation of $M$ over all
inputs (i.e. it mimics the computation of $M$ on all possible inputs in
parallel), and halts iff one of these computations halts.
If we had an oracle $H$ that decided the halting problem, it could
decide whether $M*$ halts or not, hence whether the TM $M$ halts on
some input. This is only for the decision on the existence of that
input, but the same dovetailing construction could then be used to
compute the halting input when it is known to exist. Hence we could build a TM that always halts, either with a word on which $M$ halts if there is one, or with failure when there is none.

Hence, if the halting problem were decidable, the problem of deciding
whether a TM halts on some input, and determining that input wold be
decidable too.

Conversely, let us assume that it is decidable whether a TM halt on
some input. Then given a Turing machine $M$ and and input $x$ we want
to decide whether $M(x)$ halts (the halting problem for $M$ on input
$x$).  For this we build a machine $M'$ that, independently of its
input, will simply mimic the machine $M$ running on input $x$. Hence
the machine $M'$ halts on some input (thus on any input) iff $M$ halts
on input $x$. Hence we have a decision procedure for the halting
problem if we have a decision procedure for halting on some input.

Both problems are Turing reducible to each other. Hence they are
Turing equivalent. If one were to be decidable, the other would be too. Or, to take the contrapositive, the undecidability of one implies the undecidability of the other.


Is there a problem that cannot be represented using graph?

It's trivial to encode natural numbers as graphs (represent $n$ by a path of length $n$, or by $K_n$) so anything that can be represented as numbers can be represented as graphs.


Do not understand why log n = O(n^c) (for any c>0)

It's not actually an equation $f = O(g)$ is a lazy shorthand that should be written $f \in O(g)$. So if you look back at the definition of $O$, you should be able to see what $\log n \in O(n^{c})$ for any $c > 0$ means:

  For every $c > 0$, there exists $n_{0} \geq 0$ and $k \geq 0$ such that $\log n \leq k\cdot n^{c}$ for all $n \geq n_{0}$.

Always remember that $O(\cdot)$ describes a set, $O(\log n) < O(n^{c})$ doesn't actually make sense (unless you make up a special meaning for $<$, but then no-one will know what you're talking about). You could say $O(\log n) = O(n^{c})$, as equality for sets has a understood meaning, though of course this statement in particular would be false.

As John Kugelman points out in the comments below, normal set relations do make sense, so $O(f) \subset O(g)$, $O(f) \subseteq O(g)$, etc., make sense.


Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

The complexity is O(nm)... from G compute the maximal cliques and make them vertices in your graph H (initially with no edges)... then compute all minimal separators and order them by size... pick the largest separator S and make any two cliques C,C' adjacent in H (connect them by an edge with label S) if C,C' both contain S and are in different connected components of H (initially this is of course always true, but may not be later)... then pick next largest separator and do the same... repeat until all separators are processed... the resulting graph H is the reduced clique graph of G... computing maximal cliques and minimal separators takes O(n+m)... there are O(n) cliques and O(n) separators... the rest of the construction is O(nm) as processing each separator can take O(m) time...
... this cannot be improved below O(n^2) unless you can solve the following problem: given a graph G find two vertices u,v such that N(u) contains N(v)... the latter is not known to have O(n+m) solution...
... it is therefore unlikely that a O(n+m) algorithm for computing reduced clique graphs is possible...

see Section 5 in M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. (http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf)


Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

The general idea is that the TM has only finite memory while being in the input part of the tape. It can do arbitrary computations in the right part of the tape, but it can only observe a finite memory footprint of the input. It starts in the input part (on the left) and it can reenter the input part (from the right) arbitrarily often. But each time it enters the input part, the only thing that matters is the state it has when entering (or the fact that it starts from the left). And the only outcome of processing the (read-only) input part is the state it has when it exists (or the fact that it does not exit because it has accepted or rejected in the mean time).

1) That is already  the reason for the domain and codomain. The domain is everything that matters about entering the input part, the codomain is everything that matters about exiting that part. Hence the function completely describes the behaviour of the TM on the input part. In a sense, the function contains everything the TM will ever find out about the word $s$.

Both domain and codomain are finite, hence so is the set of functions. Although the definition is about infinitely many words $s$, there will only be a finite number of different functions $F_s$.

2) $F_{\varepsilon}$ is not about $\varepsilon$-transitions. And it does not expand the previous definition. It is just the special case $s=\varepsilon$, that is the case of the empty input word. Or rather, the case of the empty prefix. After all, the paragraph where this appears is all about how $F_s$ can be computed incrementally along prefixes of $s$.

3) By now we have fully defined the automaton, except for acceptance. And the automaton state fully describes what the TM can do with the word we have read. We have not yet said anything about the part of the TM's computation that happens outside of the input word. The trick is that we do not have to delve into that computation. We just say that the state $F_s$ is accepting, if the word $s$ belongs to the TM's language. The paragraph has an explanation why that is well-defined.


There is nothing inherently wrong about either approach, however the first one is overwhelmingly more common. The reason is that complexity analysis takes place in an asymptotic setting with respect to the size of input.

Computers are machines that perform meaningless operations on meaningless symbols, it is your job to find meaning in the computation. Therefore,
determining what the size is depends on some agreed upon definition of what constitutes a reasonable symbolic representation of the input. Formally, you would have to define how the machine that executes your algorithm works in order to be able to talk about complexity at all, but in this context it is sufficient to assume that any representation that uses a finite set of symbols is acceptable.

There are many ways - all in principle equally valid - to represent the natural numbers. For instance, you might say that $0$ is represented by the string x, $1$ by xx, $2$ by xxx and so on. In this case the size of input would be proportional to the numerical value.

However most of us would agree that representing numbers in some base $b$ - which is certainly acceptable as it requires at most $b$ symbols - is more reasonable; in this case the size of the input is proportional to the number of digits required to write the representation of the number, which is itself proportional to the logarithm of the numerical value.

Taking numbers to have size proportional to their logarithm is also more consistent with the way we treat other objects. If the input of an algorithm is an array, the size of the array is the number of cells (and not the number of different arrays of that length), similarly for graphs, matrices and other mathematical objects.


Why use logic gates in this situation? (XOR gates)

One reason for using such a circuit is to avoid wire crossing. Integrated circuits are laid out on several planar layers, and inside each layer, wires are not allowed to cross (for obvious reasons). Hence if you want to switch two wires, you either need to reach out to a different layer, or to use a gadget such as the one shown. I have no idea whether this kind of gadget is actually used in practice.

It should be noted that same idea can be used to swap two values without using any additional memory:

$A \gets A \oplus B$
$B \gets B \oplus A$
$A \gets A \oplus B$

In a C-like language, this would be A ^= B; B ^= A; A ^= B. This code corresponds to an execution of your circuit in topological order.


What does the following algorithm approximate? (Assume m>1,ϵ>0)

By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (last instruction) and that $x-y<\epsilon$ (exit condition). Combining the two gives you $x< \sqrt{m+x\dot\epsilon}$. If you manage to notice that $x\geq y$ at the end of each iteration of the loop, then you also get $x\geq y=\frac{m}{x}$ and therefore $\sqrt{m}\leq x< \sqrt{m+x\dot\epsilon}$.

You could write down the sequence of values taken by $x$ and $y$ mathematically (this is what you would do anyway to prove correctness and termination of the algorithm if you knew what it did/was supposed to do, but it can also help you to determine this!).

Initially, $\begin{cases}x_{0}=m\\ y_{0}=1\end{cases}$.
At the end of the $n^{\text{th}}$ iteration of the while loop: $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$

Now, analysing the two sequences we find that:

$(x_n)$ is decreasing
$(y_n)$ is increasing
$x_0>y_0$

This is enough to say both sequences converge (as they are monotonic and bounded), to say $x$ and $y$. Using $\begin{cases}x_{n}=\frac{x_{n-1}+y_{n-1}}{2}\\ y_{n}=\frac{m}{x_n}\end{cases}$ we can say that $x=y$.

So $\forall n>0,x_n\geq x=y\geq y_n$. In particular the algorithm must terminate (as $x_n-y_n$ is non-negative and converges to $0$). From there you can continue like in the first part ('By simply looking at the$\dots$').


How to write a recursive function that with certain time complexity

I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.
The set $\{0,1\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.


Worst case using the first fit $2$-approximation for the bin packing problem

The approximation ratio of first fit for bin packing is actually 1.7 rather than 2. See Dósa and Sgall, First fit bin packing: a tight analysis. The paper contains references which prove a matching lower bound.


Lambda calculus didn't seem abstract. And I can't see the point of it

There are many reasons why the lambda calculus is so important.

A very important reason is the lambda calculus allows us to have a model of computation in which computable functions are first-class citizens.

One cannot express higher-order functions in the language of middle school algebra.

Take as example the lambda expression

$$\lambda f. \lambda g. \lambda x. f(g(x))$$

This simple expression shows us that, within the lambda calculus, function composition is itself a function. In middle school algebra, this is not easily expressed.

In the lambda calculus, it is very easy to express that a function will return a function as its result.

Here is a small example. The expression (where I here assume an applied lambda calculus with addition and integer constants)

$$(\lambda f. \lambda g. \lambda x. f((g(x)))(\lambda x. x+2)$$

will reduce to

$$\lambda g. \lambda x. g(x)+2$$

Notice also that within the lambda calculus, functions are expressions and not definitions of the form $f(x) = e$. This frees us from the need to name functions and to distinguish between a syntactic category of expressions and a syntactic category of definitions.

Also, when it becomes impossible (or just notationally cumbersome) to express higher-order functions, one will also have problems with assigning types to expressions.

Function composition has the polymorphic type

$$\forall \alpha.\forall \beta. \forall \gamma. (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow \gamma)$$

in the Hindley-Milner type system.

A very strong selling point for the lambda calculus is precise the notion of typed lambda calculus. The various type systems for functional programming languages such as Haskell and the ML family are based on type systems for lambda calculi, and these type systems provide strong guarantees in the form of mathematical theorems:

If a program $e$ is well-typed and $e$ reduces to the residual $e'$, then $e'$ will also be well-typed.

And if $e$ is well-typed, then $e$ will not exhibit certain errors.

The proofs as programs correspondence is particularly noteworthy. The Curry-Howard isomorphism (see e.g. https://www.rocq.inria.fr/semdoc/Presentations/20150217_PierreMariePedrot.pdf) shows that there is a very precise correspondence between the simply typed lambda calculus and intuitionistic propositional logic: To every type $T$ corresponds a logical formula $\phi_T$. A proof of $\phi_T$ corresponds to a lambda term with type $T$, and a beta-reduction of this term corresponds to performing a cut elimination in the proof.

I urge those who feel that middle school algebra is a good alternative to the lambda calculus to develop an account of higher-order, polymorphically typed middle school algebra together with an appropriate notion of Curry-Howard isomorphism. If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me.


Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

You start with an array $A$ from 0 to N and initialize every value with $\infty$ (or some very large number).
Then you set $A[0] = 0$.

Then you loop the following until no more changes occur:

For each number $0 \leq n \leq N$ and for each integer $l\in L$ you update $A[n+l] = min(A[n+l],A[n]+1)$ (don't forget to check for array boundary violations)

When finished, the value of $A[n]$ should contain the minimum number of integers from your list that sum up to $n$.

Expected runtime of this is pretty bad (assuming you have a huge $N$ and $L = \{1,N\}$, as you will update values for $n<N$ for quite some time until you've found your solution.

You can optimize it a bit by observing, that in each iteration, the assigned values increase by one and thus, if some value has been assigned it will not be updated anymore. Therefore, as soon as $A[n] \neq \infty$ you can stop as the lowest value has been found.

Also you can keep track of a "frontier", i.e those indices $i$, for which $A[i]$ has been assigned in the last iteration. You can implement this with a queue, where you add $n+l$ to the queue if the minimum is lower than the previously found value and don't iterate over all $n$ but take the first element from the queue, which has been initialized with $Queue.add(0)$.

The resulting runtime should be $\approx\mathcal O (K\cdot r)$ (or something similar, e.g. $\mathcal O (K^2\cdot r)$) where $K$ is the number of integers in your set and $r$ is the result.

You could improve it a little bit if you replace the queue with a priority queue (e.g. a maxheap).

Alternatively you could precompute some multiples of your numbers (e.g. if $N=10^6-1$ and you have 1 and 1000, you would first determine the values for the largest multiple of each number that is below $N$ (999999*1 and 999*1000) and assign those directly).


Beta reduction of S combinator in pure lambda calculus

Parentheses matter. Honestly, if you are unclear about how $\lambda$-calculus works, it is going to be rather hard to implement it.
Here is an explicit counter-example:
$$(K S)(K S) = S$$
but
$$K S K S = ((K S) K) S = S S \neq S.$$
I would recommend learning about parsers, abstract syntax trees, and other bits and pieces that make up an implementation of a programming language.
An example of the implementation of the $\lambda$-calculus is available as lambda at PL Zoo. See repl-in-browser for an implementation that runs in the browser (an instance of which is available here).


Help understanding formal language notation

The problem seems to be that they assume you have a background in formal language theory.
Here's the basics.

$\Sigma$ is the symbol which is traditionally used for an alphabet. When you're talking about strings, you always have a finite set of symbols that can be in those strings. Here we use $\Sigma=\{a,b\}$ to say that all our strings are binary, that is, they only contain the letters $a$ and $b$. We could have just as easily chosen $0,1$ or $\vee, \wedge$ or any other symbols we like. We just need a finite set of symbols.
$\epsilon$ is the empty string, the string of length 0. Sometimes you'll see this as $\lambda$, which is confusing, so be prepared for either. In a programming language like C, you'd see this written as "". It has the property that when you append it to the beginning or end of a word, it gives you that same word.
This is a description of context-free grammars. It's basically a concise way of defining a set of strings over some alphabet. We say that a string is in the set if there's some set of derivation rules we can apply to get that string.

The derivation rules basically are a way of generating strings. The idea is that, you start with a special start symbol, usually called $S$. We have upper and lowercase letters, called non-terminals and terminals. We keep applying rules until we only have lowercase letters left.

The X -> Y things you see are the derivation rules. This is saying, in any string, you can replace the symbol on the left with the symbol on the right. The idea is that you keep doing this until you get a word with only lowercase letters.


A problem is anything you're trying to solve computationally. Problems typically specify an input and a desired output which, for most models of computation, will both be finite. Any statement of the form, "Given $X$, compute/evaluate/find/determine/decide whether/..." is a problem.

So, yes, all the things you describe in the question are problems. (Though, in the case where the input is the uncountable set $\mathbb{R}$, you need to be careful about how you specify what the input is.)


What algorithms are there for scheduling tasks

What you can do is to add another parameter to your tasks, something that I would call dynamic priority delta. Or what is equivalent, you can implement some mechanism to increase or decrease the priority of each task on top of multilevel priority queues.

The basic idea is simple. "A process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.", reads section 5.3.6 of Operating Systems Concepts, seventh edition. For an extreme simple example, you can just increase priority level by one if a task has waited for an hour. Here is more excerpt from that book.

  In general, a multilevel feedback-queue scheduler is defined by the following parameters:

  The number of queues
  The scheduling algorithm for each queue
  The method used to determine when to upgrade a process to a higher- priority queue
  The method used to determine when to demote a process to a lower- priority queue
  The method used to determine which queue a process will enter when that process needs service

  The definition of a multilevel feedback-queue scheduler makes it the most general CPU-scheduling algorithm. It can be configured to match a specific system under design. Unfortunately, it is also the most complex algorithm, since defining the best scheduler requires some means by which to select values for all the parameters.

Your situation might be even more complex since your task are also labelled with category. Without more information, I cannot advise further into your scheduling algorithm.

I encourage to read chapter "CPU Scheduling" of Operating System Concepts by Avi Silberschatz, Peter Baer Galvin and Greg Gagne. For even more content, read chapter "Uniprocessor Scheduling" and "Multiprocessor and Real-Time Scheduling" of Operating System Internals and Design Principles by William Stallings. Although they are talking about CPU or processor scheduling, most of the concepts and algorithms are the same as in or can be applied to job/task scheduling. You will find lots of inspirations and ideas and references.


Partial intersection of 10 sorted lists of integers

The simplest way is to first remove duplicates from the 10 lists, and then merge all of them. Any number appearing 3 times in the merged list also appears in 3 of the 10 sorted lists.

A more complicated way is using pointers as you indicate. Briefly, the pointers start at the beginning of the lists, and then you keep incrementing the pointer pointing at the minimal element. You can use a heap to implement detecting which pointer to advance.

If you have $m$ lists containing $n$ elements in total, the first way takes optimal time $O(n)$ but uses up space (or modifies the input), and the second takes time $O(n\log m)$ (the $\log m$ comes from the heap) but uses less auxiliary space.


In present computers, the processor manipulates virtual addresses that are generated by the compiler, but the real physical address is determined at run time by the OS.

To do that, memory is organized in pages. Typical page size is 4kB (2^12bytes). To translate from virtual addresses to physical addresses, an address is considered as having two fields: address of a byte within a page (12 bits displacement) and page address (the remaining high order bits). Translation consists to replace virtual page address in he processor by physical address, with respect to a table generated at process creation by the OS (page table).

The problem is that these table can be HUGE. With 64bits virtual addresses (as in present processors), this page address have (64-12)bits (for 4kB pages) and a page table will hold 2^52 page addresses. This is an insane size (~10^18B) largely above most computer physical memory size. Fortunately, these tables are mostly empty and only a small part of potential virtual addresses have a physical translation.

To cope with that, page tables are multi level. Virtual addresses are split in fields addressing the successive table levels. For instance, with a 4kB page, and 64bits (8B) addresses, it is possible to store 512(2^9) addresses per page. The first 9 high order bits select an address within a page, that will give the address of a new page holding 512 page address. The next 9 high order bits select a new page, and so on.

If a page address is 52 bits in at most 6 steps, we can get the final physical page address corresponding  to a logical page address.

This "page walk" or "table walk" is a complex process that requires several memory accesses and that must be done for every memory access.

To reduce the translation time, the TLB memorize recent correspondences between virtual and phys page addresses. If the physical translation of a virtual address is in the TLB, it is immediately available.

And if translation is not in the TLB, it is recreated by table walk.
TLB misses (and table walk) are very expensive. If all the page tables are already copied to cache memory, it will require some tens of cycles. But if the TLB miss also implies cache misses, the time will be measured by hundreds of cycles.

There are several good tutorials on these problems. Look for instance at the wikepedia page that give good graphical illustrations of table walk.
https://en.wikipedia.org/wiki/Page_table


What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

Yes, there is a polynomial time algorithm.  You simply iterate over all of the elements of each set and add each one to some data structure (e.g., a hashtable, a balanced binary tree) if it's not already present.  Then, you count the number of items in that data structure.

If there are $n$ input sets $S_1,\dots,S_n$, each of size $k$, then the running time of this is $O(nk \log(nk))$ if you use a self-balancing binary tree data structure.  The expected running time is $O(nk)$ if you use a hash table.  The size of the input is $\Theta(nk)$, so this yields an algorithm whose running time is polynomial in the size of the input.


How to show that the complement of a language in $\mathsf P$ is also in $\mathsf P$?

Suppose you have an algorithm that decides membership in $L$ in polynomial time (by assumption since it's in $P$). You can easily write an algorithm that uses the previous one for deciding membership in $\bar L$ and prove that it takes polynomial time.


Differences between the Actor Model and Communicating Sequential Processes (CSP)

Here is how I think Erlang works. I believe Akka is very similar.

Each process has a single mailbox. Messages are put into the
receiver's mailbox by the sender, and fetched by the receiver using
pattern matching. This matching process can change message ordering in
the sense that the oldest message in a mailbox may not match, but a
younger one does. In this case the younger one is consumed
first. Other than that, message ordering is preserved.

With this in mind, the asynchronous $\pi$-calculus extended with input
pattern matching input from buffer describes Erlang (and hence Akka)
semantics accurately, although one needs to do a bit of work in the
encoding, since the $\pi$-calculus doesn't have the restriction to
single channels per process. However, one usually doesn't want an
encoding, but rather a calculus that models the target system
directly.  Such a calculus exists, and it's called Featherweight
Erlang. It is by Mostrous and Vasconcelos. Their paper focusses on
typing, but you can ignore that and just look at the untyped calculus in Section 3.


Shortest path that visits maximum number of strongly connected components

For ease of writing, I'm going to say "component" instead of "strongly connected component."  This should cause no confusion, since it's the only kind of component we're interested in.

Let $G$ be your directed graph.  Let $H$ be the DAG made by contracting every component of $G$ to a single vertex. That is, the vertices of $H$ are the components of $G$ and there's an edge from $x$ to $y$ in $H$ if, and only if, there's an edge in $G$ from the component corresponding to $x$ from the one corresponding to $y$.  Write $h(C)$ for the vertex in $H$ that corresponds to the component $C$ in $G$.

Observe that any path in $G$ that visits the maximum possible number of components must correspond to a maximum-length path in $H$, which must run from some source to some sink.  So, we need to find the longest paths in $H$.  We can't just produce a list of them because there might be exponentially many.  So, instead, we assign a label $\ell(x)$ to every $x\in V(H)$ using the following procedure.

Topologically sort the vertices.
Set $\ell(x) = 0$ for each sink $x$.
Working back from the leaves in the topological ordering, set $\ell(x) = 1 + \max\,\{\ell(y_1), \dots, \ell(y_k)\}$ for each vertex $x$ with out-neighbours $y_1, \dots, y_k$.

Note that the topological ordering guarantees that we've already computed $\ell(y_i)$ for each out-neighbour $y_i$.  When the labelling is computed, it has the property that, for every vertex $x\in H$, $\ell(x)$ is the length of the longest path from $x$ to a sink in $H$.

Now, produce a graph $H'$ from $H$ as follows.

Delete every edge $(x,y)$ such that $\ell(x)\neq\ell(y)+1$.
Let $m = \max\,\{\ell(x)\mid x\text{ is a source in }H\}$ (this is the length of the longest path in $H$).
Iteratively delete every source $y$ with $\ell(y)<m$.

$H'$ contains exactly the vertices and edges of $H$ that appear in longest paths in $H$ (put another way, $H'$ is the union of all longest paths in $H$).  In particular, every path from a source to a sink in $H'$ has length exactly $m$, which is the greatest length of any path in $H$.

Now, produce a graph $G'$ from $G$ as follows.

Delete from $G$ any component $C$ such that $h(C)\notin H'$.
Delete from $G$ any edge from component $C_1$ to component $C_2$ if there is no edge $(h(C_1),h(C_2))$ in $H'$.

Finally, let $S\subseteq V(G')$ be the set of all vertices whose components are sources in $H'$ and let $T\subseteq V(G')$ be the vertices in components that are sinks in $H'$.  The $S$ $T$ paths in $G'$ are exactly the paths in $G$ that visit the maximum possible number of components. Use your favourite shortest path algorithm to find a shortest one.

Thanks to Bakuriu for suggesting topological sort instead of my ad-hoc algorithm.


What is an approximation factor for the Greedy Motif Search algorithm?

Quoting Master’s Thesis in Computer Science by Finn Rosenbech Jensen0, Dec. 2010, Greedy Motif algorithm approximation factor, using common superstring1 and its linear approximation2, was proved it cannot be better then 2.
Using proof by Kaplan and Shafir3 author shows that $\mid t_{greedy}\mid = 3.5 * OPT(S)$.

[0]: Master thesis by Rosenbech Jensen
[1]: Tarhio, J. and E. Ukkonen (1988).  A greedy approximation algorithm for constructing shortest common superstrings.Theor. Comput. Sci. 57(1),131–145.
[2]: Blum,  A.,  T.  Jiang,  M.  Li,  J.  Tromp,  and  M.  Yannakakis  (1994,  May).Linear approximation of shortest superstrings.   InProceedings of the23rd Annual ACM Symposium on Theory of Computing, pp. 328–336.
[3]: Kaplan, H. and N. Shafrir (2005).  The greedy algorithm for shortest su-perstrings.Inf. Process. Lett. 93(1), 13–17.


find function which is in o(log^k(n)) for fixed value of k and in ω(1)


A grammar $G$ is non-amgibuous if every word in $L(G)$ has a unique parse tree. The simplest way to prove that your grammar non-ambiguous is to prove that $L(S + S),L(S * S),L(a)$ are all distinct (here $L(\alpha)$ is the set of all words that can be generated from the sentential expression $\alpha$); given this, an easy induction shows that $L(G)$ is non-ambiguous.

It is clear that $L(S + S)$ and $L(S * S)$ are disjoint from $L(a)$. To prove that $L(S + S)$ and $L(S * S)$ themselves are disjoint, you can prove by induction that each word generated by $S$ is either $a$ or of the form $(w)$, where $w$ is a well-parenthesized expression (parenthesis close each other correctly), and this gives you a rule for identifying the first and the second $S$ in word generated by $L(S + S)$ and $L(S * S)$; the symbol in between determines whether the word belongs to $L(S + S)$ or to $L(S * S)$.


Calculating integral without quadratures

Another approach is to use a computer algebra to compute the integral exactly, symbolically.

See also Wikipedia's article on symbolic integration.  Wikipedia also has a list of techniques and computational methods for integration.


Yes, $x^{100000000000}$ is a polynomial. Your first quote gives an example; your second is the definition.


Minimal complexity for pairing two comparable sets with comparability restrictions

This is the famous "nuts and bolts" problem.  Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple randomized algorithm that achieves $O(n \lg n)$ expected running time.  However, it's very challenging to find a deterministic algorithm with a $O(n \lg n)$ time running bound.  Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.


Number of nonnegative solutions of linear Diophantine inequality

I've found a paper for you (however it's about more general case).

Welcome to the site!


Proof that a given language is not context-free

Use the pumping lemma for CFLs. Let N be the pumping lemma's constant, and take $\sigma = a^{N^{3/2}}$, which certainly has $\lvert \sigma \rvert \ge N$. So we can write $\sigma = v w x y z$ with $\lvert w x y \rvert \le N$ and $w y \ne \epsilon$ such that for all $k \ge 0$ we have $v w^k x y^k z \in L$.

But here only lengths matter. Call $u = \lvert w y \rvert$, so that the length of the pumped string is:

$\begin{align}
\lvert v w^k x y^k z  \rvert = N^{3/2} + (k - 1) u
\end{align}$

where we know that $u \le N$.

Now look for $n$ such that $(n + 1)^{3/2} - n^{3/2} > N$. By the binomial theorem:

$\begin{align}
(n + 1)^{3/2} - n^{3/2}
  &=   n^{3/2} \left( (1 + 1/n)^{3/2} - 1 \right) \\
  &=   n^{3/2} \left( 1 + \frac{3}{2 n} + \dotsb - 1 \right) \\
  &\ge \frac{3 \sqrt{n}}{2} \\
  & > N
\end{align}$

This is $n > 4 N^2 / 9$. This provides a stride larger than $N$ between lengths of strings in the language, the pumped string will fall short.


Find expression with minimal distance to target

This is a very difficult problem. For an already hard special case, you can look at the subset sum problem. So in general, one direction to look at is NP-hard optimization problems (and ways of coping with hardness).


N songs, M instruments, how to pick K instruments to cover maximal amount of songs

I don't know a canonical name for this problem, but unfortunately it's NP-hard, even when every song requires at most 2 instruments.  The upshot is that it's extremely unlikely that any polynomial-time algorithm exists that will solve every instance of your problem.  I'll show this by reduction from the NP-hard problem Maximum Clique, in which we are given an undirected graph $G = (V, E)$ and a positive integer $k$, and asked whether there exists a clique of size $k$ in the graph.

To construct an instance of your problem from the Maximum Clique Instance: Create a song $s_{uv}$ for every edge $(u, v)$ in $E$, and an instrument $t_v$ for every vertex $v$ in $V$, and make song $s_{uv}$ require the two instruments $t_u$ and $t_v$.  Set $K$ (part of the input to your problem) equal to $k$ (part of the input to the Maximum Clique problem).  Now run any algorithm that solves your problem on the just-created instance: if the answer is $\ge k(k-1)/2$ then return YES, otherwise return NO.  (Clearly this procedure could work just as easily with an algorithm that solves the "pure decision" form of your problem, i.e., when a number $r$ is also given as part of the input, and the task is to determine whether it is possible to choose at most $K$ instruments such that at least $r$ songs can be played.)

It is easy to see that, if $G$ contains a clique of size at least $k$, then we must correctly get a YES answer: by assumption, there is a $k$-vertex clique, which comprises $k(k-1)/2$ vertex pairs, each of which are connected by an edge, so choosing the corresponding $k$ instruments satisfies the $k(k-1)/2$ corresponding songs.

In the other direction, suppose that the algorithm for your problem reports that at least $k(k-1)/2$ songs can be played; we need to show that this implies that there is a $k$-clique in $G$.  Given that we permitted at most $k$ instruments to be chosen, there certainly cannot be more than $k(k-1)/2$ songs that we can play, since every song requires a distinct pair of instruments: so we can infer that exactly $k(k-1)/2$ songs can be played.  But every choice of at most $k$ instruments that does not correspond to a $k$-clique in $G$ omits at least one of these $k(k-1)/2$ edges, and thus allows strictly fewer than this maximum possible number of songs to be played; thus the only subgraphs on at most $k$ vertices that can result in at least $k(k-1)/2$ edges are subgraphs that are $k$-cliques.


Is the set of language decidable by some Turing machine computing in some given computable time bound decidable

This is a situation where coding is non-trivial. $\mathcal{C}_T$ is a class of decidable languages. To make sense of $\mathcal{C}_T$ having any effective properties, we need to choose a coding. Naturally, we would code some decidable language $L$ by the index of some TM that decides it.

So what does it mean for $\mathcal{C}_T$ to be recursively enumerable? It means that we can effectively produce a list $(M_i)$ of TMs such that $\{L(M_i) \mid i \in \mathbb{N}\} = \mathcal{C}_T$. Note that this does not give us that $\mathcal{C}_T$ is semi-decidable -- that would mean that given some TM $M$ deciding a language, we can recognize that codes a language belonging to $\mathcal{C}_T$.

The familiar "semi-decidable = computable enumerable" holds only for spaces with decidable equality -- and the space pf decidable languages does not have decidable equality.

Furthermore, the complement of $\mathcal{C}_T$ is not semi-decidable, either: While we can recognize that a given TM takes too much time, we cannot rule out that there is another TM deciding the same language, but respecting our time-bounds.


How can I explain lossless compression to a misguided audio engineer?

Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to write out the wrong thing?


How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?

There are two prominent uses of the term "average" in algorithm analysis.

Average-case as a special case of expected costs

Here, "average case" just means "expected case w.r.t. uniform distribution". Since we usually analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most cases).

Example: the average-case running-time cost of sorting algorithms
is often analyzed w.r.t uniformly-random permutations.
Average cost in the classic sense.

When analyzing data structures, we can look at average costs across
the contained elements for a fixed instance -- no probability
distribution here (well, you could...).
That is, we may still have/want to consider a worst-, average- or
best-case instance.

Example: Consider BSTs. The average search cost of a given tree is
the total cost for searching all contained elements (one after the other)
divided by the number of contained elements. This is a classic quantity
in AofA called internal path length.

Note: There are situations where average and expected do not usually mean the same thing. For instance, the expected (also: average-case) height of BSTs is in $O(\log n)$ but the average height is in $\Theta(\sqrt{n})$. That is because "expected" is implicitly (by tradition) meant w.r.t. uniformly-random permutations of insertion operations whereas "average" means the average over all BSTs of a given size. The two distributions are not the same, and apparently significantly so!

Recommendation: Whenever you use "expected" or "average-case", be very clear about which quantities are random w.r.t. which distribution.

The specific sentence you quote is indeed not clear if read in isolation -- if you ignore that CLRS specify exactly what "simple uniform hashing" means on the very same page.

There are two potentially random variables here: 1) the content of the hashtable itself, and 2) the key searched for. Simple uniform hashing is a simple way of specifying both.

We abstract from sequences of insertions¹ and just assume that every one of the $n$ elements we inserted independently hashed to each of the $m$ addresses with probability $1/m$.
We assume that the searched key hashes to each address with probabilty $1/m$.

That's how the proof works: our search hits each list with probability $1/m$ (cf 2), and they all have the same expected length of $n/m$ (via 1). Hence, the expected cost (under this specific model) for searching for $x$ not in the table is proportional to

$\qquad\displaystyle\begin{align*}
  T_u(x,n,m) &= 1 + \sum_{i=1}^m \operatorname{Pr}[h(x) = i] \cdot \mathbb{E}[\operatorname{length}(T[i])] \\
              &\overset{1,2}{=} 1 +\sum_{i=1}^m \frac{1}{m} \cdot \frac{n}{m} \\
              &= 1 + \frac{n}{m}.
\end{align*}$

The "$+1$" is there to account for computing $h(x)$ and accessing $T[h(x)]$, the sum represents the cost for searching along the list.

That is fair since the sequence of insertions does not have as much impact on the resulting structure as for, say, BSTs. The hash function shakes everything up. We don't want to talk about the precise interaction of sequence and hash function, so we just assume that the result of both is independently uniform -- that's something we can work with. It may not represent reality, of course!


This is an instance of logic synthesis.  A standard approach is to use Karnaugh maps or the Quine-McCluskey algorithm.  Finding the minimal circuit is hard (see circuit minimization), but there are tools and techniques that often work reasonably well in practice.  For instance, you can use the Espresso tool to help with this; there are other tools for this task as well.

See also Creating a logical circuit and Working out the connectives (And, Or, Not) in a Truth Table that has the outputs.


PSPACE-completeness of DFA intersection problem

Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $n_1 \cdots n_k$ is not bounded by a polynomial in the input length $n_1 + \dots + n_k$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is that, while an accepting path can indeed be as long as $n_1 \dots n_k$, the machine only guesses one symbol at a time and never stores the entire input string in memory, so we stay within the polynomial space limit.

It is a well-known fact that this problem is PSPACE-hard, but the only proof that I am aware of is not particularly trivial. I believe the first proof was given in:

  Dexter Kozen. Lower Bounds for Natural Proof Systems. FOCS 1977: 254-266.

The proof involves constructing a mess of DFAs which collectively enforce all the necessary constraints to require that any string in the intersection language is a trace of the execution of a polynomial space Turing machine that leads to an accepting configuration.


'Half-Close' figure of Data Communications and Networking, 5/e

The FIN segment consumes 1 sequence number as it does not carry data. ACK does not consume a sequence number. The FIN segment is sent by the client process. The server process receives a FIN segment but does not send a FIN segment as the connection is not closed, since it is a half-close process. Server process send only an ACK segment to acknowledge receipt of FIN segment from the client. Hence, the sequence number decreases by 1 and becomes $y-1$.
Contrast this with the Three way handshaking, where the sequence number is $y$ because in that process, the server sends a ACK segment as it acknowledges receipt of FIN segment from the client and sends a FIN segment as it terminates the connection.


Is it or is it not correct to say that the expected runtime of an algorithm is its runtime on the expected problem size? Why?

In general, it does not hold that $\DeclareMathOperator{\EE}{\mathbb{E}}\EE[f(X)] = f(\EE[X])$. For example, suppose that $X=0$ with probability $1/2$ and $X=1$ with probability $1/2$, and that $f(x) = x^2$. Then $\EE[f(X)] = 1/2$ whereas $f(\EE[X]) = 1/4$.


Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

Take $i - 1$ and $j = 2$. The algorithm is trying to find the shortest path between $1$ and $2$, by considering intermediate vertices. But at this point, most of the array dist is infinity, so we don't even find that $2$ is reachable from $1$ unless the distance is $1$ or $2$.


What's the theoretical difference between class and type?

I am sure that the mentioned standard is using the terms "class" and "type" according to their basic English meaning, without referring to the scientific terms from mathematics and computer science.

In a standard you might have a parameter which identifies the general "form" of a packet, a message, a subprotocol, or even an algorithm. To name the possible "variants" allowed by the standard, one might refer to those as "classes", "forms", "kinds", "types", "groups", or similar English terms.

These terms are not used according to any scientific meaning, but become technical terms within the standard. E.g. the standard might consistently use "algorithm class" to refer to the value of a certain field of a packet, stating which algorithm was used to encrypt the payload. The standard might have instead used "algorithm type", or "algorithm kind" for the same thing, with no effect on the meaning. Usually the standard chooses a term and uses it consistently to help the reader understand it's referring to that field: using "algorithm" alone wouldn't be as effective.

It's only a coincidence that "type" is also used in type theory, and "class" is used in set theory.


Amortized analysis for dynamic array - how to come up with a potential function?

One method is guess-and-check.  We might guess that the potential function has the form $\Phi = \alpha n + \beta m$ for some constants $\alpha,\beta$, then try to work out a proof, and see what properties $\alpha,\beta$ need to have, and look for (solve for) a value of $\alpha,\beta$ that makes the proof work out.

Another way is to use intuition.  Intuitively, the idea is that some operations are slow; and other operations might be fast to complete but are going to make our life harder down the road (i.e., are going to make other operations take longer).  We can then look for a potential function that charges extra for operations that are fast right now but will make life harder down the road, and then use the accumulated charges to pay for the slow operations.  Intuition might help us identify which operations should increase the potential and which should decrease the potential, and then we can go from there to try to work out the specifics.


Geometric rectangle is not a standard term. That's why they define it in the question.

In communication complexity, Alice has an input from the set $X$, and Bob has an input from the set $Y$. Usually we assume that the sets $X,Y$ are unstructured. A combinatorial rectangle is a subset of $X \times Y$ of the form $A \times B$, where $A \subseteq X$ and $B \subseteq Y$.

In this question, the sets $X,Y$ are ordered, and the authors defined a geometric rectangle to be a subset of $X \times Y$ of the form $A \times B$ where $A$ is a subinterval of $X$ and $B$ is a subinterval of $Y$. That is, $A = \{ x \in X : x_1 \leq x \leq x_2 \}$ for some $x_1,x_2 \in X$, and $B = \{ y \in Y : y_1 \leq y \leq y_2 \}$ for some $y_1,y_2 \in Y$.


When states that are not accepting states become accepting states in NFA, what happens?

It depends on whether the NFA contains a path for every possible word.

If there is an input word where there is no path through the NFA at all labelled with that word, then yes, this can happen.  See Hendrik Jan's answer.

On the other hand, it is often assumed that the automaton is complete: that for every possible input word, there is at least one path in the automaton labelled with that word.  (For instance, this can be arranged by ensuring that for every state $q$ and every possible input letter $x \in \Sigma$, there is a transition out of $q$ labelled with $x$.)  If you assume the automaton is complete, the answer is: No.

In particular, if the automaton is complete, the answer is: No, the magic of nondeterminism is that if there's any valid computation path that will end in an accept state, the string is accepted. In this case, all possible computation paths in the original NFA led to rejection (had there been any valid path the string would be accepted, so they must all reject), so in the inverted NFA, they all lead to acceptance.


The VC dimension is a complexity measure for a family of boolean functions over some domain $\mathcal{X}$. Families who allow "richer" behavior have a higher VC dimension. Since $\mathcal{X}$ can be arbitrary, there isn't a general geometric interpretation.

However, if you think of $\mathcal{X}$ as $\mathbb{R}^d$, then you can think of binary functions as manifolds, whose boundary is what's separating positive and negative labels. Families with more "complex" boundaries have a high VC dimension, whereas simple manifolds do not, e.g. the dimension of linear separators is $O(d)$, while convex polygons (with unbounded number of edges) have infinite VC dimension. The more complex you allow the boundary to be, the more likely it is that you can find a large set for which you can agree with any labeling, by avoiding the negative labels in a "snake like" shape.


Determine aproximation factor in a greedy algorithm

So if you are not updating the #satisfied/cost ratio after every selection, this algorithm won't perform well. Let $n$ be the number of people and $m$ the number of meals. We denote  the cost of meal $i$ by $w_i$. Let's say people $1...n-1$ are all satisfied by meals $1...m-1$ which all have the same cost, but person $n$ will only eat meal $m$. If the cost of meal $m$ is any more than $w_1/(n-1)$, then your algorithm will select every meal.

If we instead modify the algorithm so that after every meal selection we recalculate the ratio excluding people that have already been satisfied, we can prove that the bound is $H_d$, where $d$ is the maximum number of people that a single menu item can satisfy and $H_d$ is the $d$th harmonic number.

Consider instead framing the problem as a weighted set cover problem. Each meal $i$ covers some subset of people $S_i \subseteq \{1,...,n\}$ and has a weight $w_i$. You want to select meals such that all people are covered and the cost of the meals is minimized. The slightly modified version of your algorithm below is an $H_d$ approximation to the weighted set cover problem. The proof is rather involved and can be found in section 5.3 here. Note that $j\gets \arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|}$ in the algorithm is equivalent to selecting the max in your ratio i.e.

$$\arg\min_k\frac{w_k}{|S_k\bigcap Uncovered|} = \arg\max_k\frac{|S_k\bigcap Uncovered|}{w_k}$$
The algorithm is below:


that there would be no perfect strategy for poker

Nash proved that every zero-sum game has a perfect strategy called a Nash equilibrium. This is a possibly randomized strategy for both players such that given that one player follows the strategy, it doesn't pay the other player to deviate from her strategy. As an example, consider the game rock, paper, scissors. One Nash equilibrium here has both players choosing their signal randomly. If one player does that, there is no point for the other player to follow any other strategy (though it doesn't hurt).

Since Poker is a symmetric zero-sum game (both players are treated the same by the game), the value of the game is zero, and any Nash equilibrium on average results in zero expected profit for both players. According to Wikipedia, Cepheus is an approximation to such a strategy. As such, Cepehus' strategy may be randomized.

What about bluffing? Let's consider a variant of rock, paper, scissors in which players can bluff. Say each player writes their choice on a piece of paper, and then there is some structured dialog in which players announce their choice and offer the other player to capitulate. The random strategy is still perfect, in that if one player follows it, it doesn't pay for the other player to deviate from it.

While Cepehus (if it were perfect) shouldn't lose on the long run, it is not guaranteed to be a good strategy in practice, since it only promises you a small negative expected profit. Perhaps when playing against good human players it will just break even on average. That doesn't mean that humans are any better than it, just that they're not any worse. Another possibility is that while in theory the only guarantee is that it breaks even, in practice it wins against sub-optimal humans. This is an empirical question that the developers are testing right now through their website.


First, be more precise in your writing. What does $\max$ range over? What is $k$ in the inductive hypothesis and step? What is the actual statement in the induction hypothesis?

In the step, you want to establish that $r_n = \dots$ is optimal assuming all $r_k$ as computed by the proposed formula for $k \leq n$ are optimal, for some fixed $n \geq 3$.

One way you typically do this is by contradiction. Assume (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r_k$ is not optimal either, then, which is in contradiction with the IH.


You're asking multiple questions.

Why are instruction set architectures designed to use a one-dimensional address space for memory?  Memory isn't actually one-dimensional, but providing a one-dimensional abstraction is very convenient.  It makes programmer's lives simpler, it makes the CPU architecture easier to specify in a comprehensible way, and it provides a single flexible abstraction that isn't tied to a particular technology of the moment or a particular device or platform.

It's not the CPU's abstraction for memory that forces you to choose between row-major vs column-major storage, and cause the opposite way of accessing a matrix to be slower; it's the way DRAM works that forces this decision.

Why don't RAM chips provide both a row-burst and column-burst? Our current DRAM technology is highly optimized for cost, density, and power.  Supporting additional features like that would be more expensive and more complex.  It's likely that the potential performance gains you're hoping for are not worth the additional expense, and would be modest for most
applications, hence not worth it.


Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position.

For example in the input array: $$[(3, 1), (2, 3), (2, 5), (1, 6), (3, 3)]$$ you would build the map:

{
    1 : {(4, 6)} // (value 6 at position 4)
    2 : {(2, 3), (3, 5)}
    3 : {(1, 1), (5, 3)}
}

Notice that with this data structure you can solve queries in vector by finding the sum in suffix. First find the corresponding vector in $O(log N)$ (possible in $O(1)$ if used unordered_map instead of map) and use lower_bound (also in $O(log N)$) to determine the target suffix. You should keep cumulative sums of the vector to calculate the sum on a suffix in $O(1)$.

To handle updates of the form add an element of the form (key, value) to the end of the original array you should only extend the vector corresponding with key in the map. You know the new position in the original array, which is greater than all previous position since it is at the end, so add the pair (new_size, value) to the end of the array associated with given key.

Notice that we must keep cumulative sum up to date, but cumulative sum up to the first $n$ values is equal to the cumulative sum up to the first $n-1$ values plus the last value. The new cumulative sum can be computed in $O(1)$.

Notice that in practice we don't need to have on each vector in the map a pair of (position, value), but instead (position, cumulative_sum).


Is there a connection between the halting problem and thermodynamic entropy?

I am not at all an expert in this area, but I believe you will be interested in reversible computing.  This involves, among other things, the study of the relationship between processes that are physically reversible and processes that are logically reversible.  I think it would be fair to say that the "founders" of the field were/are Ralph Landauer and Charles H Bennett (both of IBM research, I think.)

It touches on quantum computing and quantum information theory, but also examines questions like "what are the limits of computation in terms of time, space and energy?"  It is known, (if I remember correctly) that you can make the energy required to perform a reversible calculation arbitrarily small by making it take an arbitrarily long time.  That is, energy $\times$ time (=action) required to perform a reversible computation can be made a constant.  This is not the case for non-reversible computations.

Many of the people studying in this area are also working on quantum computing and digitial physics (the idea that the universe is a big quantum cellular automata).  The researchers names that come to mind are Ed Fredkin, Tommaso Toffoli and Norm Margolus.

These questions are absolutely on topic for computer science.  Not just for the theory (which includes cool math as well as cool physics) but for engineers who want to know the ultimate limits of computation.  Is there a minimum volume or energy required to store a bit of information?  The action required to perform a reversible computation may be constant, but are there limits on what that constant is?  These are critical knowledge for engineers trying to push the boundaries of what is possible.


Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?

It actually depends on the way you implement a k-tape Turing Machine as a single-tape one.

Using the standard implementation, you can prove that the single-tape machine will take quadratically more computation time.


Algorithm and Formalism for Most Remote Vertices

One way to formulate your problem is well known as finding the diameter of a graph as the following description in Wikipedia.

The diameter $d$ d of a graph is the maximum eccentricity of any vertex in the graph. That is, $d$ is the greatest distance between any pair of vertices or, alternatively, $d=\max_{v\in V}\epsilon (v)$. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.
A peripheral vertex in a graph of diameter $d$ is one that is distance $d$ from some other vertex—that is, a vertex that achieves the diameter. Formally, $v$ is peripheral if $\epsilon (v)=d$.

Similarly to the way we talk about the diameter of a circle, the term "diameter of a graph" is overloaded. It can also mean, although less frequently, any shortest path between any two vertices whose length is equal to the maximum eccentricity.
If the graph is a tree, there is an algorithm that finds its diameter using only two BFS scans. Choose an arbitrary vertex $v$. Do a breadth first search from $v$ that  finds a vertex that is farthest away from $v$. Call the vertex $u$. Do another BFS from $u$ that finds a vertex that is farthest away from $u$. Call the vertex $u'$. The distance between $u$ and $u'$ is the diameter of the graph.
In a general graph, many algorithms can be used to to find the diameter of a graph. Please check this CS StackExchange question and answer, where most algorithms are in fact designed to solve the all-pairs-shortest-path problem.
In the example graph given in the question, the distance between $N$ and $M$, 9, is the diameter. In fact, $N$ and $M$ are the only two peripheral vertices in that graph. (OP calls peripheral vertices as most remote). However, $H$ is not a peripheral vertex, since the furthest distance from any vertex to $H$ is only 8. ($H$ is not a pseudo-peripheral vertex, either.)
We could define an extremum of a graph as a vertex whose eccentricity is not smaller than the eccentricity of any of its neighbors. We could also define a strong extremum of a graph as a vertex whose distance to any vertex $v$ is not smaller than the distance from any of its neighbors to $v$. Every peripheral vertices is an extremum and every strong extremum is an extremum. We can recall a leaf vertex of a graph means a vertex of degree 1. Every leaf is a strong extremum. Note that $H$ is a leaf. All those algorithms that compute all-pairs-shortest-paths can be adapted easily to find all (strong) extremum vertices as well. A simple degree-counting algorithm will find all leaves of a graph. (Please note this definition of "extremum" might not be standard at all. As far as I have tried, I have not found a single article that defines that concept. Well, I can only check probably a negligible number of articles among a myriad of them. There is probably some existing term for it in papers about social network.)


Inductive sequence of words in a biprefix code

Your paper has a typo. It should be $u_0 = v_{j-i}$ rather than $u_0 = v_{j-1}$.
Indeed, consider the following example: the alphabet is $A = \{0,1\}$, and the two codes are $X_1 = A^1$ and $X_2 = A^2$. Take $u = 01$ and $v = 10$. Then $u_0 = 01$, $v_0 = 10$, and $v_1 = 01$. If $i = 0$ and $j = 1$ then $u_i = v_j$, yet $u_0 \neq v_{j-1}$; but $u_0 = v_{j-i}$.
You already know that $u_i = v_j$ implies $u_{i-1} = v_{j-1}$. Applying this step $i$ times, you immediately conclude that $u_0 = v_{j-i}$.


what is difference between multilayer perceptron and multilayer neural network?

A perceptron is always feedforward, that is, all the arrows are going in the
direction of the output.  Neural networks in general might have loops, and if
so, are often called recurrent networks.  A recurrent network is much harder
to train than a feedforward network.

In addition, it is assumed that in a perceptron, all the arrows are going from
layer $i$ to layer $i+1$, and it is also usual (to start with having) that all
the arcs from layer $i$ to $i+1$ are present.

Finally, having multiple layers means more than two layers, that is, you have
hidden layers.  A perceptron is a network with two layers, one input and one
output.  A multilayered network means that you have at least one hidden layer
(we call all the layers between the input and output layers hidden).


What is the index of the leftest child of node in a k-nery heap?

Let's assume you store the nodes by level and then from left to right. Here are the first few levels:

Root: $1$
Children of root: $2,\ldots,k+1$
Grandchildren of root: Children of $2$: $k+2,\ldots,2k+1$; Children of $3$: $2k+2,\ldots,3k+1$, ...

Let us guess that just like in the binary case, the formula for the leftmost child of $v$ is of the form $\alpha v + \beta$.

If we consider two adjacent nodes at the same level, their leftmost children will differ by $k$ (for example, leftmost child of $2$ is $k+2$, whereas leftmost child of $3$ is $2k+2$), hence $\alpha = k$.

We can find $\beta$ by considering the root: $k \cdot 1 + \beta = 2$ implies that $\beta = -(k-2)$. Overall, we get
$$
kv-(k-2) = k(v-1) + 2.
$$
This works for the root by construction. When $v = 2$, we get $k (2-1) + 2 = k+2$, which also works out. My guess it that this formula works out, and you should be able to prove it by induction. That's where you come in...


in refutation (resolution) can we use a clause that have been resolved

suppose we've resolved C1 and C2 to C5, can we resolve C1 with C5 or C2?

No, not really. If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies. And if C1 can be resolved with C5, then it can also be resolved with C2 in a second way (assuming C1 is not a tautology, and hence cannot be resolved with itself).

  can we resolve C1 with C3 or C4 cause even it has been resolved?

We can (and often must) resolve C1 with C3, even so it has already been resolved with C2. We don't need to resolve any clause with C4 itself, rather the negation of C4 must be brought into a conjunctive normal form. The clauses of that normal for have to be added to our set S.

  and if we want to conceive an algorithm for that do we have to delete each resolved couple of clauses from our initial set I= {S, ¬C4} and add the resolvent instead?

No, that would be too simple. What you actually do is to select a variable that you want to eliminate from the clauses in the set S, and then:

for every clause C containing the variable and every clause N containing the negation of the variable

resolve C and N and add the resolvent to the set S

remove all original clauses containing the variable or its negation from the set S

Of course, you could also eliminate a variable by considering both possible assignments separately. It is said that those two approaches are equivalent in a certain sense, yet the approach to consider the assignments separately allows for backtracking, which keeps the memory consumption low by removing the need for explicit representation of the resolvents.

  and lastly, do we have to use all the clause to derive ⊥ or we stop once we find ⊥ even if we find it in the first step?

We stop once we find ⊥.

  thank you for claryfing things.

The question is tagged first-order-logic, but none of your questions even touched unification. Your questions also indicate that the resolution rule somehow seems to feel like magic to you. But the resolution rule itself is basically just the cut rule, which is an inference rule of sequent calculus:
$\cfrac{\Gamma \vdash \Delta, A \qquad A, \Gamma' \vdash \Delta'} {\Gamma, \Gamma' \vdash \Delta, \Delta'}$

The cut rule itself is just the appropriate formulation of transitivity of implication
$\cfrac{A \vdash B \qquad B \vdash C} {A \vdash C}$
in the context of sequent calculus (where you can have both a left ($\Gamma$) and a right ($\Delta$) context). A sequent $A_1,\dots,A_r \vdash B_1,\dots,B_s$ can be read as $(A_1\land\dots\land A_r) \to (B_1\lor\dots\lor B_s)$, which is equivalent to the clause $\lnot A_1\lor\dots\lor \lnot A_r \lor B_1\lor\dots\lor B_s$.

Whether this is helpful or not is of course a matter of taste. By getting rid of negation, one can write down deductions more symmetrically (and the sequent calculus has established conventions avoiding all those dots when writing things down). You could verify the assertion that "If C1 and C2 can be resolved in more than one way, then all those resolvents are tautologies." for example by checking that the deductions
$\cfrac{\Gamma \vdash B, \Delta, A \qquad A, \Gamma', B \vdash \Delta'} {\Gamma, \Gamma', B \vdash B, \Delta, \Delta'}$
and
$\cfrac{\Gamma, B \vdash \Delta, A \qquad A, \Gamma' \vdash B, \Delta'} {\Gamma, B, \Gamma' \vdash \Delta, B, \Delta'}$
cover all relevant cases.


Think of a message (ending in) FLAG. You need to escape it, of course, so your message looks like: FLAG (rest) ESC escaped-FLAG FLAG

Now think of a message (ending in) ESC. If you do not escape it, your message looks like this: FLAG (rest) ESC FLAG

Now, “ESC FLAG” and “ESC escaped-FLAG” are undistinguishable. So, that last ESC needs to be escaped.

Now you can go backwards, again and again, until you find that, if one ESC has to be escaped, they all need to be escaped, from the first one.


Implementation-level description of a Turing Machine

One approach is using Fibonacci words (each word is the concatenation of the preceding two words):
$$
\begin{align*}
&0 \\
&01 \\
&010 \\
&01001 \\
&01001010
\end{align*}
$$
You can generate them according to the following scheme:
$$
\begin{align*}
&\color{blue}0\color{red}1 \to \color{blue}0\color{red}1\color{green}0 \to
\color{blue}{01}\color{green}0 \to \\
&\color{blue}{01}\color{red}0 \to \color{blue}{01}\color{red}0\color{green}{01} \to \color{blue}{010}\color{green}{01} \to \\
&\color{blue}{010}\color{red}{01} \to \color{blue}{010}\color{red}{01}\color{green}{010} \to \color{blue}{01001}\color{green}{010} \to \\
&\color{blue}{01001}\color{red}{010} \to \cdots
\end{align*}
$$
I hope the algorithm is clear. The basic operations are copying of words and changing colors.

Why is this helpful? The lengths of the Fibonacci words are exactly the Fibonacci numbers. If you can compare lengths of words, then by generating the sequence of Fibonacci words, at some point you will either reach or exceed the input, and using that information will be able to decide your language.

While I explained how to generate the Fibonacci words, you can actually just generate the words $a^{F_n}$ directly, which is slightly easier. You can even do that on top of your input for a really slick approach.


Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

This problem (usually called QUAD) is in fact complete for the existential theory of the reals, and thus showing NP-membership would be a fantastic and unexpected result. It seems that Arora and Barak intended only to ask for a proof of NP-hardness.


Good way to describe co-RE (co-recursively enumerable)?

The class ${\sf coRE}$ contains all languages whose complement is in ${\sf RE}$. Put differently:

A language $L$ is in ${\sf RE}$ if there exists a Turing machine that can check if a requested word $w$ is contained in $L$  for every word $w\in L$. The machine always tells the truth but it may cycle on inputs $w\not\in L$.
A language $L$ is in ${\sf coRE}$ if there exists a Turing machine that can check if a requested word $w$ is not contained in $L$  for every word  $w\not\in L$. The machine always tells the truth but it may cycle on inputs $w\in L$.

An example:
The language $\{ \langle M,w \rangle \mid \text{$M$ cycles on input $w$}\}$ is in ${\sf coRE}$. Just take a Turing machine that simulates $M$ on $w$ and rejects, whenever the simulation stops.


BIT: range updates, point queries; true meaning of tree[x]

For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/

The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following operations:

$A[k] \leftarrow A[k] + d$ (Point update(k,d))
query partial sum $S[k] = A[1] + A[2] + \dotsb + A[k]$ (Range query(k))

Other variants are just converting to 1 or more of this case.

For range update - point query, it requires support following operations for array $A[1 \dotsc n]$:

$A[i] \leftarrow A[i] + d$ for all $a\le i < b$. (Range update(a,b,d))
query value of $A[k]$. (Point query(k))

First, noting that after range update $A_1[i] \leftarrow A[i] + d, (a \le i \le b)$, we have $$\begin{align}A_1[a]-A_1[a-1]=&A[a]-A[a-1]+d\\A_1[b+1]-A_1[b]=&A[b+1]-A[b]-d\\A_1[i]-A_1[i-1]=&A[i]-A[i-1]\ (i\notin\{a,b+1\})\end{align}$$
Taking $$D[i] = \begin{cases}A[i],&i=1\\A[i]-A[i-1],&1<i\le n\end{cases}$$ then there are only 2 updates $$D[a]\leftarrow D[a]+d\\D[b+1]\leftarrow D[b+1]-d$$ and $$\begin{align}A[k]=&A[1]+(A[2]-A[1])+\dotsb+(A[k]-A[k-1])\\=&D[1]+D[2]+\dotsb+D[k]\end{align}$$

Thus building BIT on $D[1\dotsc n]$, we convert the range update$(a,b,d)$ on $A$ to 2 point updates $(a,d)$ and $(b+1,-d)$ on $D$, and the point query $(k)$ on $A$ is just the range query $(k)$ on $D$.