O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”?

The idea is to repeatedly apply the following algorithm:

Determine the parity of the number of $a$'s, deleting every second $a$ on the way.
Determine the parity of the number of $b$'s, deleting every second $b$ on the way.
Accept if there were no $a$'s or $b$'s.
Reject if the parities are different.
Jump back to Step 1.

Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.

As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.


Is Context Free Language closed under perfect shuffle?

Nope. Shuffle $\{ a^n b^{2n} \mid n\ge1\}$ with  $\{ a^{2n} b^n \mid n\ge1\}$ .


Number of ways to choose same number of elements from two different sets

Sometimes a summation of products of binomial coefficients can be simplified using  Vandermonde's identity.

In your case, Assuming $p\ge q$ we have $\sum^q_{k=0}{p\choose k}{q\choose k}=\sum^q_{k=0}{p\choose k}{q\choose q−k}$, which by Vandermonde equals $p+q\choose q$.

Actually this equality can be understood with elementary combinatorial arguments. Put the $p+q$ elements in one box. Now grabbing $q$ elements from the box means you have selected some $i$ elements from $S$ and $q−i$ elements from $R$. Or unselected $i$ elements from $R$ which is the same.


Can someone give a simple but non-toy example of a context-sensitive grammar?

My favourite example of a context-sensitive language (CSL) is SAT.  The Landweber-Kuroda Theorem says that CSL = NSPACE$[n]$.  Any SAT instance has a linear-size certificate, so SAT is a CSL.  See my question Context-sensitive grammar for SAT? for references and discussion.

Many other NP-hard languages are also in CSL by the same reason, such as CLIQUE.

There are also fairly natural languages in CSL that are even harder.

However, I am not aware of any way to express an arbitrary CSL as a context-sensitive grammar (CSG), other than to use Landweber's construction in Theorem 3 of his paper.  In this construction, the CSG describes the reverse of the operation of the linear-bounded automaton that recognizes the CSL.  Productions of the CSG describe how a particular state of the machine results from one possible move.  Such a CSG is straightforward translation of the automaton into a grammar, so it is not necessarily going to correspond to language features such as being able to declare variables, but will instead be bogged down by the details of the automaton.

If you insist on a CSG rather than a CSL, and if your actual question is specifically about wanting to see a CSG for a language that involves restricted variable scoping, then Hendrik Jan's answer seems to be a good start.


If graph isomorphism yields a polynomial time algorihtm

Nothing bad is known to happen if Graph Isomorphism can be solved in polynomial time; see this question on cstheory. On the other hand, problems in the complexity class GI will all have polynomial time algorithms.


Building a context-free grammar for this language

I'm not sure to have fully understood your notation.

As production rules you could consider:

$S \rightarrow aSa \ |aSb \ | S_1 | \epsilon$

$S_1 \rightarrow bS_1a | \ bS_1b \ | \ \epsilon$

In $S$ for each $a$ you add an $a$ or a $b$ or you can go to $S_1$ and then never come back to $S$ again.

In $S_1$ for each $b$ you add an $a$ or a $b$.


Distributed algorithms - $\alpha, \beta$ synchronizers

Please find solutions of all cases:

For case A ($\alpha$-synchronizer), the pulse at a node can either be more, equal, or less by one (therefore, $\{26,27,28\}$). This is because a node must inform its neighbors about its safeness and not all the other nodes (according to your question).

You can see the rules in the following (copy-pasted from the paper)

A new pulse may be generated at a node whenever it is guaranteed that no
message sent at the previous pulses of the synchronous algorithm may arrive at
that node in the future.
Using the acknowledgment mechanism described above, each
node detects eventually that it is safe and then reports this fact directly to all its neighbors. Whenever a node learns that all its neighbors are safe, a new pulse is generated.

For case B: ($\beta$-synchrnoizer) - if $v$ is the root, then at $v'$ the pulse is either the same or less (therefore, $\{26,27\}$).

For case C: ($\beta$-synchrnoizer) - if both $v$ and $v'$ are leaves, then here we may assume that the broadcast of the root is not received at the same time - since the network is asynchronous (otherwise, why would we need a synchrnoizer). Here, if $v$ is 27 then $v'$ is either 28 if the update of $v'$ is received before $v$ ,, or 26 if the update of $v'$ is received after. Or they both have the same pulse  (therefore, the range is $\{26,27,28\}$.


Hardness of checking maximal magnitude of a sum of a subset of vectors

I suppose you are talking about the euclidean norm. Consider the optimal solution $S$ and let $w=\sum_{v\in S}v$, and we assume there's no zero vector in $V$.

For any $v\notin S$, it must holds $v\cdot w<0$, otherwise $\|w+v\|^2\geq \|w\|^2+\|v\|^2>\|w\|^2$. Similarly for $v\in S$ it holds $v\cdot w>0$, otherwise $\|w-v\|>\|w\|$.

That means $S$ is exactly determined by the direction of $w$. You can exhaust the possibilities by sorting the polar angles of the vectors, and rotate the orthogonal line of $w$ which has only $n$ essentially different partitions.


Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

Consider any problem in which there are several different solutions, for example MAX-CLIQUE on a graph in which there are several cliques of maximum size. Any convex combination of optimal solutions in another optimal solution which isn't integral.

If the optimum value of the integer program is the same as its linear programming relaxation, then any optimal solution to the integer program is also an optimal solution of the linear program. The problem is that there could be other optimal solutions to the linear program, and an LP solver might find one of them instead of an integral optimal solution. It would be, however, inaccurate to say that the LP and ILP have the same value but not the same solution. Rather, all optimal solutions of the ILP are also optimal solutions of the LP. It's just that the LP has more optimal solutions.


Can languages that are not closed against the Kleene star be regular?

No, your argument is not correct.

The "hence it's not regular" doesn't follow.  Not every regular language is closed under Kleene star.  Some regular languages aren't closed under Kleene star.  I think you've misunderstood the closure property: the closure property states "If $L$ is regular, then $L^*$ is regular".  Note that you can still have a regular language where $L \ne L^*$.

To learn how to solve this question correctly, you may want to check out our reference questions.  See especially How to prove a language is regular?, Show whether the language with almost as many 0 as 1 in every prefix is regular, Language where every prefix has almost equal a's and b's.


There are two types of answers:

Practical: You are looking for good stream ciphers. Several exist, though we don't know for sure that they are secure.
Theoretical: You are looking for cyptographically secure PRNGs. There are several suspected constructions, but such objects are not known to exist; if P=NP, then they don't exist.

In both cases, there is quite a wide literature on the subject.


The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the word being read, being in an accepting state whenever they are the same.

Instead of writing a state diagram, here are the Myhill–Nerode equivalence classes of your language (given as regular expressions), which can be converted into a DFA with the same number of states as the number of equivalence classes:

$q_0$: $\epsilon$.
$q_1$: $a$.
$q_2$: $b$.
$q_3$: $(aa+bb)(a+b)^*$.
$q_4$: $(a+b)^*aa \setminus (aa+bb)(a+b)^*$.
$q_5$: $(a+b)^*ab \setminus (aa+bb)(a+b)^*$.
$q_6$: $(a+b)^*ba \setminus (aa+bb)(a+b)^*$.
$q_7$: $(a+b)^*bb \setminus (aa+bb)(a+b)^*$.

The initial state is $q_0$, and the accepting states are $q_3,q_4,q_7$.

Here is the transition function:
$$
\begin{array}{c|cccccccc}
& q_0 & q_1 & q_2 & q_3 & q_4 & q_5 & q_6 & q_7 \\\hline
a & q_1 & q_3 & q_6 & q_3 & q_4 & q_6 & q_4 & q_6 \\
b & q_2 & q_5 & q_3 & q_3 & q_5 & q_7 & q_5 & q_7
\end{array}
$$


Let's assume that $\mathbb{Z}_q$ is the field of size $q$. In order for your family to be 3-wise independent, we need the following condition to hold: for every $x_1,x_2,x_3,y_1,y_2,y_3 \in \mathbb{Z}_q$ where the $x_i$ are all different,
$$
\Pr_s[h_s(x_1) = y_1 \land h_s(x_2) = y_2 \land h_s(x_3) = y_3] = \frac{1}{q^3}.
$$
Since your family consists of $q^3$ functions, this is the same as the following property:

  If $x_1,x_2,x_3 \in \mathbb{Z}_q$ are all different, then for every $y_1,y_2,y_3 \in \mathbb{Z}_q$ there exist unique $s_0,s_1,s_2 \in \mathbb{Z}_q$ such that
  $$ s_0 + s_1 x_i + s_2 x_i^2 = y_i, \quad i \in \{1,2,3\}. $$

This is a property that you can prove using linear algebra.


Getting from one language to the other using closure properties(automata)

If I understand your argument correctly, you are reducing languages in the wrong direction.

  If $L$ is not context-free, then $K$ is not context-free.

Is equivalent to

  If $K$ is context-free, then $L$ is context-free.

We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful closure properties of the non-context-free languages.

PS. The pumping argument seems out of place here.


Calculating positions of nodes relative to a known point

I wrote an algorithm that determines a configuration if one exists, given a distance matrix. It repeatedly uses circle-circle intersection  to triangulate new nodes based on their distance to the first, second and third. As others have mentioned in comments, the first three points have some degree of freedom, which I've made assumptions for, in line with yours.

The code assumes all points are unique and invariant to changes smaller than a certain $\epsilon$.

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

const double epsilon = 0.00001;

struct Point {
    double x, y;
};

double dist(Point p, Point q) {
    return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}

vector<Point> intersections(Point p, Point q, double pr, double qr) {
    double d = dist(p, q);
    if(pr + qr < d) return vector<Point>();
    if(min(pr, qr) + d + epsilon < max(pr, qr)) return vector<Point>();
    double a = (pr * pr - qr * qr + d * d) / (2.0 * d),
        h = sqrt(pr * pr - a * a);

    Point m = { p.x + (a * (q.x - p.x)) / d,
        p.y + (a * (q.y - p.y)) / d },
        r = { m.x + (h * (q.y - p.y) / d),
            m.y - (h * (q.x - p.x)) / d },
        s = { m.x - (h * (q.y - p.y) / d),
            m.y + (h * (q.x - p.x)) / d };

    return {r, s};
}

int main() {
    int N;
    cin >> N;

    vector<vector<double> > adj(N, vector<double>(N));

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }

    vector<Point> ps(N);

    for(int i = 0; i < N; i++) {
        if(i == 0) ps[i] = {0.0, 0.0};
        else if(i == 1) ps[i] = { adj[0][1], 0.0 };
        else if(i == 2) {
            vector<Point> is = intersections(ps[0], ps[1], adj[0][2], adj[1][2]);
            if(is.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            ps[i] = is[0];
        } else {
            vector<Point> first = intersections(ps[0], ps[1], adj[0][i], adj[1][i]),
                second = intersections(ps[1], ps[2], adj[1][i], adj[2][i]);
            if(first.empty() || second.empty()) {
                cout << "Invalid" << endl;
                return 0;
            }
            if(min(dist(first[0], second[0]), dist(first[0], second[1])) < epsilon) ps[i] = first[0];
            else if(min(dist(first[1], second[0]), dist(first[1], second[1])) < epsilon) ps[i] = first[1];
            else {
                cout << "Invalid" << endl;
                return 0;
            }
        }
    }

    for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) {
        if(abs(dist(ps[i], ps[j]) - adj[i][j]) > epsilon) {
            cout << "Invalid" << endl;
            return 0;
        }
    }

    cout << "Valid" << endl;
    for(const Point &p : ps) {
        cout << p.x << " " << p.y << endl;
    }

    return 0;
}

