Number of words within Hamming distance $\delta$

That's an inaccuracy. If $\delta < 1/2$ is constant then it is the case that $\sum_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on $\delta$. (When $\delta$ is close to $1/2$ this doesn't hold: for example, $\sum_{k=0}^{m/2} \binom{m}{k} = 2^{m-1}$ for even $m$, while $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right)$.)

At any rate, what they are interested in really is the estimate $\sum_{k=0}^{\delta m} \binom{m}{k} \leq (1-\epsilon) 2^{H(\delta)m}$, which holds for every $\epsilon > 0$ and large enough $m$ (depending on $\epsilon,\delta$).


What do you mean by "practice sorting"? Sets of data to sort by hand? Just whip something up with a random number generator. Examples showing how the methods work? At least Wikipedia has detailed algorithms with pretty animations, or search for "algorithm animation", it is quite popular.


VC dimension of the class of polynomial classifiers of degree $n$

The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$.

On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is a polynomial of degree $n$ which interpolates them, given by the Lagrange interpolation formula. Using $y_i = \pm 1$, you can easily show that any set of $n+1$ points is shattered. Therefore the VC dimension is exactly $n+1$.


I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (consider a formula where half the variables appear only in clauses where every literal is positive and the rest appear only in clauses where every literal is negative, and half the clauses are all-positive, half all-negative).


Just an extended comment on the second part of the question (if I understood it correctly).

The problem is a special case of the general version; so if you allow $0$ "fixed" points (a fixed point is a point that must be in  a particular position in the Hamiltonian paths), then there is an immediate reduction from the problem of counting Hamiltonian paths.

If your problem says that at least $k$ points must be fixed, then this reduction should work: given a graph $G$ and two vertices $s$ and $t$, and $e_1,e_2,...,e_m$ are the edges from $s$; then for each $e_i$ split it in $k+1$ pieces adding $k$ nodes, and solve your problem fixing the first $k$ nodes (and the number returned will be equal to the number of Hamiltonian paths from $s$ to $t$ in $G$ that start with $e_i$).

At the end the total number of Hamiltonian paths in the original $G$ is the sum of the number Hamiltonian paths returned by your algorithm fixing the first $k$ points in the splitted $e_1, e_2, ... e_m$.


Linear programming formulation for the single-source shortest path problem

Any optimal solution to the problem must satisfy
$$
d_v = \min_{u\colon (u,v) \in E} (d_u + \ell_{uv}),
$$
as well as $d_s = 0$, of course. Assuming the graph is connected, you can prove by induction on the length (number of edges) of a shortest path from $s$ to $v$ that $d_v$ is at most the distance from $s$ to $v$, which we denote by $d^*_v$. In particular, the optimal value is at most $\sum_v d^*_v$.

On the other hand, it is not hard to check that $d_v = d^*_v$ (for all $v$) itself is a feasible solution, showing that the optimal value is exactly $\sum_v d^*_v$, and it is achieved only when $d_v = d^*_v$ for all $v$.


How do you implement a language with greater capabilities using subordinate languages?

The key point is that essentially all programming languages are equally powerful, and as powerful as we know how to make any computing system. That is, they can all simulate a Turing machine, up to the limitations of the computer they're used on. (Real computers can run out of memory; Turing machines can't.)

The only differences between programming languages is in how convenient it is to express certain ideas. For example, you can implement objects in C using structs containing function pointers, though it's not very convenient because the compiler doesn't help you much so you have to do a lot of things manually that something like C++ would do automatically for you.


Find all critical edges for minimum spanning tree

Since Kruskal's algorithm sorts the edges according to their lengths, the trick here i to partition the edges into subsets of edges with equal lengths.

For each subset (in increasing order) check which components are being joined using each edge of this set before joining them. If two (separate) components are being joined using more than one edge of this subset then both (all) these edges are non critical (since we can choose any of them and still get a spanning tree).

Now we are visiting each subset (and accordingly each edge) two times, the complexity is still in $O(|E|)$ and we need an additional $\log$ for the DSU join operations.

However, you should be aware of the case where for example three edges $\epsilon_1,\ \epsilon_2,\ \epsilon_3$ of the same lengths joins components $V_1-V_2, V_2-V_3, V_3-V_1$ respectively, which makes non of them critical point since we can use any two of them and leave the third one. A solution of this problem is to add all this edges at first to the Graph, then you will have a non tree graph, with cycles in places where you had many choices, and that makes the critical edges exactly the Bridges (check the link) in this graph.

P.S since bridges can be found in $O(|V| + |E|)$ total runtime is still $O(|E|*\log|E|)$


Why when I unchecked DMA in Windows 7, the CPU usage was still very low?

Your understanding of DMA is OK. But disk accesses are generally slow. So the CPU may spend is time on waiting for the disk to write the bytes on the disk, he is not stressed.
May be you can try to run something like CPU Burner that will stress the CPU and then measure the time to copy with/without DMA enabled.
Note that many things can interfere with your measurements, particularly HD caches.


Making an algorithm that picks a unique random number in fixed set more efficient

If you want to generate a list of $n$ random codes, from a space of at least $2n$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat.  The running time will be $O(n)$.  This is the method you have rejected in the question.
If you want to generate a list of $n$ random codes, from a space of not much more than $n$ random codes, then use a Fisher-Yates shuffle.  Create a list of all random codes (0, 1, 2, 3, ...), then randomly permute it using a Fisher-Yates shuffle, then take the first $n$ codes in the resulting list.  The running time will be $O(n \log n)$.


Here is a simpler example. Consider the set $\mathbb{N}$ of natural numbers:
$$
\mathbb{N} = \{0, 1, 2, \ldots\}.
$$
The set $\mathbb{N}$ is infinite, but each number is finite.

In fact, your situation is very similar, since
$$
\Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n.
$$
Each of the sets $\Sigma^n$ is finite, yet the set $\Sigma^*$ is infinite.

Each word in each $\Sigma^n$ is finite, so each word in $\Sigma^*$ is finite.

Here is a related point.

Words in $\Sigma^n$ have bounded length, but the length of words in $\Sigma^*$ is unbounded. Yet the length of each word itself is finite.

Similarly, each number in $\mathbb{N}$ is finite, yet $\sup \mathbb{N} = \infty$.

Finally, let me say that words of infinite length are quite useful. The set $\Sigma^\omega$, known as the set of $\omega$-words, consists of all "one-way" infinite words. A word in $\Sigma^\omega$ is a mapping $w\colon \omega \to \Sigma$ ($\omega$ is another symbol for $\mathbb{N}$). We think of it as given by symbols $w_n \in \Sigma$ for all $n \in \mathbb{N}$.

Two-way infinite words form $\Sigma^\zeta$, where $\zeta$ is the same as the set $\mathbb{Z}$ of all integers.

More generally, you can consider $\Sigma^\alpha$ for every linear order $\alpha$.


Master theorem: what to do with constant in parenthesis?

Usually the general form of the recurrences solved by the Master theorem is stated as:
$$
T(n) = aT\left(\frac{n}{b}\right) + f(n).
$$
In your recurrence you have $a=2$, $b=\frac{8}{5}$, and $f(n)=1$.


Number of ways of tiling a 3*N board with 2*1 dominoes problem

These two cases are already counted in the recursive calls g(n-1).

A****
A****
BB***
g(n-1)

g(n-1) counts all possibilities to fill the empty space in this ^ form. One way would be to fill it out like the following image, so this case already gets counted and you don't need to add another recursive call.

AC***
AC***
BB***


Function that enumerates a recursively enumerable language

This function maps nonnegative integers to the set of integers of the form $a^pb^p$. Enumerating is trivial, just start $i$ from 0, compute $p_{i+1}$-th prime, compute $a^{p_{i+1}}b^{p_{i+1}}$ and output that number.

As for the index $i+1$, I guess that is because $0 \in N$ and it is assumed that primes are ordered starting from the index 1 not from 0, in other words we start from $p_1$ not from $p_0$, e.g., $f(0) = a^{p_1}b^{p_1}$.


Is P^SAT with only one query equal to the union of NP and coNP?

Under the assumption that $NP\neq \mathrm{co}NP$, we have that:

$$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$

Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$.

Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due to $SAT\notin \mathrm{co}NP$. So, $(SAT\dot{\land}UNSAT)\notin NP\cup \mathrm{co}NP=P^{NP[1]}$.

We conclude that $P^{NP[1]}\neq P^{NP[2]}$.$\blacksquare$

In the above, $(SAT\dot{\land}UNSAT)=\{(\phi_1,\phi_2)\mid\phi_1\in SAT \land \phi_2\in UNSAT\}$.

So, though it might be tempted to push $P^{NP[1]}$ downto $NP\cup \mathrm{co}NP$, this result (if true) could tell us more about where the polynomial-time hierarchy $PH$ would actually collapse to. And, in this case, your proposition would save $PH$ from collapsing to $P^{NP[1]}$.


Is there a discipline studying the prioritizing of repeated tasks?

By far the simplest solution is probabilistic. Let's suppose you have $k$ classes, and their relative importance is $c_1,\ldots,c_k$. Let's also suppose that there are $N_i$ objects in class $i$. You want the frequency of appearances of each symbol in class $i$ to be proportional to $c_i$.

Let $P = \sum_i c_i N_i$ and $p_i = c_i N_i/P$. At each step, choose class $i$ with probability $p_i$, and output a random element from the class. The probability that a specific element from class $i$ appears is $p_i/N_i = c_i/P \propto c_i$.

To increase fairness among class $i$, instead of outputting a random element, you can keep a counter for each class (counting modulo $N_i$), incremented any time the class is chosen, and output the corresponding element from the class.

A similar approach should work for fairness across classes, but here it's not as straightforward so I'll leave it to you.


Exact meaning of metalinguistic variable

Personally, I call them "non-terminals", following Chomsky rather than Backus.

But I'm not going to attempt to argue any sort of universal correctness of that terminology. Definitions in mathematics are purely instrumental, just like variable names in a program (or even metavariable metanomenclature).

You can α-convert a mathematical exposition by consistently replacing a defined phrase with some other phrase not used anywhere in the text, say "colourless green ideas", and every assertion will retain the same truth value. It might be harder to follow, but that's a purely aesthetic consideration.

