Converting maximization to minimization in aproximation algorithms

One connection is that maximizing some function $f$ is the same as minimizing its reciprocal $1/f$. You can use this to convert between maximization and minimization.

The general problem of maximizing a function $f$ under some constraints can be very different from the corresponding minimization problem (of the same function $f$). A case in point is MIN-CUT versus MAX-CUT. Whereas MIN-CUT is in P, MAX-CUT is NP-hard to approximate better than some constant.


How to prove that the pre-order tree traversal algorithm terminates?

Hint (by Raphael):  How do you prove that the recursive factorial function terminates?

Answer (by Kejia): The recursive factorial function's universe is non-negative integers, which is countable and so well-found, and so it is very easy to prove with mathematical induction.

By analogy, we can find a mapping from trees to a well-founded universe so that a similar proof works.

   Our mapping is to the size of the subtree.
 At each recursive call, the size of a subproblem (i.e. a subtree) is strictly decreasing and always non-negative. Therefore, we can proceed by induction.

 Suppose (induction hypothesis) that the function on a tree of size of at most k terminates. Now consider an input tree with k+1 nodes...


Is it decidable that a context free language contains a given regular language?

Indeed, it is undecidable whether a context-free grammar generates all strings over its alphabet. But I guess you want to know how such a result is obtained.

The classical result "undecidable $L(G) = \Delta^*$ for CFG $G$" was obtained by Bar-Hillel, Perles and Shamir in 1961 using a coding of Turing Machine computations. They showed that the set of strings that where not codings of valid TM computations form a context-free language. Of course if there are no valid computations then that language is $\Delta^*$.

You can do the same with codings of solutions of the Post Correspondence Problem. Given set of pairs $(u_1,v_1), \dots, (u_n,v_n)$ you can code PCP "solutions" as strings $u_{i_1}\dots u_{i_k}\#v^R_{i_k}\dots v^R_{i_1}$ such that both sides are equal (or rather, mirror image).

Argue that the non-solutions form a context-free language.


Why has research on genetic algorithms slowed?

Well, machine learning in the sense of statistical pattern recognition and data mining are definitely hotter areas, but I wouldn't say research in evolutionary algorithms has particularly slowed. The two areas aren't generally applied to the same types of problems. It's not immediately clear how a data driven approach helps you, for instance, figure out how to best schedule worker shifts or route packages more efficiently.

Evolutionary methods are most often used on hard optimization problems rather than pattern recognition. The most direct competitors are operations research approaches, basically mathematical programming, and other forms of heuristic search like tabu search, simulated annealing, and dozens of other algorithms collectively known as "metaheuristics". There are two very large annual conferences on evolutionary computation (GECCO and CEC), a slew of smaller conferences like PPSN, EMO, FOGA, and Evostar, and at least two major high-quality journals (IEEE Transactions on Evolutionary Computation and the MIT Press journal Evolution Computation) as well as a number of smaller ones that include EC part of their broader focus.

All that said, there are several advantages the field more generally thought of as "machine learning" has in any comparison of "hotness". One, it tends to be on much firmer theoretical ground, which the mathematicians always like. Two, we're in something of a golden age for data, and lots of the cutting edge machine learning methods really only start to shine when given tons of data and tons of compute power, and in both respects, the time is in a sense "right".


This is a pretty common version of partition and in this case you need N+1 comparisons.

For example consider an array containing ${1,2,\ldots,N}$.

Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison.

Then, pivot 1 is compared with $N,N-1,\ldots$. Note that the right item will be 1 as we want a number less than or equal to the pivot. Hence you need to compare 1 with all the elements $N,N-1,\ldots,1$. Thus here you need $N$ comparisons.

In total you need $N+1$ comparison.

In general we have two pointers one from left and one from right. pivot is compared with elements pointed by these two pointers. Left pointers moves towards right, right pointer moves towards left. Thus all the elements are compared with pivot at least once. But, one element is compared twice where the two pointers meet and cross. Thus we need $N+1$ comparisons.


Why mod operation can be used as hash function