I haven't had time to comment the code. If you want me to, leave a comment. I took your drawing as a sample (which is invalid) and wrote another sample myself:

4
0 10 11 10
10 0 8 11
11 8 0 8
10 11 8 0

Invalid

4
0 4 5 3
4 0 3 5
5 3 0 4
3 5 4 0

Valid
0 0
4 0
4 -3
0 -3

As you can see, a valid configuration is printed if one exists. The complexity of the construction algorithm is $O(N)$, but we need to check if all matrix entries are valid after construction, which is $O(N^2)$.


What is discrete mathematics and why am I learning about it?

Very roughly speaking, Discrete Mathematics is the body of material that a computer scientist needs to know. You can look at it as that part of mathematics which doesn't involve limits, continuity, differentiation, or integration. In set notation, we have Discrete = Mathematics \ Calculus.

The usual topics in a Discrete course and their applications to CS are

Propositional and predicate logic: used to establish the correctness of a program.
Proofs: used throughout CS, for things like establishing the closure properties of, say, regular languages.
Functions: obvious uses, since functions are ubiquitous in CS.
Sets: you can't do much in the theory of databases without them
Relations: again, fundamental for databases and also the basis for algorithms such as topological sorting
Recurrences: lists and trees can be viewed as recursively defined. Also, you can't do much to establish the time or space complexity of algorithms without being conversant with recurrence relations
Graphs and trees: when establishing the properties of networks
Counting: again, fundamental for the design and analysis of algorithms
Probability: for example, finding the average time complexity of an algorithm

Obviously, I've left out many more uses, but you get the idea. One could make the point that essentially all of CS beyond Programming I uses the concepts of Discrete in one way or another.


Why aren't recognizable languages and co-recognizable languages not reducible to each other?

Suppose that $L_1$ is recognizable, $L_2$ is co-recognizable, and there is a computable reduction from $L_1$ from $L_2$. The computable reduction shows that $L_1$ is also co-recognizable, and so decidable.

We conclude that if $L_1$ is recognizable but not decidable, then it cannot be reduced to any co-recognizable language.


Don't expand the squared terms; it'll just add confusion. Think of the recurrence as
$$
T(\fbox{foo}) = T(\fbox{foo}-1)+\fbox{foo}\;^2
$$
where you can replace foo with anything you like. Then from
$$
T(n)=T(n-1)+n^2
$$
you can replace $T(n-1)$ by $T(n-2)+(n-1)^2$ by putting $n-1$ in the boxes above, yielding
$$
T(n) = [T(n-2) + (n-1)^2]+n^2 = T(n-2)+(n-1)^2+n^2
$$
and similarly
$$\begin{align}
T(n) &= T(n-2)+(n-1)^2+n^2\\
     &= T(n-3)+(n-2)^2+(n-1)^2+n^2\\
     &= T(n-4)+(n-3)^2+(n-2)^2+(n-1)^2+n^2
\end{align}$$
and in general you'll have
$$
T(n) = T(n-k)+(n-k+1)^2+(n-k+2)^2+\dotsm+(n-1)^2+n^2
$$
Now if we let $k=n$ we'll have
$$
T(n) = T(0)+1^2+2^2+3^2+\dotsm+n^2
$$
Now if you just need an upper bound for $T(n)$ observe that
$$
1^2+2^2+3^2+\dotsm+n^2\le \underbrace{n^2+n^2+n^2+\dotsm+n^2}_n=n^3
$$
so we conclude that $T(n)=O(n^3)$, in asymptotic notation.

For a more exact estimate, you can look up the equation for the sum of squares:
$$
1^2+2^2+\dotsm+n^2=\frac{n(n+1)(2n+1)}{6}
$$
so
$$
T(n)=T(0)+\frac{n(n+1)(2n+1)}{6}
$$


Meaning of the "why not" modality from linear type theory?

First off, one thing I'd recommend is reading Filinski's Linear Continuations for ideas on how to interpret linear connectives (note, the ? modality got typeset as Γ in that for some reason).

In that paper, he uses the modality as part of the interpretation of call-by-name into linear logic. The idea is that you can kind of think of the non-modal types $T$ as being total, while $?T$ adds the possibility of divergence. If you want an analogue of "infinitely many copies of $T$", then it's, "zero or one $T$".

But of course, it's not like $1 + T$. It's more like a partiality monad living in an otherwise total language.


Morioka considers uniform versions of his circuit classes:

  Throughout this paper we write $\mathbf{NC^1}$ to mean $\mathbf{Dlogtime}$-uniform $\mathbf{NC^1}$, which is equivalent to the class $\mathbf{Alogtime}$ of languages accepted by an alternating Turing machine in $O(\log n)$ time.

The paper you mention should imply the equivalence of these two definitions. The statement you quote, however, is just true by definition.


Why the given statement can't be expressed using predicates and quantifiers in the way described in details?

Rephrasing that second version back into English:

  There exists a person $x$, such that if $x$ is a student, then $x$ has gone to Mexico.

If there exists anyone who's not a student, this ends up being true. "If false then [anything]" is always true, so when "$x$ is a student" is false, "if $x$ is a student, then $x$ has gone to Mexico" is true—whether or not $x$ has gone to Mexico.

What you want is:

  There exists a person $x$, such that $x$ is a student, and $x$ has gone to Mexico.

That is indeed what the first given solution means.


I suspect the answer is that in general $\phi'$ might need to be of exponential size, but I am not certain.  There are known examples of a boolean circuit $C$ (with negations) of polynomial size that computes a monotone function, while the smallest monotone boolean circuit $C'$ (with no negations) has exponential size.  See http://www.cs.cornell.edu/~eva/Gap.Between.Monotone.NonMonotone.Circuit.Complexity.is.Exponential.pdf and Simple example of exponential gap between monotone and non-monotone circuits.  It's possible that perhaps this could be extended to an argument that covers your case as well: if there is a polynomial-size formula $\phi$ corresponding to $C$ (this would need to be checked), the results above imply that any monotone formula $\phi'$ computing the same function would need to be of exponential size, so there would necessarily be an exponential gap for some functions, no matter what set of substitution rules ("biconditionals") you use.  The gap in this argument is verifying whether Tardos's example can indeed be computed by a polynomial-size circuit; it's not clear whether it can, as circuits are more powerful than formulas, and I haven't verified this, but perhaps you can do so.


Where do the length restrictions of the pumping lemma come from?

The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ trivially and always holds.

The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.

But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that all valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there has to be a pumpable decomposition with $|xy| \leq p$ with constant $p$.

Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.


Why does an inverted page table keep a chain of pages per frame when it can only store one of such pages?

Hash functions can have collisions, and you need to resolve the collisions.  If two (PID, page_number) pairs map to the same row, only one can be stored there, and you need to have a mechanism to find the other one.
You can use page tables to map multiple virtual addresses (pages) to the same physical address (frame).  For instance, this may be used to support shared memory, copy-on-write, on-demand zeroing for memory allocation, and more.


Is subset sum with a fixed target sum NP-complete?

We can throw away all zeroes in $A$. If a subset of $A$ sums to $10$, then this subset contains at most $10$ elements. There are at most $10|A|^{10}$ such non-empty subsets, so we can go over all of them in polynomial time.


What are good resources for self teaching parallel/concurrent/multithreaded programming techniques?

IMHO the best way to learn parallelism/concurrency is to learn how it is done in FP languages and then look for the ways to do the same in {your beloved one}. My own list:

Communicating sequential processes and Communicating Sequential Processes (CSP), by C. A. R. Hoare (PDF Version)
Erlang and books on Erlang/OTP
Parallel and Concurrent Programming in Haskell
Structured Parallel Programming Book


Without multi-line statements, it's rather simple; assuming line is the non-terminal for well-formed line, change its right-hand-side appearances to

