k-Closest pairs in Delaunay triangulation

This article [1] shows that this is not always true for the second-nearest neighbour and forth.
It shows that it is indeed the case for the (1st) nearest neighbour, and it's trivial, given the theorem that claims that if the circle defined by 2 points (as its diameter) is empty of other points then these points lie on an edge of the delaunay triangulation.

I didn't find a proper proof for that, and it is definitely not true for the opposite direction (not every edge of the DT defines an empty circle), but I have an idea of why this is true -

Let the points a,b define a circle Cab, having a-b as its diameter, empty of other points. The circle is empty of points, but cannot be empty of edges (the line connecting any pair of points must either be an edge or intersect an edge (by convexity of the map, and the fact that there are no diagonals in triangles).
Suppose a-b is not an edge of the DT, then it intersects an edge c-d, with both c and d out of Cab, that is part of a triangle c-d-e that either has w.l.o.g e=a, or e != a and is also outside of Cab, but this doesn't matter.
Anyway, the angles $\angle acb$ and $\angle adb$  have to be both sharp, as they are supported by the diameter of Cab, a-b, and lie outside of it, so this means $\angle cad + \angle cbd > 180^{\circ}$ (sum of angles in tetragon is 360), but as c-d is a chord in Ccde, so this means that at least one of the points a,b lies in Ccde, so c-d-e is not a legal delaunay triangle - contradiction.

Hope this hand waving is sufficient for your understanding.

All closest neighbors are proper Delaunay edges
generalized, and its application to parallel
algorithms by Arne Maus and Jon Moen Drange (2010)


How to define at least one occurrence of a string between two tokens in bottom up LALR(1) parser grammar

My solution, suggested by a friend, is to use a Finite State Machine. I drew a Deterministic Finite Automata, and $C$ is the final state accepted by this machine:

I then transformed it into a right regular grammar:

section     ::= c ;
a           ::= CODE SC ;
b           ::= a CODE SC ;
c           ::= c HOUR SC | b HOUR SC | e CODE SC ;
d           ::= HOUR SC | d HOUR SC ;
e           ::= e HOUR SC | a HOUR SC | d CODE SC ;

Hope it helps.


Should your heuristic for an A* search algorithm be the same scale as your actual weights?

I think you might have misunderstood the heuristic function.  It is supposed to give an underestimate on the distance from a node $n$ to the goal node $t$.  The closer this estimate is to the true value, the better A* will perform.
The only criterion for the heuristic function is that it never gives a higher value for $h(n)$ than the true cost of going from $n$ to $t$.
Let $\text{dist}(a, b)$ be the "true" distance from $a$ to $b$, and let $\text{dist}_0(a,b)$ be an underestimate (e.g. the Euclidean distance from $a$ to $b$ if you have a map).
If you are searching for a path from $s$ to $t$,
then $g(n)$ is defined to be $\text{dist}(s, n)$, whereas $h(n)$ is $\text{dist}_0(n, t)$.  So
$$ \text{dist}(s, n) + \text{dist}_0(n, t) = g(n) + h(n) = f(n).$$
There is nothing about scale of $g(n)$ and $h(n)$, except that $h(n)$ must give a lower value than (or equal to) the true distance from $n$ to $t$.


Is an undirected graph consisting only two connected vertices cyclic?

(1.) No, undirected cycles are also natural.

(2.) No, what you describe is a path on two vertices. It does not form a cycle, since by definition, you cannot find a subset of the edges that form a path where the first node of the path corresponds to the last.

To be sure about these type of things, you must always look at the definitions.


Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$

Your calculation is an example of proof by contradiction. You assumed that $a_n = Cn2^n$, and reached a contradiction $0 = 22$. You can conclude that $a_n \neq Cn2^n$.

Your calculation shows that the general solution to your equation is
$$
a_n = A + 2^n B + n2^n C.
$$
For some reason you forgot about the first two terms.

Let $P(x) = \sum_{n=0}^\infty a_n x^n$. Setting $a_{-1} = a_{-2} = 0$, we have
$$
(2x^2-3x+1) P(x) = \sum_{n=0}^\infty x^n (2a_{n-2} - 3 a_{n-1} + a_n) = \\
a_0 + (a_1 - 3a_0) x + \sum_{n=2}^\infty x^n (6 \cdot 2^n) = \\
a_0 + (a_1 - 3a_0) x + 24x^2 \sum_{m=0}^\infty (2x)^m = \\
a_0 + (a_1 - 3a_0) x + \frac{24x^2}{1-2x}.
$$
Since $2x^2-3x+1 = (2x-1)(x-1)$, it follows that
$$
P(x) = \frac{(1-2x)(a_0 + (a_1 - 3a_0) x) + 24x^2}{(1-2x)^2(1-x)} =
\frac{a_0 + (a_1 - 5a_0)x + (24-2a_1+6a_0)x^2}{(1-2x)^2(1-x)}.
$$
Routine calculation shows that
$$
\frac{1}{(1-2x)^2(1-x)} = \sum_{n=0}^\infty (1+2^{n+1}n)x^n,
$$
and so for $n \geq 2$ we get the formula
$$
a_n = a_0 (1 + 2^{n+1}n) + (a_1 - 5a_0) (1 + 2^n(n-1)) + (24 - 2a_1 + 6a_0) (1 + 2^{n-1}(n-2)).
$$
Opening this up, we get the solution
$$
a_n = 24 - a_1 + 2a_0 - (24 - a_1 + a_0) \cdot 2^n + 12 \cdot n2^n.
$$


it is given that L is a finite language over the unary alphabet and L+ is not regular.

That's impossible.  Since $L$ is finite, it is regular.  Since $L$ is regular, $L^+ = L L^*$ is regular.  See, e.g., https://en.wikipedia.org/wiki/Regular_language#Closure_properties.

You're not wrong; you are right.


Have you read Wikipedia's article on page tables?

There are two ways that a multi-level page table saves memory. First, you don't need to create parts of the page table for memory that isn't being used by the process: you only create the subtables for the parts of the virtual address space that are in use. Second, if you want to really live by the seat of your pants, you can use your virtual memory system to swap parts of the page table out of physical memory.


How is the definition of monads in category theory equivalent to the definition in functional programming?

The Haskell monads are known as Kleisli triples in mathematics.  I am guessing you're coming from the Haskell land, so let me just put down the translations between the two formulations in Haskell (I define everything from scratch on purpose and avoid clashes with standard notation):

{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE FlexibleInstances #-}

class MyMonad t where
  fun :: (a -> b) -> (t a -> t b) -- functorial action, known as fmap
  eta :: a -> t a
  mu :: t (t a) -> t a

class KleisliTriple t where
  ret :: a -> t a
  (>>==) :: t a -> (a -> t b) -> t b

instance KleisliTriple t => MyMonad t where
  fun f x = (x >>== (ret . f))
  mu x = (x >>== id)
  eta = ret

instance MyMonad t => KleisliTriple t where
  ret = eta
  (>>==) x f = mu (fun f x)

There's a bunch of equations to be verified, but they all work out, which is not to say that you should trust me or anyone else, work them out, it's a good exercise. Actually, you should try to reconstruct things by yourself. Take the code above and delete the two instances. Then try to reconstruct their definitions.

As for your question about monads being monoids in the endofunctor category, you'll just have to unfold all the definitions in the privacy of your own mind. I can give you a roadmap, but until you pick up pencil and paper and go through it all by yourself, it's not going to click.

Recall that a monoid is given by a set $T$, a multiplication operation $\mu : T \times T \to T$, and an element $\eta \in T$ such that

$\mu (x, \eta) = x$
$\mu (\eta, x) = x$
$\mu (\mu (x, y), z) = \mu (x, \mu (y, z))$

$\newcommand{\CC}{\mathcal{C}}$
$\newcommand{\pair}[1]{\langle #1 \rangle}$
This can be generalized as follows. Consider a monoidal category $\mathcal{C}$. It has a tensor product $\otimes$ which behaves a little like ordinary binary products, and it has a special object $I$ which is a unit for the tensor. A monoid object in the monoidal category $\CC$ is given by the following data:

an object $T \in \CC$
an arrow $\mu : T \otimes T \to T$
an arrow $\eta : I \to T$

subject to the laws that correspond to the three laws above. I am not going to reproduce the laws here, you can find them here.

If we take $\CC = \mathsf{Set}$, $A \otimes B = A \times B$, and $I = 1$ then we recover the usual notion of monoid.

Now let $\CC$ be any category (no monoidal structure required). The functor category $\CC^\CC$ is monoidal if we take the tensor to be composition of functors $F \otimes G = F \circ G$, and the unit the identity functor $I = \mathsf{Id}_{\CC}$. What is a monoid object in $\CC^\CC$? It is given by the following data:

a functor $T : \CC \to \CC$
a natural transformation $\mu : T \circ T \to T$
a natural transformation $\eta : \mathsf{Id} \to T$

subject to some laws. When we unfold those laws we get, you guessed it, precisely the laws for a monad.


Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size formula. The idea seems pretty straightforward too:
Everything stated previously applies to all rings, so if the elements of the matrix were $Z_2$, then we could consider the ring of $n \times n$ matrices over $Z_2$. There's clearly a $\log n$ depth formula for the product of $n$ ring elements, so we can apply theorem 4.
The only additional considerations are

Theorem 4 says the program will need only 3 working registers, but since each register holds an entire matrix, these registers will take up $O(n^2)$ space. This turns out to be completely fine for us, since we have polynomial catalytic space to work with.

In order to actually translate the program back onto our (catalytic) turing machine, we need to rewrite matrix instructions to instructions on the underlying ring ($Z_2$ for example). Luckily, this is trivial since each instruction in the form $r_i \leftarrow r_i \pm x \ast y$ becomes $n^3$ primitive instructions: $r_i^{uv} \leftarrow r_i^{uv} \pm x^{uw}y^{wv}$ for $u,v,w = 1 \ldots n$ and no extra space of any sort is used.

This seems to be roughly in agreement with the $O(n^9)$ time complexity given by the second reference from the OP -- the program size of $4^d$ from Theorem 4 combined with the $\log_2 n$ depth of the straightforward matrix multiplication formula makes an $O(n^2)$ sized program, each matrix instruction which is further broken down into $O(n^3)$ "primitive" instructions, and each instruction might take up to $O(n^3)$ time to execute on a turing machine due to the size of the inputs.


Exercise 12 (online version) in §1 of Ryan O'Donnell's Analysis of Boolean functions shows that all Fourier coefficients of a degree $d$ function are integer multiples of $2^{-d}$. In particular, the number of zeroes of $f$ is an integer multiple of $2^{n-d}$.

Moreover, for every integer $k \in \{0,\ldots,2^d\}$ there is a degree $d$ Boolean function having exactly $k2^{n-d}$ zeroes. This easily follows from the fact that a function on $d$ variables has degree at most $d$.


What are advantages / disadvantages of horizontal and vertical microprograms?

This questions seems dated, about the way computers and instruction sets were designed in the 70's.

AFAIK, micro-ops in x86 CPUs have about 100 bits, and are decoded separately in each operation unit (ALU, LSU, FPU...) There is no gigantic flat microcode controlling every multiplexer.

There used to be several layers of microcode and ROM decoding tables instructions are translated into "vertical" micro-ops which are then decoded into "horizontal" signals (IIRC, the MC68000 was like that).

Pure horizontal microcode is impractical in modern chips. Long wires have parasitic capacitance and are "slower" than transistors. Using a large and wide microcode ROM outputting hundreds or thousands of signals to individual adders, multiplexers and registers would make a large and slow chip.

Additionally, nowadays processors are pipelined : A wide microcode would need hundreds of flipflops to propagate instruction decoding along the pipeline.


Let us verify that $S$ is a decider for $A_{\text{TM}} = \{⟨M,w⟩\mid M \text{ is a TM and }M\text{ accepts } w\}$.

Let $⟨M,w⟩\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

First, construc $M_w$. Since $M$ accepts $w$, $M_w$ simulate $T$.
Use TM $R_P$ to determine whether $⟨M_w⟩ \in P$. Since $M_w$ simulate $T$, $⟨M_w⟩\in P$. So, the answer is YES. So, accept.

Now let $⟨M,w⟩\not\in A_{\text{TM}}$ be the input to $S$. Let us see how $S$ runs according to its specification.

First, construc $M_w$. Since $M$ do not accept $w$, $M_w$ simulate $T_\emptyset$.
Use TM $R_P$ to determine whether $⟨M_w⟩ \in P$. Since $M_w$ simulate $T_\emptyset$, $⟨M_w⟩\not\in P$. So, the answer is NO. So, reject.

The above analysis shows that $S$ is a decider for $A_{\text{TM}}$.

Hope this helps.

Exercise of a minute or less. Verify that if $M$ do not accept $w$, $M_w$ simulate $T_\emptyset$.


You can't prove a general theorem by proving one special case. So even if your proof of the special case were correct (and it isn't), all it does is prove that the theorem holds in that specific case.

Your proof is erroneous since $L/R$ is larger than what you indicate. In fact, whenever $\epsilon \in R$, we always have $L/R \supseteq L$. In your case
$$
L/R = \{ a^{n_1} b^{n_2} : n_2 \leq n_1 \} \cup \{ a^n b^n a^{m_1} b^{m_2} : m_2 \leq m_1 \}.
$$


Prove $\{abc : a+b=c\}$ is not context-free using pumping lemma

Suppose that $L$ were context-free. Then $L \cap 10^*20^*30^*$ would also be context-free. What is this language? It is easy to see that each of $a,b,c$ needs to contain a non-zero digit. Therefore $a = 10^i$, $b = 0^j20^k$, and $c=0^\ell30^m$. Clearly $i=k=m$, and so
$$L \cap 10^*20^*30^* = \{10^{i+j}20^{i+\ell}30^i : i,j,\ell \geq 0\} = \{10^i20^j30^k : i,j \geq k\}.$$

To make our life easier, let us consider instances with more structure: $L \cap 30^*130^*160^*2$. Consider any word $30^i130^j160^k2$. The only way in which $a+b$ ends with $2$ is if $a,b$ end with $1$, and so $a=30^i1$, $b=30^j1$, $c=60^j2$. This shows that
$$
L' \triangleq L \cap 30^*1 30^*1 60^*2 = \{ 30^i130^i160^i2 : i \geq 0\}.
$$
If $L$ were context-free, so would $L'$ be. Now define a homomorphism $h$ which maps $1,2,3,6$ to themselves and $a,b,c$ to $0$. Clearly
$$
L'' \triangleq h^{-1}(L') \cap 3a^*13b^*16c^*2 = \{3a^i13b^i16c^i2 : i \geq 0\}.
$$
If $L'$ were context-free so would $L''$ be. Finally, define a homomorphism $k$ which erases $1,2,3,6$ and fixes $a,b,c$. Then the following language would also be context-free:
$$
k(L'') = \{ a^i b^i c^i : i \geq 0 \}.
$$
However, this language is well-known to be non-context-free.

If for some reason you want to prove that $L$ is not context-free using the pumping lemma (the only reason I can see is that you were given this as an exercise), then you could consider instances of the form $30^n130^n160^n2$, which might be easier to handle than your original suggestion.


This looks like an advertisement for Microsoft...

The intention was that while DOCX can be created using the rather expensive but commonly available Microsoft Word, PDF is created by Adobe Acrobat (not the free Reader!) which is not commonly available. However, there are many other ways to create PDFs, and nowadays you can print to PDF even on Windows, which is roughly as commonly available as Microsoft Word.

In conclusion, it's an oversight by the question setters, who appear to be parroting material which has been influenced by Microsoft for obvious commercial purposes.


Computational Complexity of Not All Equal SAT variant

Your problem is NP-hard, as can be seen by a (known, I believe) reduction from CNF-SAT: Reduce from (for example) $3$-SAT as follows. Given a formula $F$, create a formula for your special NAE-SAT by introducing exactly one additional variable, say $y$. Add $y$ to every clause in $F$ to obtain $F'$.

Example: $F = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_2 \vee x_3 \vee \neg x_4)$ becomes  $F' := (x_1 \vee x_2 \vee \neg x_3 \vee y) \wedge (\neg x_2 \vee x_3 \vee \neg x_4 \vee y)$

After doing this, every clause contains $y$ and thus shares (at least) one literal.

Proof sketch:
If $F$ is satisfiable, use the same satisfying assignment to satisfy $F'$, together with $y = false$.

If $F'$ is satisfiable, there are two options

$y = false $, in this case the same assignment satisfies $F$ ($F'$ has at least one true literal per clause, and it is never $y$, thus $F$ has at least one true literal per clause as well)
$y = true$, negate the satifying assignment for $F'$ to satisfy $F$ (at least one false literal per clause in $F'$, after negating the assignment we have at least one true literal per clause)


Finding a string with some specified hamming distances from other strings

Your problem is likely hard. I will consider a decision version of your problem in which the goal is to ask whether there exists any solution. I will show that the binary variant is NP-complete, and the same ideas probably imply that this decision version of your problem is also NP-complete.

Other decision versions of your problem are likely also hard, though perhaps not NP-hard. For example, consider the problem in which you are promised that a unique solution exists, and your goal is to determine the value of its first bit. This problem cannot be NP-hard since it has the same complexity as its complement. Nevertheless, it is probably hard in some other, appropriate sense.

The decision version of your problem that I will analyze asks whether there is an answer.
The problem is clearly in NP, and we prove that it is NP-hard by reduction from X3SAT, a variant of 3SAT in which a formula is satisfiable if every clause contains exactly one satisfied literal. Given a 3CNF on $n$ variables $x_1,\ldots,x_n$, we will consider strings of length $2n$ which encode a truth assignment: a 1 in position $2(i-1)+1$ encodes that $x_i$ is true, and a 1 in position $2(i-1)+2$ encodes that $x_i$ is false.

In order to force that any solution must have exactly one 1 in each of the positions $2(i-1)+1,2(i-1)+2$, we ask that it have distance $n$ from the strings $(00)^n$ and $(00)^{i-1}(11)(00)^{n-i}$ for $1 \leq i \leq n$. In order to force any solution to satisfy all clauses, for every clause we take the string which has 1s in the positions corresponding to the literals in the clause, and we ask that the solution be at distance $(n-3)+2$ from this string. A string satisfies these $n+m+1$ constraints (where $m$ is the number of clauses) if and only if it is a satisfying assignment to the given 3CNF.


Optimizing greedy solution for choice game

The first player cannot always win – consider the case in which all numbers are the same. But we can always guarantee a draw. Here is the strategy – I'll let you figure out why it works.

  Given the sequence $a_1,\ldots,a_{2n}$, calculate $a_{odd} = a_1 + a_3 + \cdots + a_{2n-1}$ and $a_{even} = a_2 + a_4 + \cdots + a_{2n}$. If $a_{odd} > a_{even}$, always pick odd indices. If $a_{even} > a_{odd}$, always pick even indices. Otherwise, the game is a draw.


Can partial sorting help with lookup cost in arrays?

If you run "balanced Quicksort" (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(\log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/2^k)$, for a total complexity of $O(n/2^k + k)$.

If $k = o(\log n)$ then the partial sorting takes time $o(n\log n)$. If $k = \omega(1)$ then the lookup algorithm takes time $o(n)$. Thus if $1 \ll k \ll \log n$ we get $o(n\log n)$ preprocessing time and $o(n)$ lookup time. For example, if $k = \log\log n$ then preprocessing takes $O(n\log\log n)$ and lookup takes $O(n/\log n)$.


Proving that a preorder traversal of a rooted tree can be performed in linear time

You can prove that formally by using structural induction. The structure of the proof is as follows:

Observe that a preorder traversal of a tree with $1$ vertex requires constant time.

Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the preorder traversal of a tree $T$ with $i+1$ vertices requires at most $c \cdot (i+1)$ time. Here you use the induction hypothesis and the definition of the traversal. In particular, notice that the subtrees of $T$ that are rooted in the children of the root have at most $i$ vertices.


The recursive solution is to use the recurrence directly.

It corresponds to the following algorithm:

Function OPT(i, site):
    If i = 0, return 0
    If i > 0 and site = N, return N(i) + min(OPT(i-1, N), OPT(i-1, S) + M)
    If i > 0 and site = S, return S(i) + min(OPT(i-1, S), OPT(i-1, N) + M)

If you run this algorithm using memoization (not recomputing the value for the same input), then you get essentially the dynamic programming solution.

One way to implement this kind of approach is like so:

Function OPTm(i, site):
    If i = 0, return 0
    If (i, site) in Database, return Database(i, site)
    If site = N, answer = N(i) + min(OPTm(i-1, N), OPTm(i-1, S) + M)
    If site = S, answer = S(i) + min(OPTm(i-1, S), OPTm(i-1, N) + M)
    Database(i, site) = answer
    return answer


You will have $O(n^2)$ in worst case. Actually what you do is really close to insertion sort. Worst case is attained when you got the array in decreasing order.

\begin{align}
T(n) &= T(n-1) + n\\
&=T(n-2) + n-1 + n \\
&= \vdots \\
&=T(n-k) + \sum_{i=0}^k (n - i)
\end{align}
Algorithm terminates at $k = n$, i.e. we shall get
$$T(n) = T(0) + \sum_{i=0}^n (n - i)$$
where $T(0) = O(1)$. So, upon a change of variable, we get
 $$T(n) = \sum_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$$


How to handle missing continuous attribute values in ID3 (Iterative Dichotomiser 3)?

Take a look at the C4.5 algorithm.  C4.5 is a successor to ID3.  It is more complex.  However, Wikipedia lists as one of its advantages over ID3 that C4.5 can handle data with missing attribute values.  So, you might take a look at how C4.5 handles missing attribute values -- or even simply use C4.5 rather than ID3.


How Do Common Pathfinding Algorithms Compare To Human Process

Humans tend to choose not strictly optimal, but close to shortest solutions. So you'll need to look at fuzzy (approximate) algorithms, not at A*.

The closest algorithm to human thinking I've aware of is a Contaction hierarchies on par with a Reach pruning algorithm. When I need to find a path between A and B on the map, I do a quick overview, taking into account if there is crossing river or something else and looking for some general ways and then adding details that could shorten path.


Assume that $A\in NP$, and let $V$ be a verifier for it. That is, $V$ takes as input $(x,y)$ and outputs 1 if $y$ witnesses that $x\in A$. That is, we can write $A=\{x:\exists y,\ V(x,y)=1\}$.

We show that $A\in coNP$, by showing that $\overline{A}\in NP$. We construct a verifier $V'$ for $\overline{A}$ as follows:

Given input $x$, $V'$ expects a witness of the form $(w_1,y_1,...,w_{n^3},y_{n^3})$, where $|x|=n$, such that $y_i$ is a witness that $w_i\in A$, and for every $i$ we have $w_i\neq x$. That is, a witness for $x$ not being in $A$ is simply a list of all the $n^3$ words that are in $A$. Clearly verifying this can be done in polynomial time using $V$ (which we assume to run in polynomial time).


The first instruction (I1) will pass through all the stages one by one without any stall and will take $3+4+2+4=13$ cycles.

The second instruction (I2) goes next and it begins at the end of cycle 3. As soon as it finishes the execution of S1, it is ready to go to next stage. But it is occupied by the previous instruction. Hence, I2 needs to stall for 1 cycle (as in yellow). After this stall, it need not to pause for any cycle and finishes at cycle 17.

The same pattern is followed by the coming instructions.

So, the first instruction finishes in 13 cycles.
Each of the remaining $n-1$ instructions finishes after 4 cycles taking $(n-1)*4$ cycles.

You put $n=1000$ and the total number of cycles comes to be $13+999*4 =4009.$

Hope it helps.


Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset

Here is what the fastest solution is doing. It is indeed computing your function
$$ g(n) = \sum_{\substack{d \mid n \\ d < n}} g(d), \quad g(1) = 1. $$
Given $n$, we factor it (see below) and then compute all factors (see below) $f_1,\ldots,f_m$ in some order such that $f_i|f_j$ implies $i \leq j$ (property P). We now compute $g$ according to the formula by going over the factors in the given order. Property P ensures that when we compute $g(d)$, we have already computed $g(e)$ for all non-trivial factors $e$ of $d$. There is also an optimization (see below).

In more detail, we go over the factors in order, and for each factor $f_i$, we find all of its non-trivial factors by checking which of $f_1,\ldots,f_{i-1}$ divides $f_i$.

Factoring: Preprocessing: we make a list of all primes below $10^9$ using the Eratosthenes sieve. Given $n$, we simply use trial division.

Generating all factors: This is done recursively. Suppose $n = p_1^{k_1} \cdots p_t^{k_t}$. We run $t$ nested loops $l_1 \in \{0,\ldots,k_1\},\ldots,l_t \in \{0,\ldots,k_t\}$, and output $p_1^{l_1}\cdots p_t^{l_t}$. You can prove property P by induction.

Optimization: Since the program is run on several inputs, we can use memoization to save time across different inputs. We only memoize small values (up to $10^5$), and this allows us to store all memoized values in an array. The array is initialized with zeroes, and so we can tell which values are already known (since all computed values are positive).

If the prime factorization of $n+1$ is $p_1^{k_1},\ldots,p_t^{k_t}$, then $f(n)$ depends only on $(k_1,\ldots,k_t)$, and in fact only on the sorted version of this vector. Every number below $10^9$ has at most $29$ prime factors (with repetition), and since $p(29)=4565$, it seems feasible to compute $f$ (or rather $g$) for all of them, recursively. This solution could be faster if there were many different inputs; as it is, there are at most $10$.

It is also possible that this function, mapping partitions to the corresponding $g$, has an explicit analytic form. For example, $g(p^k) = 2^{k-1}$, $g(p_1\ldots p_t)$ is given by A000670, and $g(p_1^2 p_2\ldots p_t)$ is given by A005649 or A172109.


Comparing two algorithms for all-pairs shortest paths

There is no standard definition for sparse graphs. Some common definition include graphs in which $E = o(V^2)$, $E=O(V^{2-\epsilon})$, $E = O(V^{1+\epsilon})$, $E=O(V^{1+o(1)})$, $E = O(V\log^C V)$, and $E = O(V)$.
In most situations, it is safe to assume that the graph is connected, and so $E \geq V-1$. In such cases, $VE + V^2\log V = O(V^2 E)$, and so an upper bound on the running time of the form $O(VE + V^2\log V)$ is better than an upper bound of the form $O(V^2 E)$: indeed, the former implies the latter.


Maximize pairings subject to distance constraint

You can formulate this as a maximum matching problem in an undirected graph, and then apply standard algorithms for this problem, such as Edmonds' algorithm.  These algorithms are reasonably efficient and should be fast for your parameters, and they are guaranteed to find the optimal collection of pairings.

In particular, the graph is as follows.  You have a vertex for each person.  Draw an edge between two people if they are within 10 miles of each other.  Now, you want a maximum matching in this undirected graph: i.e., a collection of edges (pairs of people) such that no two edges have a vertex in common (each person is paired up with at most one other person), and that is as large as possible.

There's lots written on the maximum matching problem; a search should turn up plenty of additional information.


Would proving P≠NP be harder than proving P=NP?

As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of approximation algorithms.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are conditional: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as hardness of approximation, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.


Travelling salesman problem with small edge weights

Travelling salesman remains NP-complete even if you restrict to two different edge weights $a<b$.  Reduce from Hamiltonian cycle by giving weight $a$ to every edge and weight $b$ to every non-edge.  Then the resulting complete graph has a TSP tour of length $na$ (where $n$ is the number of vertices) if, and only if, the original graph has a Hamiltonian cycle.


Exponential-size numbers in NP completeness reduction

Changing the encoding of the inputs changes the problem.
When inputs are given succinctly the problem can become much harder.
On the surface of what you are saying
they are proving the NP-hardness of a succinct version of the problem,
not the original problem.

You can also think of it as a reduction from Partition
where numbers are given in unary to the original problem.
The unary version of Partition is in P.
So does not show the problem is NP-hard.
(It might be possible to use 3-Partion in place of Partition
which remains NP-hard even when numbers in the input are encoded in unary.)

The issue is that it is not clear what are the inputs to the problem.
They seem to be working with a version of the problem where $\gamma$s are not
part of the input to the problem
but are  determined from $\tau_e$ which is part of the input.
In the theorem it seems that
$\gamma_e$ is fixed to be $2^{c\tau_e}$ (where $c$ is a fixed constant)
and are not part of the input.
If $\gamma$ is not part of the input and fixed to be determined from $\tau$ as stated
then it doesn't matter that they are exponentially large.

In summery, the paper is not very clear in its treatment of the issue.
It seems that in the theorem
they are considering those numbers as not being part of the input to the problem (determined from $\tau_e$).
Or that they are given in a succinct form of $a2^e$.
The paragraph after the theorem
where they say that it is open whether the results holds in case the usual binary encoding of numbers is used seems to support that.
So they are not proving that the problem where $\gamma$ is part of the input
and encoded as normal binary numbers is NP-hard.
That is still open according to them.
They are proving that variants of the problem mentioned above are NP-hard.


Is binary tree just a two-dimension-doubly-linked-list?

"[A] binary tree shares a similarity to doubly linked list"

Why, yes, it does, but the doubly linked list format you have made is really just a way to represent a connected graph, with the one limitation that a node can be connected to at most 3 other nodes. A lot of structures could fit into that format, for instance a binary tree or many cyclic structures in addition to lists.

You have made one limitation to a general graph, of which binary trees are a subset. The reason we care about more restricted versions of graphs is that it allows for many useful optimizations. Your two dimensional doubly linked list has many redundant properties regarding use as a binary tree, for instance it allows for cyclic structures, which a binary tree can not be, and it includes information about the parent node, which is also unnecessary as such trees are used for descending searches.


Can integer linear programs have non-integer OPT solutions?

Something that might be causing you confusion: "integer linear programming", by definition, restricts the variables to integer values.
Linear programming instances in which the input numbers are integers can easily have only non-integer solutions. Consider:

$\begin{cases}
\begin{alignat}{1}
2 &\cdot x \le 1
\\[1.5ex]
-2 &\cdot x \le -1
\end{alignat}
\end{cases}$


Why is one often requiring space constructibility in Savitch's theorem?

This is elaborated nicely in Dexter Kozen's Theory of Computation textbook, in chapter 2.

Savitch's Theorem (Theorem 1 in his paper) says: if $S(n) \ge \log n$, then $\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$.  Space-constructibility often seems to be assumed in a proof, but this requirement can be removed by restarting the search with a fixed space bound that is allowed to increase with each attempt.

The confusion perhaps arises because the original Savitch paper is largely about investigating whether $\text{NSPACE}(S(n)) \not\subseteq \text{DSPACE}(S(n))$.  It therefore spends a lot of effort on space-constructible functions, due to the following observation from the paper:

  It is natural to ask if there is any storage function whose deterministic and nondeterministic complexity classes are equal. The answer was given by Manuel Blum and is "yes". Blum showed that there are arbitrarily large storage functions L(n) such that a set is accepted within deterministic storage L(n) if, and only if, it is accepted
  within nondeterministic storage L(n). These functions L(n) are not, however, "well-behaved" and Theorem 3 does not apply to them.

(Here "well-behaved" refers to the space-constructible functions, called measurable by Savitch.)


Do the Turing machines involved in Chruch-Turing thesis have to halt on all the inputs?

The Church-Turing thesis is an informal notion so it is not strange to see different authors taking slightly different positions.

To me, the second definition makes a bit more sense: CT tries to characterize "functions that are calculable in all cases", and for instance, we don't consider lets say, second order unification computable. The halting problem also falls in that category so I really wonder what do the authors mean.

Some interesting recent discussion about CT can be found in this thread: http://www.cs.nyu.edu/pipermail/fom/2016-August/020027.html


3-SAT reduction to jobs scheduling problem (np-completeness)

I see that you have posted this question before with no luck, and I think that this might be due to the amount of work needed to the answer such an open question. I looked at it also when you posted the first time, but needed a couple of hours to read through the proof and would have needed another couple of hours if I should have written a clear explanation for you (I know you are just asking for hints, but they are hard to give when I do not know which parts you already understand and which you don't). I at least, for one, would have been more inclined to write you an answer if you had asked more specific questions to the reductions, like e.g. what a role of a certain job is, or the like.

Also, your question does not contain all the info needed to answer, so one has to download the paper to find the relevant information oneself, and many people probably never go to that step, even when they are actually able to answer. You should have posted at least the definition of P4 and the time limits, and preferably also the example you posted in your last post, but with the explanation of the example and not just the table.

But, alas, after all this explanation of why you might not have gotten any answers, I really like these puzzle-y reductions so seeing that you posted again I made this little picture that can hopefully be of some help.

If you have questions after this, you are very welcome to write some (specific) questions, and I shall see if I can answer.


Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$?

You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

S <- new empty set
T <- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v <- remove some element from T
        add v to S
        do something with v
        for each vertex w that is adjacent to v:
            if w is not in S and not in T:
                add w to T

Notice the outer loop on the variable u. This loop is present in some descriptions of DFS/BFS/etc. and absent in others. Why is this? The answer is that graph searches are used for different purposes. Sometimes, you have a particular start vertex u and you just want to search for everything that is reachable from u. However, other times you are using the graph search to find the connected components of the graph, or as part of an algorithm for computing some other property of the entire graph such as biconnected components. In these cases, the outer loop is necessary.

The crucial special property of graph search is that, even with the outer loop, the runtime is still bounded by $O(|V| + |E|)$, and not just by $O(|V| \cdot |E|)$. This property is what makes efficient algorithms possible for computing connected components, etc.

It's also worth noting that the $O(|V| + |E|)$ bound assumes that the white/gray/black status of a vertex (i.e. which set it is in) can be checked and modified in $O(1)$ time. This can be achieved by creating an array of size $V$, or by attaching a flag to each vertex; either way, it takes $O(V)$ time to initialize all the vertices into the white set at the start of the algorithm. If you don't use one of these methods, you probably have to add a logarithmic overhead for tracking the vertices in set data structures. This is true even in cases where you don't need the outer loop.


Function is recursive iff its graph is recursively enumerable

In order to prove your claim, you need to prove two things:

If a function is recursive then its graph is r.e.
If the graph of a function is r.e. then it is recursive.

Let's see what you have to do to prove these two claims.

Claim 1. Suppose that $f$ is recursive, i.e. it is computable by some program. You have to come up with another program that enumerates $x\#f(x)$. For example, assuming the inputs are natural numbers, it could output $1\#f(1),2\#f(2),3\#f(3),\ldots$.

Claim 2. Suppose that $\{x\#f(x)\}$ is r.e., that is, some program enumerates $x\#f(x)$ for all legal inputs $x$, in some order. Given an input $y$, we need to use this enumeration to compute $f(y)$. It is natural to wait for $y\#f(y)$ to be enumerated and extract $f(y)$.

Your task now is to flesh out these proof sketches.


How to derive the worst case time complexity of Heapify algorithm?

It's a variable substitution.
First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when $i = k$, $k-i = 0$). So, the range of the first summation can be written as $1 \le i \le k-1$. Now, substitute $i$ with $k-i$. $i$ iterates over the set ${1, 2, ... , k-1}$ and $k-i$ iterates over the set ${k-1, ... 2, 1}$, they are the same set, so, we can do this.


Finding pair of non-adjacent cliques in a dense graph

Here is one approach:

Find any 6-clique, call it $C$.
Find all vertices that aren't adjacent to any vertex in $C$.  Mark them red.
Find a 6-clique among the red vertices.

How long will this take?  Let's analyze the running time of each step.

You should be able to find a 6-clique by randomly sampling $2^{15}$ possible ways to choose 6 vertices and checking whether it forms a clique; a random collection of 6 vertices has a $1/2^{{6 \choose 2}} = 1/2^{15}$ probability of being a clique, so you're likely to find one in this way after about $2^{15}$ trials.  There are faster ways to find a 6-clique, but this will already be very fast.
This can be done in $6 \times 5000$ operations, i.e., very fast.
Now you have the problem of finding a 6-clique in a smaller graph.  How many red vertices do you expect to have?  If you pick a vertex at random, then it has a $1/2^6$ probability of being red.  Therefore, we expect about $(5000-6)/2^6 \approx 78$ red vertices.  It is very likely that a 6-clique exists among them, as there are ${78 \choose 6} \approx 2^{28}$ possible ways to choose a subset of 6 nodes, and each one has about a $1/2^{15}$ chance of being a 6-clique.  You can find a 6-clique among the red vertices in the same way as before (randomly choosing a collection of 6 red vertices and checking to see if they form a clique).  This takes about $2^{15}$ trials.

So all in all you expect this to be successful, and to take about $2^{16}$ trials, where each trial is very fast.  So this algorithm should be very fast.  There are probably ways to optimize it further, by using standard algorithms for finding a clique more efficiently than brute force, but I'd guess this should already be adequate, and it has the advantage of being easy to implement.


This depends... If the number of input numbers is $n$, assuming the word-ram model of computation, a word size of $\Theta(\log n)$ bits, and worst-case inputs:

Radix sort would require $O(n \log n)$  time and $O(n)$ auxiliary space.
Quicksort with fixed or random pivot selection would require $O(n^2)$ worst-case time and $O(\log n)$ auxiliary space.
Mergesort requires $O(n \log n)$ time and $O(n)$ auxiliary space.

Radix sort and Merge sort are then equivalent in this setting.

Notice that using quicksort with random pivoit selection results in a time complexity of $O(n \log n)$ with high probability. Selecting the pivot deterministically in a way that partitions the elements into two sets whose cardinalities are at most a constant factor apart gives your an algorithm with worst-case time complexity of $O(n \log n)$ and $O(\log n)$ auxiliary space.


Order a list of edges to make the the complexity of searching for an edge O(lg E)

Any total order will do; more is not needed for sorting and searching with binary search in a sorted list.

The lexicographic order would be a canonical choice for sorting tuples.

If your elements are (unordered) sets (e.g. edges of undirected graphs) you can sort them before comparing by the order on tuples as well.


Undecidability of REGULAR_TM (Detail within Proof)

This proof assumes, for the purpose of contradiction, that there exists a Turing machine
$R$ deciding $R_{TM}=\left\{\langle M\rangle | \hspace{1mm} L(M) \text{ is regular}\right\}$, and uses the existence of $R$ to construct a Turing machine deciding $A_{TM}=\left\{\langle M,w\rangle | \hspace{1mm} M \text{ accepts $w$}\right\}$.

$R$ halts on every input (since it decides $R_{TM}$), so there is no problem running it (it will finally halt and either accept or reject the input). This avoids the problem of running $M$, some arbitrary Turing machine, on some input $w$, since we do not know that $M$ will finally halt.

Now, Sipser constructs a new Turing machine, $M_2$, such that:

$L(M_2) \text{ is regular} \iff M \text{ accepts $w$}$

If the above holds, then you would have $\langle M_2\rangle\in L(R) \iff M \text{ accepts $w$}$, so you could find out if $M$ accepts $w$ simply by running $R$ (which always halts) on $M_2$.

To see why this property holds, note that $M_2$ always accepts strings of the form $0^n1^n$, and it accepts any string not of this form iff $M$ accepts $w$. This means that $L(M_2)=\left\{0^n1^n | n\ge 0\right\}$ if $M$ does not accept $w$, and $\Sigma^*$ (which is regular) otherwise.


Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$

Let $L = \{0^i1^j : i \neq j\}$. You can prove that $L$ is not regular in many ways. Here are some examples.

Closure properties

If your language were regular then so would $0^*1^* \setminus L$ be, but that language is $\{0^n1^n : n \in \mathbb N\}$, which presumably you already know isn't regular.

Myhill–Nerode

The words $\{0^i : i \in \mathbb N\}$ are pairwise distinguishable modulo $L$: if $i \neq j$, then $0^i1^i \notin L$ but $0^j1^i \in L$. It follows that $L$ isn't regular.

Pumping lemma

If $L$ is regular then it satisfies the pumping lemma, say with constant $n$. Consider the word $w = 0^n 1^{n+n!} \in L$. According to the pumping lemma, there should be a decomposition $w = xyz$ such that $|xy| \leq n$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \in \mathbb N$. Let $|y| = \ell$, so that $y = 0^\ell$. Pick $i = 1 + n!/\ell$. Then $xy^iz = 0^{n+n!} 1^{n+n!} \notin L$, contradicting the pumping lemma.


Why is a quantum computer not capable of solving more problems than a classical computer?

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.


The sweeping algorithm, suggested by @adrianN, can be elaborated this way.

Step 1. Put all your rectangles in a map of sets in such way, that:

the map key is left boundary of rectangle
the map value is ordered by lower boundary set of rectangles, having this left boundary

For your example, this map will be:

0 => (2, 5, 10)
4 => (6, 7, 11)
8 => (3, 4)
11 => (9, 12)
15 => (8)
19 => (1)

Step 2. Create a similar map of rectangle sets, having the same right boundary.

Step 3. Define active rectangle set, which will "sweep" the data structure above, from left to right, generating pairs of adjacent rectangles.

At first assign to the active set the rectangle set with minimal left boundary $x_0$. You can immediately generate a number of pairs of adjacent rectangles from the active set (because it's ordered and there are no "holes" in it).

Then move the active set to the next position of the left boundary, let's say $x_1$. You will need to update the active set, removing rectangles with right boundary $x_1$, and adding rectangles with left boundary $x_1$. You already have these rectangle sets in data structures, created earlier. The active set will be ordered after this update - generate pairs from it.

And so on...

For your example - active sets A0, A1 etc. will be:

A0 = (2, 5, 10)
A1 = (5, 6, 7, 11)
A2 = (5, 6, 4, 3)
A3 = (9, 6, 4, 12)
A4 = (9, 8, 4, 12)
A5 = (1)

This algorithm will generate all pairs of rectangles, adjacent in vertical direction only. Some of pairs will be generated more than once - you'll need to filter repetitions out.

In order to get all pairs of rectangles, adjacent in horizontal direction, you'll need to "rotate the picture" by 90 grades and repeat the algorithm. Another option - much more complex processing of rectangles during the active set update.

Time complexity of this algorithm depends on complexity of set operations union and minus.


Decidability of $E_{TM}$ and $A_{TM}$ for "erasing" Turing machines

An ETM (Erasing Turing machine) can be safely simulated due to its erasing-only nature.

It can only pass the right-end of the input to a finite limit or else would plunge off to infinity. Adding this to the input itself, we can conclude that the languages accepted by an ETM must be context-sensitive.

So, an ETM can only accept some context-sensitive language. As a result, $A_{ETM}$ is decidable.

Where is the source that says $E_{ETM}$ is undecidable?


Context-free grammar for $L = \{a^n : n\leq2^{20}\}$

As Karolis mentions, one solution is
$$
S \to \epsilon | a | a^2 | a^3 | \cdots | a^{2^{20}}.
$$
However, we can do better:
$$
\begin{align*}
&A_{20} \to A_{19} A_{19} \\
&A_{19} \to A_{18} A_{18} \\
&A_{18} \to A_{17} A_{17} \\
&A_{17} \to A_{16} A_{16} \\
&A_{16} \to A_{15} A_{15} \\
&A_{15} \to A_{14} A_{14} \\
&A_{14} \to A_{13} A_{13} \\
&A_{13} \to A_{12} A_{12} \\
&A_{12} \to A_{11} A_{11} \\
&A_{11} \to A_{10} A_{10} \\
&A_{10} \to A_9 A_9 \\
&A_9 \to A_8 A_8 \\
&A_8 \to A_7 A_7 \\
&A_7 \to A_6 A_6 \\
&A_6 \to A_5 A_5 \\
&A_5 \to A_4 A_4 \\
&A_4 \to A_3 A_3 \\
&A_3 \to A_2 A_2 \\
&A_2 \to A_1 A_1 \\
&A_1 \to A_0 A_0 \\
&A_0 \to a | \epsilon
\end{align*}
$$
The start symbol is $A_{20}$. You can prove by induction that $A_k$ generates $\{ a^n : n \leq 2^k \}$. If you want an even shorter solution, you can try
$$
\begin{align*}
&A_{20} \to A_{18} A_{18} A_{18} A_{18} \\
&A_{18} \to A_{16} A_{16} A_{16} A_{16} \\
&A_{16} \to A_{14} A_{14} A_{14} A_{14} \\
&A_{14} \to A_{12} A_{12} A_{12} A_{12} \\
&A_{12} \to A_{10} A_{10} A_{10} A_{10} \\
&A_{10} \to A_8 A_8 A_8 A_8 \\
&A_8 \to A_6 A_6 A_6 A_6 \\
&A_6 \to A_4 A_4 A_4 A_4 \\
&A_4 \to A_2 A_2 A_2 A_2 \\
&A_2 \to \epsilon|a|aa|aaa|aaaa
\end{align*}
$$
Many more options are possible, see which one you like most.

Comments:

In terms of number of symbols, a grammar based on powers of 2 is the most efficient.
This approach seems (at first) to work only for powers of 2, but in fact you can use the binary representation to handle any upper bound (exercise).


Equivalance of NFAs, understanding the solution

Your confusion is understandable.  The solution outline you've quoted misses an important point and suggests the opposite of that point.

The DFAs are, as you say, exponentially big.  We can construct them, but not in polynomial space.  However, the key point is that we don't need to construct and store the whole automaton.  The reachability algorithm doesn't need that.  All it needs is the ability to know what state it's in at the moment and construct the list of states it could move to next.  Both of these can be done easily, on the fly, from the description of the NFAs.  Likewise, we don't need to literally construct the product automaton: we can do that implicitly as well, by just tracking our position in each automaton separately.

Let's do a simplified example.  Suppose that we just want to know if a particular NFA $N = (Q, \Sigma, \Delta, q_0, A)$ accepts at least one string, i.e., if an accepting state is reachable from the initial state.  In this simplified scenario, we could just work directly with the NFA but we'll ignore that and convert to a DFA, $M$.  If $N$ has $n$ states, then $M$ will have $2^n$ states so, if we were to write out its full transition graph, we'd need exponential space.

However, the reachability algorithm doesn't require us to write out the whole graph.  As it runs, it says things like, "OK, I'm at vertex $v$. Where can I go next?"  Normally, we imagine that it looks up that vertex in the graph's adjacency matrix to answer this question, but that's not the only way. It could calculate what vertices can be reached, using the rules of the subset construction that generates $M$ from $N$.  Specifically, if we're at vertex $v$ then $v = \{s_1, \dots, s_\ell\}\subseteq Q$ and the vertices we can move to are the vertices of the form $\Delta(s_1,a)\cup\dots\cup\Delta(s_\ell,a)$ for each symbol $a\in\Sigma$.  Each such vertex is a subset of $Q$, which we can write down in $n$ bits, and there are at most $|\Sigma|$ different possibilities, so you can write all of them down in $n|\Sigma|$ bits, which is polynomial in the size of $N$.  Once the reachability algorithm has decided what to do next, it can forget this list of vertices and re-use the space.  If it needs to access the list of $v$'s neighbours again, it can recalculate it.

The reachability algorithm never needs the whole adjacency matrix of the graph to be written down at the same time.  Pretend, for a moment, that we did have the graph written down.  Since the graph has $2^n$ vertices, we would need  working space $O(\log 2^n) = O(n)$ to run the algorithm. Now, instead of writing the adjacency matrix down, we'll calculate it on the fly.  That will require additional working space $O(n)$ for the calculations of what the adjacency matrix is.  So the total space used is still $O(n)$, even though the graph can't be stored in that little space.

By the way, this trick of calculating things on the fly is a common trick in logarithmic space computations.  Another prominent example is showing that logspace reductions compose (i.e., if there are logspace reductions $A\to B\to C$ then there's a logspace reduction $A\to C$). What you'd like to do is just do the first reduction, store the result on a tape and then apply the second result to that; but you can't because the result of the first reduction might be too big to store.  So, instead, you start with the second reduction. Every time you need to know some character of the output of the first reduction, you recompute it from scratch.


Can such an algorithm be written using recursion

Off the top of my head i would perform a recursion this way:

Solve(N,V,target_value):
    if target_value == 0:
        return {}
    if target_value<0 or |V|==0:
        return false
    for 0<=i<N:
        sol = Solve(N-1,V\V[i],target_value-V[i]
        if sol is feasible:
            add [V[i]+sol] to the list of feasible solutions
    if there are any feasible solutions, return them. else return false.

This is obviously pseudo-code that needs to be tweaked a bit. But the general idea is to reduce the problem instance by thinking "If I take element i, what other elements do I have to take?". So assuming you take element i, you reduce the target value and exclude i from the available other elements and perform a recursive call.

The recursion base is reached when:

The target value becomes negative (= we put too many elements into the sack already!)
We used up all elements and still didn't reach the target value! The problem is therefore unsolvable
We reached the target value and can return the current chain of elements. This is done by returning an empty list, which is then filled when the stack is being unwinded (line 9).


Is there any base representation that produces a non-regular language for set S?

You are right in saying that the binary representation of the language is regular because it is defined by the expression $10^*$(regular expression).
You are also right in saying that this does not hold for the ternary representation.
You can prove the latter in various ways including the "calssic" pumping lemma (quite cumbersome in this case) or using Cobham's Theorem.

This theorem says that if you have a subset of $\mathbb{N}$ and you take $m,n \in \mathbb{N} $ such that they are multiplicatively independent, then your set is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is ultimately periodic.


Does $\mathsf{P} \ne \mathsf{NP}$ imply that $|\mathsf{NP}| > |\mathsf{P}|$?

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.


What languages does a (1-way) quantum finite state automata recognize?

Quantum finite automata (QFAs) are quantum counterparts of the usual finite automata.

In [1] it is shown that 1-way QFAs recognize a proper subset of the regular languages:

Proposition 6: Let $L$ be any language recognized by a 1QFA with bounded error. Then $L$ is regular.

Proposition 7: The language $L = \{a,b\}^*a$ cannot be recongized by a 1QFA with bounded error.

However in [2] :

... Our first results consider relations between 1-way QFAs and 1-way reversible automata.
Clearly, a 1-way reversible automaton is a special case of a QFA and, therefore, cannot
recognize all regular languages. It is a natural question whether 1-way QFAs are more
powerful than 1-way reversible automata. Interestingly, the answer depends on the accepting
probability of a QFA. If a QFA gives a correct answer with a large probability (greater than
7/9), it can be replaced by a 1-way reversible automaton. However, this is not true for 0.68...
and smaller probabilities.

Then, we show that QFAs can be much more space-efficient than deterministic and even
probabilistic finite automata. Namely, there is a 1-way QFA that can check whether the
number of letters received from the input is divisible by a prime p with only $O(\log p)$ states
(this is equivalent to $\log \log p$ bits of memory). Any deterministic or probabilistic finite
automaton needs p states ($\log p$ bits of memory). We think that this space-efficient quantum
algorithm may be interesting for design of other quantum algoritms as well....

For a quick introduction see:

[1] Attila Kondacs and John Watrous, On the Power of Quantum Finite State Automata;
[2] Andris Ambainis and Rusins Freivaldsy, 1-way quantum nite automata: strengths, weaknesses and generalizations;
[3] Abuzer Yakaryilmaz and A. C. Cem Say, Unbounded-error quantum computation with small space bounds;
[4] Andris Ambainis and Abuzer Yakaryilmaz, Superiority of exact quantum automata for promise problems;
[5] Cristopher Moore and James P. Crutchfield, Quantum Automata and Quantum Grammars;
[6] Andris Ambainis, Quantum Finite Automata.


Is Space Complexity Always Less Than Or Equal To Time Complexity?

The reason it's common knowledge and not formally proved anywhere is because it's obvious.
During each time step, you can only access one memory location. Therefore you can never access more memory locations than you have time.

I found the following reference, showing an even slightly stronger result: every deterministic multitape Turing machine of time complexity $t(n)$ can be simulated by a deterministic Turing machine of tape complexity $t(n)/\log t(n)$.

  If it is true that space complexity is always less than or equal to time complexity, then instead of doing a logspace reduction, I can show that the reduction can be done in log time, which is much easier in my particular case.

This suggests that something is wrong with your understanding. Showing that it runs in logarithmic time is strictly harder than showing it uses logarithmic space. Something really weird has happened. As Robert Anderws rightfully points out in his comment, no reduction from the Circuit Value Problem can run in logarithmic time and be correct, since it can't even read the entire input.


Costs of updating arrays to contain only zeroes

To initialize an array of length n has complexity O(n), as far as I understand. If I set every element to zero (with one code line), does that have time complexity O(n) also?

The answers to both questions depend on the machine model. In common ones, like e.g. the RAM model, writing every memory cell take a constant amount of time $c$. Hence, intializing an array of length $n$ takes time $cn + d \in \Theta(n)$, with $d$ being some constant overhead.

Now, doing

arr = new array[n]
for i = 0 to n-1
  arr[i] = some_value
end

incurs both the cost for initializing arr plus the cost for the for-loop, which is not too hard to analyse. It has, in fact, linear runtime cost (with common RAM-model assumptions).

  setting an n-array to zero inside a loop with n iterations should be O(n²), right?

I don't understand your algorithm perfectly, but if you mean above code with some_value = 0 then no. The total running-time cost is linear since costs add up.

If you mean something like

arr = new array[n]
for i = 0 to n-1
  setAllToZero(arr)
end

then it depends on how set_all_to_zero is implemented. If it contains an explicit loop, then we'd expect quadratic runtime cost. If there are machine-level instructions to set a whole stretch of memory to zero, it may be faster.

The same holds for array initialization, by the way: if the machine (model) does not guarantee any specific value after array intialization, or has some nifty way to ensure zeroes everywhere without extra cost, array initialization may only take constant time.


One way to read this "identity" is as follows:

  If $a = O(f(n))$ and $b = O(g(n))$ then $a+b = O(\max\{f(n),g(n)\})$.

This indeed holds, as you can prove using the definition of big O.

There is another possible interpretation:

  $\{ a + b : a = O(f(n)), \; b = O(g(n)) \} = \{ c : c = O(\max\{f(n),g(n)\})\}$.

This also holds, as you van prove using the definition.

Whether it is a legitimate claim in an exam is up to your professor. It is definitely a legitimate claim in a paper.


Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an "e" value and a "n" value?

You have the public key. The whole point about public key cryptography is that the message is encrypted with the public key and must be decrypted with the private key, which you don't have.

The public key is not a secret: it is distributed publically so that people can encrypt messages for its owner. If you could decrypt the message knowing the cyphertext and the public key, RSA would be completely broken, because then anybody could decrypt any message. If anybody knows how to do this, they're keeping it a secret.


As far as we know there is no efficient way to do that.  Such a way would constitute a break of the DSA scheme, and no break of the DSA is known.  In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.

If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$.  Or, you can solve

$$a^x \equiv b \pmod p.$$

Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c < (p-b)/q$ and solve

$$a^x \equiv b + cq \pmod p;$$

if you can't find a solution for a particular value of $c$, try another one until you can.  This won't be efficient once $p,q$ get large.


Total number of calls during insertion into binary tree

The key observation here is that the input is assumed to be such that all insertions fill level 0 (the root level), then completely fill level 1, then completely fill level 2, and so on.

In filling level $i$ we will have constructed $2^i$ new nodes, each of which will require $i+1$ calls to INSERT, so the total cost to fill level $i$ will be $(i+1)2^i$. Thus, the cost to fill levels $0, 1,\dotsc,  k-1$ will be
$$
\sum_{i=0}^{k-1}(i+1)2^i
$$
Now let's say we're finishing by filling level $k$ partially or fully. We're then inserting elements $n=2^k,2^k+1,2^k+2, \dotsc, 2^{k+1}-1$. Each of those will cost $k+1$ calls to INSERT, so for $n$ elements we will have used $n-2^k+1$ insertions, each of cost $k+1$ for a total of $(k+1)(n-2^k+1)$ calls. That must be added to the cost of filling the upper rows, so you get a total cost of inserting $n$ elements level-by-level equal to
$$
\left(\sum_{i=0}^{k-1}(i+1)2^i\right) + (k+1)(n-2^k+1)
$$


Computability of equality to zero for a simple language

This is a rather tricky question! As you seem to understand, the real issue is the presence of $\hat{}$. It is intimately related to a well known conjecture: Schanuel's conjecture, which states that, essentially, there are no non-trivial algebraic relationships between $\pi$ and $e$.

The (expected) positive answer to this conjecture would give you a decision procedure for comparison with $0$:

Reduce the expression using algebraic equalities (e.g. $(x^y)^z = x^{yz}$ etc.)
Separate the terms with exponents and the terms without.
Check that the base ($x$ in $x^y$) of the terms with exponents are all linearly independent.
The term is 0 iff it is trivial i.e. it reduces to 0 by algebraic operations.

A related question is Tarski's exponential function problem which involves variables. However it is relatively simple to reduce concrete expressions with exponents to functions with variables given the Lindemann-Wierstrass theorem.

Edit: I don't know anything about the actual complexity of the problem, though. Note that it strongly depends on your computational model e.g. whether arithmetic operations constant time.

Edit 2: I made a crucial mistake: it's not the base $x$ in $x^y$ that needs to be taken but rather $y\ln(x)$, which is much harder to check for linear independence.


Question about the undecidability of $A_{TM}$

If you know what the program is doing, you can predict its outcome even without running it. For example, consider the following program.

INPUT: a polynomial P with integer coefficients
n = 0
while P(n) is different from zero:
  n = n + 1

This program halts if the input polynomial $P(x)$ has a non-negative integer root. It turns out that this problem is decidable - there is a clever shortcut that determines the outcome of the program. How can we rule out the existence of such shortcuts in general? The proof you describe is one clever way of doing that.


sorting a sorted array that has been inc/dec by random numbers

Your algorithm doesn't work since you're analyzing it under some (suspect) random model, whereas the problem setters wanted a worst case guarantee. The worst case for you is that everything falls into the same bucket, and then you just get the usual $O(n\log n)$ guarantee.

Instead of your approach, I suggest trying to use the following observation:

  After sorting, each value moves at most $2X$ positions.

As an example of why this is useful, note that you can find the minimum of the array in time $O(X)$ by looking only at the first $2X$ elements.


What you want is not necessarily possible. So you have to build grammars
that will make it possible.

Try prefixing both languages by $\{0,1\}^3$ (for example).  That is,
if $L_G$ and $L_H$ are the languages corresponding to your grammars,
consider the languages $\{0,1\}^3$.$L_G$ and $\{0,1\}^3$.$L_H$.

You should be able to build grammars for them, and also prove that
they are complement of each other. You should also be able to show
that since, there are DPDAs recognizing the two languages $L_G$ and
$L_H$, you can build from them DPDAs that recognize your augmented
languages.

If you build the grammars as you should (it is very easy), you will
get your double handle.

The only problem is that, since both handles are on the same side, you
cannot use them for a bicycle, or for a heavy pot.


How do I solve this graph with Dijkstra's Algorithm?

Firstly, I suggest that you start off with a simple graph (5 nodes would do). I believe you are mixing Dijkstra with A* search algorithm and are trying to perform A* search (even without knowing it).

For Dijkstra:

Assign to each node a distance value. 0 for initial node and infinity for all other nodes (since they are not visited)
Set initial node as current. Mark other nodes as unvisited. Create a set of all unvisited nodes.
For the current node, consider all of its neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, keep the current value.
When we are done considering all of the neighbors of the current
node, mark the current node as visited and remove it from the
unvisited set. A visited node will never be checked again.
If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity, then the algorithm has finished.
Otherwise, select the unvisited node that is marked with the
smallest tentative distance, set it as the new "current node", and
go back to step 3.

If you need more help on this method, let me know!


How is CLR(1) grammar more powerful than LALR(1) grammar

LALR(1) is the grammar obtained by merging states of CLR(1). The states with the exact same production rules i.e. the exact same core, but different lookahead are combined together.
Specifically, consider
$$I_i: A\rightarrow \alpha \bullet \beta, \; a \;\; \mbox{and}\;\; I_j: A\rightarrow \alpha \bullet \beta, \; b$$
The merged state looks like
$$I_{ij}: A\rightarrow \alpha \bullet \beta, \; a/b$$
This merging introduces reduce-reduce conflict, even if the original LR(1) grammar was free of such conflicts. To show this, we will consider an example.
Let there be two states $I_i$ and $I_j$ in the LR(1) grammar.
$I_i:$

$A\rightarrow \alpha \bullet, \; p$
$B\rightarrow \alpha \bullet, \; q$

and $I_j:$

$A\rightarrow \alpha \bullet, \; r$
$B\rightarrow \alpha \bullet, \; s$

The merged state $I_{ij}$ is

$A\rightarrow \alpha \bullet, \; p/r$
$B\rightarrow \alpha \bullet, \; q/s$

Now, for the LALR(1) grammar to have a reduce-reduce conflict either

$p=s$ which is possible without a reduce-reduce conflict in $I_i$ and $I_j$ OR
$q=r$ which is also possible without a reduce-reduce conflict in $I_i$ and $I_j$

Thus, it proves why LALR(1) is less powerful than CLR(1).


DFA for Strings with third symbol from RHS as 1

You probably want to substitute $a$ with $1$ and $b$ with $0$ but apart from that your solution is correct.

Finding an equivalent NFA is easy with Thompson, Glushkov etc. From that you can derive an DFA via powerset construction. However, for this short expression you also can just write the DFA down. Imagine the states as storage what the last 3 symbols were, and accept if the third last was a 1, i.e. name the states 000 to 111 where 000 is the initial state and all states with a leading 1 are accepting. A transition is just a shift-left with the last read symbol on the right, i.e. $\delta(abc, d) = bcd$, with $a,b,c,d \in \{0,1\}$.


Since you don't provide any attempt on your own part, note two things.

The definition of countability.

  A set $A$ is countable if and only if $A$ is finite or there is a bijection $f : A \to \mathbb{N}$.

How do you represent pushdown automata in a formal way?

If you digest the first item and answer the second, the answer should become apparent.


You gave the closed form for the number of operations:
$$
\sum_{m=1}^n n(n-1)\cdots(n-m+1) = \sum_{m=1}^n \frac{n!}{(n-m)!} = n! \sum_{m=0}^{n-1} \frac{1}{m!}.
$$
We can estimate this sum as follows:
$$
n! \sum_{m=0}^{n-1} \frac{1}{m!} =
n! \left(e - \sum_{m=n}^\infty \frac{1}{m!}\right) =
en! - 1 - \frac{1}{n+1} - \frac{1}{(n+1)(n+2)} - \cdots = \\
en! - 1 - O\left(\frac{1}{n}\right).
$$


Are functions that are equal to a constant as you take a limit to infinty O(1)?

By definition of $O$ notation, if you can find a constant $c$ and $n_0$ such that $f(n) < c g(n)$ for all $n > n_0$, we can say $f(n) = O(g(n))$. In this case, suppose $n_0 = 1000$ and $c = 3$ and $g(n) = 1$. You can show that as $f(n)$ is increasing function and $\lim_{n\to\infty}f(n) = e$, it is true $f(n) < 3 g(n)$ for all $n > 1000$. Therefore, $f(n) = O(1)$.


Remove duplicates from dictionary in a safe and clever way

Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given examples.

Your algorithm might return the wrong result. For example, consider the following dictionary.

{ 1, ["A", "B"] }
{ 2, ["A", "B"] },
{ 3, ["C", "A", "B"] },
{ 4, ["D", "A", "B"] }
{ 5, ["C", "D", "E", "F"] }
{ 6, ["C", "D", "E", "F"] },

Your algorithm might proceed to remove value "C" from key 3 followed by removing value "D" from key 4. You can check that each keys still has at least 2 values and each value is still at least assigned to 2 keys. However, you can see that key 1, 2, 3 and 4 have two values in total, "A" and "B". So it is not possible to assign each of those four keys with a different value. However, there is an assignment that is possible in the beginning, i.e., { 1, ["A"] }, { 2, ["B"] }, { 3, ["C"] }, { 4, ["D"] }, { 5, ["E"] } and { 6, ["F"] }.

The problem you are trying to solve is fundamentally finding the maximal matching in unweighted bipartite graphs. You can find various algorithms given in that Wikipedia page such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. I will let you figure out how to adjust or extend those algorithms a bit to solve your task of "removing duplicates from dictionary".


How could i create a multi-threading system in a kernel?

In a multiprocessing system the other cores of the CPU are initiated with boot code like UEFI or legacy bootloader just like the first core of the computer.
The CPU is manufactured to use a "core 0" as the first core of the system. After boot, the kernel needs to use the Local APIC of core 0 to send IPI ( interprocessor interrupts) to other cores to start them. As stated on osdev.org,
IPIs are sent through the BSP's LAPIC. Find the LAPIC base address from the MP tables or ACPI tables, then you can write 32-bit words to base + 0x300 and base + 0x310 to send IPIs. For a init IPI or startup IPI, you must first write the target LAPIC ID into bits 24-27 of base + 0x310. Then, for an init IPI, write 0x00004500 to base + 0x300. For a SIPI, write 0x00004600, ored with the page number at which you want to AP to start executing, to base + 0x300. For more information, see http://wiki.osdev.org/APIC#Local_APIC_registers.


Choice of machine learning algorithms frequency of parts of speech

You're trying to classify the sentences' sources, right? I would suggest grouping your training data by their sources (but only up to some fixed size, in which case you would have a duplicate entry for that source). E.g., if you are trying to classify the source of a tweet, you would make each tweet (not sentence, and that means each vector would represent a string of up to 140 characters) a vector and calculate its corresponding features, which should span the contents that the feature vector would relate to. Further if you could get each of the fixed bodies of text into  ARFF format, where the last value in the vector would represent the source of the fixed body of text and the feature vectors would each have the same number of features (the features of which you would pick, more on this in a bit) then you wouldn't be too far from being able to use the Weka suite of classifiers. As for which classifier you should use, I suggest skimming through the following paper:

Antti Puurula, Sung-Hyon Myaeng.  Integrated Instance- and Class-based Generative Modeling for Text Classification.  ADCS 2013.

It comes from the same machine learning group that produced the Weka suite of classifiers and should give you some pretty good insight.

For your choice of what features you would like to vectorize the fixed bodies into, it would be good to count classes of tags. For example, you could count the number of adverbs as a feature, and/or count the number of first-person/second-person/third-person pronouns as a feature, and/or count the number of verbs in a certain tense as a feature, etc. The features you choose are more so based on your understanding of the bodies. If your fixed bodies could include multiple sentences then some other features could also be the average length of sentences (with respect to number of tokens), the average length of tokens (omitting punctuation, for example, from this group), and/or even just the number of sentences in the fixed body.

Make sure to pick enough features, and make sure to pick features you think would be better at differentiating your classes of sources. For example, if any two of your sources are likely to differ in the formality of their tones, then a useful feature would be the number of slang tokens per fixed body.


In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:

\begin{align}
\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\
&\text{and $M$ }accepts\text{ $w$ after a finite computation}\}
\end{align}


Detect cycles of odd total weight in a graph with {0,1}-weighted edges

Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.

What is happening here? Let us consider the original edge-vertex incidence matrix. Rows corresponding to cycles sum to zero, since each vertex appears in exactly two edges. Conversely, if we have a set of rows summing to zero, then the degree of each vertex is even. Starting at an arbitrary edge, we can trace a walk that will eventually close onto itself. We remove the corresponding cycle (which need not contain the original edge), and continue. In this way, we see that a set of rows summing to zero correspond to an edge-disjoint union of cycles.

By adding an additional $1$ column to the matrix, we are tracing the parity of the cycle. An odd cycles sums up to the vector $0,\ldots,0,1$. Conversely, if a set of rows sums to $0,\ldots,0,1$, then it corresponds to a set of cycles whose total length is odd, so one of the cycles is odd.

Finally, finding whether a vector is in the row space of the matrix is a standard problem in linear algebra, which can be solved using Gaussian elimination and related algorithms.


PAC learnability given information about the expectation of the training/true error

$\mathcal{H}$ is not necessarily pac learnable.

Lets break down your statement, you have an algorithm $\mathcal{A}$, which given a set of labeled samples $S\subseteq \mathcal{X}\times \mathcal{Y}$, generates a hypothesis in $\mathcal{H}$. You also know that $\mathcal{A}(S)$ achieves a generalization error which is close to its sample error (the closeness is determined by $\epsilon_m$).

If $\mathcal{A}$ was guaranteeing low sample error, then we were safe. However, this is not necessarily the case, take for example the rather stupid learning algorithm which always outputs some constant $h\in \mathcal{H}$ (and ignores the samples). This algorithm has equal sample/generalization error (so the condition is satisfied), but this obviously does not mean $\mathcal{H}$ is pac learnable (you can implement this algorithm even for $\mathcal{H}$ with infinite VC dimension).


The language of Turing machines that accept exactly $k$ inputs

Hint: to decide whether $M$ halts on input $w$, consider a new machine $M'$ that rejects every input except $w$ and simulates $M$, otherwise. That's not quite the answer but it should get you close enough.


How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?

The proof is by induction. The case $n = 1$ is clear. For $n > 1$, choose two leaves at maximal depths, and merge them. Huffman's algorithm could have chosen these two leaves at the first step and merged them. Now apply the inductive hypothesis to complete the proof.

Note that Huffman's algorithm, as described in your textbook, is non-deterministic in the sense that at any step there could be many valid choices. Any actual implementation of the algorithm will use a tie-breaking rule to arbitrarily choose which two leaves of minimal probability to merge at any given step.


Proving a language with $(ab)^n$ is not regular with pumping lemma?

Let's suppose, for concreteness, that $p = 3$.
You choose the word $z = (ab)^3a^k(ba)^3$. How does this word look like? It is impossible to tell, since we don't know what the value of $k$ is. Let's therefore take $k = 3$, that is, we are looking at the word $z = (ab)^3(ba)^3 = abababbababa$.
Next, we are given a decomposition $abababbababa = uvw$, where $|uv| \leq 3$ and $v \neq \epsilon$. There are six possibilities:

$u = \epsilon$, $v = a$, $w = bababbababa$.
$u = \epsilon$, $v = ab$, $w = ababbababa$.
$u = \epsilon$, $v = aba$, $w = babbababa$.
$u = a$, $v = b$, $w = ababbababa$.
$u = a$, $v = ba$, $w = babbababa$.
$u = ab$, $v = a$, $w = babbababa$.

You need to be able to handle all of them. There are four different cases: $v \in (ab)^*$, $v \in (ba)^*$, $v \in a(ba)^*$, $v \in b(ab)^*$. For each of them, you need to find a value of $i$ so that $uv^iw \notin L_2$. When showing that $uv^iw \notin L_2$, you have to show that there are no $n \geq 0$ and $k < 3$ such that $uv^iw = (ab)^n a^k (ba)^n$.


Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?

XORSAT is in P, so any such language would have to be in P as well.

As such, it is easy to exhibit such an example: the problem XORSAT itself satisfies all your requirements, as XORSAT is Cook-Levin reducible to XORSAT (let $f$ be the identity function).


How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular?

A decimal number is divisible by 4 if the number formed by its last two digits are divisible by 4. Stated differently, divisibility by 4 depends only on the last two digits. That should be enough for you to show that your language is regular.

The language of numbers in base $b$ divisible by $m$ is regular for all $b,m$, but that's somewhat harder to show.


Is my lambda calculus reduction correct and final form valid in simply typed lambda calc?

While your way of calculating the types isn't quite how it works, it gives the right answer here. As you say, you end up with f 0 having type R and g 0 having type R. Since we apply f 0 to g 0, R must be of the form R -> X for some X. In other words, you have the equi-recursive type R = R -> X. Such types are almost always disallowed. Thus, this would be a type error. If R is a fixed primitive type, e.g. a type of primitive natural numbers, then it is simply not the case that R = R -> X and so you would also get a type error.


How do I interpret this divide and conquer algorithm for removing duplicates in a list?

As wvxvw suggested, the dot notation is a shorthand way of separating the head and the tail of a list, as in LISP or ML. For example, if we have a list $L=\langle\,4,7,8\,\rangle$ then we can write $L$ as $c_1.c_2$ where $c_1=4$ and $c_2=\langle\,7,8\,\rangle$.

The function $\Delta$ takes two sorted lists, $c_1.c_2$ and $d_1.d_2$ and recursively produces a list without duplicates. For instance, we might have
$$\begin{align}
\Delta(\langle\,6\,\rangle,\langle\,3,5,6\,\rangle) &=\langle\,3,\Delta(\langle\,6\,\rangle,\langle\,5,6\,\rangle)\,\rangle&\text{by rule 3}\\
&=\langle\,3,5,\Delta(\langle\,6\,\rangle,\langle\,6\,\rangle)\,\rangle&\text{by rule 3}\\
&=\langle\,3,5,6,\Delta(\varnothing,\varnothing)\,\rangle&\text{by rule 2}\\
&=\langle\,3,5,6\,\rangle
\end{align}$$
This is where the real work is done. The function $SD$ uses $\Delta$ by splitting the original sorted list $\langle\,s_1,s_2,\dotsc,s_n\,\rangle$ into two: the odd-indexed part, $\langle\,s_1,s_3,s_5,\dotsc\,\rangle$ and the even-indexed part, $\langle\,s_2,s_4,s_6,\dotsc\,\rangle$ and applies $\Delta$ to them, to remove duplicates. For instance,
$$\begin{align}
SD(\langle\,3,3,3,5,6,6\,\rangle&=\Delta(SD(\langle\,3,3,6\,\rangle),SD(\langle\,3,5,6\,\rangle))\\
&=\Delta(\langle\,3,6\,\rangle,\langle\,3,5,6\,\rangle)&\text{since $SD$ removes dups}\\
&=\langle\,3,5,6\,\rangle
\end{align}$$
as we saw above. It's worth noting that the arguments to both functions must be in sorted order. To see why, trace the action on, say, $\langle\,3,4,2,3\,\rangle$.


Difference between ⫾ (U+2AFE) and ⫿ (U+2AFF) in the context of Dijkstra's Guarded Command Language?

Non-deterministic guarded choice is an associative-commutative binary operator. My guess is that the character ⫾ U+2AFE is intended to be used as an infix binary operator and the character ⫿ U+2AFF, which is larger and described as “n-ary”, is intended to be used as a prefix operator which is typeset larger, in prefix position, and typically with a subscript and sometimes a superscript to indicate the range over which the operation is carried out.

$$⫿_{i=1}^n c_i \rightarrow a_i \qquad = \qquad  \mathsf{if}\; c_1 \rightarrow a_1 ⫾ \cdots ⫾ c_n \rightarrow a_n \;\mathsf{fi}$$

Typeset with inline math: $⫿_{i=1}^n c_i \rightarrow a_i = \mathsf{if}\; c_1 \rightarrow a_1 ⫾ \cdots ⫾ c_n \rightarrow a_n \;\mathsf{fi}$

It's the same relationship as between $+$ (binary) and $\sum$ (n-ary), or between $\times$ (binary) and $\prod$ (n-ary) ($\prod$ is sometimes a different product such as $\cdot$). For binary operators other than the two classics addition and multiplication, the n-ary version is the same glyph, just bigger.


You understand this correctly. the set $CS - CF$ denotes the strict difference between these two levels of the Chomsky hierarchy. If you are reading this in a textbook, you will soon learn that $CS-FS \not= \emptyset$, that is, context-sensitive grammars are strictly more expressive than context-free ones. For example, context-sensitive grammars can count, whereas context-free ones, not so much: the language $\{a^nb^nc^n | n \in \mathbb{N}\} \in CS-CF$.


DFA that accepts decimal representations of a natural number divisible by 43

If the string read has a certain decimal value, then reading the next digit changes that value: multiply by $10$ and add that digit. The DFA keeps track of that value modulo $43$. Thus, for $q\in \{0,1,\dots,42\}$ and $a\in \{0,1,\dots,9\}$ you do

$\qquad \delta(q,a) = (10\cdot q + a) \bmod 43$.

Note that the DFA does not actually perform the computation; the transition is hard-coded.


show that language $L'$ is regular (given $L$ regular)

For language $L-$ $M=(Q,\Sigma,\delta, q_0, F) $
For language $L'-$ $M'=(Q',\Sigma,\delta, q_{start}, F')$
$Q'=(Q\times Q)\cup q_{start}$
Transistions
$\delta'(q_{start}, \epsilon)=\{(q,q_{acc})|q_{acc}\in F\}$
Transition from $(q_1, q_2)$ to $(q_3,q_4)$
$\delta'((q_1,q_2),a\in\Sigma) = \{(q_3,q_4)\}\text{   iff }\delta(q_1,a )=q_3 \text{ and } \delta(\delta(q_4,b),c)=q_2 $ for some $b,c\in\Sigma$
Accepting states
$F'=\{(q,q)|q\in Q\}$


How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

If you want to find the worst-case asymptotic running time, then you can't use probabilities; you have to assume that at each branch, it takes the slower path.  Thus you get a recurrence relation

$$T(n) = \max(T(3n/4), T(n/4)) + O(1).$$

If you want to find the expected running time, then you can use probabilities:

$$T(n) = p_0(n) T(3n/4) + p_1(n) T(n/4) + O(1)$$

where $p_0(n)$ is the probability of taking the "then" branch and $p_1(n)$ is the probability of taking the "else" branch.  If you don't know the probabilities, this kind of analysis won't be useful and you presumably won't be able to calculate the expected running time.  There are some important caveats here as well; the random choice must depend only on internal random choices of the algorithm, not on $n$, or else funny things can happen.

Solving the recurrence relations above is a separate matter.  Often it suffices to apply the master theorem.

Normally, in theoretical computer science, if we are talking about asymptotic running time, the default assumption is that you are talking about worst-case running time.  If you want to focus on something else (e.g., expected running time), it's important to state that explicitly, otherwise you might cause confusion among readers.

Since you seem to lack some basic understanding of running time analysis, I suggest studying big-O notation, running time analysis, and recurrence relations.  This is a slightly tricky example, and it's not the simplest one to start with to start learning the subject.  We do have some resources on that subject here; see, e.g., How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Sorting functions by asymptotic growth, Is there a system behind the magic of algorithm analysis?, Solving or approximating recurrence relations for sequences of numbers, and a good algorithms textbook.


The standard solution is to build an index: a data structure that maps from search term to all of the records that match that search term.  Your index could be a hashmap or a B-tree, for instance.  In this case, the search terms are things like "google" or "facebook" or "facebook.com", and each one maps to a list of all records that match it.  Thus, facebook.com would be associated with two search terms ("facebook.com" and "facebook") and would be present in two of these lists.

You raised some concerns about this approach, but they are all manageable:

Yes, search terms like "com" will match many records.  You should decide whether searching for "com" is useful or not.  If it's not useful, don't include that in the index: build a list of "stopwords" (e.g., com, org, etc.), and don't include any of them in the index.  For instance, you might decide that the TLD part of a domain name is not one of its matching search terms.
Yes, inserting or removing one record will require updating multiple entries in the index.  But this just isn't that big a deal.  Most domain names have very few components: e.g., "www.google.com" will require changing 2 entries in the index (assuming you have blacklisted "com"), which just isn't that big a deal.
Hash collisions are dealt with using standard methods for building hash tables and just aren't that big a deal.  Or, you can use any other data structure, like a B-tree.
No, this can't handle mis-spellings.  Mis-spellings are an entirely different problem, which require a range of different solutions, and you should ask a separate question about that (but first, study Levenstein distance, metric trees, and data structures for spelling correction and answering nearest-neighbor search in the Levenstein distance metric -- there are a bunch of questions on this site that are relevant).
No, there is no reason that the hash key needs to be 64 bits.  The hash key needs to be at least the number of buckets in your hashtable.

I suggest you read some standard resources on building indices, e.g., in database textbooks, and read about how search engines work.  Those topics are well-studied and those techniques will be applicable to your problem.


Turing Machine to return all prime numbers

Designing a Turing machine is very laborious, even for simple tasks. So I suggest you keep the algorithm as simple as possible, even if it is very inefficient.

The very simplest prime generating algorithm (even simpler than the sieve of Eratosthenes) is as follow:

Start with $n=2$ - this is prime.
Set $j$ equal to $n$.
Add $1$ to $n$
Set $k$ equal to $n$.
Subtract $j$ from $k$.
If $k$ is greater than $0$ go to step $5$.
If $k$ equals $0$ then $n$ is not prime; go to step $2$.
Subtract $1$ from $j$.
If $j$ equals $1$ then $n$ is prime; go to step $2$.
Go to step $4$.


Pumping-Lemma regular languages: Consider multiple cases?

Of course, you have to consider all possible cases. Otherwise you do not prove that "there exists a factorization" is false. So you actually have to consider all $ab^k$ with $k < n$. Here you get some prefix $ab\cdots bab\cdots b$ and therefore the words are outside tha language. Or you chose a different word $z$ if $n=0$ is allowed, which depends on your definition of the natural numbers - then you only have one case.

For the case you treat, probably stating that $uv^2w = ab^{n+k}c^n$ would be more complete than saying "obviously."


Probability that a uniformly random sequence is already sorted

You can have $k^n$ possibilities of generating a sequence.

Now, there are only $^{n+k-1}C_{k-1}$ favorable outcomes .

So, the probability that your sequence is already sorted is: $$ \frac{^{n+k-1}C_{k-1}}{k^n}$$


Can both $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$ happen at once?

Consider the following statement about two functions $f,g$:

  $f(n) \neq O(g(n))$ and $g(n) \neq O(f(n))$.

The question wants you to choose which of the following holds:

The statement holds for every $f,g$.
The statement holds for no $f,g$.
The statement holds for some $f,g$, and doesn't hold for other $f,g$.

The third option is correct in your case, and this is the meaning of "sometimes true".

Indeed, if $f(n) = g(n) = 1$ then the statement doesn't hold. Conversely, if $f(n) = 1$ and $g(n) = |n\sin n|$ (where $\left|\cdot\right|$ denotes absolute value) then the statement does hold.


Why does counting sort copy the input elements?

They do not need to do it this way, but they might have found it more elegant.

Their idea is not:

  Put every element j in 0..k-1 into b exactly c[j] times.

But rather:

  Use the counts to compute the position of every a[i] in b.

That is what the second loop is for: it subsequently computs the offsets for the block of elements i in b.
(The should use j here to avoid confusing, but well.)

As KWillets notes, the latter idea lends itself¹ better to sorting more complex data, say objects, by an integer key; then you would need to copy the references in proper order. Note how it is even stable!

On the other hand, if you do not need resp. make use of this, I expect the first idea to be much more efficient in practice: observe how the second implementation makes non-sequential accesses to arrays b and c which may cause a lot more cache misses than the alternative.

The given implementation can only sort integer arrays, of course.


First thing is that OSI model is a reference and theoretical model which breaks down the functionality in different layers although the real implementation of network might differ.

It is better to have abstractions over abstractions. It is good to have multiple layers with different functions rather than a monolithic implementation. If every layer would have its own concern then it will be easy to find the root cause of failure if it occurs.

Also a network for e.g. Internet is a very complex structure which requires different protocols to actually implement it. If the headers would be constructed all at once then it will not be distinguishable how the protocols are actually applied. A protocol which applies to the physical medium (e.g. Ethernet protocol) cannot be applied before actually producing reasonable and transmittable chunks of the data (which is done at an upper layer).

So it is a good practice to do it progressively and this generally applies to entire Computer Science because it is never recommended to have one monolithic chunk rather than multiple small understandable chunks.


Removing constant symbols from language to prove irregularity

The language $L'$ is the "same" as $L$ (in fact, it's an asymmetric relation) in two steps. If $L$ were regular, then so would be $L'' = \{0^n 2^n : n > 0 \}$ (take a DFA for $L$ and replace $1$ edges with $\epsilon$ edges). In its turn, $L''$ is the same as $L'$, up to change of symbols.


Relation between simple and regular grammars

A Simple Grammar (s-grammar) is one in which every production is of the form $A \rightarrow aB_1B_2...B_n$ where $a$ is a terminal and all $B_i, i\geq0 $ are non-terminals, and there is only one production with any pair $\langle A,a\rangle$.

Clearly, every s-language (produced by an s-grammar) is unambiguous and easily parsed, since each terminal symbol from left-to-right and non-terminal uniquely determine the production to apply.  For example, if the string is $abc$, then the pair $\langle S,a\rangle$ uniquely determines the first production of the parsing, and so on for each terminal and the non-terminal to its immediate right.  Thus, a language defined by an s-grammar can be parsed one symbol at a time, without lookahead, yielding linear parsing time, in fact, time $|x|$.

S-grammars are not terribly important in their own right, since most real languages exceed their power. But they are a stepping stone to other grammars parsed in linear time, such as $LL(k)$ grammars in which there is a bound $k$ on the lookahead needed to determine a production during parsing. In effect, an s-grammar is an $LL(0)$ grammar.

The connection to automata is that an s-langauge can be parsed with a pushdown automaton with a single state which just looks at the input symbol and top stack symbol to determine a string of stack symbols to push.  But since the s-grammar...

$S \rightarrow aSB|\#\\ B\rightarrow a$

...generates non-regular $\{a^i\#a^i:i \geq 0\}$, s-languages cannot in general be recognized by finite-state automata, deterministic or non-deterministic.


Solving Independent Set through Vertex Cover

It is that simple, those questions are talking about fixed parameter tractable algorithms w.r.t. the size $k$ of an independent set/vertex cover. Your algorithm will work just fine setting $k' = |V| - k$. Clearly, the new value $k'$ also affects the running time of your algorithm.


How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

One type of conversion is simply the reverse of the k-sat-to-3-sat conversion:

Recall, the conversion of k-sat to "j"-sat, $j<k$:

$$\begin{eqnarray*}
&& (x_1 \vee x_2 ... \vee x_j \vee ... \vee x_k)\\
\rightarrow && (x_1 \vee x_2 ... x_j \vee d)
               \wedge (\overline d \vee x_{j+1} \vee x_{j+2} ... x_k)\\
\end{eqnarray*}$$

Here, $d$ is a dummy variable, which means something like "This clause isn't true, but another clause I know is". The other clause being the next clause that was split off of the original. The above is an example where $2j \geq k$, otherwise the 2nd split node will still be larger than $j$, and we must split that one again, in the same way.

Reversing the conversion

$(x_1 \vee x_2 ... x_j)
 \wedge (\overline x_j \vee x_{j+1} \vee ... x_k)$ then you can combine the clauses into:

$(x_1 \vee x_2 ... x_{j-1} \vee x_{j+1} \vee x_{j+2} \vee ... x_k)$

Notice the missing $x_j$ in this new formula.

Of course, you aren't guaranteed to find clauses like this in an arbitrary formula so the smallest guaranteed $n_{k+m}$ is equal to $n_k$.

However, on ordinary formulas, a variable and its negation will appear in the formula; otherwise you can perform pure-literal-elimination (described here). For simplicity, lets also assume that $k+m \geq 2k-2$. Then we can combine any two clauses that contain a literal in one and its negation in the other. Since every literal should have another clause with a negation, one can empirically guess that you should be able to approximately halve the number of clauses (you might get stuck with some literals and their negations in already joined clauses, and thus you will be stuck with some unjoinable clauses at the end; optimally joining clauses like this might be another interesting problem).

EDIT:

After reflection, I realized that $x_j$ must be free and not used elsewhere in the formula in order to collapse the two clauses that it belongs to. Therefore, these type of clauses (one containing a literal, and the other its negation, with this literal not being used elsewhere in the formula) is much rarer than I previously thought above. So the real answer is, there is no guarantee of how much we can reduce the number of clauses in the formula.