So here's my aesthetic argument for calling these things "non-terminals" rather than "metalinguistic variables" or "syntactic categories": the term "non-terminal" does not in any way imply that the objects have any useful semantics. A generative grammar does not rely on any particular semantic connotation for the intermediate symbols used in the derivation, and indeeds quite common to write grammars with rather artificial non-terminals which do not serve any need other than that of facilitating a particular parsing algorithm.

I suppose "metalinguistic variable" might also be neutral in that sense, but it seems a bit much to describe a placeholder and "non-terminal" rolls more easily off the tongue.


Why is data fragmentation not possible on main memory (RAM)?

According to https://lwn.net/Articles/211505/, what you imagine should be done by the OS, is already done:

  Since Linux is a virtual memory system, fragmentation normally is not a problem; physically scattered memory can be made virtually contiguous by way of the page tables.

There are limits to this, as hardware devices may request contiguous hardware memory, and this creates memory holes (at least for hardware devices).

Another limitation is that doing all memory allocations and deallocations through page tables is inefficient. Setting up new page table entries takes longer than managing allocations through software and, if the page size is 4K, only works for allocations that are a multiple of 4K. Therefore the malloc and free glibc calls first allocate 4K blocks through mmap (using page tables) and manage this memory. They divide it into smaller contiguous memory areas and return them when a malloc call requests a small chunk of memory. Algorithms to reduce memory fragmentation of software-managed memory are for example the Buddy memory allocator.


Given a regular language, calculate its equivalence classes

Whether a word and its extensions belongs to $L_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different length-$n$ suffixes, then they definitely belong to different equivalence classes.

In contrast, we can check that any two words with the same length-$n$ suffix are equivalent. Indeed, suppose $x,y$ are such words, and consider a word $z$. If $|z| \leq n-1$ then $xz \in L_n$ if the $n-i$'th letter from the end of $x$ is $1$. Since $x,y$ have the same length $n$ suffixes, the condition for $yz \in L_n$ is identical. If $|z| \geq n$, then whether $xz \in L_n$ or not only depends on $z$, and in particular holds just as well for $yz \in L_n$.

Finally, what about words which are shorter than $n$ letters? Recall the test we had above: $w1^{n-i} \in L_n$ iff the $i$th letter from the end is $1$. If $|w| < i$ then $w1^{n-i} \notin L_n$, and so $w$ behaves as if the $i$th letter from the end is $0$. Pursuing this route, we find that the equivalence class of $w$ depends on the length-$n$ suffix of $0^nw$, and this definition works whether $|w| \geq n$ or not.


What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)?

One possibility is to use the standard greedy algorithm.  It can be adapted to weighted set cover by counting the total weight of previously uncovered elements that will be covered by adding a particular set, instead of counting the number of such elements.  This is standard and covered in standard textbooks and resources.  Another option is to use linear programming or integer linear programming.  A little research on set cover approximation algorithms will find much more that is written on the subject.  In the future, I suggest doing more research before asking here.


Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

Hint: The PDA has three phases: an $a$ phase, a $b$ phase and a $c$ phase. Your goal in the $a$ phase is to "compute" $i$ by strong an appropriate load on the stack. Your goal in the $b$ phase is to compute $j-i$. Finally, your goal in the $c$ phase is to compare $j-i$ to $2k$.


Method to construct a finite state machine for a finite-size language L

Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ otherwise. When at $q_\bot$, always stay there.

To show that this works, prove inductively that when reading a word $w$, if $w \in S$ then the DFA is at state $q_w$, and otherwise it's at state $q_\bot$.


When you put a new process in the ready queue, you are just adding the process, not changing anything to running as a result. With a non-preemptive scheduler this is also the case for waiting to ready. But, when you have a preemptive scheduler, tasks that come from waiting to ready get a higher priority than newly running tasks, so that "scheduler decision-making" is determining the priority of this newly ready task in the queue. It looks like they get a higher priority than new tasks because they've already been delayed enough waiting for IO.


Non-deterministic algorithm for solving figure of 8

If you want to prove that this problem is in NP, then all you have to do is to come up with a polytime algorithm that verifies the correctness of a solution.  I.e., in polynomial time, verify that a given sequence satisfies the conditions you wrote.

This should also help you in actually construct the non-deterministic algorithm.


what does it mean to extend an assignment?

It means that you have a partial solution, and you extend that partial solution by assigning at least one more variable to some value, thus producing either a new partial solution or a solution where every variable is assigned a value.

Put differently, if $x$ extends an assignment $a$, it holds that $x$ does precisely the same assignments as $a$ and assigns any number of other variables in addition.


There is a more general theorem which says that if $A$ is a decidable language and $B$ is a decidable language that is not trivial (in the sense that $B\ne\Sigma^*$ and $B\ne\emptyset\, $), then $A\le_m B$. Roughly speaking, this says that all non-trivial decidable languages are many-to-one reducible to each other, meaning that $\le_m$ is too coarse a metric to distinguish between decidable languges.

In your problem, suppose that $L\subseteq \Gamma^*$ and define a mapping $f:\Gamma^*\rightarrow\Sigma^*$ defined by:
$$
f(x) =
 \begin{cases}
   \mathtt{aa} & \text{if $x\in L$}\\
   \mathtt{a} & \text{if $x\notin L$}
 \end{cases}