line (# .*)?

(borrowing regular expression syntax for brevity).

Otherwise, if you explicitly handle line breaks, replace occurrences of the line-break token CRLF (or so) similarly by

(# .*)? CRLF

If line breaks remain implicit, one chance you have left is make it part of the lexer; don't only skip whitepace, but also (# .*)? [\r\n]. You can also create a token COMMENT for that and place it in all places of the grammar where it may appear. This strategy doesn't work for nested multiline comments, though, a common problem in older languages.


Find maximum distance between elements given constraints on some

What you describe is a linear program. You can use the following formulation:

Let $x_i$ be the $i$th element. The variables are $d_1,\ldots, d_{n-1}$, where $d_i$ denotes difference between $x_{i+1}$ and $x_i$. You require $d_i\ge 0$.

If two elements $x_i,x_j$ should be at least within some distance $\ell^-_{ij}$, then you set
$$ d_i+d_{i+1}+\cdots +d_{j-1} \le \ell^-_{ij}.$$
If they should be at least $\ell^+_{ij}$ away from each other you set
$$ d_i+d_{i+1}+\cdots +d_{j-1}  \ge \ell^+_{ij}.$$
Then maximize the objective function $\sum_{i=1}^{n-1} d_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.


An $\mathbb F$-algebra as input to an algorithm

This seems to be consistent with the presentation in Equivalence of $\mathbb{F}$-algebras and cubic forms, Agrawal & Saxena (2006).


Forward checking vs arc consistency on 3-SAT

Both forward checking (FC) and arc consistency (AC) are methods of inference. Regardless of the problem you are solving, choosing a specific method of inference is always a tradeoff. Basically, the more you are willing to pay in terms of time, the more you gain in terms of strength of inference. So yes, it is faster to perform forward checking than arc consistency, but arc consistency is more effective at pruning the search space. If you are willing to pay even more, there are even stronger forms of consistency. The book by Russell & Norvig gives a nice, quick introduction.

Both FC and AC are relatively cheap and easy to implement, too. The suitable choice depends on the specific structure of your problem. I think at least in general, it is best that you experiment with both.


Is $n$ times $O(1)$ equivalent to $O(n)$?

Think in terms of the definition: $f(m)=O(g(m))$ means that there exists some constants $c>0, M\ge 0$ such that $f(m) \le c\cdot g(m)$ for all $m\ge M$ so when you write
$$
\sum_{i=1}^nO(1)
$$
you mean that there are $n$ functions, $f_1, f_2, \dotsc, f_n$ and constants $c_1, c_2, \dotsc, c_n$ such that $f_i(m)\le c_i\cdot1$ for all sufficiently large values of $m$. Your sum then is
$$
\sum_{i=1}^nO(1)=\sum_{i=1}^nf_i(m)\le \sum_{i=1}^nc_i\le \max_{1\le j\le n}\{c_j\}\cdot n
$$
for all sufficiently large $m$. The problem here is, as Hendrik and babou pointed out, the $\max$ term is a function of $n$. For instance, if $f_i(m) = i$ were constant functions, individually they are all in $O(1)$ but their sum
$$
F(n) = \sum_{i=1}^nf_i(m)= \sum_{i=1}^ni = \frac{n(n+1)}{2}\notin O(n)
$$
The constants are not the only problem here, though, even if we restricted them all to be bounded by some constant $K$. Suppose we had defined the functions $f_i(m)$ to be
$$
f_i(m) = \begin{cases}
2^i & \text{if $m<i$}\\
1 & \text{if $m\ge i$}
\end{cases}
$$
Now each $f_i(m)\in O(1)$, since for each of them we could find a $c_i>0,M_i\ge 0$ such that for all $m\ge M_i$ we have $f_i(m)\le c\cdot 1$ (just pick $c_i=1$ and $M=i$ for instance).

In this case, we also don't have $F(n)\in O(n)$: even though all the $c_i = 1$
we can't now find a fixed N so that $F(n)\le Kn$ for all $n\ge N$, since we chose the functions $f_i$ so that the "crossing point", $M_i$, is a moving target. No matter what $N$ you pick, there will be a point where beyond $N$ the sum will be larger than $Kn$.

It seems that the best you can say is that $F(n)=O(n)$ when all of the $c_i$ are less than or equal to a single fixed bound and the same holds for all the $M_i$. Useful in some cases, I suppose, but woefully wrong in general.


How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?

Your answer to question 1 is nice and correct.

On question 2, of course, you can use a single word $w$ to test the grammar $G$. However, it is not enough to use just one word, since the grammar could be ambiguous on another word.
Well, we can use all words to test the grammar.
Here is the high-level description of a Turing machine $R$ that recognizes $K$.

Loop through all words:

for each word $w$, try every derivation in $G$ of length $2|w|−1$.
If two derivations generate $w$ stop the machine and accept $G$.

There are many ways to loop through all words. For example, we can fix an arbitrary order of all terminals and iterate by short-lexicographic order.
Note that when $G$ is not ambiguous, $R$ will run forever. That means $R$ is not a decider for $K$. In fact, no Turing machine can decide $K$ since $K$ is undecidable.


You have a dataset with at least billions of entries, whose size is that of a medium-sized hard disk. This is large. If something takes only “many hours” and not many months, that's as good as you can expect.

Sorting the file is a viable strategy to get rid of the duplicates. You'll also need to canonicalize the pairs. If you stick with a flat file, the most likely strategy is to do a pass of canonicalization where you define an order relation on the IDs and swap the pairs if the larger ID comes first. For the canonicalization step, you can use awk or a custom C program. For the sorting step, use sort, which is (at least on Linux) capable of doing external sorts and is likely to be faster what you'd come up with. Do this in a C locale to make processing faster (based on bytes rather than multibyte characters).

If you want to do lookups, a terabyte-sized flat file is not the right format. This is large even for a database. On the topic of databases with billions of records, read Can MySQL reasonably perform queries on billions of rows? and Which database could handle storage of billions/trillions of records?. A database may or may not be adequate for your task — this depends if the pairs are all you have or if there's other data to consider, and on whether there's structure to the IDs. I think a database would be the right tool if you want to support queries like “list the pairs that contain this ID value”. You should ask database professionals, rather than computer science professionals, whether and which database would be suitable; be sure to explain the structure of your data and what kind of queries you'll want to make. If you decide to use a database, there's no need to remove duplicates or canonicalize entries before importing them, that will happen on the fly.

If you determine that you aren't going to benefit from a database, then you should organize your data in a structured way. The best structure depends on the density of the data, i.e. how many of the potential pairs are present, how many of the potential IDs are present, the distribution of IDs, etc. Here's an example of the kind of structure that might work:

A toplevel directory determined by the first two characters of the first pair.
A second-level directory determined by the next two characters of the first pair.
In these directories, a file per first ID, named with the first ID and containing the list of second IDs.

This is just an example — you need to find a repartition that works. With typical Linux filesystems, aim for about 100–1000 entries per directory (i.e. 100–1000 toplevel directories, 100–1000 subdirectories in each directory, 100–1000 file in the deepest directories).

There's no need to remove duplicates before moving the data into a structured file set like this. You may want to do a pass of canonicalization first (or do it on the fly).

If you're going to make a lot of queries and you expect many of them do come up negative, build a Bloom filter. Define a fast hash function on pairs whose output is $N$ bits, and write an array of $2^N$ bits to a file where the nth bit indicates whether there exists a pair whose hash is $n$.


Is there a term for the common semantics of global variables, static local variables, and fields?

One standard term is "shared mutable state".

Let's unpack that.  "State" is any place to store data: e.g., a variable or object.  "Mutable" means that the data can be modified.  "Shared" means it is shared among multiple threads.  Thus, shared mutable state is state that is visible to multiple threads and can be modified by multiple threads.

Usually, immutable state is not a concern: even if it can be read by multiple threads, no one can write to it, so there is no potential for data races or concurrence problems.

Usually, non-shared state is not a concurrency concern: there's only a single thread that can read or write it, so we don't have to worry about concurrency -- merely single-threaded-correctness.

Note that this also helps clarify how we should think about a case that wasn't mentioned in your original question.  What about state that can only be written by a single thread, but can be viewed by multiple threads?  That's shared mutable state.  And that's exactly the right classification, because such state can cause concurrency problems: if you're not careful, it can cause data races and other issues, so it's only right that it be lumped together with other kinds of shared mutable state.

(For instance, in your question you write that "local variables... are not subject to modification by other threads during the execution of a method".  This is true, but it doesn't go far enough.  The relevant fact about local variables is that they can't be modified or read by other threads.  Also, this highlights that not all local variables qualify: for instance, if you take the address of the local variable and pass that pointer to another thread, the local variable now becomes shared mutable state and is a concurrency problem.)


What does it mean when a time complexity has another time complexity within it?

This is somewhat informal, and to figure out what it means, just parse it inside-out:

$f(n)$ is $O(1)$ means, as usual "$\exists c, n_0: f(n) \leq c$ whenever $n \geq n_0$".
$f(n)$ is $n^{O(1)}$ is meant to mean "$f(n)$ is of the form $n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c, n_0: f(n) \leq n^c$ whenever $n \geq n_0$.
$f(n)$ is $O(2^k \cdot n^{O(1)})$ means "$\exists c, n_0: f(n) \leq c\cdot 2^k\cdot n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c_1, c_2, n_0: f(n) \leq c_1 \cdot 2^k\cdot n^{c_2}$ whenever $n > n_0$.

Note that you cannot simply replace the internal $O(1)$ with any fixed constant. You know that a suitable constant does exist, but its value is left unspecified.


Proving closure under complementation of languages accepted by min-heap automata

Claim: $\mathrm{HAL}$ is not closed against complement.

Proof Idea: We have agreed that $\mathrm{EPAL}$ (the language of even palindromes over a non-unary alphabet) is not in $\mathrm{HAL}$. We show that $\overline{\mathrm{EPAL}} \in \mathrm{HAL}$.
This works for type-1 only (as type-2 can accept $\mathrm{EPAL}$); the proof can be adapted to suit type-2 though, see below.

Proof: Note that

$\qquad \displaystyle \begin{align*}
  \overline{\mathrm{EPAL}} &= \{vw : |v|=|w|, v\neq w^R\} \\
                           &\cup\ \,\{w : |w| \in 2\mathbb{N}\!+\!1\}
\end{align*}$

We construct a min-heap automaton with two heap symbols $b < a$ that works like this:

In the starting state, decide nondeterministically wether the input's length is even.
On the uneven path, use finite control to accept the input if and only if its length is odd.
On the even path, proceed like this:
$$ \underbrace{v_1\ \dots\ \mathbf{v_{i}}}_{+a}\ \underbrace{v_{i+1}\ \dots\ v_n}_{+b}\ \underbrace{w_n\ \dots\ w_{i+1}}_{-b}\ \underbrace{\mathbf{w_i}\ \dots\ w_1}_{-a}$$

Start by adding one $a$ to heap for every read symbol.
At a nondeterministically determined position, store the current symbol in finite control and start adding one $b$ (and no $a$) to heap for every read symbol.
At a nondeterministically determined position, stop adding symbols and consume one $b$ per input symbol.
When all $b$ are consumed, compare the current symbol with the one stored in control. If they are unequal, continue; else reject the input.
Consume one $a$ per input symbol. If the heap is empty at the same time the input ends, accept the word; reject otherwise.

The described min-heap automaton accepts $\overline{\mathrm{EPAL}}$. As its complement, $\mathrm{EPAL}$, is not in $\mathrm{HAL}$, we have proven the claim.

Note: The proof can be performed in the same way with $\{ww \mid w \in \{a,b\}^*\}$ (which is in $\mathrm{CSL} \setminus \mathrm{HAL}$) and its complement. This extends above result to type-2.


Daniel Rasmussen replied via email:

  SNNs take less long to train

  This really depends on the training method, and the implementation.
  If you just implemented an abstract DNN approach to solve the same
  task as is being solved in those NEF RL papers, it would be a pretty
  simple network and would train quite fast (almost certainly faster
  than with the simple PES rule).  On the other hand, if you recreated
  the internal structure of the SNN model, and trained it using a DNN
  approach (e.g., using something like nengo_deeplearning), I suspect
  that that would never converge to something useful.  So overall it's
  hard to say something useful to compare them in this sense, but I
  think if you had to commit to something, the DNN training methods are
  probably more efficient than SNNs.

  SNNs can be deployed on existing neuromorphic hardware

  Yep

  SNNs are more easily extended into continuous cases

  I'm not sure if this is true.  It is true that there aren't a lot of
  examples of people doing continuous state processing with DNNs, but
  that's also true of SNNs.  I'm not sure it's any easier or harder for
  DNNs than SNNs (it's just harder than the discrete case in both
  paradigms).

  SNNs do more inference between states

  Again, don't think this is true in general, it'll all depend on how
  things are implemented.

  DNNs can map larger and higher dimensional state spaces

  Also depends on the implementation, but it is true that DNNs tend to
  be more computationally efficient than SNNs (because they're not
  incorporating all those biological features).

  DNNs require less knowledge of the task for the programmer

  Not categorically true, but probably true in most cases.


One option is to reduce your problem to Longest Common Subsequence. I'll let you figure out how.


I suppose the file is too large to fit in the main memory at once. In this case a basic solution is to divide the file into small enough parts so that you can sort each part individually in memory using any standard sorting algorithm. You can then merge the parts by placing a pointer to the start of each file and repeatedly advancing the pointer with the smallest element, collecting the elements into one big sorted file (you can keep track of the minimum using a heap data structure). This is called a $k$-way merge, where $k$ is the number of parts. If the heap does not fit into the main memory, then we can merge just $k' < k$ files at a time, and then merge $k'$ of the merged files at a time, then merge $k'$ of those, and so on, until only one file remains.

I think this is more or less what the Linux sort command does for large files. It can also handle keys consisting of multiple columns. Check the manual of the program for the details.


Recurrence relation for the number of "references" to two mutually recursive function

It looks like that you are exhausted after a long and tiring journey that you have taken to comprehend the setup of assembly-line scheduling, the step 1 on the structure of the fastest way through the factory and the step 2 on a recursive solution.
It is straightforward to understand formula (4) and (5).
When we program a recursion solution using formula (1), (2) and (3), the left-hand side of each formula is transformed to the signature of its implementing method while the right-hand side is transformed to the body of the method.
For example, (3) is transformed to pseudo-Python code
def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

So, when $f^\star$ is referenced, i.e., when f_star is called, $f_1[n]$ and $f_2[n]$ will be referenced, i.e., f_1(n) and f_2(n) will be called, where f_1(.) and f_2(.) will be explained below. Since we will call f_star(n) once, which is enough to get the value of $f^\star$, we get formula (4).
Formula (1) is transformed to pseudo-Python code
def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

So whenever $f_1[j]$ is referenced, i.e., when $f_1(j)$ is called, $f_1[j-1]$ will be referenced exactly one, i.e., f_1(j-1) will be called exactly once.
Similarly, whenever $f_2[j]$ is referenced, $f_1[j-1]$ will be referenced exactly once. (You can write the function f_2(j) explicitly yourself to check it out.)
Note that any reference to $f_1[j-1]$ must be brought by either a reference to $f_1[j]$ or a reference to $f_2[j]$. So we have
$$r_1(j-1) = r_1(j) + r_2(j).$$
Similarly or by symmetry, we also have
$$r_2(j-1) = r_1(j) + r_2(j).$$
Replacing $j$ by $j+1$, we get formula (5).


Why is a Tree a concrete data structure and not abstract?

An abstract data type (ADT) is an interface: it describes the operations that can be performed and what their externally visible behavior should be.  There are typically many possible ways to implement that interface.

A data structure is an implementation of such an interface: it provides code or fully specifies the internal behavior.

A binary search tree is not an ADT; it specifies more than a list of supported operations (like insert, find) but also how they can be implemented (by a particular data structure in the shape of a tree).  A heap is not an ADT; it specifies more than a list of supported operations (extract-min, insert), but also how those operations should be implemented (by storing the elements in an array in a particular way and manipulating them in a specific fashion).

See also https://en.wikipedia.org/wiki/Abstract_data_type.


reinforcement learning in gridworld with subgoals

The subgoals are encoded in external rules to determine if a reward is given and in what amount. The creation of the rules and the used features is done manually by experts. There is no algorithm which calculates the reward function by itself.


No.  This is as hard as factoring, and there is no known efficient algorithm for factoring.  In particular, there is a standard reduction to show that if you could compute Euler's totient function efficiently, then you could factor efficiently.


Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?

In classical logic it is possible to define a function which is not computable, and $UC$ is such a function. What probably confuses you is that you think that a function must always be given in a symbolic form, or as a set of instructions on how to compute it, or some such. But this is not necessary. Officially a function $f : A \to B$ is the same thing as a subset $F \subseteq A \times B$ satisfying the functionality condition:

  For every $x \in A$ there is exactly one $y \in B$ such that $(x,y) \in F$.

We may apply this to our situation to define $UC$ as the set of pairs
$$UC = \lbrace
((\alpha, x), d) \mid
(\text{$M_\alpha$ halts on $x$ and $d = 1$})
\lor
(\text{$M_\alpha$ does not halt on $x$ and $d = 0$})
\rbrace.$$
Even though nobody told us how to discover the output $d$ for a given input $(a, x)$, it is still the case that for every $(a,x)$ there is exactly one $d$. Indeed, if there were more than one then we would have a machine $M_\alpha$ which both halts and does not halt on input $x$. And if there were no such $d$, that would mean we have a machine $M_\alpha$ which neither halts nor not halts on input $x$.

In constructive logic one cannot define a non-computable function. And neither can one show that all functions are computable. So there $UC$ would not satisfy the functionality condition, and it would only define a partial function. But we could still talk about the fact that the Hlating problem is not decidable because the same classical argument still applies (we just avoid talking about $UC$). Assume there is a Turing machine $H$ such that:

$H$ halts on every input.
If $M_\alpha$ halts on $x$ then $H$ on input $(\alpha, x)$ outputs $1$.
If $M_\alpha$ does not halt on $x$ then $H$ on input $(\alpha, x)$ outputs $0$.

We now proceed with the usual diagonalization argument and construct a machine $B$ with a code $\beta$ such that $B(\beta)$ halts if, and only if, $H(\beta, \beta)$ outputs $0$. Everything here is perfectly constructive. I only took care never to assume that every machine either halts or not (such an assumption is implicit in the definition of $UC$).

So perhaps you should stick to constructive mathematics, and there will be fewer surprises for you.


Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

If $W \ge n \cdot P$ you can add all elements in the knapsack.
Otherwise $W < n \cdot P$ in which case any algorithm with complexity $O(n W)$ will also have complexity $O(n \cdot (nP)) = O(n^2P)$. In particular the pseudo-polynomial dynamic programming solution described in Wikipedia works in $O(n W)$.


Why is the halting problem unsolvable by a turing machine?

It can be proved that the halting problem cannot be solved by any Turing machine. There are several question regarding this on this side which you can look up.

It is not true that humans can determine if a given Turing machine halts. For example, we have been unable so far to compute many values of busy beaver functions, which measure the maximal number of steps a halting Turing machine can run given the number of tape symbols and number of states.

According to the Church–Turing thesis, every machine can be simulated by a Turing machine. So DNA computers, quantum computers and the like will not help. All they can do (especially the latter) is to dramatically speed up computation, but they cannot help computing non-computable functions.

There is a field known as hyper-computation which studies machines stronger than Turing machines, but these are not believed to be realizable by most practitioners. Recursion theory explores such models from a more theoretical perspective.


What Measure of Disorder to use when Analysing Quicksort

Lomuto vs Hoare
Lomuto partition suffers when sorting equal keys, whilst Hoare partition does not.
Both partition schemes suffer equally when using a pivot distant from the median.

Measure of disorder
The measure of disorder to choose for the purposes of quicksort is simple.
A: How far removed from median is the fixed pivot, compared to random data?
If you insist on using Lomuto partition and if you assume duplicate values are allowed you need to add the following test against randomness:
B: How many duplicate elements are there, compared to random.

Of course it is rather silly to assume that duplicate values are allowed in your data set and still evaluate Lomuto partition, so you should probably either eliminate duplicates beforehand or switch to Hoare partition or assume duplicates are rare.

Both measures are trivial to quantify using statistics.

We can rule out pathological data
Any other deviations from randomness will not matter for the purposes of analysing quicksort. As long as the pivot is close to the median it will perform well on all data that is not pathological.
The distance from random would have to be great indeed to be quicksort-pathological, so we can rule that out.

Never use any fixed pivot(s) in real code
Do note that if you write real code with a fixed pivot*) (whatever that pivot may be) you are opening yourself up to a denial of service attack, because an attacker can insert a pathological value at just that point and thus you should always choose a random element as pivot.

*) or multiple pivots if you choose best of x pivots.