The output of the function can always be expressed as a 256-bit value.  The value 5 is expressed as 00000...000101 (some 0's omitted).


"Byte addressable" means that a 32-bit address points to a single byte of memory, so if you increment that address, it points one byte further.

"Word addressable" means that (on a 32-bit processor) every 32-bit address points to a 32-bit word, so if you increment that address, it points four bytes further in memory.

Some machines can support both byte addressable and word addressable modes of operation.  But for the naming, we're concerned with the smallest unit they can address.


Encoding the pigeonhole principle in CBMC

If I understand correctly, you're actually looking for a technique to check if an out-of-bounds condition exists (more pigeons than pigeonholes).

Here's some example code that fits your analogy. I think you're asking about this technique as an analogy to whatever problem you're actually trying to encode, but next time be direct with what problem you want to solve rather than an analogy :)

/* pigeonhole.c */
int main() {
  _Bool holes_occupied[3];
  unsigned int pigeon;
  for (pigeon = 0; pigeon < 4; ++pigeon) {
    holes_occupied[pigeon] = 1;
  }
  return 0;
}

Run with:

cbmc --bounds-check pigeonhole.c

VERIFICATION FAILED (with error trace)


The decision problem that corresponds to $L$ deals with the behaviour of Turing machines, not with strings of $1$'s and $0$'s.

More precisely, the decision problem is

  Given a Turing machine $M$, is it the case that $L(M) = \{ 1^n0^n \mid
> n \geq 0 \}$

A decider for this decision problem would take as input the description $\langle M \rangle$ of an arbitrary Turing machine $M$ and tell us if $M$ accepted exactly those strings that are of the form $1^i0^i$ for some $i \geq 0$. A pushdown automaton that recognizes the language $\{ 1^n0^n \mid
> n \geq 0 \}$ is clearly not such a decider.

A reduction from $A_{TM}$ to $L$ will, given an instance $\langle M,w \rangle$ build a description $\langle M' \rangle$ such that

$$M \text{ accepts } w \iff L(M') = \{ 1^n0^n \mid
> n \geq 0 \}$$

Here is $M'$:

  On input $x$

  If $x \neq 1^i0^i$ for some $i \geq 0$, reject
  Else simulate $M$ on $w$ and answer what $M$ answered.

Clearly, if $M$ accepts $w$ then $L(M') = L$. If $M$ does not accept $w$, then $L(M') = \emptyset$.


Let $b_i = a_{2i} - a_{2i-1}$. The problem is then finding $\sum \varepsilon_i b_i = 0$. Here $\varepsilon_i = 1$ if $a_{2i} \in A'$ and $-1$ otherwise. Let $B' = \{b_i \mid \varepsilon_i = 1\}$. Note that $\sum_{b \in B'} b = \sum _{b \in B \setminus B'} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$.

Let $b_{2i} = a_i$ and $b_{2i-1} = 0$. Note that if $b_{2i} \in B' \leftrightarrow a_i \in A'$ and $\sum_{B'} = \sum_{B \setminus B'}$ then $\sum_{A'} = \sum_{A \setminus A'}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.


Is the set of programs that compute some function other than $h$ recursively enumerable?

The set $S$ is in fact neither c.e. nor co-c.e. You can prove this via an m-reduction to $\overline{TOT} = \{ x | \varphi_x \mbox{ is not total } \}$ (which is also neither c.e. nor co-c.e.).

Define:

$ \varphi_{f(x)}(y)=\begin{cases}
    h(y) & \mbox{if $\forall z\leq y~\varphi_x(y)$ halts}\\
    undefined & \mbox{ow.}
    \end{cases}
    $

Where $f$ is from the s-m-n theorem.

Then you have that $\overline{TOT} \leq_m S$ via $f$ because, for all $x$:

$x \in TOT \iff \forall y~\varphi_x(y) \mbox{ is defined} \iff \forall y~\forall z\leq y~\varphi_x(z) \mbox{ is defined} \iff \forall y~\varphi_{f(x)}(y)=h(y) \iff f(x) \notin S$


Representing abstract syntax tree as a graph

Every tree is itself a graph, so of course an AST is a graph -- no mapping is needed, it is already a graph.  I don't see any way that this is useful in practice, though.
Rather than trying to convert to a graph and then use graph neural networks, I suggest using a more direct approach: e.g., using a neural network on the AST or on the code itself.  Since you haven't told us what you want to do with the neural network, it's impossible to suggest something more concrete, but I encourage you to do a literature search; there are many recent papers on using neural networks on code.

Alternatively, if you insist on having a graph somewhere, perhaps you will be interested in learning about control-flow graphs, which are one use of graphs in program analysis where the graph structure is useful.


If the question is, "Is this grammar LL(1)?", then the answer is "No".

If the question is, "Can this grammar be made LL(1)", then by all means remove the left-recursion.

The distinction is important because removing left-recursion does not preserve derivation order, so the left-recursion-eliminated grammar produces different parse trees. If it is being used to parse, it is not the same grammar.


It is evident that $B$ can be followed by $a$  — in other words, that $a\in \text{FOLLOW}(B)$ — as shown by the partial derivation

$$\begin{align}S&\to A B C&(S\to ABC)\\
&\to  AaBC &(A\to Aa)\\&\to aBaBC&(A\to aB) \\
\end{align}$$

So the answer provided does not correspond to this grammar.


Formally, this is a special case of the "$k$-independent set problem", and can be stated as follows:

  Given a graph with 400 vertices, can you pick 100 vertices such that no two of them are adjacent?

(A "graph" is a set of vertices (students) and edges (students who are incompatible). Two vertices are "adjacent" if there is an edge between them (they're incompatible).)

You can find easy solutions for some groups of students: for instance, if there are no incompatibilities at all, any choice of 100 students will work. But the difficult problem is solving this in general, coming up with an algorithm that can solve it for any selection of $k$ students from a group of $n$, with a "polynomial runtime" (which basically means it can be solved reasonably quickly even for large values of $n$).

"Proving" that the problem is solved involves a formal mathematical proof, a way of demonstrating that your algorithm works for any group of students, no matter what the incompatibilities are, no matter how many there are, and takes only polynomial time to run.

Examples won't work as a proof, because no matter how many examples you show, it's always possible that your algorithm would fail on the next one you haven't tried.

If you're actually interested in approaching this problem, the formal problem description explains it more thoroughly. (You will need some mathematical background though.)


Language of all even-length words with no 1's in left half

Two points:

the reasoning is incomplete: you need to show that pumping $y$ in the two first cases also leads to elements outside $L$
the reasoning does not use $ |xy|<d$ which entails that only the first case occurs.

But it is not wrong. If you want to ignore $|xy|<d $ then you need to argue the three cases. The first case holds because deleting $y$ creates a string of odd length or one in which a $1$ appears in the first half. The second case holds because if we pump $y$ $ n >1$ times a $1$ will flow into the first part.


How many edges can a unipathic graph have?

A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges.

   Consider a complete bipartite graph, with oriented edges $\forall (i,j) \in [1,m]^2, a_i \rightarrow b_j$. This graph is unipathic and has no cycle: all its paths have length $1$. It has $2m$ vertices and $m^2$ edges.

 (Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)


The problem you are describing can be solved in $O(n)$.

Let's define the prefix sum as:
$$\text{psum}[i] = \sum_{0 \le j \le i} A[j]$$
Then your function can be expressed as:
$$\Phi(i, j) = \text{psum}[j-1] - \text{psum}[i-1]$$

Assuming we fix the right boundary $j-1$ (we want to find the window of size at most $w$ ending at $j-1$ with the maximal sum). It should be easy to see, that this window has the sum:
$$\text{psum}[j-1] - \min_{i \ge j - w}\left\{\text{psum}[i-1]\right\}$$

For the actuall implementation we use a data structure called Minimum Queue. It is a queue (FIFO) that does the normal push/pop operations in amortized constant time and it additionally supports extracting the minimum of its current stored elements in constant time.

With it we can find the maximal window in linear time:

best = 0
initialize min_queue
min_queue.push(psum[-1])  # psum[-1] can be defined as 0
for j = 1 to n:
    if len(min_queue) > w:
        min_queue.pop()
    cur = psum[j-1] - min_queue.min()
    best = max(best, cur)
    min_queue.push(psum[j-1])

One way of implementing a Minimum Queue is to store the elements in a dequeue using value-index pairs. And you keep this queue in non-decreasing order, i.e. you only store the subset of pairs that are or can become the minimum at some point and ignore the remaining elements. This means whenever you push a new element, you remove all previous elements that are bigger from the back of the queue, since the currently added element will dominate them at all times. Therefore the minimum will always be the first element.

This approach, and also two (similar) alternatives are described on cp-algorithms.com.


It depends on how $X$ is given. If $X$ is given unsorted, find the minimum element larger than $z$, and the maximum element smaller than $z$. If $X$ is given sorted, use binary search.


Drawbacks of adding type equality to 1ML

Your proposal is an instance of a general design pattern for type systems that some would call a design smell: whenever you are stuck on an inference constraint that you cannot solve, or cannot solve in a principal way, include it in the resulting type. "It's not a problem, it's in the solution."

This solution can be made to work, but in general it may run into several practical issues:

Constraint explosion. If those tricky problems occur more often than you would think, you can end up with many constraints (in particular if you sometimes need to introduce disjunctions of constraints; this is the end). This is problematic for user readability, and type-checking time.
Loss of abstraction. The collected constraints reveal which unifications were done in the implementation, and sometimes they reveal too much details about the implementation compared to what the user had in mind. (On the other hand, they are usually principal, so what the user has in mind is not more general.)
Delayed error. If you don't check that those delayed constraints are solvable, then you may delay error: all attempts to use the value will be an error, but there is no error as definition-site. (This gives the same usability issues as C++ templates.)

Not all instances of this "putting constraints in the solution" pattern have all these problems. In your example for example, it may be possible that the specific shape of equality constraints occurring (1) have no need for disjunction of equalities and (2) let you check solvability of constraints when they are introduced. You would have to think carefully about that.


Could quantum computing eventually be used to make modern day hashing trivial to break?

Quantum computers might have some advantage over classical computers for some cases. The most remarkable example is Shor's Algorithm which can factor a large number in polynomial time (while classically, the best known algorithm takes exponential time). This completely breaks schemes like RSA, based on the hardness of factorization.

This is not necessarily the case for hash functions. First, we need to define what it means to break a hash function. One way to break it is called pre-image attack: you give me hash value $v$, and I need to find a message $m$ such that $\operatorname{hash}(m)=v$. Another attack is the collision attack, in which you give me nothing, and I need to come up with two different messages $m_1, m_2$ that have the same hash $\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$. This is easier than finding a preimage, since I'm not bound to the a specific $v$.

What can Quantum computers do? The main result is Grover's search algorithm: a method for a quantum computer to search in an unsorted database of size $N$ with time $O(\sqrt{N})$ (while classically it will take an expected time of $N/2$).

With Grover's algorithm, finding a preimage of a hash function whose output is $k$-bits  takes $O(2^{k/2})$ time, rather than $O(2^k)$.

Is this a problem? Not necessarily. Hash functions are designed such that time $2^{k/2}$ is considered "safe" (in other words, the hash designers always double $k$). This is due to the Birthday paradox with which finding a collision is possible with time $O(2^{k/2})$ by a classical computer.

The nice thing about Grover's algorithm that it is optimal - every other quantum-algorithm to find an element in an unsorted database will run in time $\Omega(\sqrt{N})$.

Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are $t$ items (that is, preimages), the time to find one is reduced to $O(\sqrt{N/t})$. But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose $m_1$ at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks.

(this answers the more general question, without restricting the computer to 20 qubits, which will not be enough to break the current 1024-bit hashes).


Non-deterministic Büchi vs Rabin: Automaton size for LTL->automaton

Consider a nondeterministic Büchi automaton $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, \alpha\rangle$. The acceptance condition of $\mathcal{A}$ is a subset of states $\alpha\subseteq Q$, and an infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots $ is accepting iff $r$ visits a state in $\alpha$ infinitely many times.
In Rabin automata, the acceptance condition is given by $\alpha = \{\langle \alpha_1, \beta_1 \rangle, \langle \alpha_2, \beta_2 \rangle, \ldots , \langle \alpha_k, \beta_k \rangle \}$, where $ \alpha_i, \beta_i\subseteq Q$, for all $i\in [k]$. An infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots $ is accepting iff for some $i\in [k]$, $r$ visits a state in $\alpha_i$ infinitely many times, and visits the states in $\beta_i$ finitely many times. The number $k$ is the index of the automaton, and is usually taken into account when defining the automaton's size.
Clearly, a Büchi condition $\alpha$ is equivalent to the Rabin condition $\{ \langle \alpha, \emptyset \rangle\}$. Thus, nondeterministic Büchi automata can be translated to nondeterministic Rabin automata with no blowup (they can be thought of as a simple fragment of Rabin automata - although they are equally expressive).
So, nondeterministic Büchi automata cannot be more succinct than nondeterministic Rabin automata. However, a nondeterministic Rabin automaton with $n$ states, $m$ transitions, and index $k$, can be translated to a nondeterministic Büchi automaton with $O(n\cdot k)$ states, and $O(k\cdot m)$ transitions. The later translation is justified by a lower bound. So, nondeterministic Rabin automata are polynomially more succinct than nondeterministic Büchi automata, which is not significant.
A comprehensive overview of the translations can be found here (along with other relevant references).
Note that you can easily translate an LTL formula into a nondeterministic Büchi automaton (see section 6 here), and the translation has a tight exponential bound. However, following your comment, if you're interested in translating the LTL-formula into a deterministic automaton, then you can translate the Büchi automaton to a deterministic Rabin automaton (such determinization construction has a tight bound of $2^{\Theta(n \log n)}$). Also, the double exponential blow-up of translating LTL formulas to deterministic automata cannot be avoided (see theorem 26 here).


$\qquad \begin{align}
  \lim_{x \to \infty} \frac{ (\log(x))^{99} }{x^{\frac{1}{99}}}
&= \lim_{x \to \infty} \frac{ (99^2)(\log(x))^{98} }{x^{\frac{1}{99}}} \\
&= \lim_{x \to \infty} \frac{ (99^3) \times 98(\log(x))^{97} }{x^{\frac{1}{99}}} \\
&\vdots \\
&= \lim_{x \to \infty} \frac{ (99^{99})\times 99! }{x^{\frac{1}{99}}} \\
&= 0
\end{align}$

I used L'Hôpital's rule law in each conversion assuming natural logarithm.


Is there a name for this type of Turing machine?

Not sure about a name, but real computers aren't based on Turing machines at all.


Utility of D latch/flip-flop and how it differs from an SR latch/flip-flop

One big difference is that while the SR flipflop has a "not-allowed" state (i.e., inputs S=1, R=1), the D flipflop has no such condition.

Another difference, is that the D flipflop just mirrors the input into the output, while SR has two inputs: one for setting the ouput to 1, and one for resetting the output into a 0.


How do I find the roots of the disconnected subgraphs of a directed graph?

You can apply the following algorithm:

Identify the weakly connected components (i.e., the disconnected subgraphs). To do this, you can turn all edges into undirected edges and, then, use a graph traversal algorithm.
For each  component, select the node that has no incoming edges (i.e., the source node) as the root. If there is more than one source node, then there is no root in this component.

Note that this solution assumes the root of a directed acyclic graph $G=(V,E)$ to be a node $r$ such that $\forall v \in V-\{r\} \Rightarrow \exists P=[(r, v_1),(v_1,v_2), ...,(v_{n-1},v)]$, where $P$ represents a directed path from $r$ to $v$.


How can I decide manually whether two CTL formulae are equivalent?

It seems to me that "$\Phi≡\Psi$" is equivalent to "Neither $(\Phi ∧ ¬\Psi)$ nor $(\Psi ∧ ¬\Phi)$ is satisfiable".

Therefore deciding equivalence is as difficult as deciding satisfiability, since "$\Phi$ satisfiable" is equivalent to "not ($¬\Phi≡\top$)".

In this article there is a mention of a an exponential procedure to decide satisfiability in CTL, so it should be enough to run the algorithm on the two formulas I wrote above.

PS: I am not at all an expert in this field, so please check what I wrote. If this makes sense, I will remove the various "seems" and "should".


Is a two-opt move guaranteed to produce a non-worse tour?

2-Opt is a move that doesn't guarantee to give a better tour.

We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour).
Local search consists of browsing all (feasible) tours that can be produced with only one move from the input.
If the input tour is not improved, we call it a local optimum which may be the optimal solution.


How to give a context-sensitive grammar for a^nba^nba^nb?

One possible grammar is:

\begin{align}
S&\rightarrow Tb &(1)\\
T&\rightarrow AXY &(2)\\
T&\rightarrow ATXY &(3)\\
YX&\rightarrow YZ &(4)\\
YZ&\rightarrow WZ &(5)\\
WZ&\rightarrow WY &(6)\\
WY &\rightarrow XY &(7)\\
AX &\rightarrow AbA_X &(8)\\
A_XX&\rightarrow A_XA_X &(9)\\
A_XY&\rightarrow A_XbA_Y &(10)\\
A_YY&\rightarrow A_YA_Y &(11)\\
A&\rightarrow a &(12)\\
A_X&\rightarrow a &(13)\\
A_Y&\rightarrow a &(14)
\end{align}

We can generate $A^n(XY)^n$ using Rule (1) to (3). Rule (4) to (7) are used to change $YX$ to $XY$, thus we can generate $A^nX^nY^n$. At last, using Rule (8) to (14) we can generate $a^nba^nba^nb$.

Note we needn't worry that in a pattern $YX$, $Y$ yields to $A_Y$ (or $bA_Y$) before we exchange $X$ and $Y$, because otherwise there is no rule to eliminate $X$ in this pattern.


Introductory Book on Pseudo-Random Number Generation

The book Random numbers and computers by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python. It is aimed at "anyone who develops software, including software engineers, scientists, engineers, and students of those disciplines".


Proving that shortest path distance of adjacent nodes can't differ by more than one

I don't understand your diagram but the point is that, if there is a $x$–$y$ path of length $k$ then the distance from $x$ to $y$ cannot be bigger than $k$.

So, suppose the shortest path1 $P$ from $s$ to $v$ has length $k$. If that path includes $u$, then there is a path of length less than $k$ from $s$ to $u$. Since there is a path of length less than $k$, the distance from $u$ to $v$ is less than $k$, so it is less than or equal to $k+1$, as required.  On the other hand, if $P$ does not include $u$, then $P$ followed by the edge $uv$ is a path from $s$ to $v$ of length $k+1$. Since there is a path of length $k+1$, the shortest path can't be longer than that, so the distance is at most $k+1$.

1 I should really say "a shortest path", since there can be multiple different paths, all of the same length.


Prize collecting Steiner tree on graph without weights on edges

Something seems not quite right.  Your problem can be solved in polynomial time, so I doubt that it is NP-hard.  Let me explain how to solve it in polynomial time.

First note that there exists a positive integer $t$ such that your problem is equivalent to finding $H$ that maximizes

$$f_t(H) = \sum_{v \in V_H} w(v) + t,$$

subject to the additional constraint that $\deg_H(v) \ge t$ for all $v \in V_H$.  Also, $1 \le t \le n$, where $n=|V|$ is the number of vertices in $G$, so there are at most $O(n)$ possible values for $t$.  That means we can try them all and, for each $t$, find the optimal choice of $H$.  Given $t$, maximizing $f_t(H)$ can be done by a simple iterative fixpoint algorithm, where you keep as many vertices of $V$ as possible.

In this way, we obtain the following algorithm:

For $t := 1,2,\dots,n$:

a. Repeatedly delete vertices of degree $\le t$ until there are no more to delete.  In other words, while there exists $x \in V$ such that $\deg(x) \le t$, delete $x$ from $V$.

b. If there exists a single connected component of $G$ that contains all vertices of $Q$, set $H$ to be that component, compute $f(H)$, and if this $f(H)$ is better than anything found before, remember this $H$.

Correctness follows from the above discussion.  This can be implemented so that its running time is $O((n+m) \alpha(n))$, where $n=|V|$ and $m=|E|$ and $\alpha(\cdot)$ is the inverse Ackerman function.


Numeral systems other than unary used in nature or in animal and human behaviours

There is at least one example where a string of symbols from an alphabet is also used: proteins.

Proteins consist of chains of 20 different amino acids (usually, in some cases, it's 21 or 22) and the sequence of amino acids determines what given protein does.

This example is closely related to the DNA example you gave, because each amino acid in a protein is encoded by a triplet of bases in DNA.

For more information, see the article Genetic code on Wikipedia.


How is functional property guaranteed in type theory when function type is defined?

Type theory shows that every element of a function type has the "function property". Let $A$ be a type and $B(x)$ a dependent type with $x : A$. We can construct an element of
$$\Pi (x : A) (y , z : B(x)) \,.\, f x =_{B(x)} y \to f x =_{B(x)} z \to y =_{B(x)} z$$
quite easily, because we just use symmetry and transitivity of equality. For instance in Coq:

Definition functional_property (A : Type) (B : A -> Type) (f : forall x, B x)
  : forall (x : A) (y z : B x) (p : f x = y) (q : f x = z),  y = z
  :=
   fun _ _ _ p q => eq_trans (eq_sym p) q.

What this means is that, as others already pointed out, the "functional property" is there by construction. It may help to say the following: in type theory we do not think of mathematical objects as existing independently and beforehand. Instead, type theory is a theory of how objects are constructed. Thus, the elements of the function type are constructed in a certain way (known as "$\lambda$-calculus") that guarantees the desired properties by construction. There is no such thing in type theory as "a thing that wants to be a function but isn't because it doesnt have the right properties". That sort of thinking simply does not apply: if you have a thing, then it was constructed according to the rules of some type and therefore the thing has that type.

You are probably thinking set-theoretically, i.e., given a relation $R \subseteq A \times B$, we should be able to get a function out of it, provided that $R$ is single-valued (what you call "functional property") and total. There is a corresponding statement in type theory, but it is not the definition of functions. It is instead a theorem stating that the function type $A \to B$ is equivalent to the type of total functional relations.


The state of the art for solving parity games is now quasipolynomial time. Here are references:

  Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.

  A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.

  Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić, LICS 2017.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak


Any mathematical tools for analyzing mutable memory

See separation logic and theory of arrays in SMT solvers.  Both of these provide a principled, mathematically rigorous foundation for reasoning about mutable memory.


What is the evidence that that types are more basic specifications, and specifications are more detailed types?

As Gilles points out, it depends on what you count as types. If you mean by types something like
types in Java or Scala or Haskell, then this is clearly true.

One easy way to see this is (simplifying a bit) to use a general framework of
specifications to express the behavioural content of types as a
specific case of specification. The best framework to do this at the
moment is $\pi$-calculus as a programming language and Hennessy-Milner
logic as a specification language. I suggest to choose $\pi$-calculus
because it's expressive, and well studied. In particular, most
sequential programming languages are easily seen to be (behaviourally
equivalent to) specific sub-calculi of $\pi$-calculus.  Hennessy-Milner
logic is an expressive modal logic that can be used to nail down
processes up to behavioural equivalence.  Now we take an arbitarty
type, say the function space constructor
$
   int \rightarrow bool
$
and express the constraints this type imposes on programs as a
specification in Hennessy-Milner logic.

Conversely, we need to show that specifications are strictly more
expressive than types but that's fairly obvious, for we cannot specify
e.g. that a method is sorting its input array.


Prove no DFA with four states can accept L={111}

This depends on your favorite definition for DFAs. If your definition allows the transition function to be undefined on some state-symbol pairs $(q, a)$ then your DFA in your comment does the trick. Otherwise, you would need a fifth state (a sink) that is not accepting and catches all missing transitions.
To show that there is no DFA with less than five states accepting $L = \{111\}$, we can check the Myhill-Nerode equivalence classes of $L$ which are

$[\varepsilon]_L = \{\varepsilon\}$,
$[1]_L = \{1\}$,
$[11]_L = \{11\}$,
$[111]_L = \{111\}$,
$[0]_L = \{w \in \{0, 1\}^\ast \mid w \notin \{\varepsilon, 1, 11, 111\}\}$.

(To show that these are indeed the five classes is left as exercise.)
The equivalence classes have a 1:1 correspondence to the unique minimal DFA of the latter definition (with transitions for all state-symbol pairs).


Here's a simple technique.

Train an LDA using something like MALLET over your collection of texts. For each pair of documents you want to compare, obtain the topic distributions and compute the Hellinger distance between them.

Things you can tweak include term weighting, the LDA hyperparameters, and the metric for comparing distributions. Term weighting would obviate both the need for a list of important words, and the restriction to only English.


It will be easier to analyze $S(n) = \log f(n)$, which is given by the formula
$$ S(n) = \sum_{i=2}^n \log\log i. $$
According to the Euler–Maclaurin formula,
$$
S(n) = \int_2^n \log\log x \, dx + \frac{\log\log 2 + \log\log n}{2} + \sum_{k=1}^s \frac{B_{2k}}{(2k)!} [(\log \log)^{(2k-1)}(n) - (\log\log)^{(2k-1)}(2)] + R,
$$
where the remainder satisfies
$$
|R| = O_s \left(\int_2^n (\log\log)^{(2s+1)}(x) \, dx\right).
$$
Here $(\log\log)^{(r)}$ is the $r$th derivative of $\log\log$ and $B_{2k}$ are Bernoulli numbers.

In order to get big O asymptotics, it suffices for the error to be of order 1. The first few derivatives of $\log\log x$ are
$$
\log \log x, \frac{1}{x\log x}, -\frac{\log x + 1}{x^2\log^2 x}, \frac{2\log^2 x + 3\log x + 2}{x^3\log^3 x}.
$$
The third derivative has constant sign (for $x$ larger than some constant), and so when $s=1$, the growth rate of the remainder term can be bounded by the second derivative evaluated at $n$, which is $o(1)$. So it suffices to choose $s=1$. We obtain
$$
\begin{align*}
S(n) &= \int_2^n \log\log x \, dx + \frac{\log\log 2 + \log\log n}{2} + \frac{\frac{1}{n\log n} - \frac{1}{2\log 2}}{12} + o(1) \\ &=
x\log\log x - Ei(\log x) \bigr|_2^n + \frac{\log \log n}{2} + O(1) \\ &=
n\log\log n - Ei(\log n) + \frac{\log \log n}{2} + O(1),
\end{align*}
$$
where $Ei(x)$ is the exponential integral. The exponential integral doesn't really reduce to any known function, but it is known that $E_i(x) = (e^x/x)(1 + O(1/x))$. Therefore
$$
S(n) = n\log\log n - \frac{n}{\log n} + O\left(\frac{n}{\log^2 n}\right).
$$
This gives the value of $f(n)$ up to a factor of $e^{O(n/\log^2 n)}$. In the same way, we can get an explicit expression with error $e^{O(n/\log^k n)}$ for any constant $k$, using the divergent series for $Ei(x)$. If we want an expression with $O(1)$ multiplicative error, then the best we can get is
$$
f(n) = \Theta(e^{n\log\log n - Ei(\log n)}\sqrt{\log n}).
$$
With a bit of effort we can also find the hidden constant.


Is the per-vertex error over a PageRank iteration monotonically decreasing?

No. Consider the case of an isolated component with a central vertex v that is pointed to by vertices x_1, ...., x_k. The initial value at v is 1/n, and the final value should be roughly k * the restart probability/n. But the value at v in the second round is roughly k/n. If the restart probability is significantly less than 1/k, then the value got further from the ultimate value.


What are some real world examples of nearly sorted lists

What about log files described in AWStats logfile analyzer 7.5 Documentation?

  An error log file is not always completely sorted but only "nearly" sorted because of cache and writing log engines used by a server.


is AVL tree is better than heap for sorting purpose?

Both of them will work, and both of them support insertions${}^1$ and deletion${}^2$ of the minimum element in $O(\log n)$ worst-case time (where $n$ is the number of elements currently in the data structure).
It really depends what you mean by "better". An AVL tree will have the additional binary-search-tree property that the heaps do not have, and this allows to quickly support other operations (in addition to returning the ones above). For example you can quickly search for any element in the tree (both for its value and its rank).
Indeed, the typical use of AVL trees is to implement a dictionary.
Since there isn't really any reason to use an AVL tree for sorting (they are a bit more complex to implement than an heap), you could stick with an heap. See also: heapsort.

${}^1$ Notice that constructing an AVL tree of $n$ elements by repeated insertions takes $O(n \log n)$ time. You can also construct an heap by repeated insertions in $O(n \log n)$ time but, since the arrangement of the elements in an heap is more relaxed than a BST, this can actually be improved to $O(n)$. For the purpose of sorting this doesn't really matter since its complexity will be subsumed by the one of the subsequent $n$ deletions.
${}^2$ Deletions are not really necessary if an AVL tree is used. Since an AVL tree is a BST, it suffices to return the elements in the same order as they are considered by a symmetric traversal of the tree.


Do all languages in $P$ have polynomial proofs that they are in $P$?

Depending on how the language is specified, the answer may be yes or no.  For instance, consider the following language: $L_S = \{0\}$ if statement $S$ is true, otherwise $L_S =$ the language of the halting problem.  Note that if $S$ is true, then $L_S$ is in $P$, otherwise $L_S$ is not in $P$.  Now by Goedel's incompleteness theorem, there exists a true statement $S$ that has no proof that it is true.  Thus, the corresponding language $L_S$ is in $P$ but has no proof that it is in $P$.  You haven't given us enough details about how you propose to represent a language to determine whether your representation is expressive enough to allow defining such a language.  So, the answer is unanswerable as stated.

This highlights why it is crucial to explain how you represent the inputs.  There is no accepted, standard way to represent a language as a finite bit string -- indeed, the set of all languages is uncountable, so for any representation you might have in mind, there will always exist some languages that cannot be represented.  Without this, the question isn't well-posed and can't be answered until you specify this deatil.

As Yuval Filmus explains, the usual understanding of the word "proof" in CS is something that can be verified in polynomial time, so if it has a proof, it has a proof that can be verified in polynomial time.


An n-dimensional index where the search key specifies an exact match on certain dimensions?

If you only want to be able to search on a single dimension at a time (as in your example), this is readily solved by precomputing an index.  Basically, you scan the entire database and build up an index for each dimension.  For instance, an index for the first dimension is a hashtable that maps from the value of $x_1$ to the tuple $(x_1,\dots,x_n)$, for each tuple.  You then build an index for the second dimension, for the third dimension, etc.  You do this once, in advance.  Once you have the index, it's easy to answer queries.  Also, it's easy to update the index when you insert or delete vectors.

A simple way to program this would be to insert your data into a database.  Most databases will automatically build indices and update them as you change the data in the database.  This will spare you having to implement that logic yourself.


Why do we discard the constant 1 in proving that $2^{n+1} = O(2^n)$

No, there exists such a constant. Indeed take $c=2$, then
$$\forall n \in \mathbb{N}\quad 2^{n+1}=2^1 \cdot 2^n \le  c \cdot 2^n.$$
So $2^{n+1}=O(2^n)$.


Decidability of the language of all deterministic LBA where all states are reachable

After days of constantly refreshing this page in hope for an answer today I woke up and my very first thought might be it.

If all states are reachable and it is deterministic this means there has to be a set of inputs where every state  will once be reached.

semi-decidable Algorithm:

Validate if DLBA-Encoding and reject if not;     # returns 'no' on bogus
k = 0;
Repeat until every state has been at least once been reached {
   For every possible input w for the DLBA of the length of k {
      Simulate DLBA with w for g(M,k) steps while keeping record of the reached states;
   }
   k++;
}
return 'yes'

It will accept if all states are reachable

It will reject if not a valid DLBA-Encoding

It will run forever if valid DLBA but not all states are reachable

I figured out, that DLBAs can have states where there are a series of transitions leading from the starting state to those but they still can never be reached.
So just looking at transistions isn't enough


Proving non-regular language using the pumping lemma

Your language is not regular. Indeed, let $n$ be the pumping lemma constant, and consider the word $ab^nab^na = a(b^na)^2 \in L$. Suppose that your language were regular. Then you could write $ab^nab^na = xyz$, where $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. We consider two cases:

Case 1: $x = \epsilon$, and so $y = ab^t$ for some $t \geq 0$. Then $xy^0z = b^{n-t}ab^na$. Suppose this were of the form $vu^2$. Considering the second copy of $u$, we see that $u$ ends in $a$. Since there are two copies of $a$, necessarily $u = b^na$. This is only possible if $t = 0$ (which is OK) and $v \neq \epsilon$ (which is not OK).
Case 2: $x = ab^t$, and so $y = b^s$ for some $t \geq 0$ and $s \geq 1$. Then $xy^0z = ab^{n-s}ab^na$. Suppose this were of the form $vu^2$. Since $v \neq \epsilon$, the word $u^2$ is a suffix of $b^{n-s}ab^na$, and so as before, necessarily $u = b^na$ and we reach a contradiction since $s \neq 0$.

Now, why does your regular expression $(a+b)^* (aa+bb) (a+b)^* (a+b)^*$ not work? You are implicitly assuming that if you write "$r \cdot r$" then the semantics are that the same word must be chosen twice. However, this need not be the case. For example, the word $aab$ matches your regular expression, but is not in $L$.


Space is counted in machine words rather than in bits. A machine word is allowed to contain a member of the universe $U$, and so is $O(\log |U|)$ bits wide. The array $G$ stores hash functions, via their index inside some collection of universal hash functions. The lecture notes don't mention this, but there are collections of universal hash functions of size $O(|U|^2)$. If you use one of these collections, each entry of $G$ takes $O(\log (|U|^2)) = O(\log |U|)$ bits to store, and so $O(1)$ machine words.

Why is it meaningful to count space in machine words? First of all, even if you store your set as an array (with logarithmic access time, using binary search), the number of bits is $O(n \log |U|)$ rather than $O(n)$. If we want such an array to be considered taking up linear space, we need to "divide" by $\log |U|$, and the simplest way to accomplish this is to allow each memory cell to contain $O(\log |U|)$ bits (the exact constant doesn't matter).

Another reason we would like to allow cells to contain an unbounded number of bits is so that they can store indices. When you implement binary search, or any other algorithm, you have variables which store indices in the array. These variables take $O(\log n)$ bits to store. When discussing algorithms, however, we often think of an index as taking $O(1)$ space. Again, the way to accomplish this is to allow each memory cell to contain at least $\log n$ bits.

On the other hand, if we allow memory cells to be of arbitrary size, then the space measure becomes trivial, since anything can be done in $O(1)$ space (though depending on the exact computation model, you might have to pay in terms of running time). The usual convention in algorithms is to allow each memory cell to contain $O(\log n)$ bits, where $n$ is the input size (in bits). In this particular case, it is more meaningful to allow a machine word to contain $O(\max(\log n, \log |U|))$ bits, and this is the way we measure the space consumption of the algorithm.


$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness.

Here is a polynomial algorithm.

Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge c_2\cdots \wedge c_m$, where $c_i$ is the $i$-th clause.
Output: true if $\phi$ becomes 1 under some assignment of all variables.
Procedure:

Construct set $B_i$, the variables that appear in at least one of $c_i, c_{i+1}, \cdots, c_{i+k}$, $1\le i\le m-k$.
Construct set $A_i=\{f: B_i\to\{0,1\} \mid c_i, c_{i+1}, \cdots, c_{i+k} \text{ become 1 under} f\}$.
Construct set $E=\cup_i\{(f, g)\mid f\in A_i, g\in A_{i+1}, f(x)=g(x)\text{ for all }x\in B_i\cap B_{i+1} \}$
Let $V=A_1\cup A_2\cdots\cup A_{m-k}$. Consider directed graph $G(V,E)$. For each vertex in $A_1$, start a depth-first search on $G$ to see if we can reach a vertex in $A_{m-k}$. If found, return true.
If we have reached here, return false.

The correctness of the algorithm above comes from the following claim.

Claim. $\phi$ is satisfiable $\Longleftrightarrow$ there is a path in $G$ from a vertex in $A_1$ to a vertex in $A_{m-k}$.
Proof.
"$\Longrightarrow$": Suppose $\phi$ becomes 1 under assignment $f$. Let $f_i$ be the restriction of $f$ to $B_i$. Then we have a path $f_1, \cdots, f_{m-k}$.
"$\Longleftarrow$": Suppose there is a path $f_1, \cdots, f_{m-k}$, where $f_1\in A_1$ and $f_{m-k}\in A_{m-k}$. Define assignment $f$ such that $f$ agrees with all $f_i$, i.e., $f(x)=f_i(x)$ if $x\in B_i$. We can verify that $f$ is well-defined. Since $c_\ell$ becomes 1 for some $f_j$ for all $\ell$, $\phi$ becomes 1 under $f$.

The number of vertices $|V|\le 2^{3(k+1)}(m-k)$. Hence the algorithm runs in polynomial time in term of $m$, the number of clauses and $n$, the number of total variables.


What algorithm solves high-order unification for untyped terms in most cases?

Maybe you should try nominal unification. In the paper nominal unification, it gives 4 examples which are untyped $\lambda$-terms.


Will irrational parameters make a problem not well-defined on complexity

The appearance of square roots does not make this an ill-defined problem.

Note that $(\sqrt{2\sum_{i\in S}a_i}-1)^2=0$ if $\sum_{i\in S}a_i = 1/2$ and $(\sqrt{2\sum_{i\in S}a_i}-1)^2>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.


A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix $A$ and a vector $b$ over $\mathbb{F}_2$, and an integer $w$, determine whether there is a solution to $Ax = b$ with Hamming weight at most $w$.

You can reduce this problem to your problem. The system $Ax = b$ is equivalent to the conjunction of equations of the form $x_{i_1} \oplus \cdots \oplus x_{i_m} = \beta$. If $\beta = 1$, this equation is already of the correct form. If $\beta = 0$ then we XOR an extra variable $y$ to the right-hand side, and then we force this variable to be $1$ by adding an extra equation $y = 1$. We define the weights as follows: $y$ has weight $0$, and the $x_1$ have weight $1$. We have now reached an equivalent formulation of maximum likelihood decoding which is an instance of your problem.


Relation between logspace-uniform circuits and P-uniform circuits

The circuit value problem (CVP) is, given a circuit and an input, to evaluate the circuit. This is a well-known problem which is P-complete with respect to AC$^0$ reductions. Thus one can define P as the class of problems AC$^0$-reducible to CVP. We get the same class if we consider the class of problems polytime-reducible to CVP, or in general $L$-reducible to CVP, where $L$ is any intermediate class between AC$^0$ and P. An $L$-reduction to CVP is very similar to an $L$-uniform circuit (the only difference is that the inputs to the circuit could be any $L$-functions). Specifically, an AC$^0$-reduction to CVP can be converted to a uniform circuit (the notion of uniformity depends on the exact format of circuits, but it can probably be taken all the way down to AC$^0$).

The same phenomenon occurs whenever we have a universal circuit (in the case of P, this is the circuit solving CVP). For a recent example, see this paper on comparator circuits.


Degree conditions sufficient for Hall's theorem

Are you by any chance looking for Hall's theorem ? It gives a complete characterization of when a bipartite graph admits a perfect matching. Specifically:

G admits a perfect matching if and only if for all subsets $S \subset L$, we have
$$ |\Gamma(S)| \ge |S|$$ where $\Gamma(S) \subset R$ is the set of neighbors of vertices in $S$.


How do I test if a polygon is monotone with respect to a line?

Hint: A generic simple polygon is monotone with respect to the $x$-axis if and only if it has exactly one vertex whose $x$-coordinate is smaller than its neighbors.  This observation immediately suggests an $O(n)$-time algorithm, at least if no edge of your polygon is vertical.

Spoilers ahoy:

  IsMonotone(X[0..n-1], Y[0..n-1])
    local_mins ← 0
    for i ← 0 to n-1
        if (X[i] < X[i+1 mod n]) and (X[i] < X[i-1 mod n])
            local_mins ← local_mins + 1
    return (local_mins = 1)

If you're worried that your polygon might have vertical edges, use the following subroutine in place of the comparison X[i] < X[j] to consistently break ties:

IsLess(X, i, j):
    return ((X[i] < X[j]) or (X[i] = X[j] and i < j))

Finally, if $L$ is some other line of the form $ax+by=c$, modify IsLess as follows:

IsLess(X, Y, i, j):
    Di ← a·X[i] + b·Y[i]
    Dj ← a·X[j] + b·Y[j]
    return ((Dj < Dj) or (Di = Dj and i < j))


Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c>0$.  That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).


Convert (x + y = z) to propositional logic formula for 8-bit numbers

You can obtain a formula in CNF form by writing down a truth table (with $2^{24}$ rows) and then converting each row to a single clause.  This will yield a formula with $2^{24}$ clauses, but the method is straightforward.

If you want a shorter formula, I suggest using logic synthesis, e.g., Quine-McClusky, Espresso.

The usual path to get a small formula is to allow introduction of additional variables, build a circuit (e.g., an adder circuit followed by a comparator), then convert to a formula using the Tseitin transform.  This yields much smaller formulas, but it requires introducing extra variables, which you said you don't want.


Suppose you are running two concurrent processes (or threads), which both perform intensive disk I/O. Both repeatedly attempt to read/write on some file.

Now, the scheduler must decide which requests to handle. The scheduler could serve the first process, then the second on, then the first, etc. in a round-robin fashion. This would guarantee fairness: any process request is eventually served.

Suppose instead that the scheduler wants to maximize disk throughput. One way to do that is to move the disk head as little as possible. This can be done by serving the I/O request which operates on the closest file (roughly speaking) to where the head is found at the moment. Assume the first process only accesses file A, while the second process accesses only file B. If both continuously perform requests on their files, the only one of them will be served: e.g. if A is the first accessed file, B will never get accessed since keeping the disk head on A optimizes performance with respect to moving the head to file B. Hence, the second process will never get served, and will "starve". This scheduler is not fair.


These are two distinct phenomena.   Contention refers to the fact that when thread $A$ has accessed a resource $B$ needs to wait until $A$ frees it.

Race refers to the fact when both threads $A$ and $B$ want to secure access to a resource.  The fastest will secure it and thus lead to contention.


Finding minimum possible cost of road network between cities with distance from capital condition

The MST indeed adresses conditions 1 and 3 but not conditions 2. The solution of the global problem (as shown by your example) is not the MST but still a tree.
Let's call $T$ the solution for the input graph $G$. Let's also call $T_i$ the solution for the problem $G_i$ which is the subgraph of $G$ containing vertices with range index lower or equal to $i$ (I will use the term "range index" to prevent confusion with the vertex indexing used for Prim's algorithm).
Trivially $T_0$ and $G_0$ contain only the capital. Now what about $G_1$ ?
The cities having a range index of 1 cannot use largest index cities to connect captial. Thus $T_1$, which is by the way MST of $G_1$, is a subgraph of $T$.
$T_{i+1}$ is built the same way using $T_i$ and $G_{i+1}$. The edges of $T_i$ are kept and only the new edges to connect the cities having range index $i+1$ are added using any MST algorithm.


Regular languages and constructing a regular grammar

First of all it is enough if we can give regular expression for a regular language. To determine if a language is regular you have to show existence of a DFA or a regular expression for the language. Or you can show it is regular if you can prove it is union, intersection, concatenation, etc. (operations under which regular languages are closed) of other known regular languages.

The language in question is regular because it has regular expression $aa^*bb^*cc^*dd^*$.

To construct a regular grammar you need to do it step by step.

$A \rightarrow aA\ \  | \ \ a$
$B \rightarrow bB\ \  | \ \ b$
$C \rightarrow cC\ \  | \ \ c$
$D \rightarrow dD\ \  | \ \ d$

Then finally,

$S \rightarrow ABCD $

Yet another method to get a regular grammar is to convert from DFA. Then you will get (which might be a little difficult to understand right away):

$S \rightarrow aA$
$A \rightarrow aA\ \ |\ \ bB$
$B \rightarrow bB\ \ |\ \ cC$
$C \rightarrow cC\ \ |\ \ dD$
$D \rightarrow dD \ \ |\ \  \epsilon $

My two cent opinion is directly write a lexer (or use automatic-lexer-generator like flex) rather than writing a parser (or using automatic-parser-generator like bison).


What is the difference between dynamic programming and a mere caching?

There are some other key aspects of dynamic programming besides caching, namely, it is about writing solutions of optimization problems recursively to exploit the fact that optimal solutions are constructed out of optimal solutions to subproblems, and further that caching limits the number of recursive calls to the maximum number of distinct subproblems that need to be solved.

Also, dynamic programming is not so much a formalism, as an intuitive framework for solving many optimization problems recursively.

Further, the use of such an "epic buzzword" is largely the result of brilliant marketing by Richard Bellman...


Woman optimal Gale Shapley Stable Matching

Yes, of course you can switch the roles of men and women in the algorithm and you'll get a woman-optimal solution. It's just convention that we call one side of the graph "men" and the other side "women" but the algorithm itself doesn't care what names we use. We could just as well call them "horse" and "blueberry".


Maintaining data structure with two operations

You might want to look into R-trees (described in detail here) or a similar tree data structure for spatial indexing.


How to use an old SAT solver to discover a new one, as is done in The Golden Ticket?

Actually, probably you can't use a SAT solver to find another SAT solver, unless something surprising happens.

If P = NP, then you can.  If P = NP, then the polynomial hierarchy collapses (i.e., P = PH), so there is a polynomial-time algorithm for every problem in PH.  The problem of asking whether there is a faster SAT solving algorithm is essentially a $\Sigma_2$ problem, which is part of the polynomial hierarchy; if the polynomial hierarchy collapses, there's a polynomial-time algorithm for every problem in PH and thus for every problem in $\Sigma_2$.  Thus you can in polynomial time search for a better SAT solver, if P = NP.

But most researchers expect that P is not equal to NP, so this statement is most likely moot and unlikely to be helpful in practice.

If P is not equal to NP, then this reasoning doesn't work.  In fact, many researchers expect that $\Sigma_2$ is even harder than NP (there are problems in $\Sigma_2$ that are harder than any problem in NP), so it would be surprising if there was a simple reduction to express the problem "find me a faster SAT solver" as an instance of SAT.  In particular, SAT solvers can solve SAT, or any other problem in NP -- but in any case, only problems in NP.  If (as we suspect) $\Sigma_2$ is harder than NP, then SAT solvers can't solve problems in $\Sigma_2$.

Of course, we don't actually know.  It's always possible that the conventional wisdom is wrong, and that tomorrow we discover that P is actually equal to NP.  That would be a great surprise, but we can't completely rule it out.

The Golden Ticket is trying to give a deeper understanding of why complexity theorists consider the P vs NP problem so important and so fundamental.  Part of that involves exploring counterfactual worlds and counterfactual assumptions that we suspect are probably false, to see what their consequences would be.

Or, to explain it a different way:

The problem is that finding a better SAT solver is a $\exists \forall $ kind of statement.  The statement is of the form $\exists A \forall x . P(A,x)$, where $P(A,x)$ is the statement that $A$ is fast and correctly solves the SAT instance $x$.  Those kinds of statements can't be solved with a SAT solver.  SAT solvers can solve problems of the form $\exists x. Q(x)$.  However, $\exists \forall$ statements are harder than $\exists$ statements.  This is basically the difference between $\Sigma_2$ and NP.


Flow graph with non zero lower bound or 0 capacity

Your problem is NP-hard.  In the special case where no job requires any particular features, and all printers have the same availability, this becomes just the bin packing problem, which is (strongly) NP-complete.
You could try adapting standard algorithms for bin packing to your situation.  For instance, one approach would be to use integer linear programming and hope the ILP solver can handle the resulting problem instance.


Computing parity function on n variables with O(n) gates

Because the parity is 1 if and only if the XOR of all the bits is 1.  In other words, computing the parity is equivalent to computing the XOR of the bits.  Sipser describes how to compute the XOR of the $n$ bits with $O(n)$ gates, which means that this same circuit computes the parity of those $n$ bits with $O(n)$ gates.


Longest possible path from root to a leaf of a red black tree

As you can read as "Properties" in the "Wiki Red-Black Tree", "the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.".

For a Red-Black Tree having 'N' nodes, the mean length path is 'ln(N + 1) + 1' (for 'N=10' 'Lmean = 2.397 + 1 >> 4').

Note: `ln(X) = neperian logarithm'.

So the Longest balanced-path from root to leaf is shorter than the double of the mean length '< 2 * ln(N + 1) + 1'. (for 'N= 10' longest < 8).


For a problem to be approachable using what we presently call "AI methods", it has to be, at least theoretically, also solvable using "regular" methods (writing a set of instructions that solves it, line by line). Thus, decidable.

AI systems may create effective algorithms whose operation no human can understand. Also, by using AI methods we may find solutions to new problems, by accident, or discover that problems are decidable. These things do not contradict the affirmative above.

An algorithm exists that solves the problem.


Suppose first that $\log n$ stands for base 2 logarithm. In this case, since $n = 2^{\log n}$, we have
$$
2^{c\log^2 n} = (2^{\log n})^{c\log n} = n^{c \log n},
$$
from which your identity immediately follows.

If $\log n$ uses some other base, we still get the same result, because both sides of the identity are insensitive to the base of the logarithm. This is because different logarithms differ by a constant factor, and this constant factor can be swallowed by the union over $c$. Details left to you.


How do I determine the basic operation of this algorithm?

"Basic operations" are whatever you choose. You may get different results based on your choice, which is great as it leads to understanding algorithms better! You may have seen the number of comparisons and swaps being analyzed independently in array sorting algorithms.

As a corollary, your professor can pick whatever they want. We can't possibly know their mind; you'll have to ask them.

That said, if you're after "time complexity", you want to count how often a dominant operation occurs. See here and here (section "A note on asymptotic cost"). In case of doubt, just count all candidate operations.

  Getting different results based on my choice is something I also think is not applicable here, as the two options I am struggling between have identical results in when going towards infinite input sizes.

In that case, the choice doesn't matter. Either both operations are dominant and your result is correct, or they are both not and you need to pick another operation entirely.


Closure of Deterministic context-free languages under prefix

DCFL are known to be closed under quotient with regular languages, but the quotient of $L$ with $\Sigma^{*}$ is precisely $\text{pref}(L)$ so yes, if $L$ is a DCFL then $\text{pref}(L)$ is a DCFL.


Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$

More generally, you can use Myhill–Nerode to prove the following characterization:

For $A \subseteq \mathbb{N}$, let $L(A) = \{ a^n : n \in A \}$.
The language $L(A)$ is regular iff $A$ is eventually periodic.

In particular, if $A$ is an infinite set with density zero then $L(A)$ is not regular. Here density zero means:
$$
\lim_{n\to\infty} \frac{|A \cap \{0,\ldots,n-1\}|}{n} = 0.
$$
This shows that $\{a^{n^k} : n \in \mathbb{N}\}$ is not regular for any $k \geq 2$.

Let us prove the claimed characterization. If $A$ is periodic, say with period $m$, then $L(A)$ is clearly regular: it is accepted by a circular DFA with $m$ states. If $A$ is eventually periodic then there is a periodic $B$ such that $L(A),L(B)$ differ in finitely many words, and so standard closure operations show that $L(A)$ is regular.
Now suppose that $L(A)$ is regular. The equivalent class of $a^m$ is the set $E_m = \{ k \in \mathbb{N} : m+k \in A \}$. Since there are finitely many equivalence classes, there exist $m < p$ such that $E_m = E_p$, that is, for all $k \in \mathbb{N}$, $m + k \in A$ iff $p + k \in A$. In other words, for all $\ell \geq m$, $\ell \in A$ iff $\ell + (p-m) \in A$. Hence $A$ is eventually periodic (with period $p-m$).


Examples of Regular, Context-free and Context-sensitive languages

$L_1$, $L_2$ and $L_4$ are correct (notice that you are not showing that $L_2$ is not regular and $L_4$ is not context-free, which can be done using the appropriate version of the pumping lemma).

As far as $L_3$ is concerned, let  $x$ be the number that is encoded in binary and call $x_i$ its $i$-th least significant bit, indexed from $0$. Then, counting modulo 5, we have:

$\displaystyle x = \sum_{i=0}^\infty x_i 2^i = \sum_{i=0,4,8..} x_i + 2 \sum_{i=1,5,9..} x_i + 4 \sum_{i=2,6,10..} x_i + 3 \sum_{i=3,7,11..} x_i$.

I.e., the least significant binary digit contributes $1$ to $x \bmod 5$, the next one contributes 2, then 4, 3, 1, 2, 4, 3, ... and this pattern repeats.

This means that you can create a DFA that recognizes $L_3^R$ (and hence $L_3$) using at most 20 states, namely $\langle i,j \rangle$ where $i \in \{0,1,2,3\}$ is the index, modulo 4, of the next character in the string, and $j \in \{0,1,2,3,4\}$ is the partial sum, modulo $5$, of the contributions of binary digits seen so far.

If the next bit is $0$ then:
$\langle i,j \rangle \to \langle i+1 \pmod 5, j \rangle$.

If the next bit is $1$ then $\langle i,j \rangle \to \langle  i+1 \pmod 5, j+ 2^i  \pmod 5\rangle$. Writing this down explicitly:

$\langle 0,j \rangle \to \langle 1, j+1  \pmod 5\rangle$;
$\langle 1,j \rangle \to \langle 2, j+2  \pmod 5\rangle$;
$\langle 2,j \rangle \to \langle 3, j+4  \pmod 5\rangle$;
$\langle 3,j \rangle \to \langle 0, j+3  \pmod 5\rangle$.

The initial state is $\langle 0, 0 \rangle$ and the final states are all the ones of the form $\langle i, 0 \rangle$.


The case that $P \subset NP = coNP$ is possible. The reason why $P = NP$ implies $NP = coNP$ is that $P$ is closed under complement, and so if $P = NP$, $NP$ must be closed under complement as well.

A class being closed under complement doesn't necessarily imply anything about its deterministic counterpart. For example, we know that $NL$ is closed under complement, but don't know whether $L = NL$.


why is this computational method by Knuth "effective" and "powerful"?

It's necessary to have some restriction such as "$\alpha$ is shortest possible string for which $\sigma = \alpha \theta_j \omega$" so the algorithm is unambiguous, because it's possible for $\theta_j$ to appear at multiple locations in $\sigma$.
After seeing Knuth's answer to exercise 1.1.8, I see how something like $x^k$ can be computed this way. Below is my rather cumbersome approach.

Let $A = \{a,b,c,d,e,t\}$ and $N=10$.

Given $x,k$ where $x>0$ and $k \ge 0$, the input will be $a^xb^k$ ($2^3$ would have input $aabbb$), and output will be the string $c^{x^k}$ ($x^k$ number of $c$'s. empty string denotes 1).

\begin{array}{cccccc}
j & \theta_j & \phi_j & b_j & a_j & \text{comments}\\
0 & b & (\text{empty}) & 1 & 9 & \text{remove one $b$. if no $b$, done.} \\
1 & c & c & 3 & 2 & \text{if first time (no $c$'s), add $c$. else expand} \\
2 & a & tc & 2 & 8 & \text{add a $c$ for each $a$} \\
3 & a & t & 4 & 6 & \text{for each $a$, add in $c$ amount of $d$'s} \\
4 & c & ed & 4 & 5 & \text{for each c, add in a $d$} \\
5 & e & c & 5 & 3 & \text{change $e$ back to $c$} \\
6 & c & (\text{empty}) & 6 & 7 & \text{clean up. remove all $c$'s} \\
7 & d & c & 7 & 8 & \text{clean up. change all $d$'s back to $c$'s}\\
8 & t & a & 8 & 0 & \text{clean up. change $t$'s to $a$'s}\\
9 & a & (\text{empty}) & 9 & 10 & \text{remove all $a$'s. return}
\end{array}


When using a hash and a collision occurs and linear probing is used how is that item found again

Any given equality function over the objects.  You're asking if an object is in a hash table, and it is if there is an object that is "equal" to the given object.

And remember that object equality implies hash equality.


Finding the longest path of sum $0$ in a weighted tree

If the (simple) path needs to go from the root to a descendant:

Perform BFS or a preorder DFS visit of your tree and, for each vertex $v$, record:

the length $\ell(v)$ of the unique path from the root of the tree to $v$; and
the depth $d(v)$ of $v$ in $t$.

This can be done in constant time per vertex since, if $v$ is the root $\ell(v)=d(v)=0$, otherwise $\ell(v) = \ell(u) + w(u,v)$ and $d(v) = d(u) + 1$, where $u$ is the parent of $v$.

Return the vertex $v$ for which $\ell(v)=0$ and $h(v)$ is maximized. The total time spent is linear.

If the (simple)  path needs to go from an ancestor to a descendant:

Perform a preorder DFS visit and maintain a dictionary $D$ that stores the ancestors $u$ of the current vertex $v$. The key of a vertex $u$ in $D$ is the length $\ell(u)$.

When an edge $(u,v)$ is traversed moving away from the root, add $\ell(u)$ to $D$. When an edge $(u,v)$ is traversed (moving towards the root) remove $\ell(u)$ from $D$. In case of ties in $D$ break them in favor of the lowest vertex.

When a vertex $v$ is visited, we want to search $D$ for an ancestor $u$ of $v$ with key $\ell(u) = \ell(v)$, meaning that the path from $u$ to $v$ has length $\ell(v) - \ell(u) = 0$. This can be done in $O(\log H) = O(\log n)$ time, where $H$ is the height of the tree.

The overall time complexity is then $O(n \log H) = O(n \log n)$.

If the (simple) path can be arbitrary:

For each vertex $v$ compute its depth $d(v)$ in any standard way.

Perform a postorder DFS visit and, for each vertex $v$, maintain a dictionary $D_v$ that stores all descendants $z$ of $v$. The key of $z$ is the distance from $v$ to $z$. Break ties in favor of vertices $z$ with larger $d(z)$. In addition to the standard operations, you can also assume that $D$ is able to increase all its keys by a constant amount in $O(1)$ time.

When $v$ is visited and $v$ is a leaf, $D_v$ contains only $v$ itself with key $0$. Otherwise, let $u_1, \dots, u_k$ be $v$'s children and assume w.l.o.g. that  $u_1$ maximizes $|D_{u_1}|$. Construct $D_v$ as follows:

Initially $D_v = D_{u_1}$.  Notice that $D_{u_1}$ will not be used anymore. This operation amounts to renaming $D_{u_1}$ to $D_v$.
Increase all the keys in $D_v$ by $w(v, {u_1})$.
Add $v$ with key $0$ to $D_v$.
The vertex $z$ with key $0$ in $D_v$ is such that the path from $v$ to $z$ has length $0$ and the number of edges from $v$ to $z$ is maximized (remember our tie-breaking rule). This is a candidate path.
For each $u = u_2, \dots, u_k$:

For each vertex $a$ with key $\ell_a \in D_u$:

Check whether there is a vertex $b$ in $D_v$ with key $\ell_b = -\ell_a - w(v,u)$. If this is the case then there is a candidate path from $a$ to $b$ of length $0$ and hop-length $d(a) + d(b) - 2d(v)$.

For each vertex $z$ with key $\ell_z \in D_u$:

Move vertex $z$ from $D_u$ to $D_v$. Its new key in $D_v$ is $\ell_z + w(v,u)$.

Return the best candidate path seen during the visit.

To bound the time complexity notice that, apart from a $O(n \log n)$ term needed to add the vertices $v$ into $D_v$, it is dominated by the complexity needed to move vertices $z$. When a vertex $v$ is moved from $D_u$ to $D_v$, the size of $D_v$ will be at least twice the size of $D_u$. This means that each vertex can be moved at most $O(\log n)$ times.

The overall time complexity is therefore $O(n \log^2 n)$.


Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V

You never say what the goal is. I suspect that you want to find the shortest a path from a given vertex $s$ to a given vertex $t$ that passes through at most two vertices in $X$.
In this case you can assume w.l.o.g., that $s,t \not\in X$. Moreover, you can assume that the input graph is directed. If this is not the case, then  you can preliminarily replace each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$.
Let $G=(V,E)$ be the input graph and let $F = \{ (u,v) \mid u \in X\}$ be the set of outgoing edges from some vertex in $X$. Make a new graph $H$ containing three copies $G_1, G_2, G_3$ of the graph $(V, E \setminus F)$.
Then, augment the graph as follows:

For each edge $(u,v) \in F$ add:

an edge (of weight $0$) between the copy of $u$ in $G_1$ and the copy of $v$ in $G_2$.
an edge (of weight $0$) between the copy of $u$ in $G_2$ and the copy of $v$ in $G_3$.

Add a new vertex $t^*$ and the three edges (of weight 0) between each copy of $t$ in $G_1$, $G_2$, and $G_3$ and $t^*$.

You can now find a shortest path $P$ between the copy of $s$ in $G_1$ and $t^*$.
The list of vertices traversed by $P$ (except for the final vertex $t^*$) will induce the sought shortest path on $G$.


Sigmoid does add nonlinearity -- and the nonlinearity "builds" as you add more layers.  Neural networks can recognize arbitrary decision boundaries (given enough neurons and enough layers).

I think your visualization of what the sigmoid activation does is a bit off.  Take a look at http://playground.tensorflow.org/ and play with some of the tuning knobs to see the kinds of decision boundaries that can be achieved -- that site is a helpful way to get some intuition.

So, the answer to your question is: we don't need a separate version of neural networks.  Standard neural networks already can support arbitrary decision boundary shapes.

[ About the kernel trick: The kernel trick can be used here, but is possibly a bit more expensive than in the case of SVM's; for SVM's, there's a particular mathematical trick that avoids the need to generate all of the "extra features", but that trick is specific to SVM's.  You can still construct derived features and add them to the feature vector before applying a neural network, though, if you want -- nothing prevents you from doing it.  But the kernel trick isn't needed, because neural networks can learn non-linear functions.  In contrast, without the kernel trick, SVMs can only learn linear decision boundaries, so it's needed more there. ]


How many syntax trees can be made by a BNF

The answer is given by the Catalan numbers; if you have $n$ operators, the number of syntax trees is $\frac{1}{n+1}{2n \choose n}$. The problem is equivalent to finding all ways of inserting $n$ parentheses pairs in a word of $n+1$ letters, as mentioned in OEIS:

  Number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).

There are several ways to prove this, e.g. via the Dyck language. The Wikipedia article contains several ones.


Ordering a list of lists subject to constraints

This problem is an instance of the list coloring problem.  The list coloring problem is a variant of the graph color problem, where additionally have constraints that provide for each vertex a list of allowable colors that can be used for that vertex.

Here's the relationship.  Let $V$ denote the set of distinct values that appear in any row.  In Example 1, $V=\{A,B,C,D,E\}$; in Example 2, $V=\{A,B,C,D\}$.  Form an undirected graph $G$ where $V$ is the vertex set (so each value is a vertex).  Add an edge $(u,v)$ between two values if there is some row where those two vertices appear together.

Now suppose we want to arrange these in a matrix with $c$ columns (i.e., $c$ is the length of the longest row).  We'll imagine having $c$ colors, numbered from $1$ to $c$, where color $i$ corresponds to the $i$th column.  If the value $v$ is colored $i$, we take this to mean that every appearance of value $v$ should appear in column $i$.

Now from each row that is less than $c$ values long, we obtain some constraints.  In particular, if we have a row that is $\ell$ values long, then each value in that row needs to be colored with a color in the set $\{1,2,\dots,\ell\}$ (to ensure the lower-triangular requirement).  These are the lists that make this a list coloring problem.

Now any solution to the list coloring problem yields a solution to your problem: the colors tell you what column to put each value into, which tells you how to permute each of your rows to form a valid solution.  Therefore, you can use any algorithm for the list coloring problem to solve your problem.


Viterbi training vs. Baum-Welch algorithm

From my comment:

This answer on crossvalidate.SE may be of use. I wasn't aware of viterbi-training. I have only used BW or other EM-based methods in the past. Based on the answer in the link, I think BW would be the most useful. It seems Viterbi-Training gives no guarantee on bounds. However, the latter does have useful application if BW takes far too long to compute.


Cost of find operation on a tree data-structure

Since my two comments already form the solution, I can also write the answer in total.

If you have a datastructure consisting of a bunch of trees, then the worst-case cost of a Find-Operation is the maximal height of a tree in your data structure. Your trees are built from $n$ trees consisting of a single node each by $n-1$ Merge-Operations. A Merge-Operation merges two trees such that the tree of smaller height is added to the root of the tree of larger height.

First observation:
If you merge two trees of different height, then the resulting tree has the same height as the initial tree of larger height.

Second observation:
If you merge two trees of the same height $h$, then the resultung tree has height $h+1$.

Conclusion: To increase the maximum height from $h$ to $h+1$, you first need two trees of height $h$.
So the worst-case scenario in your setting is the following:
You initially merge two trees consisting of a single node each. This gives a tree of height $1$. You now need to merge two other trees consisting of a single node each such that a second tree of height $1$ occurs. If you now merge this trees of height $1$, then you have a resulting tree of height $2$. Now if you want to increase the height again, you need again $4$ of the initial trees to construct an other tree of height $2$.

The iteration of that argument shows that you can only increase the height $\log n$ times, where $n$ is the number of initial trees.


Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.
Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ with capacity $3$; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.
Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$.
Your problem admits a solution if and only if the amount of flow $|\phi|$ is $3|V|$.
To see this, first observe that $3|V|$ is an upper bound on $|\phi|$. Then suppose that there exists a feasible orientation $\mathcal{O}$ and look at any partial orientation $\mathcal{O}'$ in which each vertex $v$ has exactly three outgoing edges.
A flow $\phi$ such that $|\phi|=3|V|$ is obtained by sending one unit of flow across each edge $(v,e) \in F$ such that $e$ is oriented away from $v$ in $\mathcal{O}'$, the flow across each edge $(s,v)$ is $3$, and the flow across $(e,t)$ is 1 if $e$ is oriented in $\mathcal{O}'$ and $0$ otherwise.
Suppose now that there is a flow $\phi$ such that $|\phi|=3|V|$. W.l.o.g., $\phi$ is integral. A feasible orientation is obtained by orienting each edge $e \in E$ away from the (at most one) endpoint $v$ of $e$ for which $\phi(v,e)=1$. If no such endpoint exists, then $e$ can be oriented arbitrarily. Notice that this procedure is constructive and immediately yields an algorithm for your problem.


Difference between SRSW and MRSW safe Boolean registers

You do not know anything about the behavior of the register if read calls overlap.

Perhaps the register is a sensitive electrical component and overlapping reads will blow it up?

Perhaps reading (counter-intuitively) requires changing the state of the register, for instance writing the target memory location which the value must be read in to? If two reads overlap then it might end up writing the value to the wrong location or to only one of the two locations?


Plotting isn't foolproof: for any $k,\varepsilon>0$, we have $\log^kn = o(n^\varepsilon)$ (here, I've cancelled the common term of $n^2$). However, you can need to take $n$ really big to see it when $\varepsilon$ is small (e.g., $0.095$) and $k$ isn't so small (e.g., $5$).  Here's the plot for $0\leq n\leq 10^{131}$, again with the $n^2$ term cancelled, and it looks quite different from your plot up to $n=10^5\,$!

Indeed, this question may even have been designed to catch you out if you try to compare the asymptotic growth by plotting instead of by understanding.


The application itself gets to decide what it wants in virtual memory (within some restrictions). By default that will be the code it run and the memory it uses. The application can also request files to be mapped into memory, or that memory gets shared with another application.

Then the kernel will decide which parts of virtual memory are loaded in RAM based on various factors like: how much ram is available; how much is needed by other processes; how recently a region of virtual memory was accessed, ...


Logarithmic Randomness is Necessary for PCP Theorem

You can actually show a slightly stronger result: if $SAT \in PCP(o(\log n), o(\log n))$ then P=NP. The idea is to apply the implied reduction repeatedly, reducing the size of the instance all the way down to $O(\log n)$, at which point you can solve it by trying all certificates.

For more details, Arora and Safra (page 76) suggest looking at Theorem 26 in the appendix of FGLSS (journal version). Unfortunately, this appendix doesn't seem to be available any more.


Classification of the complement of a language

The complement of $L$ is:

$\bar{L} = \{\langle M \rangle \mid \text{ all strings accepted by $M$ have the same length} \}$

Your intuition that $\bar{L}$ is not recursively enumerable is correct, it is in fact complete for $\Pi^0_1$ by reduction from the emptiness problem. If you only need to prove that $\bar{L}$ is not in $\textsf{RE}$, it is sufficient to observe that $L$ is undecidable (reduction from the halting problem) but $\textsf{RE}$ (trivial).


Subgraph Isomophism Problem - Color Coding Technique - Proof Sketch

The idea is to repeat the proof of Theorem 6.1, only during the recursive construction in the second paragraph, we use the tree decomposition of $H$ rather than $H$ itself. We pick a vertex in the tree decomposition, which correspond to up to $t+1$ vertices of $H$, and split $H$ into two parts $H',H''$ accordingly, applying the algorithm recursively. Since we are dealing with groups of up to $t+1$ vertices at a time, we have to calculate the color sets for sets of $t+1$ vertices rather than for single vertices.

There are many resources online for this general approach, dynamic programming for graphs of bounded treewidth. You can consult Section 2.4 of Hajiaghayi's thesis or a presentation by Marx.


structure of cache when CPU uses words smaller than the main memory

So the question is a bit confusing because there are two types of words: CPU words that are 16 bits, and memory words that are 32 bits. This can happen when the CPU registers have 16 bits but the memory chip is organized in such a way that the minimum accessible unit (a word) is 32-bit. The cache will always read/write multiple of memory words, in this case one word per line. Since the CPU word is 16 bits, each memory word (32 bits) actually holds two CPU words, those are the Word 0 and Word 1 on the picture.

Now, when the CPU accesses memory, the cache will find which lines corresponds to the request. This line contains 32-bit, but maybe the CPU only wanted 8 bits, so we have to extract those 8 bits from the line. In this example, bit 1 will select between Word 0 and Word 1 (which are CPU words). The resulting word still has 16 bit, so we use bit 0 to select between the low or high 8 bits of that word.

If you still find confusing, forgot about Word 0 and Word 1 and just imagine that each cache line stores 4 bytes (=32 bits). Now to select one byte in 4, you need to discriminate based on the lower 2 bits of the address. If the cache had 8 bytes per line, then you would use 3 bits. And so on. In general, the format of an address is

| Tag | Index | Offset |

where Index selects the line (there are many way of doing so) and Offset selects the byte within the Line.


Insertion sort maintains the following loop invariant:

After iteration $i$, the first $i$ positions in the array are the first $i$ positions of the input, in sorted order

Note that this doesn't mean that they need to be in their final positions for the sort to work at the end.  I'd say that this is the defining thing for "insertion sort", but that's not really a formal statement.

Insertion sort is not hard to turn into a recursive procedure.  The main routine you want is a helper called  insert-sorted such that consumes a sorted list and a number, and outputs a new sorted list (one longer) that includes the number.  You can write it in a way that is pretty much paradigmatic for Scheme (note, code just typed in, not tried):

(define (insert-sorted n l le)
    (if (null? l)
        (list n)
        (if (le n (car l))
            (cons n l)
            (cons (car l) (insert-sorted n (cdr l) le)))))

In words, if n comes before the first element of l or l is empty, then n goes in first position.  Otherwise, the list we want starts with the first element of l and ends with n in the right place in the tail of l.

With the helper, involves repeatedly calling insert-sorted to build up the sorted list.  If you want to follow the invariant exactly, then an approach like this will work:

(define (insertion-sort l le)
    (define (rec s l)
        (if (null? l) s (rec (insert-sorted (car l) s le) (cdr l))))
    (rec '() l))

However, this solution explicitly maintains s, the partially sorted list.  More idiomatic scheme would be to just use the call stack for this:

(define (insertion-sort l le)
    (if (null? l)
        '()
         (insert-sorted (car l) (insertion-sort (cdr l) le) le)))

I'll leave it to you to work out what the invariant for each implementation is.


Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?

No, it doesn't become easier. Metric TSP (the version where the distances obey the triangle inequality) is still NP-complete but, in this scenario, the shortest tour always visits every city exactly once. The triangle inequality guarantees that going directly to a new city is always faster than going there via somewhere you've already been.


Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem

I'm referring here to the proof of the hierarchy theorem as I am familiar with it, in which I don't see the problem you mention.

We define the language
$L=\{(M,w): M $ does not accept $(M,w)$ within $\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\}$ (where $t$ is the time function we are working on).

We show that $L$ is decidable in $O(t(n))$ using the universal machine, and in the universal machine each step is indeed dependent on the size of the machine, which is why we have $|M|^3$ in the denominator (the 3 is just some upper bound on the computations needed to simulate a step).

For completeness of the answer: when we try to reach a contradiction, then we assume that there exists a machine $T$ that decides $L$. After this assumption, the encoding of $T$ is fixed, and then a simulation of a single step really does take constant time, and we can reach a contradiction by taking a long enough $w$ to increase the length of the input without changing $T$.


What is the fastest algorithm for finding all shortest paths in a sparse graph?

Since this is an unweighted graph, you could run a Breadth First Search (BFS) from every vertex $v$ in the graph. Each run of BFS gives you the shortest distances (and paths) from the starting vertex to every other vertex. Time complexity for one BFS is $O(V + E) = O(V)$ since $E = O(V)$ in your sparse graph. Running it $V$ times gives you a $O(V^2)$ time complexity.

For a weighted directed graph, the Johnson's algorithm as suggested by Yuval is the fastest for sparse graphs. It takes $O(V^2\log V + VE)$ which in your case turns out to be $O(V^2\log V)$. For a weighted undirected graph, you could either run Dijkstra's algorithm from each node, or replace each undirected edge with two opposite directed edges and run the Johnson's algorithm. Both these will give the same aysmptotic times as Johnson's algorithm above for your sparse case. Also note that the BFS approach I mention above works for both directed and undirected graphs.


Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular

Here is a counterexample. Let $L_1$ be any language over some alphabet $\Sigma$ containing the empty string, and let $L_2 = \Sigma^*$. Then $L_2 = L_1L_2 = L_2L_1 = \Sigma^*$ are all regular, but $L_1$ need not be, in fact it could even be uncomputable!


Enumerate all maximal subset of a weighted knapsack

There might be exponentially many such maximal subsets, so there is in general no efficient way to enumerate all of them.

It's not hard to write a recursive algorithm to enumerate all subsets.  There are only two cases:

The subset doesn't contain item 1.  It consists of a maximal subset of items 2,3,... that sum to $P_\max$ or less.
The subset does contain item 1, plus a maximal subset of items 2,3,... that sum to $P_\max-v_1$ or less.

You can enumerate all subsets of the first type with a recursive call to the procedure, and enumerate all subsets of the second type with a second recursive call.  The base case: if $P_\max \le 0$ or $A$ is empty, then the only such subset is the empty set.


One area that you could consider is Fault Tolerant Parallel Computation. Expander codes and graphs could be efficiently used in them like:

Highly fault-tolerant parallel computation, by Daniel A. Spielman

On word-level parallelism in fault-tolerant computing


Thompson's construction, The empty-expression

It's not a special case since $a$ is a symbol of the alphabet whereas $\epsilon$ is a symbol representing the empty word. However, you could lump the two cases together if you wish.

It all boils down to your recursive definition of regular expression. Most definitions will have three "axioms": $a$ for $a \in \Sigma$, $\epsilon$, and $\emptyset$. This necessitates three different base cases in the construction.


What's the flaw in the P != NP proof in the article "The Computational Complexity of the Traveling Salesman Problem"

Yes, you are right: there are plenty of other possible algorithms the author ignores. Briefly, the author claims that the $\Theta^*(2^n)$ dynamic programming approach in the paper is nessecary to solve TSP. However, he completely ignores any sort of structure that may or may not exist in TSP instances.

So, we can look at special cases of TSP where we do know that we have special structure to see their argument is insufficient. For a simple example, consider the graph class where there is exactly one tour with cost $X$ and all edges not part of this tour have cost $>X$. Clearly, we can find a tour in $O(|E|)$ by selecting all edges with cost $\le X$. Note that if the argument of this paper would apply to the general case, it would also apply to this one, so this is a contradiction with his argument. Clearly, even if the claim of the author is correct, he has not proven it.


Finding duplicates in a stream of numbers

There might be other variations, but your answer should be pretty good.

There are two improvements to your algorithm, though.

Instead of a hashmap that counts the number of times each integer appears, you can just use a hashset to record the appearance of each integer.
While you are calling foo() in a loop, you will return immediately if you find the returned integer is in the hashset and if you are not required to finish the loop till the returned value of foo() is -1. Many built-in implementations return false when you insert an existing value into a hashset.


How can you bound the error of an approximation without knowing the optimal solution?

In general when you want to bound the approximation ratio of an algorithm you look for an easy lower bound on the optimal value. The most straightforward is often the LP relaxation of a (suitably chosen) ILP formulation of the problem. Sometimes other things are used, for TSP for example you can also use the weight of a MST (the optimal tour minus one edge is a tree, so it can't weigh less than the MST).

For particular instances you can of course still use the thing you use in your proofs, i.e. you can solve the LP and compare your heuristic solution to the LP value. If you have more CPU time on your hands you can also start a branch-and-bound process to solve the ILP. Even if you don't solve the ILP completely, you get better lower bounds from LP duality.


Help in geometrically understanding "Linear Decision Trees"

At each point in the linear decision tree, we branch according to whether $f(x) > 0$, $f(x) = 0$ or $f(x) < 0$, where $f$ is some linear functional. That means that the values of $x$ reaching some leaf are exactly those values satisfying some system of linear equations and inequalities
$$
\begin{align*}
&f_1(x) = f_2(x) = \dots = f_a(x) = 0, \\
&g_1(x), g_2(x), \dots, g_b(x) > 0, \\
&h_1(x), h_2(x), \dots, h_c(x) < 0.
\end{align*}
$$
Here $f_i,g_i,h_i$ are conditions encountered along the way. (In fact we can get rid of the $h$s, but this doesn't matter.) Each of these conditions — $f_i(x) = 0$, $g_j(x) > 0$ or $h_k(0) < 0$ — is convex, so their intersection is convex. This means that the set of all points getting to that leaf is convex, and in particular, either empty or connected.

In order to get a lower bound for element distinctness (for example), we show that the set $\{x : \text{all components of $x$ are distinct}\}$ has many (in fact $n!$) connected components. If we take one vector each from all the connected components, then all these vectors must land at different leaves (why?), so there must be many leaves, hence the tree must be deep.


Can there exist a recurrence relation for "sequential search"?

Sure.

The cost of searching a list of length zero is zero; the worst-case cost of searching a list of length $n$ is one greater than the cost of searching a list of length $n-1$. So
$$\begin{align*}T(0)&=0 \\ T(n)&=T(n-1)+1\,,\end{align*}$$
with solution being, as you'd expect, $T(n)=n$.