$$
for some $\mathtt{a}\in\Sigma^*$. This is a total computable function (since by definition, we can use the computable decider program to determine $x$'s membership in $L\, $) and it's easy to verify that $x\in L$ iff $f(x)\in A$, which is all you need to show $L\le_m A$. As Yuval noted, you don't need any results about regular or context-free languages to answer this question.


What is a fast algorithm for partitioning an array into $k$ subsets $A_1<\dots<A_n$?

You can do $O(n \log k)$ by finding $mk/2$-order statistic, partitioning the array into two parts of size $mk/2$ and recursing on each side until $k = 1$. You get the recurrence on running time $T(m, k) = 2 T(m,k/2) + \Theta(m k)$ and $T(m, 1) = \Theta(1)$, which solves to $T(m,k) = O(m k \log k) = O(n \log k)$.


Is there a difference between $\lambda xy.xy$ and $\lambda x.\lambda y.xy$?

The first is an abbreviation for the second. It's a common syntactic convention to shorten expressions.

On the other hand, if you have tuples in the language, then there is a difference between

$\lambda x.\lambda y.xy$ and
$\lambda (x,y).xy$.

In the former case I can provide a single argument to the function, and pass the resulting function around to other functions. In the latter case, both arguments must be supplied at once. There is, of course, a function that can be applied to convert 1 into 2 and vice versa. This process is known as (un)currying.

The definition of $\text{pair}$ you mention is an encoding of the notion of pairs into the $\lambda$-calculus, rather than pairs as a primitive data type (as I hinted at above).


Give an efficient dynamic programming algorithm that decides if a string is an interleaving of two other strings

Let's use caps, S for input string, A for x and B for y. Furthermore, let |S| = lenS, |A| = lenA, |B| = lenB.

With any Dynamic Programming problem, it is useful to append to the problem:

  "... demonstrate one such solution." or, equivalently
  "... provide one such proof certificate."

This is because a Dynamic Programming solution is equivalent to searching over proof certificates. For this problem, what's a proof certificate? There are many possibilities. One of them is: Strings over {a, b} of length lenS.

  Certificate aabbaa encodes: S[1] = A[1], S[2] = A[2], S[3] = B[1], S[4] = B[2], S[5] = A[3],... where array indices in A & B wrap around i.e. A[r + lenA] = A[r].

Clearly, S is an interleaving of A & B if and only if such a proof certificate exists. The task now boils down to finding one such certificate, if it exists.

Source code in C++ (Repl: https://repl.it/@vemana/csstackexchange#interleaving/main.cpp)

#include <bits/stdc++.h>

using namespace std;

const int MAX_LENS = 100, MAX_LENA=100, MAX_LENB=100;

// Memoization array
// Initialize: to -1.
int memo[MAX_LENS][MAX_LENA][MAX_LENB];

// Initialize: to 0
// Encodes the Proof Certificate, C
// SELECT[r] = 1 implies C[r] = a
// SELECT[r] = 2 implies C[r] = b
int SELECT[MAX_LENS][MAX_LENA][MAX_LENB];

// The input strings
string S, A, B;

// Initialize: lenS = S.size(), lenA = A.size(), lenB = B.size()
// Expected: lenS > 0, lenA > 0, lenB > 0
int lenS, lenA, lenB;

vector<string> getCertificate() {
  if (SELECT[0][0][0] == 0)
    return vector<string>(); // No solution

  vector<string> ret(2);

  int s = 0, a = 0, b = 0;
  while(s < lenS) {
    if (SELECT[s][a][b] == 1) {
      ret[0] += A[a];
      ret[1] += '_';
      a = (a+1)%lenA;
      s = s + 1;
    } else {
      ret[0] += '_';
      ret[1] += B[b];
      b = (b+1)%lenB;
      s = s + 1;
    }
  }
  return ret;
}

// Finds certificate for S[s...lenS] where
// next index in A is a (0 based)
// next index in B is b (0 based)
//
// Returns 0 if not found
// Returns 1 if found
int findCertificate(int s, int a, int b) {
  if (s == lenS)
    return 1; // Found the "empty" certificate.

  int& ret = memo[s][a][b];
  if (ret != -1)  // already computed
    return ret;

  // Try to match S with A
  bool takeA = (S[s] == A[a]) && findCertificate(s+1, (a+1)%lenA, b) == 1;

  // Try to match S with B
  bool takeB = (S[s] == B[b]) && findCertificate(s+1, a, (b+1)%lenB) == 1;

  if (takeA) {
    SELECT[s][a][b] = 1; // SELECT A to extend the certificate
    return ret = 1;
  }

  if (takeB) {
    SELECT[s][a][b] = 2; // SELECT B to extend the certificate
    return ret = 1;
  }

  return ret = 0; // Neither matched. So, no certificate found
}

// Just run with ./a.out < in
// File 'in' has three strings, one per line, representing A, B & C.
int main() {
  // initialize S, A, B, lenA, lenB, lenS, SELECT, memo

  cin >> A;
  cin >> B;
  cin >> S;
  lenA = A.size();
  lenB = B.size();
  lenS = S.size();
  memset(memo,-1,sizeof(memo));
  memset(SELECT, 0, sizeof(SELECT));

  int out = findCertificate(0, 0, 0);
  vector<string> cert = getCertificate();
  string output = cert.empty() ? "NOT INTERLEAVED" : ("INTERLEAVED\n" + cert[0] + "\n" + cert[1]);
  cout << output << endl;
  return 0;
}


Replacing n with 2n in asymptotic bounds

In mathematics we have the substitution principle. If a certain statement is true, then it also holds if you replace all occurrences of $n$ by some other expression, as long as that other expression has the same type as $n$. In particular, you can substitute $2n$ for $n$ and deduce that $|p-q|_1 \lll 2^{-\Omega(2n)}$. You can then conclude that $|p-q|_1 \lll 2^{-\Omega(n)}$, using the definition of $\Omega$.


For the given Petri Net, the number of tokens for P_1,P_2  and P_3  is represented by m_1,m_2  and m_3  respectively. Based on the definition of boundedness of a Petri Net by Popova-Zeugmann (2013), the given Petri Net is bounded because m_1 ≤ 2,m_2 ≤ 2 and m_3 ≤ 2. In other words, there is a natural number (2 in this case) such that the number of tokens in P_1,P_2  and P_3  never exceeds the number.

I am also providing an example of an unbounded Petri Net and an example of a bounded Petri Net. Regardless of the initial marking, the Petri Net in Figure 1 is not bounded (or it is unbounded) because m_0 → ∞ when T_0  keeps firing.

For the given initial marking, the Petri Net in Figure 2 is bounded because m_0 ≤ 1 and m_1 ≤ 2. In general, the Petri Net in Figure 2 is bounded: let the initial value of m_0 = q_0  and the initial value of m_1 = q_1; m_0 ≤ q_0  and m_1 ≤ 2q_0+q_1

References

Popova-Zeugmann, L. (2013). Chapter 2 The Classic Petri Net [Electronic version]. Time and Petri Nets. Berlin; Heidelerg: Springer-Verlag.


Bounded Quantification: Full F<: intuition

Consider these assertions:

all the cats in my house are grey
all the cats in my town are grey

The second assertion implies the first, since any cat in my house is also in my town, so by the assertion it must be grey. In other words, "cats in my town" is a superset of "cats in my house", so the second assertion is stronger (it applies to more cats).

In the same way, the type S = ∀X<:S1.T2 is stronger than T = ∀X<:T1.T2 since S1 is a supertype of T1. A program of type S must work in all cases (types X) where a program of type T would work, and possibly even more cases.


Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

Let us call your problem as $TD$ (Total Distance problem).
Now, we will show that there is a polynomial-time reduction from the $k$-clique problem to $TD$. Note that, the $k$-clique problem is $NP-hard$ and is defined as follow:

Given an undirected graph $G_{C} = (V_{C},E_{C})$. Does there exist a clique of size $k$ in $G_{C}$?

The reduction from $k$-Clique to $TD$ happens in the following way:
Define a complete weighted undirected graph $G = (V,E)$ such that $V = V_{C}$ and for an edge $(u,v) \in E$, the weight $w(u,v) = \infty$ if $(u,v) \notin E_{C}$, and $w(u,v) = 1$ if $(u,v) \in E_{C}$. Here, the vertex set $V$ represents the set of locations and weight on an edge represents the travelling cost between two locations.
A $k$ size clique can be easily stated by some object sequence $S$. For example, suppose $k = 4$, then the object sequence would be: $S = (1,2,3,4,1,3,4,2)$. Similarly, for $k = 5$, the object sequence would be: $S = (1,2,3,4,5,1,3,5,2,4,1)$. Note that, we have $n$ number of distinct objects but only $k$ of them appears in the sequence. Now, the problem instance of $TD$ consists of the graph $G$ and sequence $S$. This completes the construction.
Now, suppose $A$ is an algorithm of $TD$ that returns a correct mapping of the objects to the locations such that the total traveling cost is minimized.
Now, if the traveling cost of the mapping is $\infty$ then $G$ does not have a $k$ size clique. And, if the mapping gives the finite traveling cost then $G$ does have a $k$ size clique.
The above reduction implies that $TD$ is also $NP-hard$. So, we can not expect a polynomial-time running algorithm for $TD$.

Note that, in the reduction, instead of setting the edge weights of $G$ to be $\infty$, you can also use finite weights but with sufficiently large values such as $|V|^{|V|}$. That would also work.


How can I compute the average weight of an undirected graph?

If $w(i,j)$ is the weight of edge $ij$ then:

$avg = \frac{1}{2|E|}\sum_{i\neq j}w(i,j)$.

Why $2E$ ? Because when traversing vertices you will calculate both edges $ij$ and $ji$. Since it's the same edge, you are adding its weight twice, so you need to remove this redundancy by dividing by 2.


Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$?

Jonathan Katz explains the original construction due to Baker, Gill and Solovay in his lecture notes.

The idea is to construct such a language by diagonalization. The first step is to show the lemma that for any deterministic, polynomial-time oracle machine $M$, you can construct a language $B$ so that $M^B$ (that is, $M$ with oracle access to $B$) does not decide the language $L_B = \{1^n\textrm{ | }B \textrm{ contains a string of length } n\}$. For sufficiently large $n$, $M$ can not query all strings of length $n$ of $B$, so it is possible to "hide" (or not) a string of length $n$ in $B$ so that $M$ gives the wrong answer.

Note that $L_B$ is in $NP$ since for a given $n$ we can guess the string of length $n$ (if any) that is in $B$ and then query the oracle once.

This doesn't give the desired result (it says that for any deterministic, polynomial-time TM there is a language rather than for any language there is a TM). However, we can enumerate all deterministic, polynomial Turing oracle machines $M_1,M_2,M_3,\ldots$. We can (by the lemma) construct a language $B_1$ for which $M_1^{B_1}$ fails to decide $B_1$. Using a construction similar to in the lemma, we can then modify $B_1$ to obtain $B_2$ so that both $M_1^{B_2}$ and $M_2^{B_2}$ fail to decide $B_2$, and so on...

We eventually obtain a language $B_{\infty}$ so that $L_{B_{\infty}}$ is in $NP^{B_{\infty}}$, but not in $P^{B_{\infty}}$


Why is there a 2n+1 comparison for a linear search algorithm?

procedure last_even_loc(a1,a2,...,an:integers)
1.location = 0;
2.for i = 1 to n
3.    if (a_i = 0) (mod 2) then location = i
4.return location;

statement 1 is executing only once.
statemet 2 is executing total n+1 times.
statement 3 is executing total n times.
statement 4 is executing only once.

The running time of the algorithm is the sum of running time of all the statements executed.so running time=1+1+n+(n+1)=O(2n+3)=O(n).so there is total n+1+n=2n+1 comparisons(statement 2 and 3).


Talking about suborders of $\mathbb{Q}$ explicitly makes things a bit harder to think about than is necessary, in my opinion. Really we should be talking about general computable (or rather, c.e.) linear orders - the point is that $\mathbb{Q}$ is "big enough" that we can WLOG construe these as suborders of $\mathbb{Q}$ for concreteness. This does make some definitions snappier, but I think obscures the intuition; instead, I think it's best to think of linear orders being built by progressively "laying down points" (or refraining from doing so of course).
For example, suppose I have a Turing machine $\Psi$ and I want to tell whether $\Psi(0)$ halts. Consider the following process for building a linear order: I start building a descending sequence until I see $\Psi(0)$ halt, at which point I build an ascending sequence starting from the very first point I laid down. For example, if $\Psi(0)$ halts at step $5$, the linear order I build is $$\color{red}{a_4<a_3<a_2<a_1<a_0}\color{green}{<a_5<a_6<a_7<a_8<...,}$$ the red part corresponding to the points added before I saw the computation halt and the green part corresponding to the points added after I saw the computation halt. It should be clear that if $\Psi(0)$ halts then I wind up building something isomorphic to $\mathbb{N}$, whereas if $\Psi(0)$ doesn't halt I build something isomorphic to $\mathbb{N}^*$ (= the "reverse order" of $\mathbb{N}$); thinking along these lines, you should be able to prove that $0'\le_T \{ e: (R_e,<)\cong (\mathbb{N},<)\}$.
Now thinking towards Question $2$, we want to generalize the above idea to higher jumps: e.g. find some "analogue of $\mathbb{N}$" which gets $0''$, and another which reduces $0'''$, and so on ... until we get an idea for one which gets every (finite) iterate of the jump all at once. At this point ordinals become useful for organizing ideas; I recommend thinking about $\omega^2$ in particular, and how we can think about this ordinal as $\omega$-many copies of $\mathbb{N}$ (keeping in mind how a single copy of $\mathbb{N}$ can encode a specific question about the halting problem).

OK, what about Question $1$?
Well, let's think about how hard it is to tell whether a computable linear order $L$ looks like $\mathbb{Z}+\mathbb{Z}$. This amounts to the following:

$L$ is nonempty. This is $\Sigma_1$: "At some stage we lay down a point."

Every point in $L$ has both an immediate successor and an immediate predecessor. This is $\Pi_3$: "For every point $a$ in $L$ there are $b,c\in L$ such that $b<a<c$ and at no stage do we add a point other than $a$ to $(b,c)$."

Note that these two conditions alone ensure that $L$ is a sum of copies of $\mathbb{Z}$. We now need to do the hard bit: ensure that we have exactly two copies of $\mathbb{Z}$ in $L$. This leads to our third and fourth conditions:

There are two points which are infinitely far from each other. This is $\Sigma_3$: "There are $a<b$ such that at every stage there is some later stage at which we add a new point to $(a,b)$."

There are no three points which are each infinitely far from each other. This is $\Pi_3$: "For every $a<b<c$ we either stop adding points to $(a,b)$ at some stage or we stop adding points to $(b,c)$ at some stage."

Once appropriately formalized, this shows that $A$ is $\Pi_3\wedge\Sigma_3$; it's now natural to hope that every $\Pi_3\wedge\Sigma_3$ set $m$-reduces to $A$, and Question $1$ is a step towards this. If we want to reduce an arbitrary $\Sigma_3$ set to $A$ we probably want to focus on the "$\Sigma_3$-part" of the characterization of $A$; in the above, this was the "There are two points infinitely far apart from each other" bit.
Here's a construction which starts us off in the right direction:

Suppose I have a $\Sigma_3$ sentence $\varphi\equiv\exists x\forall y\exists z(\theta(x,y,z))$ with $\theta\in\Delta_0$; I want to "computably build" a linear order which has a pair of points infinitely far from each other iff $\varphi$ is true. To do this, I work in "blocks:"

For each $i\in\mathbb{N}$ I have a block $B_i$. Every point in $B_i$ will be above every point in each $B_j$ with $j<i$ and below every point in $B_k$ with $k>i$, and each $B_i$ starts off with a single point.

I add points to $B_i$ in such a way that $B_i$ is isomorphic to $\mathbb{N}$ iff $\forall y\exists z(\theta(i,y,z))$ and is finite otherwise. For example, add an element to the "end" of $B_i$ each time I see $\{y: \forall y'<y\exists z(\theta(i,y',z))\}$ gain an element.

If $\varphi$ is true then at least one $B_i$ is infinite, and this forces a pair of points to be infinitely far apart (consider a point in $B_i$ and a point in $B_{i+1}$). Conversely, if $\varphi$ is false then each $B_i$ is finite and we wind up building a copy of $\mathbb{N}$.

Now (even ignoring the formalization) there are two issues with this, as far as Question $1$ goes. First, there's the problem that the "blocks" look like $\mathbb{N}$ instead of $\mathbb{Z}$; this is easily fixed, though. More serious is the issue that if $\varphi$ is true we might wind up with too many infinite blocks; fixing this will require some thought (and ultimately some injury).


What would a formal grammar for a binary file format look like?

The Chomsky hierarchy is a hierarchy of grammars described by a given formalism.  The other grammar descriptions that you are giving (attribute grammars, ...) are not part of that formalism so they are outside the Chomsky hierarchy (and if I'm not mistaken are able to recognize some languages of higher level in the hierarchy while being unable to recognize other languages at a lower level).
Context-sensitive grammars are not at the top of the Chomsky hierarchy, unrestricted grammars are.
Context-sensitive grammars can generate what you are asking for, but it's painful to write.  Here is a grammar which generate a s followed by a binary number, followed by as many p as determined by the binary number.

\begin{align}
S & \rightarrow \text{s} \; C \\
\text{s} \; C & \rightarrow A \\
\text{s} \; C & \rightarrow \text{s} \; B \; \text{p} \\
\text{s} \; C & \rightarrow \text{s} \; B \; C \; \text{p} \\
A \; C & \rightarrow A \; D \\
A \; D & \rightarrow B \; D \\
B \; D & \rightarrow B \; \text{p} \\
B \; D & \rightarrow B \; C \; \text{p} \\
B \; C & \rightarrow B \; E \\
B \; E & \rightarrow X \; E \\
X \; E & \rightarrow X \; \text{p} \\
X \; E & \rightarrow X \; C \; \text{p} \\
A \; X & \rightarrow A \; F \\
A \; F & \rightarrow B \; F \\
B \; F & \rightarrow B \; A \\
B \; X & \rightarrow B \; G \\
B \; G & \rightarrow X \; G \\
X \; G & \rightarrow X \; A \\
\text{s} \; X & \rightarrow \text{s} \; B \; A \\
 A & \rightarrow 0 \\
 B & \rightarrow 1 \\
\end{align}

Yes that's a lot of rules (I may have missed some shortcuts, but on the other hand I may have missed some cases where unwanted strings are generated which could be avoided only with a more complex grammar).  Some explanations:

I'm using $A$ and $B$ for temporary place holder for $0$ and $1$ because context sensitive rules do not allow to modify terminals.  The last two rules replace them by the terminals they were acting for.
the first three rules are pretty obvious.
the fourth is starting the count
the next four are transforming a count ending by a $0$ in a count ending by a $1$ and a $\text{p}$
the next four are transforming a count ending by a $1$ in a count ending by a $X$ (meaning a carry to be propagated) and a $\text{p}$
the last seven rules are doing the carry propagation.


what is actually a circular array and representation

Circular array is just a fixed size array. We call it circular just because we define the operations on the array in such a manner that its limited size can be utilized again and again and it apparently appears that we are traversing the array in clockwise or anti-clockwise way.

The best example for understanding the circular array is a Queue. We can implement Queue with the help of a circular array. In a Queue we insert at the end and delete from the front.

Suppose you have an array of size 5. Let say we implement Queue using this array. We will have two pointers - one for the front of Queue and one for the rear of Queue. Initially front and rear both will point at index 1. We may do let's say 3 insertions in the beginning. Rear pointer would point at index 3 and front would point index 1 at this moment (consider 1-based indexing).

Now let say we make 2 deletions and now front is 3 and rear is 3. At this moment we have 2 array positions vacant in the front of array. We can use this space again rather than reallocating an array once rear reaches the end of the array. What we can do to utilize these spaces again, is to introduce the circularity, which when rear or front reaches the end of the array re-indexes the rear to 1th index. Since we have changed the index from last index to the first index, we say that the array is circular (apparently in a clockwise manner).

The idea to re-allocate an array and copy the original array twice is totally wrong. The % operation lets you re-index the pointer once you have reached the end of array (e.g. 6%5 = 1). The approach with the mod operation is the correct approach to implement a circular array.

EDIT

I have added an image which will help you:


Why is reflexivity enough in this HoTT formulation of quotient types?

Your Quot construction is a set-truncated quotient by an arbitrary relation $R$ since you never use the reflexivity assumption in the construction. That is, you don't even need the reflexivity of $R$ to perform the quotient and derive its basic properties.

As the HoTT book explains in Section 6.10, it is perfectly possible to make set-truncated quotients by an arbitrary relation because reflexivity, transitivity and symmetry are taken care of by the paths themselves (because there are identity paths, paths can be reversed, and composed). That is, the quotient $A/R$ is equivalent to the quotient $A/\overline{R}$ where $\overline{R}$ is the equivalence relation generated by $R$.

There is one property that you will not get, namely that (using the notations from your file) $(x : A) \to (y : A) \to \mathsf{point}\;x = \mathsf{point}\;y \to R\;x\;y$. For that you need the fact that $R$ is a proposition and an equivalence relation.


In MIPS-speak, these areas of memory of 28 (26+2; the +2 is because instructions are four bytes in size) bit address space (256MB) are referred to as "superblocks". Pseudo-direct addressing allows you to jump anywhere within the same superblock. It doesn't matter if it's forwards or backwards.

This was never a problem in practice because it's very rare for a single binary (whether it's an executable or a shared library) to have more than 256MB of code. IIRC, the MIPS linker could handle it if it ever occurred by generating a trampoline. Suppose that the compiler generated a jal, for example, where the linker discovered that the target was in a different superblock. Then the linker would generate a couple of instructions to do the full jump, and point the jal to that.


identify abrupt frame changes in a video

Easiest is to capture video with an h.264 encoder, which uses key frames to identify switches. (It’s a bit more complicated, h264 will handle situations where frames come alternatively fro two different source, for example), but extracting that information from a video stream is easier than doing it yourself).

Source code for decoders is available, and a decoder will also give you useful information about movement, and things that become covered or uncovered.


Reducing max flow to bipartite matching?

Strangely enough, no such reduction is known. However, in a recent paper, Madry (FOCS 2013), showed how to reduce maximum flow in unit-capacity graphs to (logarithmically many instances of) maximum $b$-matching in bipartite graphs.

In case you are unfamiliar with the maximum $b$-matching problem, this is a generalization of the matching, defined as follows: the input is a graph (in our case, a bipartite graph), $G=(V,E)$, and a set of integral demands for each vertex, with the demand of vertex $v$ denoted by $b_v$. The goal is to find a largest possible set of edges $S$ such that no vertex $v$ has more than $b_v$ edges in $S$ incident on $v$. It is a simple exercise to generalize the reduction from bipartite matching to maximum flows and show a similar reduction from bipartite $b$-matching to maximum flows. (One of) the surprising result(s) of Madry's paper is that in some sense these problems are equivalent, giving a simple reduction which reduces maximum flow in unit-capacity graphs (generally, graphs where the sum of capacities, $|u|_1$ is linear in the number of edges, $m$) to a $b$-matching problem in a graph with $O(m)$ nodes, vertices and sum of demands.

If you're interested in details, see section 3, up to Theorem 3.1 and section 4 (and proof of correctness in Appendix C) of the ArXiv version of Madry's paper, here. If the terminology is not self-evident, see section 2.5 for a recap concerning the $b$-matching problem, and bear in mind that $u_e$ is the capacity of edge $e$ in the original max flow instance.


Why is it that a lambda function requiring multiple input also requires multiple functions?

One view is that there are no functions of multiple parameters. A function which takes "two parameters" is a function taking a single ordered pair. In mathematics, a function $f : A \to B$ has one domain $A$ and codomain $B$. While it is possible to speak of functions with multiple domains, it is more customary to think of a multi-variate function $g$ as an ordinary function whose domain is a cartesian product, $g : A \times B \to C$.

So, if you would like to have functions taking two parameters in $\lambda$-calculus, you should not be changing how $\lambda$-abstraction works, but you should rather extend the calculus with ordered pairs (and people do that).

But we do not have to extend the calculus with ordered pairs, because every function of two arguments $A \times B \to C$ can be converted to a function of a single argument $A$ returning a function $B \to C$. This may take some getting used to, but it works perfectly. That is, there is a bijection between functions $A \times B \to C$ and functions $A \to (B \to C)$, where the latter expression is read as "functions taking an argument from $A$ and returning a function from $B$ to $C$". This is known as currying.

The expression $\lambda a . \lambda b . a + b$ should be read as a function taking an argument $a$ and returning the function $\lambda b . a + b$. It is thus an example of a multi-variate function that has been curried to take one argument at a time.


First of all, your left DFA is incorrect - it accepts e.g. 011.

Secondly, DFAs can be canonically minimized, so in that sense, you can always find one canonical DFA for a certain language.

But in general, there are infinitely many different DFAs for every language, so you could get different correct answers.


Problem of finding a very independent set of size at least $k$ is NP-Complete

Your notion is what is called distance-2 independent sets, also a particular case of rulling sets (see here Independent set where two vertices need to have distance >= c).

Your problem is NP-complete by an easy reduction to Independent Set (which is NP-complete, https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Maximum_independent_sets_and_maximum_cliques): for every vertex $u,v$ of $G$ such that there exists $w$ with $(u,w) \in E$ and $(v,w) \in E$, add the edge $(u,v)$.

This gives you a new graph $G'$ whose independent sets are the distance-2 independent sets of $G$.


The number of iterations of the loop 3–7 depends on the value of $j$: it is $\mathit{limit} - j$. Therefore the running time of lines 3–7 is $O(\mathit{limit} - j)$. Lines 8–10 run in $O(1)$ time, so the body of the loop 1–11 runs in time $O(\mathit{limit}-j) + O(1) = O(\mathit{limit}-j)$ (using $j < \mathit{limit}$). Finally, the total running time is
$$
O\left(\sum_{j=0}^{\mathit{limit}-1} \mathit{limit}-j\right) =
O\left(\sum_{j=1}^{\mathit{limit}} j\right) =
O(\mathit{limit}^2),
$$
using the formula $\sum_{j=1}^n j = \frac{n(n+1)}{2}$.


What is the time complexity of this binomial coefficient algorithm?

The only way that your algorithm can compute ${n \choose k}$ is by adding ${n \choose k}$ 1's together.

Now prove it.


Yes, if a program runs in time $O(n)$, then it also runs in time $O(n^2)$. However, usually we try to give the best possible bound, to prevent readers from being misled. You can signify that the bound is tight using big theta: the worst-case running time of the program is $\Theta(n)$.


What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?

They are among other things very useful for calculating logarithms, or square roots and cubic roots.

For example: log x = log ($2^e * m$) = e * log 2 + log m. With 0.5 ≤ m ≤ 1, you can approximate log m using a polynomial, which wouldn't work for x which can be in the complete range of floating point numbers.

$x^{1/3}$ = $(2^e * m)^{1/3}$. Let e = 3k, 3k+1, or 3k+2, then this equals $2^k * m^{1/3}$ for 0.5 ≤ m ≤ 4. You can either use approximation by a polynomial for m, or you use Newton iteration which will be much faster for m in the small interval.


Minimal number of states for an NFA of all different words

Here is a matching $\Omega(k^2)$ lower bound.
Consider any NFA for your language. Let $Q_i$ be the set of states $q$ such that:

There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
There is some word $z$ such that starting at $q$, after reading $z$ the NFA could be at an accepting state.

Since all words in $L$ have the same length, the sets $Q_i$ must be disjoint.
Now let $i \in \{0,\ldots,k\}$. For every word $w \in \{0,1\}^i$, let $Q_i(w) \subseteq Q_i$ be the set of states that the NFA could be in after reading $w$. I claim that if $w_1 \neq w_2$ then $Q_i(w_1) \neq Q_i(w_2)$. Indeed, the NFA behaves differently after reading $w_1$ and $w_2$: it accepts $w_1 0^{k-i} @ w_2 0^{k-i}$ but rejects $w_2 0^{k-i} @ w_2 0^{k-i}$. It follows that $2^{|Q_i|} \geq 2^i$, and so $|Q_i| \geq i$. Therefore the NFA has at least
$$ \sum_{i=0}^k i = \Omega(k^2) $$
many states.


Time complexity of kruskal using array data structure

Here is the original question encountered by the OP, quoted here so that readers do not have to register to that website just to take a look at the question.

  Consider a graph with V vertices and e edges,What is the worst case time complexity for kruskal's algorithm when implemented using array data structure?
  a.) E+ElogV
  b.)VlogV
  c.)V^2
  d.)Vlog^2V

The only correct answer as I see is, the original question is ill-posed. It is ill-posed because of its unconventional, ambiguous, almost meaningless use of "using array data structure".

Array is such a fundamental data structure, it usually converys little information when you say an algorithm is implemented using array data structure. Especially in the current case of Kruskal's algorithm, we usually refer to the disjoint-set data structure used in the algorithm to keep track of which vertices are in which connected components and to determine whether an edge will join two different connected components. In fact, the whole page about Kruskal's algorithm in wikipedia does not mention "array" even once. Although well versed regarding to minimal spanning tree and Kruskal's algorithm[1], I am confused by this "using array data structure".

Let us also take a look at other aspects of the original question. It has bad capitalization, bad punctuation, and inconsistent white spacing. It introduces "$e$ edges" but use $E$ in the choices. When it lists the time complexities, it should apply the big $O$ notation such as $O(E+E\log V)$. It skips the basic description of the graph as connected edge-weighted.

All in all, it is fair to say the original question is of such a low quality, you should just ignore it. Try not to learn from it.


Finding the height of all nodes in a forest

First of all, it depends a bit how you can access your data to say which algorithms works best.

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases}
\left(\max_{u\text{ child of }v}\text{height}(u)\right)+1 & \text{if $u$ is not a leaf} \\
\hskip4ex 0 & \text{otherwise}
\end{cases}.
$$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you know that you have average degree less than two (and therefore you can test for roots in linear time).


How to call something that can be either a terminal or a nonterminal?

The long forms "terminal symbol" and "nonterminal symbol" suggest that you are dealing first and foremost with "symbols"; "terminal" and "non-terminal" are qualifiying attributes that specify a symbol's role in the grammar. A symbol that can be either one of terminal and non-terminal is, almost by virtue of logics, just an arbitrary symbol.

Therefore, "symbol" seems to be the natural choice. I am pretty sure it is the term usually used, too, but such statements are hard to validate.

If you want to stress that a given symbol can be either kind (in text), you can always use "arbitrary symbol (of grammar $G$)", or define $X \subseteq t \cup T$ explicitly. In source code, I'd just use "symbol".


What you have there is not a true nested loop. It's one loop with, what is equivalently an if-test in there, like:

while(i<n){
   if(cond)
      //something Θ(1)
   else
      //some other Θ(1) thing
   i++
}

Notice in your case, you have the same variable for both loops with no reset.

So, to answer your question, the running time is $\Theta(n)$.  In particular, it is $O(n)$.

As a commenter states, anything that is $O(n)$ is also $O(n^2)$.


Parameterized vertex cover on $r$-regular graphs

There's nothing wrong with your solution, the exercise is just easier than you expected.

Your analysis correct, apart from missing out the $-1$, so it should be $k^{\mathcal{O}(1)}\cdot\binom{r}{k-1}\cdot n$, which is, of course, of the required form $f(k+r)\cdot n^{\mathcal{O}(1)}$, and the $-1$ doesn't really change anything.

The biggest mistake is writing $\mathrm{FTP}$ instead of $\mathrm{FPT}$. The first is a protocol, the second is a complexity class.

Moving to pure speculation, I would guess the authors were, in the second part, simply looking for reinforcement of the difference between $\mathrm{FPT}$ and in class $\mathrm{X}$ for every fixed value of some parameter (in this case, something like $f(k)\cdot n^{r}$ would work for the first part of the exercise, but not the second. The Hitting Set problem, as an example, has such an algorithm, where the parameter $k$ is the size of the solution, and $r$ is the size of the input sets; it's in $\mathrm{FPT}$ for every fixed $r$, but not in $\mathrm{FPT}$ for parameter $k+r$).


The greedy algorithm does not always work. Example: $S_1 = \langle 3, 1, 1,1\rangle$, $S_2 = \langle 2, 2,2\rangle$, $W=6$.

In general, let $S_1 = \langle x_1, \dots, x_k \rangle$ and $S_2 = \langle y_1, \dots, y_h \rangle$. I will assume that individual book weights are positive integers.
To solve your problem optimally you can use a sliding-window approach. Compute, for each $i=0,\dots k$, the quantity $X_i
= \sum_{j=1}^i x_i$. Similarly, for each $i=0,\dots,h$ compute $Y_i
= \sum_{j=1}^i y_i$.

Now start with $i=0$ and $j=h$ and iteratively do the following:

If $X_i + Y_j \le W$ consider the solution $(i,j)$ that selects $i$ elements from $S_1$ and $j$ elements from $S_2$ as a candidate solution.
If $i=k$ and $j=0$ stop and return the solution that maximizes $i'+j'$ among all candidate solutions $(i',j')$.
If $X_i + Y_j \le W$ and $i<k$, or if $j=0$, increment $i$ by $1$.
Otherwise, decrement $j$ by $1$.

To see that this algorithm must work consider an optimal solution that selects $i^*$ books from $S_1$ and $j^*$ books from $S_2$. Since, at the end of the algorithm, $i=k$ and $j=0$ there must be some iteration for which $i=i^*$ or $j=j^*$. Consider the first such iteration.

If $i=i^*$ then $j \ge j^*$ meaning that for all $j' = j^*+1, \dots, j$ we must have $X_i + Y_{j'} > W$. This shows that in the next $j-j^*$ iterations $j$ will be decremented until it reaches $j^*$.

If $j= j^*$ then $i \le i^*$ meaning that for all $i' = i, \dots, i^*-1$ we must have $X_{i'} + Y_j > W$. This shows that in the next $i^*-i$ iterations $i$ will be incremented until it reaches $i^*$.

In any case the pair $i=i^*$ and $j=j^*$ is considered by one iteration of the algorithm and, since $X_{i^*} + Y_{j^*} \le W$ the solution  $(i^*,j^*)$ must be one of the candidate solutions.

A straightforward implementation requires linear time in the combined size $n$ of the two stacks.

Since you can actually stop computing $X_i$ (resp. $Y_i$) as soon as $X_i \ge M$ (resp. $Y_i \ge M$) you can reduce the time complexity to $O(\min\{n, W\})$.


Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

The idea is as follows:

We run two automata in parallel: one verifies that the input is in $A$, and the other verifies the other condition.
The second automaton simulates an automaton for $B$, in the following way. At any point in time it may simulate reading a $0$. It ignores all $0$s in the real input, and forwards all $1$s in the real input.

I'll let you construct an NFA given this description.


Comparison of constructive and local-search heuristics for TSP

So first of all lets consider the techniques. Nearest neighbour is a heuristic that directs the search. That means that it informs how the search should proceed. It can be seen as preemptive.

The 2-opt is not a search heuristic but is a technique used to attempt to improve a solution(partial solution). You can think of it as massaging the solution into a more desirable solution.

As for advantages/disadvantages... well the nearest neighbour heuristic directs the search, but it may make silly mistakes. This in effect allows the search tree to be led "Down a rabbit hole".

The 2-opt solution is computationally more complex. It requires you to consider all quadruples (all pairs of edges if your data structure allows it) and then decide if the cross has occurred. In situations that you are looking for good enough and need an answer quickly, this type of search may be too computationally intensive. Although to the best of my knowledge, in any situation where 2-opt is a reasonable idea, the fitness of your solution should only improve/stay the same... Although I would not be surprised if I were wrong about that.


Struggling to understand the thought process required to come up with some recurrences for Dynamic Programming problems

Here is a way to solve the problem of longest valid parentheses by dynamic programming as you had hoped. Or almost.
For simplicity, a string is called valid if it consists of well-formed opening and closing parentheses.
The critical observation is that a string is valid if  it is the empty string, a concatenation of two valid strings or "(" followed by a valid string followed by ")". In fact, that observation is the usual recursive definition of well-formed opening and closing parentheses! That observation indicates that a suitable set of subproblems are s[i...j].

Let s be the given string of length L.

Let dp be an L by L+1 array of booleans.
dp[i][j] will become true iff the substring s[i,j] is valid. Here s[i,j] means the substring with indices from i inclusive to j exclusive, 0 <=i <= j < L. In particular, s[i,i] means the empty string.

Initially, all dp[i][j] are false.

The base case is the empty string, dp[i][i] = true for all i.

The recurrence relation is, according to the observation above, dp[i][j] = true for i < j if s[i] == '(' and dp[i+1][j-1] == true and s[j-1] == ')' or there is an index k, such that both dp[i][k] == true and dp[k][j] == true.  We can stipulate that i < k < j.

Here is the top-down version of the above approach, following the style in the question.
private static boolean topDown(String s, int i, int j, Boolean[][] dp) {
    if (i > j) return false;
    if (dp[i][j] != null) return dp[i][j];

    if (i == j) {
        dp[i][i] = true;
    } else {
        if (s.charAt(i) == '(' && s.charAt(j - 1) == ')' && topDown(s, i + 1, j - 1, dp)) {
            dp[i][j] = true;
        } else {
            for (int k = i + 1; k < j; k++) {
                if (topDown(s, i, k, dp) && topDown(s, k, j, dp)) {
                    dp[i][j] = true;
                }
            }
        }

    }

    if (dp[i][j] != null) {
        return true;
    } else {
        dp[i][j] = false;
        return false;
    }
}

Here is the bottom-up version. The code is sped-up a bit by the observation that a string can be valid only when its length is even.
private static int longestValidSubstring(String s) {
    final int L = s.length();

    // isValid[i][j] is true iff s.substring(i,j) is valid.
    boolean[][] isValid = new boolean[L][L + 1];

    // empty string is valid.
    for (int i = 0; i < L; i++) {
        isValid[i][i] = true;
    }
    for (int l = 2; l <= L; l += 2) {  // l is the length
        for (int i = 0; i <= L - l; i++) {
            // determine isValid[i][i+l]
            if (s.charAt(i) == '(' && s.charAt(i + l - 1) == ')' && isValid[i + 1][i + l - 1]) {
                isValid[i][i + l] = true;
            } else {
                for (int j = 2; j < l; j += 2) {
                    if (isValid[i][i + j] && isValid[i + j][i + l]) {
                        isValid[i][i + l] = true;
                        break;
                    }
                }
            }
        }
    }

    for (int l = L & 0xfffffffe; l >= 2; l -= 2) {
        for (int i = 0; i <= L - l; i++) {
            if (isValid[i][i + l]) {
                return l;
            }
        }
    }
    return 0;
}

The iterative version should be faster than the top-down version. However, even the iterative version is not fast enough when L is large since it computes L * L entries, which is pretty large once L is greater than 10000. Moreover, the two dimensional array isValid uses lot of memory as well.
Here is an improved solution of $O(n)$-time and $O(n)$-space. Here is the most brilliant solution, also of $O(n)$-time and $O(n)$-space. I will not discussion them, since they are out of the scope of this answer.

Is there a way to solve the longest valid parentheses problem as a function of f(i,j) where f(i,j) represents the length of longest valid parentheses between i and j? It is ok if the runtime complexity is higher I am just curious about this.

The fundamental quality of the subproblems in dynamic programming is that you can solve a larger subproblem more easily once you have the solution to the smaller subproblem. Or, you can extend or combine the solutions to the smaller subproblems to build a solution to the larger problem.
In this particular problem, if we know whether all shorter substrings are valid or not, then it is easy to know a longer substring that is slightly longer is valid or not. On the other hand, if we know all f(i,j), which represent the length of longest valid substring between i and j, the lack of specific location of those longest valid substrings does not help us determine whether a substring of a longer substring is valid or not. The difference is critical, although might be subtle to untrained eyes. You will learn to appreciate the difference.

When I was solving the problem initially I had not thought of writing it as a function of f(i). I only thought of it as a function of f(i,j) and that turned out to be wrong. So is there an easy way to tell just by looking at a problem what states should be computed? For example why can't I solve the longest palindromic substring problem as a function of f(i)? similarly why can't I solve the longest parenthesis problem as a function of f(i,j)?

As I have shown above, it is not necessarily wrong to use f(i,j) although we should give f(i,j) a slightly different meaning.  Solving a problem efficiently might not be easy, even if it is known to be solvable by dynamic programming. Quite a few problems puzzle me for a long time even if I consider myself experienced. It requires some intelligence and experience to identify or formulate the proper set of subproblems (which are not necessarily in the exact form of the original problem).
To extend a palindromic substring to a longer palindromic substring, you need to extend it from both sides. That indicates it may not easy to solve the longest palindromic substring problem as a function of a single variable that stands for the one end of the palindromic string in a simple and efficient way. However, if we analyze the fine structure of palindromes, we could arrive at the Manacher's algorithm
, which basically use a map from a single variable that stands for the center point of palindromic substrings.


Alright,
I managed to solve this problem using Prolog.

First of all, I've converted wordlist.txt from:

word1
word2
...

Into wordlist.pl:

w(w,o,r,d,1).
w(w,o,r,d,2).

Then I've found Prolog function, that tells me if all the elements in the list are different:

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).

After that I have written Prolog function, that takes predefined format and finds all the possible words from dictionary, that meet given format:

g(Format, String):-
    list_to_set(Format, Uniques),
    alldif(Uniques),
    w(Format),
    atomic_list_concat(Format, '', Atom), atom_string(Atom, String).

Now I'm able to call:

g([A,B,C], String1), g([A,D,A], String2).

That generates me all possible combinations of String1 and string2 with following format:

"ABC ADA"


If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

This should be a comment on the original post by @Drupalist and on Ds D's answer, but it's too long. It's not enough to say that $A\le_M B$ requires $B$ be recursive or that one of $B, \overline B$ be r.e.

Let $A$ be recursive and $B=\{(\langle\,M\,\rangle,\langle\,N\,\rangle)\mid M,N\text{ are TMs and }L(M)=L(N)\}$. This language (sometimes called $\text{EQ}_{\text{TM}}$) is known to be neither r.e nor co-r.e. However, let

      M(x) =                    N(x) =
         return accept             if x = 0
                                      return reject
                                   else
                                      return accept

We have $(\langle\,M\,\rangle,\langle\,M\,\rangle)\in B$ and $(\langle\,M\,\rangle,\langle\,N\,\rangle)\in \overline{B}$. Then if $A$ is recursive, there is a decider TM, $D$, for A and if we define $f$ by

      f(x) =
         run D on x
         if D(x) = accept
            return (<M>, <M>)
         else
            return (<M>, <N>)

Then $f$ is Turing-computable and $x\in A\Longleftrightarrow f(x)\in B$, which is the definition of $A\le_M B$. So we can have such a reduction in every case where it's possible to find (not necessarily by a TM) two instances $y\in B$ and $n\in\overline{B}$.

Note that I'm not claiming that this technique will work for all possible $B$ nor am I claiming that this technique is the only possible one. All I've shown is that the problem isn't as simple as it seems at first glance.


Composable means we can check for each object separately and exactly if the property applies to all of them separately then it applies to the whole of them at once.

To show that sequential consistency is not composable we can use an example where the ordering implied by the projections on one object contradicts the ordering implied by the projection on an other object.

Consider a history

A p.enq(x)
B q.enq(y)
A p:void
A q.enq(x)
B q:void
B p.enq(y)
A q:void
A p.deq()
B p:void
B q.deq()
A p:y
B q:x

when simply written down as code. Or visualized:

A: ---*1: p.enq(x)*---*3: q.enq(x)*---*5: p.deq()=y*---
B: ------*2: q.enq(y)*---*4: p.enq(y)*---*6: q.deq()=x*

where the operations start and end at the * and are arbitrarily numbered. Note that this looks like time axes, but that's not how it's necessarily executed. Now when you look at the object p, there must be an order 4-1-5 and for q it's 3-2-6. If the history is sequentially consistent, we also need order 1-3-5 and 2-4-6. But this is not possible, all possible interleavings of 4-1-5 and 3-2-6 contradict either of 1-3-5 or 2-4-6.

(example taken from private slides of a lecture I attended)


Satisfiability of first-order logic is undecidable?

The fact that first-order logic (with some non-triviality constraints) is undecidable means that no algorithm can decide correctly whether a given first-order formula is true or not. However, for any single statement $\varphi$ it is easy to come up with an algorithm that decides $\varphi$ correctly (just hard-code the answer). So it is impossible to give examples of "undecidable statements", since there is no such thing.

What is possible is to give a restricted set of sentences whose truth value is already undecidable. In effect, this is what the proof of undecidability does. The proof shows that you can encode the statement "the Turing machine $T$ halts on empty input" in first-order logic (again, given some mild non-triviality constraints), so this infinite sequence of statement is already undecidable, that is, no algorithm can correctly decide whether such a formula is true or not.


Construct a context-free grammar for a given set of words

I think you might be referring to Sequitur.

Edit It has been suggested by other commenters that I leave more information for posterity. Fair point.

Sequitur is an algorithm by Craig Neville-Manning and Ian Witten (of Managing Gigabytes fame). It's linear time in the size of the input sequences (although so is the memory usage), and satisfies the twin properties of parsimony (no redundant rules are derived) and utility (every rule is useful).

However, it can't (IIRC) discover arbitrary nesting structure. So a prototypical expression grammar, where an expression can contain an expression, is too much for it. But it will discover word boundaries in English text, and repeat regions in DNA. It's also useful for finding dictionaries for data compression (which is one of Witten's major research interests).


What is the role of mathematics in programming?

You don't need any math to write a Hello World or a very simple website.

You will need to know some discrete mathematics and algorithm analysis to write a program that finds a route between two cities.

You will need to know matrix transformations and quaternions to write a game engine.

You will need to know a lot about all kinds of mathematical fields to write the next Wolfram Mathematica.

What I'm trying to say, what fields of mathematics you will need to know and to what degree will depend a lot on what kind of programs do you want to write. But the ones that tend to be most widely useful are data structures, algorithms and their analysis.


T(n) = aT(n/b)+f(n), I don't understand the difference between a and b

Here are three examples of algorithms with $b=2$ and $a=1,2,3$.

In all these examples, there is some small-scale cheating involved, which doesn't affect the asymptotic running time. I'll let the reader figure out where I'm cheating.

Binary search

In this algorithm, we are looking for an element $x$ in a sorted array $A$ of length $n$.

If $n = 1$, the problem is easy.

Otherwise, let $m$ be the index of the middle element:

If $x = A[m]$, we are done.
If $x < A[m]$, we recurse with the array $A[1],\ldots,A[m-1]$.
If $x > A[m]$, we recurse with the array $A[m+1],\ldots,A[n]$.

Every time we recurse, the size of the array decreases by a factor of 2. Therefore, the running time of binary search on inputs of length $n$ satisfies the following recurrence:

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

Here $a = 1$ and $b = 2$. The solution is $T(n) = O(\log n)$.

Merge sort

In this algorithm, we are sorting an array $A$ of length $n$.

If $n = 1$, the array is already sorted.

Otherwise, partition $A$ into two arrays $A_1,A_2$ of length $n/2$, sort each recursively, and then merge them in $O(n)$ time.

In contrast to binary search, in which we only recursed on one of the half-arrays, in merge sort we recurse on both. Therefore the appropriate recurrence is

  $T(n) = 2T(n/2) + O(n)$.

Here $a = b = 2$. The solution is $T(n) = O(n\log n)$.

Karatsuba multiplication

In this algorithm, the goal is to multiply two $n$-bit integers $x,y$.

We first divide $x,y$ into two $n/2$-bit integers: $x = 2^{n/2} x_1 + x_2$, $y = 2^{n/2} y_1 + y_2$. We then proceed as follows:

Compute $z_1 = x_1 y_1$.
Compute $z_2 = x_2 y_2$.
Compute $w = (x_1+x_2)(y_1+y_2)$.
Return $2^n z_1 + 2^{n/2} (w - z_1 - z_2) + z_2$.

In steps 1,2,3, we are multiplying $n/2$-bit integers (more or less; in step 3 they are $(n/2+1)$-bit integers). The rest of the algorithm consists of addition and subtraction, which can be done in linear time. Therefore the appropriate recurrence for the running time of this algorithm is
$$
T(n) = 3T(n/2) + O(n).
$$
Here $a = 3$ and $b = 2$. The solution is $T(n) = O(n^{3/2})$, improving on the trivial $O(n^2)$ algorithm.


Can a DFA have two symbols on one arrow?

The transition graph (as a drawing) is merely a representation of an Automaton, which is a well-defined model.

Formally, an DFA is a tuple $(Q,\Sigma,\delta,q_0,F)$, where the "type" of the transition function is $\delta:Q\times \Sigma\to Q$.

Thus, if you have $\delta(q_0,a)=\delta(q_0,b)=q_1$, that's fine.
In the graphic representation, you will either have two arrows from $q_0$ to $q_1$, labeled $a$ and $b$, or you can just put both letters on the same arrow, it's not a formal thing anyway.


You need to show that for every $L'\in P$ there exists a logspace reduction from $L'$ to $L$. Your $f$ has $\langle M_{L'}\rangle$ hardcoded into it. The encoding was part of its definition, $f$ does not ask what is the encoding of the machine for $L'$ when it tries to compute $f(x)$.

One way to think of this is as follows: consider the sequence of functions $\left\{f_{s ,c}\right\}_{c\in\mathbb{N}, s\in\{0,1\}^*}$ where
$f_{s, c}(x)=\left(s, x, 1^{|x|^c}\right)$. Since $L'\in P$, there exists a function in this sequence which is a reduction from $L'$ to $L$ (the specific index depends on the machine deciding $L'$, but we don't really care about it).


Hint: does being in P have something to do with the length of the input?


Is O(ln n) "exponentially faster" than O(n)?

How should we measure (asymptotic) speedup?

Say we wish to compare two functions, $f(n)$ and $g(n)$, and say something on their asymptotic behavior, that is, how they behave for large enough $n$'s, in the limit $n \to \infty$.

Let's start with a few examples.

  Example 1:  $f(n)=2n$ and $g(n)=n$.

Here it is obvious that $f$ is "twice as slow" as $g$; This is true for any $n$ and also in the limit. This needs not be the case. For instance

  Example 1.1:  $f(n)=2n$ and $g(n)=n+1000$.

Well, now, for $n<1000$, $f$ is actually faster than $g$. But still, if we take large $n$'s, we want to say that $f$ is twice as slow as $g$, or in other words, the speedup is 2.

Why 2? Because the ratio between $f$ and $g$, in the limit, is 2.

Let's take a different example to emphasize this issue.

  Example 1:  $f(n)=n+10$ and $g(n)=n$.

Here, $f$ is slightly slower than $g$. What is the speedup between $f$ and $g$? By how much is $g$ faster? The answer is "by 10 clocks". But speedup is measured as a ratio - "twice" as fast means it would take (approx.) twice the time to run the slower function. Here the ratio is approaching 1
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} \to 1$$
That is, the 10 clocks don't make any (multiplicative) difference. Running 10000 clocks and running 10010 clocks, is practically the same (the speedup is $<0.1\%$).

I hope the above establishes that the (asymptotic) speedup between $f$ and $g$ should be defined as
$$\lim_{n\to \infty} \frac{f(n)}{g(n)}.$$

When the speedup is not a constant, then the best way to describe the speedup is to set $g(n)=k$ and ask how $f(n)$ behaves as a function of $k$. If $f(n) \propto k^2$, then the speedup is "quadratic". If $f(n)\propto k^3$ the speedup is cubic. If $f(n)\propto 2^k$, the speedup is called exponential. Not that it is important to set $g$ as the base unit ($=k$). Otherwise, If we take $f$ as the base unit, then a quadratic speedup translates to $g(n)=\sqrt{k}$, which may be a bit confusing. Maybe its better to think at the other direction: instead of considering the speedup from $f$ to $g$, look at the slowdown from $g$ to $f$. (.. if $g$ is twice as fast as $f$, then $f$ is twice as slow as $g$)

If we agree on this, we can check the speedup between $f(n)=n$ to $g(n)=\log n$.
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{n\to \infty}\frac{n}{\log n}$$
Let's change the limit variable, to make $g$ the base unit for the comparison: set $k=\log n$, then,
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{k\to \infty} \frac{2^k}{k}$$
That is the ratio between them, in the limit, has an exponential gap. As mentioned, this is called exponential speedup.


Difference between properties of good hash function: uniformity and randomness

Uniformity is about potential values, while randomness is about actual values.

For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 buckets. It is uniform, because the number of possible strings starting with a particular byte doesn't depend on. But it is not random for most data sets: at least 12.5% of the values consist of nonprintable characters (control characters) that most data sets don't contain, some characters like )]} rarely appear at the beginning of a string, an English dictionary contains more words beginning with a than with z, etc.

Randomness is defined with respect to a specific data set. For example, if the data set consists of SHA-1 hashes of typical strings, then taking the first byte satisfies the randomness property. If the data set consists of people's surnames, it doesn't. If the data set consists of SHA-1 hashes strings that are deliberately chosen so that their SHA-1 hash starts with the byte 0, then taking the first byte doesn't satisfy randomness either.

In fact, there is no hash function that satisfies randomness for all datasets: for any hash function (with at least two buckets), a data set consisting solely of values that hash to bucket 0 violates randomness. The best you can hope is hash functions that satisfy randomness for datasets that are not deliberately crafted to violate randomness. This is possible in practice if the hash function includes a random factor which is based on a secret seed.


Trying to solve the recurrence relation by comparing 3 cases of master theorem

You determine $a$, $b$, and $f$ using pattern matching.

The Master theorem applies for recurrences of the form

$\qquad\displaystyle T(n) = a T(n/b) + f(n)$;

you have

$\qquad\displaystyle T(n) = \sqrt{6006} \cdot T(n/2) + n^{\sqrt{6006}}$.

Just by comparing the two formulae, you determine that

$\qquad\begin{align*}
  a &= \sqrt{6006},\\
  b &= 2, \quad\text{and} \\
  f &= n \mapsto n^{\sqrt{6006}}.
\end{align*}$

Now you go through the three cases and check which applies (if any). See also here.


What does the "0 ≤ K < N-1" expression means?

You have an array with indices from $0$ to $N-1$. $K$ is an in integer in this range, i.e. larger or equal to zero and smaller than $N-1$.

This integer splits the array into two parts as follows:

Part 1: From $0$ to $K$ (including K)

Part 2: From $K$ (excluding K, i.e. starting with $K+1$) to $N-1$.

$K$ has to be smaller than $N-1$ (and not smaller or equal) because else there would only be one Part (the whole array) for $K= N-1$.


$O(n^{k-1}$) algorithm for K-clique problem

A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega < 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh [1]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C_3$, one can use general cycle finding methods for detecting triangles. Alon, Yuster and Zwick show how triangles can be detected on an $m$-edge graph in $O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$ time [6].

For a long time, the result of Nesetril and Poljak [2] was the best known; they showed the number of cliques of size $3k$ can be found in time $O(n^{\omega k})$ and $O(n^{2k})$ space. Finally, Eisenbrand and Grandoni [3] improved on the result of Nesetril and Poljak for a $(3k+1)$-clique and a $(3k+2)$-clique for small values of $k$. Specifically, they gave algorithms for finding cliques of size 4, 5, and 7 in time $O(n^{3.334})$, $O(n^{4.220})$, and $O(n^{5.714})$, respectively.

As far as I know, for general $k$, the problem of designing better algorithms is open. For possible consequences or complexity theoretic considerations, Downey and Fellows (see e.g. [4]) showed $k$-clique with parameter $k$ is $W[1]$-hard. The class $W[1]$ denotes the class of parameterized decision problems reducible to CLIQUE with parameterized reductions. It is believed that CLIQUE is not fixed-parameter tractable. There are hundreds of other problems known to be equivalent to CLIQUE under parameterized reductions. Furthermore, Feige and Kilian [5, Section 2] have a result saying that when $k$ is part of the input and $k \approx \log n$, then a polytime algorithm is not likely to exist.

If you consider some restricted graph classes, you can solve the problem in linear time on chordal graphs. Simply compute a clique tree of a chordal graph $G$ in $O(n+m)$ time, and then check if any clique is of size exactly $k$. On planar graphs, one can also find triangles in $O(n)$ time using the methods of [6].

[1] Itai, Alon, and Michael Rodeh. "Finding a minimum circuit in a graph." SIAM Journal on Computing 7.4 (1978): 413-423.

[2] Nešetřil, Jaroslav, and Svatopluk Poljak. "On the complexity of the subgraph problem." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

[3] Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.

[4] Downey, R. G., and Michael R. Fellows. "Fundamentals of Parameterized complexity." Undegraduate Texts in Computer Science, Springer-Verlag (2012).

[5] Feige, Uriel, and Kilian, Joe. "On Limited versus Polynomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.


Hint: Suppose that $\mathcal{A}_1$ has $n$ states. Since it is acyclic, all the words it accepts have length at most $n-1$ (why?). Therefore if $L(\mathcal{A}_1) \nsubseteq L(\mathcal{A}_2)$ there must exist a word $w$ of length at most $n-1$ that $\mathcal{A}_1$ accepts but $\mathcal{A}_2$ rejects.


Multiplication function BDD size lower bounds

I think the resolution to the paradox comes from looking more carefully what is meant when we say that multiplication can be performed in logarithmic space, and looking more carefully at what we mean by a BDD.

Suppose we want to multiply two $n$-bit numbers $a,b$, and suppose the two numbers $a,b$ are stored in read-only memory.  Then we can calculate any desired bit of the product using only $O(\lg n)$ additional bits of space.  However, this fundamentally requires us to have (read-only) access to the numbers being multiplied.

(Take a look at the formula in Wikipedia for $r_i$: $r_i$ depends on $a$, $b$, and $c_{i-1}$.  The carry $c_{i-1}$ needs only $O(\lg n)$ bits of space to store.  However, just storing the carry alone is not enough.  We also need to have the numbers $a,b$ stored, and that requires $\Theta(n)$ bits of storage.)

In short, multiplying two numbers takes $\Theta(n)$ bits (read-only) for the numbers being multiplied and $\Theta(\lg n)$ bits (read-write) of additional storage.  This does prove that multiplication is in $L$.  However, it doesn't prove that there is a polynomial-size BDD for multiplication.

First, let's understand what we mean by BDD.  There are many types of BDD, but the most relevant one here is the notion of a ROBDD (read-once binary decision diagram).  A ROBDD is allowed to read each bit of the input only once.  Normally, BDD means a ROBDD: for a reference, see, e.g., the Wikipedia article on BDDs, which writes "In popular usage, the term BDD almost always refers to Reduced Ordered Binary Decision Diagram (ROBDD".  Moreover, the lower bound for the size of a BDD for multiplication is actually a lower bound on the size of a ROBDD for multiplication.  Therefore, in this answer I'll assume BDD means ROBDD.

Now, here's why the above algorithm doesn't prove there is a polynomial-size (RO)BDD for multiplication.  Given an algorithm with space complexity $s$ and time complexity $t$, you can construct a BDD with something like $2^s \times t$ nodes (but here $s$ must include all input bits that might be read more than once, as well as all additional storage).  This means that the number of nodes in a BDD could be as much as exponential in $s$.  In the case of multiplication, we have $s = \Theta(n+\lg n) = \Theta(n)$, so from the existence of the multiplication algorithm above, all we can conclude is that the size of the BDD could be (at most) exponential in $n$.  This isn't enough to show that there exists a polynomial-size BDD.

What about L vs L/poly vs BDDs?  I don't think it's true that just because a problem is in L/poly, that means it has a polynomial-size BDD.

Roughly speaking (ignoring uniformity vs non-uniformity), a problem is in L or L/poly if there is an algorithm that has read-only access to the inputs and uses only $O(\lg n)$ additional bits of (read-write) storage.  If we also knew that this algorithm reads each bit of its input only once, then that would imply that there is a polynomial-size (RO)BDD for the problem.  But if the algorithm scans back and forth over the input bits, reading them many times, then I don't think there necessarily exists a polynomial-sized (RO)BDD for the problem.  At least, I don't know of any result that implies that.  I could be missing something.

I know Wikipedia says that L/poly is "a complexity class that captures the complexity of problems with polynomially sized BDDs".  I am not sure that is exactly correct.


Shared randomness does not increase capacity of a noisy channel - Why?

Each value of the shared randomness corresponds to a communication protocol. So overall, we have a mixture of communication protocols, whose expected quality is good. There must therefore be one of these communication protocols – a setting of the shared randomness – which is as good.
As an example, we know that a random code achieves capacity. This means that some particular code achieves capacity. It might be hard to find that code, but we know that it exists.


Graph with exactly 2 Minimum Spanning Trees

Lemma: Let $C$ be a cycle of $G$ that contains an unique edge $e$ of maximum weight. Edge $e$ does not belong to any MST of $G$.

Proof:
Suppose that a MST $T^* = (V, E^*)$ of $G$ contains $e = (u,v)$.
Root $T^*$ in $u$ and let $f$ be any edge of $C \setminus E^*$ that has exactly one endpoint in the subtree of $T^*$ rooted in $v$ (this edge always exists since $C \setminus \{ e \}$ is a path from $v$ to $u$ that avoids $e$). The edge $f$ closes a fundamental cycle containing $e$ and is such that $w(f) < (e)$.
Then $(V, (E^* \setminus \{e\}) \cup \{ f \}$) is a spanning tree of $G$ that weighs less than $T^*$. This is a contradiction. $\square$

Let $T_1 = (V, E_1)$ and $T_2 = (V, E_2)$ be two distinct MSTs of $G$.
Let $C$ be a cycle in $(V, E_1 \cup E_2$).
Let $M = \arg\max_{e \in C} w(e)$.

If $|M|>1$ we are done. Suppose then that $M = \{ e \}$.
By the above lemma, $e$ is the unique heaviest edge of $C$ and hence it cannot belong to any MST of $G$. This is a contradiction since $e$ must belong to at least one of $E_1$ and $E_2$.


Prefix/suffix property of language containing only empty word

You probably mean $L=\{\varepsilon\}$, i.e. the language which contains only the empty word, as opposed to the empty language. Both the empty language and the language which contains only the empty word have the prefix/suffix property, since they satisfy the definion.

However, the prefix property is a property of a code, not a property of a language. A language can describe a code, but neither the empty language nor the language which contains only the empty word describe a code. So in the end it is irrelevant whether those languages have the prefix/suffix property.

Edit rici is right that Hopcroft&Ullman say that the LR(0) grammars define exactly the DCFL's having the prefix property. (They hasten to add that the prefix property is not a severe restriction.) So in this case it is good that the empty language and the language which contains only the empty word have the prefix property. Additionally, Berstel&Perrin allow the empty set as a code, so you can also dispute my other claim. But they agree that $\{\varepsilon\}$ has the prefix property, and is not a code:

  Proposition 2.1.9 Any prefix (suffix, bifix) set of words $X\neq \{\varepsilon\}$ is a code.

Both Hopcroft&Ullman and Berstel&Perrin consider $\varepsilon$ to be a prefix/suffix of any word, but they require a proper prefix/suffix in the definition of the prefix/suffix property. (This is clearly the right thing to do, otherwise no set of words would have the prefix/suffix property.)


Sort half-edges around common vertex in 3d

It seems that the problem here is that you try to determine something similar to a rotation system from a skeleton1 embedded in $\mathbb{R}^3$. The problem here is that such a skeleton is not enough to uniquely define a rotation system, because rotation systems encode embeddings of a graph onto a surface. Without having access to a given surface as a reference, almost any rotation along a vertex is possible, and you will not be able to find the "right" one.
So what can you do? This likely depends a bit on what it is you are actually modelling. Since the rotation around a vertex is a concept that depends on a surface, to determine it you will have to decide what your surface looks like, at least locally around the vertex you're inserting a triangle in. Likely, the edges that are part of a triangle should always be consecutive in the ordering, but that doesn't give all the information.
One possible approach on how to decide where a new triangle fits into the ordering, is to look at all consecutive pairs of triangles in the existing ordering, and insert the new triangle in between the pair with smallest distance to the new triangle. (Note that you have to store the ordering around the vertex explicitly, you cannot compute this on the fly)
More precisely, to determine where to place a new triangle incident to vertex $v$ in the ordering around $v$, consider all pairs of consecutive edges $(e_i,e_{i+1})$ that do not form a triangle with vertices $(a,b)$ being their endpoints not equal to $v$. Let $(x,y)$ be the new vertices of the triangle. Place the edges of the new triangle in between the pair of edges $(e_i,e_{i+1})$ such that $\min(\|a-x\|+\|b-y\|, \|a-y\|+\|b-x\|)$ (or another similarity measure of the pairs $(x,y)$ and $(a,b)$) is minimized.
For example, in the figure below, vertices with the same colors are the pairs we'd compare with our new vertices $x,y$.

1: I will assume that you just have a graph for now, but perhaps a simplicial complex might be a better description? I don't think it matters much for the discussion here, though.