Can an intersection of two context-free languages be an undecidable language?

Context-free languages are decidable, and decidable languages are
closed under intersection.

So, though the intersection of two CF languages may not be CF, it is decidable.

Remarks on your example:

$\emptyset=\{\}\neq$ $\{0\}$
$L_1\cap\emptyset=\emptyset$  which is context-free.
You cannot prove your claim, because it is wrong
the empty language is decidable: the answer is always "no, this string is not in the empty set".


List of intro TCS books for those who don't know much about TCS

If you would like to have a general introduction without getting to deep into the technical details, I suggest David Harel's Algorithmics: The Spirit of Computing. After that, this is my favorite list:

Michael Sipser's Introduction to the Theory of Computation: the best introduction to automata theory, computability and complexity.
Algorithms by  S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: the most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
Jon Bentley's Programming Pearls: this is not a textbook on algorithms, but it demonstrates beautifully how to use algorithm design techniques to solve real problems that irritated real programmers. :-) This might be a good start if you have some pre-knowledge on programming.


What's the complexity of Spearman's rank correlation coefficient computation?

You have to compute

two averages,
$2n$ differences,
three sums with $n$ summands -- which can be computed in constant time -- each and
one division, one multiplication and one square root.

All of this can be done in linear time if we assume elementary arithmetic operations run in constant time, therefore total time in $O(n)$ is certainly possible. Note that computing the root might screw things up.

Regarding space, you have several options:

Store only the averages, that is two numbers ($O(\log M)$ with $M$ the maximum number). You have to recompute all differences, that is perform a total of $6n$ subtractions.
Store the average and the differences, that is $2n+2$ numbers ($O(n \cdot \log M)$). This saves you $4n$ subtractions.

Which is preferable depends on your context.


In Probabilistic Graphical Models, are Cliques and Clusters the same?

A clique is a rigorously defined, exact part of a graph $G=(V,E)$;

$\qquad\displaystyle C \subseteq V \text{ is clique} \iff \{ \{u,v\} \mid u,v \in C, u \neq v \} \subseteq E$.

A cluster is more general, but also more nebulous. Here's what Wikipedia has to say:

  Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So, a cluster also is a set of nodes that is "dense" in some sense, depending on the metric used. However, while is it always clear whether adding a note increases the size of a clique, it's not always clear from looking only at one cluster whether adding a node to it is better; the quality of a clustering is defined on the whole graph.

As the Wikipedia article shows, there are many notions of clustering. Cliques can be seen as one of them.


3 dimensionnal matching to partition transformation

What they actually do is a composition of two reductions (and some optimization). The first is from 3DM to SUBSET-SUM, and the second is from SUBSET-SUM to PARTITION. For the first part, I have it written down here, and the second reduction is quite well known, e.g. here.

Note that there is a small caveat in the first reduction, where we assume that the numbers are encoded in base $|X|+1$, while SUBSET-SUM requires the numbers to be in binary. The reduction you mention does the conversion explicitly, which accounts for the strange $p$ you encountered (which is just the base-conversion constant).


What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?

Here are five remarks that might be helpful to you:

The current belief is that, despite the exponentiality of the wavefunction, quantum mechanics will not let us solve NP-complete problems in polynomial time (though it famously does let us solve certain "special" NP problems, like factoring and discrete logarithms).  The basic difficulty is that, even if a solution to an NP problem is "somewhere" in the wavefunction, that isn't useful if a measurement will only reveal that solution with exponentially-small probability.  To get a useful quantum algorithm, you need to use quantum interference to make the correct answer observed with high probability, and it's only known how to get an exponential speedup that way (compared to the best-known classical algorithm) for a few special problems like factoring.
The action principle doesn't imply that Nature has any magical minimization powers.  The easiest way to see that is that any physical law formulated in terms of the action principle, can also be formulated in terms of the ordinary time-evolution of a state, without reference to anything being minimized.
If P=NP, then certainly NP-complete problems can be solved in polynomial time in the physical universe, since universal Turing computers exist (you're using one now).  However, the converse direction is far from obvious!  For example, even if you assume P≠NP, it's still logically possible (if very unlikely) that quantum computers could solve NP-complete problems in polynomial time.
The mere assumption that there are some problems that we can't solve efficiently, certainly doesn't imply that NP-complete problems have to be among those problems!  (Maybe it will turn out that quantum gravity lets us solve NP-complete problems in linear time, but the PSPACE-complete problems still take exponential time... :-D )
For whatever it's worth, my money is firmly on the conjecture not only that P≠NP, but also that NP-complete problems are intractable in the physical universe---using quantum computers, analog computers, "black hole computers," or any other resource.  For more about my reasons why, you might enjoy my old survey article NP-complete Problems and Physical Reality


Proving Undecidability with reductions - Why do some proofs not use an Oracle?

An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.
What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ solving a problem that can't be solved - hence $M$ doesn't exist.


Get all factors of a word in linear time or constant time

No, there's no faster way to calculate all the "factors" (substrings) of $w$.  It takes $\Theta(|w|^2)$ space even to write down the list of all factors.  Any algorithm has to spend at least 1 unit of time per character of output.  So, any algorithm will have to take $\Omega(|w|^2)$ time; you can't do better than $O(|w|^2)$ time.

If you want to look for a faster algorithm, you'll need to look for a way to do it that doesn't involve calculating and storing all possible factors.  You might want to think about what operations you need to perform on these factors, and whether there's any data structure that can help you perform those operations faster (maybe a Merkle hash tree?  maybe a rolling hash?  hard to know, without knowing what you're trying to do with the factors).


Behavior of non-deterministic Turing Machines after $t_i$ seconds

There are no seconds of execution, you might want to use steps instead.
Non-deterministic Turing Machine does not behave randomly at all, so two machines $\mathcal M_1$ and $\mathcal M_2$ (being copy) are identical, they do not in any random way pick the steps, so the simulation on the first one goes like on the second one. At any time after the same number of steps the tape content matches and the current state matches.

In sny transition there might be more than one rule, the NDTM accepts when one of the paths accepts, but these are executed in copied machines. This effectively may mean that the NDTM have "guessed" the next step (counting steps to the accepted path is the shortest possible one if such exist) but it will always be the same one for given configuration. Please note that if you imagine every step as producing copy of the machine with a different transition taken then these copies might differ.

Please read also the difference between non-determinism and randomness


If you have this array: $[-2,-10,-5]$, and the problem specifies that you should return to it the sum of the maximum subarray whose length is at least $1$, you will return the sum of the subarray $[-2]$, which is $-2$. So far so good?
Now, focus here because this is where you are most probably having trouble:
The problem is now tweaked. The problem now allows you to return to it an empty subarray, which means, you can return to it a subarray that is empty - a subarray that has no elements. Bear with me:
In mathematics, an "empty sum" is a summation where the number of terms is zero. Verify.
Similarly, in computer science, an "empty subarray" is a subarray in which the number of terms is zero. This is just the definition. It's just a subarray whose sum evaluates to zero.
Now, concerning the tweaked version of the problem, what would be better, returning to it $[-2]$ whose sum evaluates to $-2$, or returning the empty subarray $( [ \ \ \ ] )$ whose sum evaluates to $0$?


The opposite is valid.

$3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$.

If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P \neq NP$. So if $P \neq NP$ then $3SAT \notin P$.


PRNG for generating numbers with n set bits exactly

What you need is a random number between 0 and ${ 64 \choose n } - 1$. The problem then is to turn this into the bit pattern.

This is known as enumerative coding, and it's one of the oldest deployed compression algorithms. Probably the simplest algorithm is from Thomas Cover. It's based on the simple observation that if you have a word that is $n$ bits long, where the set bits are $x_k \ldots x_1$ in most-significant bit order, then the position of this word in the lexicographic ordering of all words with this property is:

$$\sum_{1 \le i \le k} { x_i \choose i}$$

So, for example, for a 7-bit word:

$$i(0000111) = { 2 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 0$$
$$i(0001011) = { 3 \choose 3 } + {1 \choose 2 } + {0 \choose 1} = 1$$
$$i(0001101) = { 3 \choose 3 } + {2 \choose 2 } + {0 \choose 1} = 2$$

...and so on.

To get the bit pattern from the ordinal, you just decode each bit in turn. Something like this, in a C-like language:

uint64_t decode(uint64_t ones, uint64_t ordinal)
{
    uint64_t bits = 0;
    for (uint64_t bit = 63; ones > 0; --bit)
    {
        uint64_t nCk = choose(bit, ones);
        if (ordinal >= nCk)
        {
            ordinal -= nCk;
            bits |= 1 << bit;
            --ones;
        }
    }
    return bits;
}

Note that since you only need binomial coefficients up to 64, you can precompute them.

Cover, T., Enumerative Source Encoding. IEEE Transactions on Information Theory, Vol IT-19, No 1, Jan 1973.


Finite / Infinite Languages True/False and why?

False. There are infinitely many finite language. Just think of {0,1}*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length.
False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well.
False. Lets have a single state NFA having state q0. let 'd' be the transition function. d(q0, a) = q0 and since this is single state NFA, q0 is also final state.
This NFA will accept all strings having only 'a'. i.e. {a,aa,aaa,aaaa...} The cardinality of this set is infinite, hence it can accept infinite languages too.


How to practically construct regular expander graphs?

If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular.

Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$.
For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$.
Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$.

As an example, the 7-vertex graph in the family is a 7-cycle with vertices numbered sequentially around the cycle; there are self-loops on $6$, $0$, and $1$; finally, there are chords joining $3$ and $5$, and $2$ and $4$.

See https://mathoverflow.net/questions/124708/an-expander-graph  for further discussion and references.  There are lots of more detailed pointers by searching on "expander" at CSTheory, Math.SE, and MO.

As Yuval Filmus points out, the random construction is likely to give better results in general, but of course may not yield an expander (especially for small graphs).


Probability that a leaf with 1 will be selected in game tree evaluation

When you talk about probabilities, you should first decide what is actually random. Note that there are two possible sources of randomness here, the value of the leaves (i.e. were talking about some distribution over the possible inputs), and the random choice of what leaf to evaluate first (i.e. inner randomness of your algorithm).

When we say our algorithm is randomized, we usually mean the latter. The complexity of such an algorithm is considered with respect to the worst possible input. More formally, saying that the algorithm runs in expected time $T$, means that $T=\max\limits_{i\in I}\mathbb{E}\left[T(i)\right]$, where $I$ is the set of possible inputs and $T(i)$ is the running time on input $i$ (which is a random variable, since we have a coin-tossing algorithm). This is a worst case complexity measure, as the probabilistic analysis is done relative to the worst possible input. Here the worst case (conditioning on the output being $1$) is that exactly one leaf evaluates to $0$, and in this case the expected number of evaluations is indeed $\frac{3}{2}$.

The analysis you described corresponds to the former option, i.e. we are interested in average-case complexity, relative to the uniform distribution over possible inputs (so we actually have two sources of randomness here). In this case, conditioning on the output being $1$, you are right to say that the value of a leaf is $1$ with probability $\frac{2}{3}$, which makes the expected running time $\frac{4}{3}$ (where the expectation is taken over the leaves values and the coin outcome).


Conversion from octal numerical system to binary numerical system

Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its base $b$ representation starting from the least significant digit to the most significant digit.

Take base $10$ for example.

$427428$ in base $10$ is $(4,2,7,4,2,8)$.
$427428$ in base $10^2$ is $(42,74,28)$.
$427428$ in base $10^3$ is $(427,428)$.

You can now find an analogy to your problem.

Edit: Proof for the above claim

Let a number $n$ be represented in base $b$ positional system as

$n = (a_{m-1},a_{m-2},\space...\space,a_1,a_0)$ such that $0 \le a_i \lt b \space \forall i\in\{0,1,\space...\space,m-1\}$

where $m$ represents the number of digits $n$ has in the base $b$ representation. We wish to represent $n$ in base $B = b^k$ for some positive integer $k$.

For the sake of simplicity of the argument, let $m$ be a multiple of $k$, i.e. $m = c k$ for some integer $c$. (If $m$ is not a multiple of $k$, the representation of $n$ in base $b$ can be prefixed by $0$'s untill the number of digits are a multiple of $k$)

From the representation in base $b$, we can write $n$ as follows

$n = a_{m-1} b^{m-1} + a_{m-2} b^{m-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space= a_{ck-1} b^{ck-1} + a_{ck-2} b^{ck-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space = a_{ck-1}b^{ck-1} + a_{ck-2}b^{ck-2} + \space ... \space + a_{(c-1)k+1} b^{(c-1)k+1} + a_{(c-1)k} b^{(c-1)k}$

$\space\space\space + a_{(c-1)k-1}b^{(c-1)k-1} + a_{(c-1)k-2}b^{(c-1)k-2} + \space ... \space + a_{(c-2)k+1} b^{(c-2)k+1} + a_{(c-2)k} b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + a_{2k-1}b^{2k-1} + a_{2k-2}b^{2k-2} + \space ... \space + a_{k+1} b^{k+1} + a_k b^k$

$\space\space\space + a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0$

We can rearrange the last expression by taking out powers of $b^k$ from each sequence of $k$ terms as follows

$\space\space\space + \{\space a_{ck-1}b^{k-1} + a_{ck-2}b^{k-2} + \space ... \space + a_{(c-1)k+1} b + a_{(c-1)k} \space\}.b^{(c-1)k}$

$\space\space\space + \{\space a_{(c-1)k-1}b^{k-1} + a_{(c-1)k-2}b^{k-2} + \space ... \space + a_{(c-2)k+1} b + a_{(c-2)k} \space\}.b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + \{\space a_{2k-1}b^{k-1} + a_{2k-2}b^{k-2} + \space ... \space + a_{k+1} b + a_k b \space\} . b^k$

$\space\space\space + \{\space a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0 \space\}$

$\space\space = p_{c-1} B^{c-1} + p_{c-2} B^{c-2} + \space ... \space + p_1 B + p_0$

Where, $p_i = a_{(i+1)k-1} b^{k-1} + a_{(i+1)k-2} b^{k-2} \space ... \space + a_{ik+1} b + a_{ik} \space$
$\space\space\forall i \in \{0,1,\space ...\space ,c-1\}$

We can see that this is a representation of $n$ in base $B$ i.e. base $b^k$, with $c$ digits.

$n = (p_{c-1},p_{c-2},\space ... \space, p_1,p_0)$.

For the above to a valid representation in base $B$, $\forall i:\space0 \le p_i \lt B$

We can verify this by finding the maximum value of any of the group of terms in the above expressions.

Since, $\forall i:\space 0 \le a_i \lt b$, maximum value of $a_i$ is $b-1$.

Now we get for any $i$,

$a_{(i+1)k-1}b^{k-1} + a_{(i+1)k-2}b^{k-2} + \space ... \space + a_{i+1} b + a_i$

$= (b-1)b^{k-1} + (b-1)b^{k-2} + \space ... \space + (b-1)b + b$

$= (b-1)(b^{k-1}+b^{k-2}+\space...\space+b+1)$

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

$= b^k - 1 $

which is strictly less than $b^k$ or $B$.

Hence, we prove the claim.


If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

You ask,

  I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$?

There are many things wrong in the implied conclusion.

$O(\_)$ only gives you an upper bound. The true behaviour may be of much smaller growth.
Asymptotics (like $O(\_))$ only give you only something in the limit, that is you can only expect the bound to hold for large $n$.
Since you use $O$ as though it was $\Omega$, note that a (lower) bound on runtime does not necessarily translate into a (lower) bound on recursive calls, each of which may take $\omega(1)$ time.

Similarly, a tight upper runtime bound (which you don't have) may not be a tight upper bound on the number of recursive calls for the same reasons.

You can analyse exactly how many recursive calls you need. Just solve the recurrence

$\qquad\displaystyle
\begin{align*}
  f(0) &= 1,\\
  f(1) &= 1,\\
  f(n) &= f(n-1) + f(n-2) + 1, \quad n \geq 3,
\end{align*}$

which adds up $1$ for every recursive call your program makes. See here for more detail on how you get to such recurrences.

See here how to do that, or use computer algebra. The result is

$\qquad f(n) = 2F_{n+1} - 1$;

insert $n=5$ and you will get $f(n) = 15$.
It's not that surprising that the Fibonacci numbers $F_n$ should show up. Inserting their known closed form, we get

$\qquad\displaystyle f(n) = \frac{2}{\sqrt{5}} \cdot \Bigl( \varphi^{n+1} - (1-\varphi)^{n+1} \Bigr) - 1$

with $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.62$ the golden ratio.
This closed form of $f(n)$ implies

$\qquad\displaystyle f(n) \sim \frac{2}{\sqrt{5}} \cdot \varphi^{n+1} \approx 1.45 \cdot 1.62^n$

since $0< 1 - \varphi < 1 < \varphi$.
We see that the $O(2^n)$-bound is rather loose -- it has exponential absolute and relative error.


Prove that the language of non-prime numbers written in unary is not regular

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.


Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

In parallel computing, the threads can talk to each other and exchange information during the computation. In nondeterminism, the only "communication" between threads is that we compute the OR of all possible computation paths. This is much more limited.

If you simulate nondeterminism by spawning parallel computations for every nondeterministic choice, you need an exponential number of threads for a polynomial time computation. We know how to build parallel machines in the real world, we don't know how to build nondeterministic ones.


What is a formula for the number of strings with no repeats?

This answers the question after the number of repeat-free words per size, implying that the desired quantity even exists.

Definition: Call $w \in \Sigma$ repeat-free if and only if it does not contain a factor $xyx$ with $x \in \Sigma^{\geq 2}$ and $y \in \Sigma^*$.

Claim: For given finite alphabet $\Sigma$ with $|\Sigma| = k$, there are no repeat-free words of length greater than $2k^2 + 1$.

Proof Idea: By pigeon-hole principle. Take a word $w$ of length $2k^2 + 2$ (or a longer word and consider its prefix of this length), i.e. $w = a_0a_0' \dots a_{k^2}a_{k^2}'$. Assume $w$ is repeat-free; that means that $a_ia_i' \neq a_ja_j'$ for all $i \neq j$ (otherwise we had a repeat). Therefore, there are $k^2 + 1$ many pairs of symbols; this contradicts $|\Sigma^2| = k^2$. So $w$ is not repeat-free. $\square$

Note that this is a rough proof: factors $a_i'a_{i+1}$ might create a repeat even sooner.

Notation:

$\Sigma^{\geq k} = \bigcup_{i=k}^\infty \Sigma^i = \Sigma^* \setminus \bigcup_{i=0}^{k-1} \Sigma^i$
"factor" = "subword" = "substring"


Finding farthest item in an array with duplicates

Here's a scheme that does $O(L \lg L)$ preprocessing, and thereafter lets you answer query for the value $x$ in $O(rN \lg L)$ time, where $r$ counts the number of times that $x$ is repeated.  This will be slightly more efficient than the naive algorithm for values $x$ that don't occur too many times in the array, but inefficient for common values.

Here's how.  During preprocessing, we're going to build a map $f$ defined by

$$f(y,i) = \min \{ j>i : A[j]=y \}.$$

Similarly, we're going to build a map $g$ defined by

$$g(y,i) = \min \{j<i : A[j]=y \}.$$

(We'll also build a set of inverted indices that, given $x$, enables us to enumerate all indices where $x$ appears in $A$.)

Note that these maps $f,g$ help us compute the distance function $d$ efficiently.  In particular,

$$d(x,y) = \min \{ f(y,i)-i : A[i]=x \} \cup \{ i-g(y,i) : A[i]=x \},$$

which can be computed with $r$ evaluations of $f$ and $r$ evaluations of $g$.  Consequently, given $x$, we'll be able to find the value $y$ that maximizes $d(x,y)$ using $rN$ evaluations of $f,g$, by simply trying all possibilities for $y$.

We're going to use the preprocessing to arrange things so we can evaluate $f,g$ at an input of our choice in $O(\lg L)$ time.  How do we do that?

Unfortunately, storing $f$ explicitly would take $NL$ space, which is too much.  Fortunately, there is a lot of redundancy in $f$: there are long ranges of indices $i,i+1,\dots,i'$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')$.  This is going to help us represent $f$ more compactly.  Similarly for $g$.

In particular, we'll store $f(y,\cdot)$ as an interval tree: whenever we have an interval $[i,i']$ such that $f(y,i)=f(y,i+1)=\dots=f(y,i')=\alpha$, then we add a single interval to the tree with the mapping $[i,i'] \to \alpha$.  In this way, $f$ is stored as $N$ different interval trees.  It is possible to show that the total number of leaves, across all of these interval trees, is at most $L+N=O(L)$ (in particular, the tree for $f(y,\cdot)$ has at most $r'+1$ leaves, where $r'$ counts the number of occurrences of $y$ in $A$).  If we store these trees as balanced binary trees, their height will be upper-bounded by $O(\lg L)$.  Consequently, the total amount of space needed to store these trees is $O(L \lg L)$.  You can also show how to generate these trees in $O(L \lg L)$ time.  Finally, evaluating $f$ at a point of your choice amounts to a stabbing query in the corresponding interval tree, which takes $O(\lg L)$ time.  This shows how to achieve the time complexity quoted in the first sentence of my answer.

As an optimization, if $x$ appears in $A$ more than $L/(N \lg L)$ times, you can answer the query in $O(L)$ time using a standard linear scan (skipping the above cleverness).  Of course, you can detect quickly which values of $x$ occur that often by using the inverted indices built during preprocessing.

With this idea, we get a scheme that requires $O(L \lg L)$ preprocessing and lets us answer each subsequent query in $O(\min(L, rN \lg L))$ time, where $r$ counts the number of times that the queried value occurs in $A$.


Can LP for matroid polytopes be solved using the greedy algorithm?

You can associate with each matroid two polytopes in $\mathbb{R}^n$, where $n$ is the size of the universe over which the matroid is defined:

The matroid polytope is the convex hull of the characteristic vectors of all independent sets.
The base polytope is the convex hull of the characteristic vectors of all bases (maximal independent sets).

The maximum of a linear function over a polytope is always attained (not necessarily uniquely) at a vertex. Therefore maximizing a linear function over a base polytope is like maximizing it over the collection of bases, for which the greedy algorithm can be used. The same goes for the matroid polytope, with the necessary changes.


This publication provides a definition of prefix monotonicity: link

Definition:

"Prefix monotonicity reflects a basic property of communicating systems: assume we have
observed a finite sequence of output messages for a corresponding finite sequence of input
messages. Then if we observe additional input (thus the old input sequence is a prefix of the extended one) we may just observe additional output (thus the old output sequence is a prefix of the extended one). Prefix monotonicity provides a notion of causality between input and output. It reflects the stepwise consumption of input and production of output and guarantees the existence of least fixed points, which is mandatory for giving meaning to communication feedback loops."


Problems that are Cook-reducible to a problem in NP $\cap$ co-NP

Nice question/homework!

Stated in another way: $\mathsf{NP}$ is not closed under Cook reductions (assuming $\mathsf{P}\neq \mathsf{NP}$).

How about $\mathsf{NP}\cap\mathsf{coNP}$? Is $\mathsf{NP}\cap\mathsf{coNP}$ closed under Cook reductions? Is the only reason that $\mathsf{NP}$ is not closed under Cook reductions is because it is not closed under complement so if we take those $\mathsf{NP}$ problems whose complement is also $\mathsf{NP}$ do we get around the problem?

For example, if we have a Cook reduction from a problem to Factoring, would that mean that the problem is in $\mathsf{NP}\cap\mathsf{coNP}$?

An oracle doesn't just allow us to ask about membership and non-membership in the oracle, it allows us to ask very complicated list of questions where each question can depend on the answer for the previous one.

Let's look at a problem $Q \in \mathsf{P^{NP \cap coNP}}$. We know that there is a polynomial-time algorithm $M$ and a set $A\in \mathsf{NP \cap coNP}$ such that $M^A$ solves the problem $Q$. Is $Q$ in $\mathsf{NP}$?

Hint: when does $M^A$ accept an input $x$?

Don't read the answer below if this is an assignment, the answer is not difficult, you should be able to solve it if you spend a few hours on it, and spending those hours is what makes you learn.

   Let's look at the execution of $M^A$ on an input $x$.
 $M$ will make a number of queries to $A$ during its computation and will receive YES and NO answers, and finally will accept or reject.
 If we could compute that answers to the queries in polynomial time we would have shown that the problem is in $\mathsf{P}$,
 we would simulate the algorithm $M$ and whenever it asked a query from $A$
 we would compute the answer and give to $M$ and continue with its simulation.

 But $A\in\mathsf{NP \cap coNP}$ and we don't know how to compute the answers to queries in polynomial time. But we don't need to do this in polynomial-time! We can just guess the answers to the questions and verify our guesses in polynomial-time. To be able to verify the answers for both positive and negative answers we need $A\in\mathsf{NP\cap coNP}$, that is why this does not work for $A \in\mathsf{NP}$, that would allow only verifying positive answers.

 Let $V_{YES}$ and $V^{NO}$ be two polynomial-time verifiers for membership and non-membership in $A$. Consider the verfier $V(x,y)$ which works as follows:

  I. check that $y$ consists of 1. a string $c$ (computation of $M$ on $x$), 2. a list of strings $q_1,\ldots,q_m$ (queries to the oracle in $c$), 3. a list of strings $a_1,\ldots,q_m$ (answers to queries from oracle), 4. a list of strings $w_1,\ldots,w_m$ (certificates/proofs/witnesses for the correctness of the query answers).
  II. check that the list of queries $q_1,\ldots,q_m$ contains all oracle queries in $c$,
  III. check that the computation $c$ is an accepting computation of $M$ on $x$ if answers to the queries are $a_1,\ldots,a_m$.
  IV. for all $1\leq i \leq m$, check that if $a_i=YES$ then $V^{YES}$ accepts $(q_i,w_i)$ and if $a_i=NO$ then $V^{NO}$ accepts $(q_i,w_i)$.

  All of these steps can be checked in polynomial-time. So we have a verifier for YES answers of $M^A$. Furthermore note that if $M^A$ accepts $x$, then there is $y$ satisfying these conditions which has polynomial-size: the computation of a polynomial-time machine is of polynomial-size and the number of queries and the size of all queries are also polynomial in the input. Moreover the size of certificates for queries are also bounded by some polynomial in the size of the queries, so again are polynomial in the size of input. In short we have a polynomial-time verifier with polynomial-size certificates for $M^A$.

  This completes the proof that $Q \in \mathsf{NP}$. A similar argument shows that $Q\in\mathsf{coNP}$. So $Q\in\mathsf{NP\cap coNP}$. In other words, $\mathsf{P^{NP\cap coNP}} \subseteq \mathsf{NP\cap coNP}$.


AVL Tree or HashTable for storing relatively big data?

For search dominant operation, supported insert, delete, find only there are huge benefits in using the Hash Table.

the memory footprint is low, only colliding entries require pointer, one per entry while AVL requires two pointers per entry.
access time is expected $\mathcal O(1)$, say in the worst case 5, which gives one hash calculation and 5 equality tests while AVL has 25 full comparissons for 120000 entries in the worst case.
rehashing could be avoided with maximal capacity known in advance, otherwise it would be rare operation.

What would opt for AVL?

traversal queries, looking for ranges etc.
access to sorted data.
inexact queries, looking for nearest neighbour (at the cost of additional pointers).

By the way the perfect hash table is commonly refered to as having no collisions, which requires static setting, rehashing. What you refer to is probably dynamic perfect hashing, a two-tier scheme with guaranteed deterministic constant lookup.

If you have all data (or substantial amount) it is beneficial to sort data and create balanced tree to avoid inserting nodes one by one. (Something like DSW algorithm would help).
In that case the hash table may be constructed without collisions at all for initial data, leaving space for future elements and work really fast.

For the search part, none of the structures would help. If I understood correctly, your data is a graph, so both presented structures will help with indexing only and the Hash Table is the winner.

Sidenote:
To store compactly textual data something like Trie or Directed Acyclic Word Graph would be better. The edited part about search would require a graph, path finding algorithm and auxiliary indexing data structure, in your case probably Hash Table or DAWG used as map.


What is the O time complexity for this algorithm?

The upper bound doesn't get affected by inputs b & c so we can say it is $O(1)$.


Edit distance proof when last chars of 2 strings are the same

Let's show that if $s$ and $t$ end with the same symbol, then there is always an optimal solution in which the final letters are left alone. Note that there could be other optimal solution in which this is not the case. For example, if $s = a$ and $t = aa$, then an optimal solution would be to delete the final $a$ from $t$. All we are claiming is that some optimal solution leaves these letters alone.
Instead of deleting letters from $s$, let's add them to $t$. The situation thus looks as follows: starting with $s,t$, we add some letters to both, and change some letters in $s$, so that the resulting strings $s',t'$ coincide.
If the final letters in $s',t'$ were both added, then we can improve the solution by not adding them, so we can assume that this is not the case.
If the final letter in $s'$ resulted from changing the last letter in $s$, then necessarily the last letter in $t'$ was added; we can instead not change the last letter in $s$, and add a different letter in $t'$, improving the solution, so we can assume that this is not the case.
Thus either the last letter in $s'$ is that of $s$, or the last letter of $t'$ is that of $t$, or both; in the latter case, there is nothing to prove. The two remaining cases are symmetric, so let's suppose that the last letter in $s'$ is that of $s$, say $\sigma$, while there is a suffix of $t'$, say $r\sigma$ (it must end with $\sigma$!), which was added after the last letter in $t$, which is also $\sigma$.
Instead of adding $r\sigma$ at the very end of $t'$, we add $\sigma r$ just before the final letter of $t$. In both cases this results in an identical suffix $\sigma r \sigma$, so we have converted the given solution to a solution with identical cost in which the final letters of $s,t$ are left untouched.

Finally, let me comment that the original paper doesn't seem to make this optimization.


First, the change-of-base formula may be helpful here:
$$
\log_b(x) = \frac{\ln x}{\ln b}
$$
Also, with sums I always find it helps to write out the sum explicitly, so let's do that:
$$
T(n) = \sum_{i=2}^{n} \log_i n
= \log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_n(n)
$$

Now if you want to show this is $\theta(n)$, there are two things: you should show it is lower bounded by $cn$, and it is upper bounded by $Cn$, for some constants $c$ and $C$.

For the lower bound, use the fact that each term is greater than or equal to $1$.
For the upper bound, I suggest dividing the sum into two parts: from $i = 2$ to $i = \sqrt{n}$, and $i = \sqrt{n}$ to $n$. So the first part is
$$
\left(\log_2(n) + \log_3(n) + \log_4(n) + \cdots + \log_{\lfloor\sqrt{n}\rfloor}(n)\right).
$$
Here we have $\sqrt{n}$ terms, each which is at most $\log_2(n)$. The second part is
$$
\left( \log_{\lceil \sqrt{n} \rceil}(n) + \cdots + \log_n(n) \right).
$$
Here we have at most $n$ terms, but you can show (using the change of base formula above) that each term is at most $2$.

Now adding up the two parts, you should get an upper bound of
$$
\sqrt{n} \log_2(n) + 2n,
$$
so the final step is to show this is $O(n)$.


What is the complexity of timing a turing machine?

Let S (F, i, n) = the number of steps that F (i) takes until it halts, if it halts in n or fewer steps, and n if F (i) doesn't halt in n steps. Then you can simulate the Turning machine and get the result in O (S (F, i, n)) steps.

If this were important to you, then you could examine a few Turing machines, and see if you can detect patterns in their operation. For example, you might detect a pattern that indicates the Turing machine is trying to add two numbers x and y, and you might be able to analyse how many steps this will take and what state the Turing machine is afterwards; if you do this then you might often get a result in substantially fewer than c * N steps.

Or in your simulation, you might detect that the Turing machine enters the exact same state that it entered before; in that case it won't ever halt.


A microkernel fully hardcoded in hardware?

The key search terms here are FPGA and ASIC, since at this point the OS is no longer running on instructions executed by a CPU in the conventional sense.

Here is a relevant result I found with a quick Google search on microkernel fpga and os kernel fpga:

Susanna Nordström et al. Application Specific Real-Time Microkernel in Hardware.

  In the RTU, the scheduling, inter process communication, interrupt management, resource management, synchronization and time management control are implemented in hardware (using VHDL).

This paper goes a step further and describes an OS-like environment for FPGA programs themselves: Kermin Fleming et al. The LEAP FPGA Operating System.

  Like a software operating environment, LEAP provides both basic device abstractions for FPGAs and a collection of standard I/O and memory management services.


How Data Compression relates to Estimating Distribution?

Suppose that we have a random source $X$, and we wish to encode many independent samples $x_1,\ldots,x_n$ taken from $X$. An compression scheme is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the entropy of $X$.
In practice, we may have access to $X$ but might not know its distribution exactly. What we can do is to estimate its distribution as $Y$, and then use an optimal compression for $Y$. This will produce binary strings of length roughly $n(H(X) + D(X\|Y))$, where $D(X\|Y)$ is the Kullback–Leibler divergence (called cross-entropy by Mahoney). We have $D(X\|Y) \geq 0$, with equality only when $Y = X$. Thus optimal compression requires knowing the distribution of the source exactly.


Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).
Let $\mathcal{A}$ be a given DFA over the alphabet $\Sigma$, and consider the language $PAL\subseteq \Sigma^*$ of the palindrome words. We need to decide whether $L(\mathcal{A})\subseteq PAL$ in polynomial time. Note that $L(\mathcal{A})\subseteq PAL$ iff $L(\mathcal{A})\cap \overline{PAL} = \emptyset$. So we need to decide whether the language $L(\mathcal{A})\cap \overline{PAL}$ is empty, and we do it as follows:
1- Construct a PDA $\mathcal{B}$ for $\overline{PAL}$: this is a well known exercise.
2- Construct a PDA $\mathcal{C}$ for $L(\mathcal{A})\cap \overline{PAL}$: this is also known, and can be done in polynomial time by a product construction of $\mathcal{A}$ and $\mathcal{B}$ (for example, see here).
3- Finally, check whether the language of the PDA $\mathcal{C}$ is empty. This also can be done in polynomial time (see here, or here).


Issue triangulating a font glyph for a specific scenario

The points and control points define a spline curve. Your graphics hardware is usually not capable of handling splines directly, so you convert the spline into a polygon. You'll add enough points to the polygon so that the difference between spline and polygon is negligible. Control points are NOT part of the spline! So adding them to your straight line segments is a massive mistake. Don't do that, and your problem goes away.
I'd start with the points that are given to be on the curve, then figure out how many points you need to add between these points to keep the error low enough. You might want to add points just in the middle, so the same letter at a bigger size will contain all the points of a smaller size letter plus additional ones, and the curves will look the same.
For best quality, make sure that the area where the polygon is to the left of the spline and the area where it is to the right is about the same. That's because this could affect line thickness, and that is something very, very easy to spot by the naked eye.


Can radix sort reach exponential time complexity?

Let $n$ be the number of integers to sort, $M$ be the maximum integer, and $b$ be the chosen base.

Each execution of counting sort will take time $O(n + b)$ and the number of such executions is $O(\log_b M)$.
The total time complexity is then $O((n+b) \log_b M)$.

If you want to ensure that this complexity is exponential in the input size $s$ (which is at most $O(n \log_2 M)$) you need to select an exponential value of $b$, e.g., $b = 2^n$ if $M = O(2^{\text{poly}(n)})$.

If $b$ is constant (e.g., base $10$) then the time complexity of radix sort will always be $O(n \log M)$, which is always polynomial in the input size $s = \Omega(n + \log M)$ since $O(n \log M) = O( (n + \log M )^2 ) = O(s^2)$.
This bound is tight when $M = \Theta(2^n)$.


If you have a guarantee that any given key will be present in at most one tree, you can implement these operations using the Union-Find data structure for disjoint sets.  Basically, you use the disjoint sets data structure to keep track of which keys are present in the same "tree".  Then, you have a separate hash table on the side to map keys to values.  With these two data structures, each of your operations can be implemented in $O(\alpha(n))$ time, where $\alpha(n)$ is the inverse Ackerman function.  In fact, you can treat each operation as running in essentially constant time.

Some examples of how to implement your algorithms:

merge(tree_1, tree_2): Invoke Union(tree_1, tree_2).
insert(tree, key, value): Check that key is not already present, by looking it up in the hashtable.  If it is already present, bail out (abort).  Otherwise, create a new singleton disjoint set containing just the value key.  Merge that new set with tree_1, using a Union() operation.  Insert (key, value) into the hashtable.
update(tree, key, value): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, update the mapping for key in the hashtable.
find(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, get the mapping for key from the hashtable.
get_tree(tree, key): Check that key is in this tree, by calling Find(key); if it's not, bail.  Then, return key.
children(tree, key): Return the single-entry list [(key, value)] (pretend key is a leaf).

With this implementation, the merge operation has the side effect of destroying the old trees (so you are not allowed to retain handles to the old trees).   If you wanted a persistent data structure, you can look at persistent disjoint-set data structures.

However, this answer has two serious limitations: first, it does not allow you to specify or control the parent-child relationship; second, it requires that the key sets of the trees be disjoint (no key appear in more than one tree).  It sounds like these limitations make this answer unusable in your context, but I'm not certain yet (perhaps a future revision of the question will make this clearer).


Testing two DFAs generate the same language by trying all strings upto a certain length

It can be tested that way, provided we may use the number of states of both automata $A$ and $B$ to compute the bound.

Note that if a finite automaton $C$ has $n$ states then any state in $C$ is reachable by a string of at most $n-1$ letters, or that state is not reachable at all. Assume I want to check whether $L(C)=\Sigma^*$. If $C$ is deterministic then all reachable states must be accepting. This can be tested by checking that all strings up to length $n-1$ are in the language.

The check $L(A)=L(B)$ can be analyzed similarly by considering the product automaton, i.e., the automaton that simulates $A$ and $B$ in parallel.

The product construction needs a little twist. Rather than accepting if both automata accept (computing the intersection) you need to see whether both automata make the same yes/no decision. Thus accept when both components are accepting or when both components are not accepting. Thus the language is $(L(A)\cap L(B))\cup (L(A)^c\cap L(B)^c)$. If that language is $\Sigma^*$ then both automata are equivalent.


integer = c lg n (inputs of size n, Cormen 3rd, page 23)?

lg n is the base-2 logarithm of n, satisfying 2^lg n = n, so about lg n bits (ceil lg n to be exact) are needed for integers that can represent 0..n-1, which suffices for pointers into the input. The authors of CLRS are saying that the word size should be about this much (c lg n). This is arguably reasonable because c lg n-bit words index storage of n^c (so any polynomial in n), and c lg n-bit operations can be synthesized from lg n-bit operations in constant time. If we make the word size much bigger, then the implied data-parallelism starts to distort running times.

The mathematical preliminaries here should be covered in an intro discrete mathematics class.


Algorithm to find the minimum (additional) popular votes to win the electoral college

Here's a hint (and a sketch).
I believe the problem is NP-hard and that it is equivalent to Subset Sum.
Reducing from Subset Sum:  Suppose your instance has sum $S$ and values $v_1, v_2, \dots, v_n$.
Create $n+1$ states, one with $S$ electorals that Party $A$ is guaranteed to win.  The remaining $n$ states is such that $i$ has $v_i$ electorals.  These cost Party $B$ $v_i$ to win.
Now, the optimum solution is $S$ which exists if and only if you have a yes instance for Subset Sum.


How is it possible to compare $P$ class with $BQP$?

BQP is simply a set of languages, i.e. $\mathsf{BQP}\subseteq 2^{\Sigma^*}$, and in that sense it can be compared with any other set of languages, such as $\mathsf{P, NP}$. It doesn't matter how those sets are defined, as we can always ask whether they are comparable under the inclusion relation.

You can ask why does it make sense to compare classes obtained from different models of computation (e.g. uniform polynomial size quantum circuits vs polynomial time Turing machines). The idea is to try and capture the notion of "efficiently computable" relative to each model. If you agree that efficiency in quantum/classic computation is captured by BQP and P, then the question "can quantum computers solve more problems efficiently" translates to whether or not $\mathsf{P\subsetneq BQP}$.


Approximation ratio of greedy algorithm for makespan

The lecture notes might be misquoting the example. Here is a correct version, copied from lecture notes of Ola Svensson:

The 4/3 bound is tight, an infinite family of instances showing this is given below.
Instance: we are given $m$ machines, and $2m+1$ jobs. There are three jobs with processing time $m$, and $2$ jobs with processing times $m+ 1,m+ 2,\ldots,2m−1$ each. In case of LPT, all but one of the machines get two jobs with a total processing time of $3m−1$, and a single machine gets three jobs with a total of $4m−1$ processing time.  Thus, the makespan is $4m−1$.  OPT schedules the three $m$ jobs on a single machine, and the remaining jobs on the remaining $m−1$ machines, such that each of those machines get jobs with a total processing time of $3m$, thus the makespan of OPT is $3m$.  As $m$ grows towards infinity the approximation ratio approaches $4/3$.

In the quote, LPT is the greedy algorithm. The approximation ratio for given $m$ is $\frac{4m-1}{3m} = \frac43 - \frac1m$, which tends to $\frac 43$ as $m\to\infty$.


Are Big-Theta functions asymptotic monotonically non decreasing?

No, it may not be true.

Consider the following function on $\Bbb N$.

$$f(n)=\begin{cases}
(n+2)^2\quad &\text{when } n \text { is odd,}\\
n^2\quad &\text{when } n \text { is even.}\\
\end{cases}$$

Then $f(n)=\Theta(n^2)$. However, for all odd $n$, $f(n)>f(n+1)$. In fact, $f(n)-f(n+1)\to\infty$ when $n$ goes to $\infty$ along the odd numbers.

Here are two related exercises.

Exercise 1. Give an example of $f(n)=\Theta(n)$ such that $f(n)>f(n+1)$ for infinitely many $n$.

Exercise 2. Let $g(n)\ge0$ be an unbounded function on $\Bbb N$.

Let $h(n)=\Theta(g(n))$. Prove that $h(n)<h(n+1)$ for infinitely many $n$.
Construct $f(n)=\Theta(g(n))$ such that for any number $c$, $f(n)-f(n+1)>c$ for infinitely many $n$.


Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?

There seems to be a flaw as alluded to by Arno in his answer.  While the reduction $SAT \leq B$ seems innocuous enough (and is indeed a textbook exercise as pointed out by Ariel in his comment) it implicitly assumes the consistency of ZF. Otherwise, if ZF is inconsistent, since every statement of ZF would then have a proof, unsatisfiable SAT-instances would not necessarily be mapped to wffs $\varphi$ which do not have a relatively short proof.

Thus, if we assume that ZF is consistent and $ZF \vdash P \neq NP$ then although we can conclude metamathematically that $B \notin P$ (because being NP-complete, $B$ could not be in $P$ since we are assuming $P \neq NP$) we would not have a formal deduction of $ZF \vdash B \notin P$ (since this depends on $B$ being an established NP-complete set, so if we want to use the reduction above, we must assume that ZF is consistent, which cannot be formally asserted by Godel's Second Incompleteness Theorem).  Thus this argument cannot suggest any necessary implications of $ZF \vdash P \neq NP$.