Is deciding whether the language of a TM contains all strings of length 4 computable?

This might help you understand a standard proof technique for such problems. An instance of HP is a pair, $(\langle M\rangle, x)$ where $\langle M\rangle$ is a description of a TM $M$ and $x$ is a string. To reduce HP to 4LENGTH we require a function $f$ that maps instances of HP to instances of 4LENGTH such that $(\langle M\rangle, x)\in HP\Longleftrightarrow f((\langle M\rangle, x))\in 4LENGTH$. In other words, an instance $I = (\langle M\rangle, x)$ will have a "yes" answer ($M$ halts on $x$) if and only if the transformed instance will have a "yes" answer ($f(I)$ accepts all strings of length 4).

Given $(\langle M\rangle, x)$, we'll define a TM $M'$, using $M$ and $x$, that acts as follows:

M'(y) =
   if |y| = 4
      erase y
      write x on the tape
      simulate M
      return accept

Now if $(\langle M\rangle, x)\in HP$, then $M$ will halt on $x$ and so $M'$ will accept any string of length 4, so $M'\in 4LENGTH$.

On the other hand, if $(\langle M\rangle, x)\notin HP$, then $M$ will never halt on $x$ and so $M'$ will never get to the return accept statement and so will accept nothing. Hence if $(\langle M\rangle, x)\notin HP$, then $M'\notin4LENGTH$.

To summarize, we have established a faithful mapping from instances of HP to instances of 4LENGTH.

Now to show that 4LENGTH is not recursive, we argue by contradiction. Suppose that 4LENGTH were recursive. Then there would be a decider, $D_4$, for 4LENGTH namely, given any TM description $\langle N \rangle$, $D_4$ would take that description as input and halt and either return "yes" if $\langle N \rangle\in 4LENGTH$ and "no" if $\langle N \rangle\notin 4LENGTH$.

We can then use $f$ and $D_4$ to build a decider for HP. It would work like this:

Given an instance $I=(\langle M\rangle, x)$ of HP, use $f$ to produce an instance $f(I)=\langle N\rangle$ of 4LENGTH.
Run the decider $D_4$ on $f(I)$.
If $D_4$ answers "yes" to $f(I)$, then by the construction of $f$, $I$ must have been in HP. Similarly, if $D_4$ answers "no", $I$ must not have been in HP. In short, we've built a decider for HP, contradicting the fact that HP is not recursive.


Proof by induction concerning approximation algorithm for subset sum

You haven't described the approximation algorithm, so I assume it's something like the following one (perhaps with a few changes in some details):

Input: a universe $U = \{x_1,\ldots,x_n\}$, a target sum $T$, and an accuracy parameter $\epsilon$.
Initialize $L_i = \{0\}$.
For $i = 1, \ldots, n$:

Compute $L_{i+1} = L_i \cup \{\ell + x_i : \ell \in L_i\}$.

Remove all element larger than $T$ from $L_{i+1}$.

Replace each element $\ell \in L_{i+1}$ by the largest power of $1+\epsilon/2n$ which is at most $\ell$.

Return the element in $L_n$ closest to $T$.

This is a $1+O(\epsilon)$-approximation algorithm, in the sense that it can tell whether there is a subset of $U$ summing to roughly $T$, up to a factor of $1+O(\epsilon)$.

The exercise asks you to show that for each $i \in \{0,\ldots,n\}$, the following is true: if $y \in P_i$ (the set of all sums of subsets of $\{x_1,\ldots,x_i\}$) is at most $T$, then there is an element $z \in L_i$ which is approximately equal to $y$, in the sense that
$$ \frac{y}{(1+\frac{\epsilon}{2n})^i} \leq z \leq y. $$
Taking $i = n$ will give the desired analysis of the complete algorithm.

Let us denote the claim symbolically by $C_i$. The exercise suggests that this claim can be proved by induction on $i$. This suggests the following plan to prove $C_0,\ldots,C_n$:

Prove $C_0$.
For $i=1,\ldots,n$, assuming $C_{i-1}$ is true, prove that $C_i$ is true.

To find out what claim $C_0$ or $C_{i-1}$ is, you will need to substitute $0$ or $i-1$ for $i$ in the claim.

Good luck with executing this plan.


Here's how it works:

I'll provide 2 solutions:

$O(\log{n})$ space and $O(\log{\log{n}})$ query.
$O(\log{n})$ space and $O(\log{\log{\log{n}}})$ query.

1) Using binary search on local mins.

Find all local minimums and store them in an array $B$ in their original order - $O(n)$ time, $O(\log{n})$ space ($<O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we binary-search the array $B$ for indices $i$ and $j$ to find the closest index which has a local_min.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Perform a binary search on array $B$ for index $j$ or the smallest index larger than $j$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{n}})$.

Range between 2 local mins (not including):

Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(loglogn)$.

Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).
Again, to recognize the case, binary-search for $i,j$ in $B$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and i overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ, compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{n}})$.

2) Using y-fast trie on local mins.

Find all local minimums and store them in a y-fast trie structure (call it $Y$) and let the keys be the original indices - $O(n)$ time, $O(\log{n})$ space. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we search $Y$ for indices $i$ and $j$ (or their pred and succ) to find the closest index which has a local_min. Search of pred/succ in a y-fast-trie of $n$ elements takes $O(\log{\log{n}})$.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Search for index $j$ or its successor in $Y$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{\log{n}}})$.

Range between 2 local mins (not including):

Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(\log{\log{\log{n}}})$.

Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Again, to recognize the case, search for $i,j$ in $Y$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and $i$ overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ , compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{\log{n}}})$.

Proof for cases 1&2:

Theorem: in this type of ranges, the min is either the leftmost or rightmost entry.
Proof by contradiction: Suppose the min is somewhere inside the block, and not at the edges.
If it’s the min then it’s smaller than both its left and right neighbors. Thus it’s a local_min by definition. This is a contradiction because we assumed we have a block from a local_min to the next local_min (no local_mins’s in between).


I'm going to go ahead an assume that it's a Java 101 type of exam.

The best way to go about studying for it, in my opinion, is to practice applying the basics. Things such as Data Types, Conditional Statements, using Arrays, etc. A good place that has stuff like this is CodingBat as it gives you answers too. You could even just have a read through a beginner's Java book (a quick google search will bring up loads which you can find a PDF easily).

Then if you want to work on general problems that encompass everything you could do the problems at places like HackerRank (Which is also good practice for coding interviews as many companies use this) or the easy problems at reddit.com/r/dailyprogrammer. There are tonnes of other resources out there but if you would like some more just comment on this.

Good luck in your exam and I hope this helps you a little bit.


What is the difference between Big(O) and small(o) notations in asymptotic analysis?

Bigoh notation $O$:

This is anlogous to $\le$.
$f(n) = O(g(n))$ means that for large enough value of $n$ value of $f(n)$ will be within some constant factor of value of $g(n).$

Smalloh notation $o$:

This is anlogous to $<$ relation.
Now, $f(n) = o(g(n))$ means that if you are given any constant $c>0$ you will be able to find out some constant $n_0>0$ such that for all $n\ge n_0$, $f(n) < c.g(n)$ holds.

Intuitively smalloh notation says that $f(n)$ is asymptotically slower than $g(n)$.

For example $3n = O(5n)$ but $3n\ne o(5n)$ because for latter case if I give you $c=1/5$ you will not able to find out value of $n_0$ such that for all $n\ge n_0, 3n < c.5n$.


What are barriers to Genetic Programming with cyclic graphs

Perhaps one reason is that constraints (perhaps somewhat arbitrary ones) would have to be imposed on what it means to interpret a program represented in this fashion.

However, recent work with CGP has actually explored the addition of cycles:
Recurrent CGP


You don't have to separate them. People combine them into scannerless parsers.

The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more complicated than the corresponding combination of a regular expression doing lexing and a context-free grammar doing parsing on the token-stream. In particular, grammars for scannerless parsing tend towards ambiguity. It's easier to remove ambiguity for grammars working on a token-stream.

A pragmatic benefit of using a dedicated upfront lexing phase is that you don't couple the subsequent parser with lexical detail. This is useful during early programming language development, when the lexical and syntactic details are still changing frequently.


co-$\mathsf{P} = \mathsf{P}$. To see this, pick your favorite problem $A$ in co-$\mathsf{P}$, let $T$ be a Turing machine for the complement of $A$ (in $\mathsf{P}$) and construct a new Turing Machine $T'$ that simulates $T$, accepts if $T$ rejects, and rejects if $T$ accepts.


There is a solution with $c = 0$: what would happen if $f(x) = 1$ for every value $x$ of $\{0,1\}^n$ but one $\tilde{x}$, for which $f(\tilde{x})$ is very big?


If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?

This is known as an arborescence.  There are algorithms for this problem, such as the Chu-Liu/Edmonds algorithm, but they are more complex than just doing a BFS.  See also https://stackoverflow.com/q/21991823/781723.


Does solving subproblems in logspace in different models implies solving original problem in logspace?

The composition of two logspace functions is again in logspace. This is a classical result that you can try to prove on your own.


Implicit Leading 1 in Binary Floating Point

As @BugKiller says, if it is IEEE format, it doesn't matter how many bits (32, 64, 43, etc) uses your representation, you drop the leading 1. And I think is the same thing with subnormal numbers taking a leading 0. Other floating point representations not specified within IEEE takes the same idea, because this dropped 1 comes from binary representation as any non-zero number will have a leading one, you drop it and you gain 1 bit to expand your representation.


show that if L is a regular, then drop(L) is a regular

I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below).

   Replace all transitions labelled with "a" in the DFA for $L$ with $\epsilon$-transitions in the NFA for $drop(L)$.

Then it should be easy to show that:

If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a suitable word $w' \in L$.  Start from an accepting path $\pi$ for $w'$ in the DFA for $L$ and modify $\pi$ to be an accepting path for $w$ in the NFA for $drop(L)$.
If the NFA accepts a word $w$ then $w \in drop(L)$: look at an accepting path in the NFA for $drop(L)$ and use it construct a word $w'$ that is accepted by the DFA for $L$. Use the fact that you just proved that $w' \in L$ and the definition of the function $drop$ to conclude that $w$ must belong to $drop(L)$.

I'm purposefully being a bit vague on the details, so I don't completely give away the solution. Comment if you need more help.


SimRank on a weighted directed graph (how to calculate node similarity)

The paper "SimRank++: Query Rewriting through Link Analysis of the Click Graph" describes a weighted SimRank algorithm that is similar to my attempt. It uses this formula to update similarity scores:

$s_{k+1}(a, b) = \text{evidence}(a, b) \cdot C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b) \cdot \text{spread}(i) \cdot \text{spread}(j)$

$\text{evidence}(a, b) = \sum_{i=1}^{\left|I(a) \cap I(b)\right|} \frac{1}{2^i}$

$\text{spread}(i) = e^{-\text{Var}(\{w(i, a) ~|~ a \in O(i)\})}$

Note that the weights should be normalized to sum to 1, which I was already doing. SimRank++ also incorporates evidence scores (which account for the quantity of incoming edges) and spread (which accounts for variance of outgoing edge weights).


Python versus Matlab on the quantity 1/0

In the copy that I have of IEEE 754 (2008) it says

7.3 Division by zero 7.3.0
The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation:
― For division, when the divisor is zero and the dividend is a finite non-zero number, the sign of the infinity is the exclusive OR of the operands’ signs (see 6.3).
― For logB(0) when logBFormat is a floating-point format, the sign of the infinity is minus (−∞).

Python is choosing that the exception that the standard requires is a Python exception. My own interpretation is that this agrees with section 7.3. We don't get the value float('inf') because the exception interrupts the execution. I personally find it a bit inconvenient. I don't know the reasons they had for this choice.
One can get the behavior of obtaining a value by using numpy. With
x = numpy.float64(1.0)/numpy.float64(0.0)

we get
x = numpy.float64('inf')

and a RuntimeWarning. Alternatively, one can capture the exception ZeroDivisionError and produce the result float('inf') ourselves.
In Matlab we get inf as the result. It agrees with the standard because I think there is a warning (a flag) that can be seen by setting warning on MATLAB:divideByZero.


Digraph problem relating in- and out-degrees

There is a formulation of this as integer linear programming (ILP).  There is no theoretical guarantee that the resulting ILP will be solvable in polytime, but off-the-shelf ILP solvers are pretty good, and I wouldn't be surprised if in practice an ILP solver is often effective at solving this problem.

In particular, for each edge introduce a variable $x_e$, with the intention that $x_e=1$ means that $e \in A'$ and $x_e=0$ means that $e \notin A'$.  Then we get the obvious constraints $0 \le x_e \le 1$ and $\sum_e x_e \ge m$.  Also introduce a variable $y_e$ for each edge $e \in A$, defined as

$$y_{(u,v)} = \sum_t x_{(t,v)} - \sum_w x_{(u,w)}.$$

Notice that $y_{(u,v)} = d^-_{D'}(v) - d^+_{D'}(u)$.

Now we want to express the requirement that if $x_e=1$ then we must have $y_e\ge 0$.  One way to do this is to introduce the variables $y^+_e, y^-_e$ and add the linear inequalities $y_e = y^+_e-y^-_e$, $y^+_e \ge 0$, $y^-_e \ge 0$, $y^-_e \le c \cdot (1-x_e)$, where here $c$ is a large constant (setting $c=|V|$ is large enough).  Notice that if $x_e=1$, then these constraints imply $0 \le y^-_e \le c \cdot 0 = 0$, i.e., $y^-_e=0$, which implies that $y_e \ge 0$.  In contrast, if $x_e=0$, then these constraints imply $0 \le y^-_e \le c$, which will always be satisfied (the difference of two degrees cannot be more than $|V|$, for trivial reasons), so if $x_e=0$, there are effectively no restrictions on the allowable values of $y_e$, just as we wanted.

There will be a feasible solution to this ILP if and only if there is a subset $A'$ satisfying the desired properties.

My thanks to @user12537, who pointed out that my original answer was flawed.  This revision attempts to address those problems.


Consider an instance $G=(V,E)$ of vertex cover with $n=|V|$ and $m=|E|$, and build a directed graph $G' = (V', E')$ in which:

$V' = V \cup ( E \times \{0, 1, \dots, n\} )$.
For each $e = (u,v) \in E$, $E'$ contains all edges $(u,e')$ and $(v,e')$ for $e' \in \{e\} \times \{0, 1, \dots, n\}$.

Claim: If there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$, then there is a vertex cover of size at most $k$ in $G$.

Proof:
The existence of a set a set of $k$ observers that reaches at least $(n+1)m$ people in $G'$
implies the existence of a set $S \subseteq V$ of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

For every edge $e=(u,v) \in E$,  $\{u,v\} \cap S \neq \emptyset$.
Indeed, if $\{u,v\} \cap S = \emptyset$, then none of the vertices in $e \times \{0, \dots, n\}$ is reached by $S$ in $G'$, showing that $S$ reaches at most $(n+1)m+n - (n+1) = (n+1)m-1$ people in $G'$.
Therefore $S$ is a vertex cover for $G$. $\square$

Claim: If there is a vertex cover $C$ of size at most $k$ in $G$, then there is a set of at most $k$ observers that reaches at least $(n+1)m$ people in $G'$.

Proof:
For each edge $e = (u,v) \in E$, let $x \in \{u,v\} \cap S$. All vertices $\{e\} \times \{0, \dots, n\}$ in $G'$ are reached by $x$ and hence by $C$.
Therefore $C$ reaches at least $m \cdot (n+1)$ people in $G$. $\square$

This shows that your problem is NP-hard.


I have come up with a polynomial-time algorithm for this language that I think is in P.

Possible algorithm (-x means not x).

M = "on input <ø> where ø is a boolean formula in CNF:
1. Repeat until there are no (-x) unit clauses:
   For a unit clause (-x), remove all the clauses containing -x from ø
     and remove all occurrences of x from the clauses in ø
2. If there is an empty clause in ø, reject.
3. Let all literals x in ø be 1, -x 0, and accept.


Data structures for annotations in large-scale text editor

There are many possible data structures you could use.  I will list one.

Augmented balanced binary tree

Stores the string in a balanced binary tree.  Each leaf of the tree holds one character of the document, and you store them in a balanced binary tree data structure: e.g., a red-black tree or AVL tree.  In other words, you think of the tree as representing a map $i \mapsto S[i]$ that maps from an index $i$ to the $i$th character in the document.

This data structure will avoid the need to update the coordinate system by the simple expedient of not using any coordinate system at all.  No indices or offsets are used explicitly.  Instead, everything is represented implicitly in the shape of the tree.

Note that each internal node of the tree implicitly corresponds to a substring of the tree: namely, it is the substring obtained by concatenating all leaves that are descendants of that node.  Equivalently, it corresponds to an interval of indices: namely, the interval $[\ell,r]$ where $\ell$ is the index of the leftmost leaf under that internal node and $r$ is the index of the rightmost leaf under that node.

Also any substring of the document can be expressed into a disjoint union of $\le \lg n$ substrings obtained in this way.  Thus, if $T$ is a substring of the document, it can be viewed as corresponding to a set of $\le \lg n$ internal nodes of the tree (so that concatenating all of the leaves under those nodes yields exactly $T$).

Now you have a list of annotation objects, one per annotation.  The annotation object stores the set of internal nodes that correspond to the substring it is attached to.  Also, each internal node in the tree has a list of backpointers to annotation objects that it is associated with.

Now to attach an annotation to some substring $T$, you simply find the corresponding set of internal nodes, create an annotation object, and add backpointers to that object from each of those internal nodes.  This can be done in $O(\lg n)$ time.

Similarly, to delete or insert into the document, you insert or delete into the balanced binary tree data structure.  You can quickly identify which annotations this affects, by looking at the range of leaves affected, finding a list of $\le lg n$ internal nodes whose disjoint union is exactly that range, and following the backpointers in those nodes and all of their descendants.  Then you can update those annotation objects if needed.  Insertion and deletion doesn't disturb any of the annotations on the rest of the document, so there is no need to update any coordinate system.

What if you want to do random-access into the middle of document, i.e., given an index $i$, you want to quickly find the $i$th character in the document?  You can augment the data structure to make this efficient, by storing in each node the number of leaves it has under it.  If you insert or delete something somewhere in the document, then you update one or more leaves and all of the nodes on the path from those leaves to the root.

In this way, all operations can be performed in basically $O(\log n)$ time.


Converting truth table to algebraic normal form

The sage source code implies that algebraic normal form is the same as the Fourier expansion of the function (over the group $\mathbb{Z}_2^n$, where $n$ is the number of input bits). You can compute the Fourier transform using the well-known FFT algorithm(s).


When to use SAT vs Constraint Satisfaction?

I think this is a very good question. You could also ask: when to use a SMT solver? I have a feeling it might be hard to determine before modeling the problem and actually running the CSP/SAT/SMT solvers and finding out. It is well known that even different solvers perform very differently on the same instances! My intuition also comes from the fact that there are potentially many ways of modeling a problem. Furthermore, there are many ways of doing search and inference, depending on what type of constraints is used (if the formalism in question allows different types).

Take for example the standard Sudoku puzzle. For the standard $8 \times 8$ puzzle, a modern SAT/CSP solver will solve any such puzzle in an instant. However, I would rather use a CSP solver because it is easier to express my intention. The mentioned puzzle needs $9+9+9=27$ alldiff constraints, and I'm done. There's actually quite a bit of research in the context of CSP solvers trying to solve Sudoku instances of different size. As far as I remember, they don't do any comparisons between SAT, but rather try to determine what kind of inference works the best, or what kind of Sudoku puzzles are hard. I don't know if for say $32 \times 32$ Sudoku puzzles, SAT solvers would be faster than CSP solvers.

Different formalisms are able to capture domain specific information and exploiting it better and in different ways. For a bit more on this, see the answer and the comments here.


There are two possible ways of defining what the length or size of the formula is:

According to the size of a reasonable (and fixed!) binary encoding.
According to the size of a reasonable (and fixed!) encoding over an infinite alphabet which includes symbols for all possible variables.

The definition you mention, for example, is what you get if you apply the second type of definition with respect to the prefix or postfix encoding of a formula.

Note that these two "approaches" don't by themselves defined a concrete measure of size. In cases where it matters, a concrete definition will appear, for example the one you quote. In many cases, however, the exact definition makes no difference since all definitions are "polynomially related", that is, the size of a formula varies at most polynomially between the different definitions. Your quote, for example, cares only about the size of the formulas being polynomial, and so an exact definition isn't important.

In other places, however, it is mentioned that some formula has size $O(n)$. Here the exact encoding still doesn't matter, but there is a real difference between the two options mentioned above. Consider for example the formula $x_1 \lor \cdots \lor x_n$. Under the second option, such a formula has size $\Theta(n)$. However, any reasonable binary encoding of this formula will have size $\Theta(n\log n)$, since storing the indices also takes space. From the author's statement it follows that he uses a definition of the second kind.


Build max heap in which all the nodes at certain level are less than all the nodes at the level before them

Here's a simple way to approach it. Let's assume the array has $n = 2^k - 1$ distinct elements for convenience.

Find the median in $O(n)$ using quickselect.
Partition into two halves (greater and lesser-equal).
Insert the lesser-equal half all as leaf nodes (deepest empty nodes).
Repeat 1-3 on the greater half until you only have 1 value left which will be the max value.

Time complexity is: $$T(n) = T\left(\frac{n}{2}\right) + \Theta(n)$$
Which overall is linear $O(n)$ time complexity.


The running time of algorithm is at most $O(n^2)$

The two phrases

The running time is $O(n^2)$

and

The running time is at most $O(n^2)$

mean the same thing.
This is similar to the following two equivalent claims:

$x = y$ for some $y \leq z$.
$x \leq y$ for some $y \leq z$.

Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".


If we want to represent 8 base 10 then it will be represented as follows:

A) 7421 code
   8(10)= 7+1 = 8
   1 0 0 1 -> 7 4 2 1 code
   1x7+4x0+2x0+1x1=7+0+0+1=8
   8(10)=1001(7421)

B) 5421 code
   8(10)= 5+2+1
   therefore   5 4 2 1
               1 0 1 1
  8(10)= 1011(5421)

C) 4221 code
   8(10)= 4+2+2
   therefore 4 2 2 1
             1 1 1 0
   8(10)= 1110(4221)

There you go. If this is helpful then please select this as an answer.


Best algorithm for correlation between time series?

You haven't given us much information about your problem, so let me give you some hints about how to approach this.

First, look for a model.  Ask yourself: Do you have a plausible biological/physical model for how the dependent variables might depend on the independent variables?  Why do you think it's plausible that the independent variables might help in predicting the dependent variables?  This may help you select an appropriate machine learning tool.

If you don't have a model and don't have any physical/biological reason to expect a causal relationship, then you're doing data mining (and maybe you should reconsider why you are doing this project, or maybe you need to study the underlying application domain better to try to investigate candidate explanations why there might be a causal connection between the two).

Second, classify the data you have.  The right algorithm will depend on what data is in the time series.  Ask yourself: What is the value at each point in time, for the dependent variables and the independent variables?  For each, decide whether you have ordinal data, categorical data, or interval data -- that will play a huge role in narrowing down which machine learning algorithm might be applicable.  Also, ask yourself whether you know anything about their distributions.

Third, visualize your data.  Before you start diving into complex machine learning algorithms, do some data visualization.  Try to find as many ways as you can think of to look at your data.  Sometimes when you stare at data in the right way, that suggests hypotheses or relationships that might be relevant.

So, do all of that.  That will help you think more clearly about the problem, and may help you narrow down the scope of machine learning problems.  Once you've done all of that and can answer all of those questions, you might be in a position to ask a better-crafted, more narrowly scoped question.

Last, don't forget to consider some variety of linear regression: for interval data where you hypothesize some kind of linear relationship, it's a natural first thing to try.


Maximizing quantities/length in buckets to match each other

I would solve this problem with an SMT solver like z3. Example in Python:

import z3

buckets = [
    [(2, 4), (2, 4), (4, 4)],
    [(1, 1), (2, 4), (13, 15)],
]

solver = z3.Optimize()

m = z3.Int("m")

for bnr, bucket in enumerate(buckets):
    springs = []
    for b, (lo, hi) in enumerate(bucket):
        include_spring = z3.Bool(f"is{bnr},{b}")
        spring = z3.Real(f"s{bnr},{b}")
        solver.add(lo <= spring)
        solver.add(spring <= hi)
        springs.append(include_spring * spring)

    solver.add(z3.Sum(springs) == m)

solver.maximize(m)
solver.check()

model = solver.model()
print(solver.model())

The constraints are easy to express and SMT solvers are really quite powerful nowadays.


Usually writing an ip address and a number after the : ,it means the number after the : is  the port

In the internal part:
192.168.0.2 is the private ip address of the host its his ip address inside the network,notice that we have 2 types of ip addresses: private ip address-which is the ip address inisde out network and public ip address which is our ip address in the "internet"
so 192.168.0.2 its the private ip address of the host and the 1234 its the port of the client-the host

now the 42.35.12.33 is the ip address of the web page and the page listens to the port 80

In the external part:
we can see the  ip address of the host has changed,why has it changed?because what i said before about private and public ip addresses this-this ip is the external ip which the host was provided(i suggest reading about NAT if you want to understand this part deeper) the port of the host stays 1234


Since physical memory is the RAM where is logical memory stored on the computer?

I'm not sure what you mean by "logical memory"...

Memory is usually composed of physical memory and virtual memory. Physical memory is usually RAM, hard drives, solid-state drives, etc. It's the actual chips and stuff you plug into your computer (hence "physical").

However, it would be impractical if a larger scale OS is trying to run various applications at once and we only use this memory in a sequential manner, right? That's where virtual memory and virtual mapping comes into play. It's a matter of optimization used by the OS to improve performance.

"It" isn't exactly "stored" anywhere.


Why companies that create native mobile apps are forced to make duplicate versions on other platforms?

Duplicate here refers to the functionality only.

Imagine you were making a row boat out of oak, or out of pine... not quite the same thing.

Android and iOS platforms in particular encourage you to program in different languages, Java or Swift, which can be very different for highly complex apps.


What is the relation between countability and recursive enumeration?

If a language is recursively enumerable then it is countable. However, there are languages that are countable but not recursively enumerable. For example, consider the $A_{TM}$, the language of the Halting problem. This language is recursively enumerable while its complement $\Sigma^*-A_{TM}$ is not recursively enumerable, otherwise $A_{TM}$ would be decidable. However, $\Sigma^*-A_{TM}$ is clearly countable since it is a subset of a countable set $\Sigma^*$.

Hence one simple relation between countability and enumeration is that every r.e. set is countable, but the opposite is not always true.


Your approach, for this problem at least, will work, but there are interesting things happening in the background. Simply setting the two terms equal and solving for $m$ will give you
$$
m=\frac{n\log n}{n-\log n}
$$
However, I doubt that you want to substitute this back into the two original expressions and try to find a $g(n)$ so that each of your original expressions is in $O(g(n))$. Let's try something else.

For no particular reason, let's try letting $m=\log n$. Then your two expressions become
$$\begin{align}
n\log n+m\log n&=n\log n+\log^2n \in O(n\log n)\text{, and}\\
n\:m&=n\log n\in O(n\log n)
\end{align}$$
Hooray! If $m=f(n)=\log n$ we get a common upper bound with $g(n)=n\log n$.

Let's do the same thing, now with $m=n$. The two expressions are now
$$\begin{align}
n\log n+m\log n&=n\log n+n\log n \in O(n\log n)\text{, and}\\
n\:m&=n\; n\in O(n^2)
\end{align}$$
Drat. No common upper bound, but by transitivity, we have $n\log n+m\log n\in O(n^2)$ and so again, we find a common upper bound, namely the asymptoticly larger $g(n)=n^2$.

You can do this for all kinds of other $f(n)$, like $f(n)=\log\log n$ and even $f(n)=1$, both of which have common solutions $g(n)=n\log n$. In fact, it seems that we can do this for any $f$ whatsoever.


Turing Machine-Like Formalism for The Actor Model

computer scientists generally are of the consensus that the Church Turing thesis[1] is correct and definitive, ie that Turing machines describe computation, and that more powerful forms do not really exist, and take assertions that some model is "more powerful" than Turing machines with extreme skepticism, even near hostility.[2] neophytes to the field who dont fully understand the concept are prey to near-marketing slogans of some theory as "more powerful" than Turing machines but those claims are rarely made by mainstream/reputable computer scientists.

but as a flip side to this, many models of computation are Turing complete.
therefore in CS there is in practice mostly a tolerant, "live and let live" attitude with many different models of computation proliferating depending on what is most relevant and convenient for the problem studied. most basic programming models are Turing complete with basic structures such as memory, conditionals, and loops, subroutines etcetera. so more reasonable claims are, "model [x] is better suited to study [y] because [z]". the Actor model focuses on message passing, communication, concurrency & some security.

nevertheless there is some mostly philosophical debate in CS about some models being "more powerful".

[1] Church Turing thesis

[2] Interactive models of computing vs Church Turing thesis


Is a PDA's stack size linear bounded in input size?

No. In NPDAs, you can have cycles of $\varepsilon$-transitions that add symbols to the stack. Thus the stack content can be unbounded.

Proving that CFL ⊆ CSL via automata is tough; the trusted route via grammars seems advised.


A reduction attempt ....

Reduction from Hamiltonian path on digraph $G = (V,E)$ with max degree 3 which is NPC [G&J]

ignore the direction of the edges, and using a first depth (undirected) scan from an arbitrary node, divide the edges of $G$ in two sets of distinct (undirected) paths (red and green in the figures);
join the red paths adding extra "linking nodes" (purple nodes in the figure B) and make an undirected red circuit; join  the green paths adding extra "linking nodes" (purple nodes in the figure) and make an undirected green circuit;
transform each original node $b \in V$ of indegree 1 and outdegree 2 (figure C), adding $k$ yellow nodes on the inbound red edge $a\to b$, and adding $k$ yellow nodes on the first outbound red edge $b \to c$; finally add $k$ yellow nodes "towards" the second outbound green edge $b \to d$ using a "wrapped" path around $b$ that touches the outermost yellow nodes of the red edges (figure D).

In the resulting graph all the $3k$ yellow nodes can be traversed by a simple path only in the two ways showed in figure E and figure F, which correspond to the two valid traversals of the original node $b \in V$; informally if an edge towards the extra "linking" purple node is used, $k$ yellow nodes cannot be traversed.

transform each original node of V of indegree 2 and outdegree 1 in a similar way

Picking a large enough $k \gg |V| $, the result graph $G'$ has an simple path of length greater than $3k(|V|-1)$ if and only if the original graph $G$ has an Hamiltonian path (of length $|V|-1$)

The larger picture can be downloaded here


Generalization of Horn clauses in logic programming?

$\lambda$Prolog is a logic programming language based on a much richer logic than Prolog. In particular, the formulas that constitute its language are (higher-order) hereditary Harrop formulas. Horn clauses are a pallid fragment of that. The enabling concept for $\lambda$Prolog is the notion of a uniform proof, and additionally switching to an intuitionistic perspective on the logic. That last paper introduces the notion of an abstract logic programming language based on the notion of uniform proof and shows that classical first-order and higher-order Horn clauses form an abstract logic programming language.

Basically, a uniform proof is one where the rules used can be given an operational interpretation based on goal-directed search. This isn't the actual definition of a uniform proof, but the motivation behind the actual definition. An abstract logic programming language is one where uniform proofs suffice to prove any formula in the language with respect to a given notion notion of provability that is contained by the usual classical one.

Even the class of higher-order hereditary Harrop formulas doesn't allow $P \to Q_1\lor Q_2$ as a program clause. (It is allowable as a goal.) Why not? Obviously, $P, P\to Q_1\lor Q_2 \vdash Q_1\lor Q_2$, that is, if we know $P$ holds, and we know $P \to Q_1 \lor Q_2$ holds, then we can prove $Q_1 \lor Q_2$. However, this proof succeeds without ever specifying which of $Q_1$ or $Q_2$ holds. Indeed, neither $P, P\to Q_1\lor Q_2 \vdash Q_1$ nor $P, P\to Q_1\lor Q_2 \vdash Q_2$ is true. Formally, the proof of $Q_1\lor Q_2$ from $P$ and $P\to Q_1\lor Q_2$ is not a uniform proof. Informally, the operational interpretation we'd like to give to proving $Q_1 \lor Q_2$, is that we search for a proof of $Q_1$ and a proof of $Q_2$, and if either search succeeds we've established $Q_1 \lor Q_2$. Obviously this search approach will fail in the above example since neither $Q_1$ nor $Q_2$ can be individually established.

Finally, why do we need to "retreat" to intuitionistic logic in the hereditary Harrop formula case (we don't for Horn clauses)? This is because $P\lor(P\to Q)$ is a goal in the class of hereditary Harrop formulas, and it's classically true. However, if we again apply our operational interpretation, the search would proceed as follows: First try to prove $P$, this fails. Next, try to prove $P\to Q$ which reduces to proving $Q$ given $P$ which fails. $P\lor(P\to Q)$ isn't true intuitionistically since when $Q$ is false, this is just the law of the excluded middle. Of course, it requires a more involved proof (which is in the paper) to show that there isn't a similar failure with respect to intuitionistic logic for the class of higher-order hereditary Harrop formulas.

Since 1991, the notion of an abstract logic programming language has been extended. The most notable extension is the generalization of uniform proofs to focusing proofs, and the idea has been applied primarily in the context of linear logics.  In many ways disjunction and negation are more tractable in linear logic. However, the idea has also been applied to Disjunctive Logic Programming. The idea was (first?) applied in Uniform Proofs and Disjunctive Logic Programming, but it didn't provide any guidance on how to handle quantifier elimination.  That is, the idealized interpreter of an abstract logic programming language assumes you can "magically" guess the term to use in existential quantifier elimination. Normally this is accomplished with unification, but unification interacts with proof search. For example, higher order unification generates extra backtracking and the universal quantifiers in hereditary Harrop formulas lead to eigenvariables. Unification interacts with disjunction as well. The later paper A New Abstract Logic Programming Language and its Quantifier Elimination Method for Disjunctive Logic Programming gives a story not just for the abstract logic programming part of Disjunctive Logic Programming, but also how unification needs to be modified in this context.

To my knowledge, DLV seems to be the only serious implementation of any form of disjunctive logic programming.


A verifier for a language $L$ is an algorithm that accepts as input an instance $x$ of $A$ and a witness $w$, and has the following properties:

The algorithm always halts.
If $x \in A$ then there is a witness $w$ such that the algorithm accepts $\langle x,w \rangle$.
If $x \notin A$ then for all witnesses $w$, the algorithm rejects $\langle x,w \rangle$.

We are often interested in polynomial time verifiers. Such a verifier exists for the clique problem, which is: given a graph $G$ and a parameter $k$, decide whether $G$ contains a $k$-clique. Here is one polynomial time verifier for this problem: it accepts as witness a list $S$ of vertices, and on input $G,k,S$ it accepts if $S$ is a set of $k$ vertices which form a clique in $G$. I'll let you check that this satisfies all the required properties.


Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open?

The way to tell if it is open is to read more recent papers to see if any of them make progress.  If not, it's still open.  The way to find more recent papers is to look up that paper on Google Scholar and look through all the papers that site it.  If someone has made progress, it's likely they'll cite that paper.

In general, don't expect to necessarily find a paper somewhere that says "it's still open".  People aren't necessarily going to bother repeating "yup, still open" every year.


improving java 8's implement to hash map using avl tree

This page on Oracle's website says:

  The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins containing a large number of colliding keys improve performance by storing their entries in a balanced tree instead of a linked list. This JDK 8 change applies only to HashMap, LinkedHashMap, and ConcurrentHashMap.

"Balanced tree" typically means either an AVL tree or a red-black tree. I would expect red-black tree, since TreeMap is already implemented as a red-black tree, and this Stack Overflow answer agrees. In that case, using an AVL tree wouldn't change much because AVL trees and red-black trees have basically the same complexity characteristics: search, insertion, and deletion are all worst case $O(\log n)$.

If the worst case for lookup in Java 8 HashMaps is $O(n)$, I'm not seeing how it could be the tree's fault. The motive behind this change is that HashMap buckets normally use linked lists, but linked lists are worst case $O(n)$ for lookup. Ordinary binary search trees have pathological cases where they become $O(n)$, but red black trees are specifically designed to prevent these cases. In a HashMap with linked lists, if you have a really really awful hash function, you could end up with all the items hashing to the same bucket and get $O(n)$ lookup, but it seems like with this red-black tree scheme, even if all the items hashed into the same bucket, you should get $O(\log n)$ lookup.


LR(0) parsing: how can I know sets of items corresponding to states?

An item is a rule with dot marker in it.  Think of the dot marker as what you've seen so far and what you are hoping to see in the future.  Itemsets are sets of items.  In the diagram above they are the boxes with all the items (nodes in the graph).  The kernel (or core) of an itemset are the rules that are in white.  Those items are given to us (rule 1) in CLOSURE from a different part of the table building algorithm.  Taking closure of all the kernel items gives you the full itemset and includes non-kernel items (the darker ones in your diagram). The CLOSURE(I) operation is this expansion algorithm.

Take I7 for example.  We start with only one kernel item.

T -> T * . F

Step 2 of CLOSURE is saying that since F is in front of the dot we have to expand it, adding those items to the itemset. Hence, we add items the following items.

F -> . ( E )
F -> . id

This is everything that F can expand to.  So the full itemset is now:

T -> T * . F
F -> . ( E )
F -> . id

We reapply rule (2), but see that the . is not in front of any new non-terminals that we haven't expanded, we are done.  The itemset is now closed.

The other half of the parse table building algorithm generates new itemsets.  This involves moving the dot across each symbol of each item.  For example, moving the dot over the 'F' gives you the itemset with the kernel item below.

T- > T * F .

This is I10 in your diagram.  Note, that edges from I7 to I10 is labeled F (since the dot crossed that symbol).  You'd reapply the same closure algorithm here and loop this process.

See the Wikipedia entry on this for more information.


Is $L = \{a^jb^ia^{j-i}\mid i,j \ge 0\ , j > i\}$ context-free?

You are trying the wrong way. It is context-free.

(added.) The structure of the language (to guide the grammar construction) is better seen by setting $k = j-i$, so $j=k+i$. Then the language becomes $\{ a^ka^ib^ia^k \mid i\ge 0, k>0 \}$.


Why we need EEPROM in this micro-controller

See EEPROM#Related_types on Wikipedia. Your Program Memory is likely flash memory, which you'll flash (i.e. completely erase and rewrite) with your program every time you like to change it.
8KB is smaller than the usual size of blocks for flash memory, so its unlikely that you can erase only a half or a quarter of your Program Memory.

The program itself may store small quantities of information (a few bytes for important data) without erasing itself by using the EEPROM, which can be written to bytewise (or wordwise).

So the EEPROM is like a tiny hard disk and the Program Memory is more like a tiny rewritable CD.


A schedule is not conflict-serializable. Is it serializable?

A schedule is considered serializable if it is equivalent to a serial one. The conflict graph that appears on the answer to item (a) is proof that the schedule is not conflict-serializable, and it is also not view-serializable, because there is still a cycle between $T_1$ and $T_3$, when considering just the history of the data they visualize. That means the schedule cannot be considered serializable at all.

Conflict-serializability is stronger than view-serializability. It is the criterion used for the implementation of most schedulers, and that is why the quiz emphasizes this point.


Perhaps the following helps:

If a tree has diameter 3 then either it is a single vertex, or there are two neighboring vertices $x,y$ such that every other vertex is a neighbor of either $x$ or $y$.

To see why this is true, consider a tree of diameter 3 with more than one vertex. If all vertices have degree 1, then the tree is of that form. Otherwise, let $x$ be a vertex of degree at least 2. If all neighbors of $x$ have degree 1, then you can designate one of them as $y$ and get the above structure. If $x$ has two different neighbors $y,z$ of degree at least 2 then the diameter is at least 4 (a neighbor $y' \neq x$ of $y$ is at distance 4 form a neighbor $z' \neq x$ of $z$), which is impossible. Therefore $x$ has a single neighbor $y$ of degree at least 2. Every vertex is thus either a neighbor of $x$ or a neighbor of $y$.


Sorry, in complete generality this is an undecidable problem. Pick your favorite undecidable problem $P$ and an instance $a$, and write e.g.:
def value(a):
     if P(a):
         1
      else:
         "Hello, world!"

print(41 + value(a))

Under the (conservative!) assumption that all execution paths are possible, you see that the above is badly formed (value returns an integer or a string). That restriction is doable, and not too hard either:   Do a postorder traversal of your AST, recording the possible types of each node. If any node could have conflicting types, flag a (possible) error.


Adding constraints in grammar for Grammatical Evolution

You can enforce that units match by duplicating nonterminals, one per unit.  For instance, instead of var, you can have varA and varB (if A and B are the two types of units); instead of expr, you can have exprA and exprB; with rules like <varA> ::= Close, <varB> ::= Volume, <exprA> ::= ...|<exprA><matbi><exprA>|...|varA, <exprB> ::= ...|<exprB><matbi><exprB>|...|varB, and so on.

There's no good way to modify the grammar to ensure that it cannot generate any expression that would evaluate to 0.  That is best handled by other methods, not by changing the grammar.


Parsing CFLs (simulating PDA vs CYK algorithm)

Wikipedia mentions that the class of deterministic context-free languages can be parsed in linear time, using an LR parser. In contrast, the fastest algorithm for parsing general context-free languages, Valiant's modification of the CYK algorithm, runs in time $O(n^\omega)$ (where $\omega$ is the matrix multiplication constant), and there is evidence due to Lee that any practical implementation of Valiant's algorithm will run in time proportional to $n^{2.43}$ at best (substitute $\epsilon = 3-2.81$ in Lee's paper; here $2.81$ is the exponent of Strassen's algorithm), and in time proportional to $n^3$ for most values of $n$ occurring in practice.

Context-free grammars used in practice tend to be deterministic, precisely because DCFLs can be parsed faster than CFLs. Indeed, even more restricted variants are commonly used (LALR languages) for reasons of efficiency.


I tried it on square grayscale images myself (just hoping they would be invertible, which was always the case (not much luck involved here, since invertible matrices lie dense)). I added a few examples so you can judge the inverses yourself. Their precise look of course depends on the particular normalization (I used cv2.normalize and also normalized manually by

as done here (I used this to create the LaTeX expression)).

Moreover, I ran this procedure on all test/cat images from CIFAR-10. You can find the results here. Notice that actually a lot of these 32x32 images were (as a matrix) not invertible.
As was asked for by user fiveclubs, here are the normalized inverses of the normalized inverses. They are nowhere near their originals.
Dolphin inverse of inverse:

Painting inverse of inverse:

Tower inverse of inverse:


Regular expressions and 'capturing parentheses' with 'backreferences'

These extended notions of regular expressions capture more than just the regular languages.  For example, ([ab]*)\1 matches the language $\{ww\mid w\in\{a,b\}^*\}$, which isn't regular and isn't even context-free (Example 2.38 of Sipser, Introduction to the Theory of Computation, 3rd edition).

"Regular" expressions that don't match regular langauges can't be translated to finite automata, since finite automata match only the regular languages. A side-effect of this is that many libraries don't even try to compile to automata, which can lead to extremely slow matching, even when a "regular" expression is a true regular expression. Russ Cox wrote an excellent article about this, which goes into a lot of the history, too.


Some points about type checking of simply typed $\lambda$-calculus?

Your example is poorly chosen. In $(\lambda x : \mathsf{bool} . x) \, \mathsf{true}$ you can obviously read off the type from the $\lambda$-abstraction because it tells you that $x$ should have type $\mathsf{bool}$. A more relevant example is
$$
((\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)) \, \mathsf{true} : \mathsf{bool}
$$
Now we are faced with determining $T$ by looking at $(\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)$.

The usual algorithm to be used for this sort of thing is bidirectional typechecking: some terms have their types checked but others have their types inferred. No unification is required, because all types are inferred immediately. (Unification happens when we postpone decisions until a later time.)


Build a boolean classifier that classifies a message as either "task" or "not a task".  Choose a classifier that can output a confidence score (many classifiers can, including ensembles like random forests; neural networks and deep learning; logistic regression; and more).

Train the classifier on many messages.

For a collection of 3 messages, apply the classifier to each message and get the confidence score.  Then, use the confidence scores to rank the 3 messages: e.g., choose the message that has the highest confidence/probability of being "task" as the one that is most likely to be the task.

This is different from what you had in mind: here each instance is a message, not a conversation.

Which features to use is a separate question, but you'll probably want to use standard NLP features (bag of words, word2vec, and so on).  That belongs in a separate question.  As a warning, if each message is very short as indicated in your example, the performance of your classifier might not be great.

Also, you will need a large collection of messages where you know the label (classification) of each.


In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked.

According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-Completeness and Enumeration of Number Link Puzzle, IEICE technical report. Theoretical foundations of Computing 109 (465): 1–7

I did not check the fine print.

Added. Following a comment from domotorp, Numberlink usually has an additional constraint. Indeed, quoting from Adcock etal:

  Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class.

Adcock et al. Zig-Zag Numberlink is NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi:10.2197/ipsjjip.23.239


Weaknesses arising from using same key in both channel directions

Suppose that the keys used in both directions are the same. You listen to something sent from A to B:

kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

You then listen to something sent from B to A:

jh35i798fdgkjh53jkh87gfhkjsfhtjk35h1o8798ug

Does it matter that the key is the same? Can you understand any of the messages?

If the answer to these questions is negative, then eavesdropping can be ruled out.

In contrast, suppose that you sent the following message from B to A:

kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

You don't necessarily have any idea what this means, but it is identical to a message sent from A to B.

Because the key is the same, whatever meaning the original message had, so does this one.

This kind of attack (which is easy to thwart even if the keys are the same) is known as replay.


I think instead of performing merge at the beginning. We can add a node which has the similar edges as the two merged vertices.

Having the following DAG.

If we want to merge node A and B. We add a new node which has the similar attributes as A + B.

Then trasverse  from new node AB (should be Depth-first):

If it find Node A or B, then the merge should be cancelled because it creates a cycle. simply delete Node AB.
If we do not se Node A or B, the merge is valid so delete node A and node B.


Hint: Use the technique of dovetailing, mentioned in several of the comments. The idea is to maintain a growing list of simulated Turing machines, all of them copies $T_1,T_2,\ldots$ of the input Turing machine $T$, operating as follows:

Initialize $T_1$ with the $1$st possible input, and run $T_1$ for one step.
Initialize $T_2$ with the $2$nd possible input, and run $T_1$ and $T_2$ for one step each.
Initialize $T_3$ with the $3$rd possible input, and run $T_1,T_2,T_3$ for one step each.
And so on.

You get the idea. It is perhaps not obvious how to maintain the states of several Turing machines at once, but you can figure it out on your own.


Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas

The words "exceptional" and "typical" have absolutely no formal meaning. Let's rephrase the definition using two other words, "Clinton" and "Bush".

We say that a (possibly randomized) algorithm $A$ $\epsilon$-refutes random 3CNF with ratio $\Delta$ if:

Given a 3CNF formula $\varphi$ with $n$ variables and $\Delta n$ clauses such that a $1-\epsilon$ fraction of the clauses (at least) is satisfiable, the probability that $A(\varphi)$ outputs "Clinton" is at least 75%.
With high probability, $A(\varphi)$ outputs "Bush" given a random 3CNF formula with $n$ variables and $\Delta n$ clauses.

What does the algorithm $A$ try to do? It tries to identify "Clinton" inputs, which are inputs that are at least $1-\epsilon$ satisfiable. At the same time, on a random input, which is with high probability not "Clinton", it should return "Bush". So it tries to separate the rare "Clinton" inputs from a random input.


Let G = (V, E) be a weighted DAG, s and t be two vertices of G, and LSTMC = (G, s, t) be an instance of the logical s-t min-cut problem. It is obvious that the LSTMC problem is NP.Now, we should show that the LSTMC is NP-Hard. We reduce the hitting-set problem to the LSTMC problem. Let S = {s1, s2, ..., sn} be the given sets and {a1, a2, ..., am} be the union of all the sets. Given the number k1, the decision problem of the hitting set problem states whether there exists a set A with k1 elements such that every element of S (every set si s.t. i = 1..n) contains at least one element of A. We denote the hitting set problem as HS(S). We construct the weighted DAG G′ from the set S by Algorithm HS2LSTMC. This algorithm considers s as the source vertex of the DAG G′. For each set si of HS s.t. i = 1..n, the algorithm considers the corresponding vertex, si, and adds an edge with infinite weight from s to each si. Then, for each element aj of the union of the input sets s.t. j = 1..m, the algorithm considers the corresponding vertex, aj, and adds an edge with zero weight from each si to any aj s.t. aj ∈si in HS. Finally, the algorithm considers two final vertices called t and k, and add two edges from each aj s.t. j = 1..m to the both final vertices. It is clear that G′ can be made in polynomial time.

Now, we should demonstrate that HS(S) has an answer with k1 elements if and only if LSTMC = (G′, s, t) has an answer with some logically removed edges such that the sum of the weights of the removed edges is k1.

For simplicity, we perform this part of proof, by providing an example:

In the following figure, suppose that S = {s1, s2, s3} such that s1 = {1, 2, 3}, s2 = {1, 4}, and s3 = {2, 5}. Fig. 2 shows the weighted DAG G′ of the LSTMC problem corresponding to the hitting set problem HS(S). In this example, the set A, namely the union of all elements of S, is A = {1, 2, 3, 4, 5}. We have |S| = 3 and |A| = 5. This example shows how an arbitrary instance of the hitting set problem can be solved by the help of a specific instance of the logical s-t min-cut problem in a weighted DAG. If we compute an answer to LSTMC = (G′, s, t) and consider those removed edges of the answer which are in the form of (aj, t) called E1 (1 ≤ j ≤ m), then the tail set of E1 is an answer to HS(S). An answer to the LSTMC problem is the edge set E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. So, the tail set of the subset E2 = {(1, t), (2, t)} of the edge set E1, namely the set {1, 2}, is an answer to the HS(S).


Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

Yes, you can.

We use the master theorem in the context of giving upper bounds to increasing functions $T$. In this context, we know that $T(n)=aT(\lfloor n/b\rfloor) + g(n) \leq aT(n/b)+g(n)$ so any upper bound on the recurrence without $\lfloor\cdots\rfloor$ is also an upper bound on the recurrence with $\lfloor\cdots\rfloor$.


I am assuming that you have some background in a functional programming language like Haskell or ML or OCaml because that is the easiest thing for me to explain this in terms of.

Haskell is, or can be viewed as, a rewrite system. When you simplify little expressions you are rewriting the expression in little steps until you get to the final result (normal form).

For instance a list like [1, 2, 3] can be denoted by the term (1 : (2 : (3 : [])))

Another term is a term like

(1 : (2 : [])) ++ (3 : [])

which can be reritten as

1 : ((2 : []) ++ (3 : []))

which can in tern be rewritten as

1 : (2 : ([] ++ (3 : [])))

which can (finally) be rewritten as

(1 : (2 : (3 : [])))

This was all based on the following rewrite rules

(x:xs) ++ ys -> x : (xs ++ ys)
[]     ++ ys -> ys

where x -> y can be thought of as "if you see 'x' replace it with 'y'"

So basically a rewrite system is a system that has a set of rules that explain how to rewrite certain subterms of a term in a system. Once there are no rules left that apply the term is in normal form. Some times terms have no normal form however, these are either errors or infinite loops in systems like Haskell.

example:

addLots x -> 1 + addLots x

addLots 0 (this expression has no normal form as we just have to keep adding 1s on)

Haskell also gives us some guarantees on the order that it will apply the rewrite rules (but does not fully define it). For instance

case 1 : (addLots 0) of {x : xs -> 2}

will evaluate to 2. If the order was either unspecified or chose to fully evaluate 1 : (addLots 0) then it would have not ever reached it's normal form.

A rewrite system does not in general have to have such an order however; it just has to say which rewrites are valid. Another example of a rewrite system is first order logic. You are given a set of rewrite rules called "inference rules" and a set of terms called "first order logic terms". You can derive tons of expressions from other expressions in just such a way. Like the following two rewrite rules.

~~x -> x
x -> ~~x

we could keep gong back and forth between these and we would get an infinite loop but a human knows how to apply these in just the write way to derive interesting theorems.

edit:
It seems to me (from a brief look) that the K semantic framework is a system for defining what terms on in the language (quite like data expressions in Haskell but more advanced) and then it lets you define rewrite rules on these expressions (a bit like functions in Haskell). In the K semantic framework syntax and rules are totally separated where as in Haskell data expressions define the syntax of normal forms and function definitions define a new bit of syntax along with a reduction rule on that new syntax.


Isomorphism of finite dimensional polynomial algebras over finite fields

As you mentioned, you can factor $f_1$ and $f_2$ in polynomial time.  Consider the multiset $D_1$ of degrees of the factors of $f_1$, and the multiset $D_2$ of degrees of the factors of $f_2$.  If $D_1 \ne D_2$, they are not isomorphic.  If $D_1 = D_2$, they are isomorphic.  That takes care of determining whether they are isomorphic.

Computing an isomorphism explicitly is harder.  Let me focus first on the case where $f_1,f_2$ are squarefree, for ease of exposition.  Note that if $f = g_1 \times \cdots \times g_m$, then we have a sort of Chinese remainder theorem:

$$\mathbb{F}_q[x]/\langle f\rangle \cong \mathbb{F}_q[x]/\langle g_1 \rangle \times \dots \times \mathbb{F}_q[x]/\langle g_m \rangle.$$

Consequently, by matching factors of same degree, you can reduce the problem to the case where $f_1,f_2$ are irreducible and $\deg f_1 = \deg f_2$ (in the squarefree case).  Then both fields are isomorphic to $\mathbb{F}_{q^n}$, where $n= \deg f_1$.

Finding an isomorphism explicitly (if $f_1 \ne f_2$ and $\deg f_1 = \deg f_2$) looks related to the discrete log problem over $\mathbb{F}_{q^n}$.  The discrete log problem is believed to be hard in general: the fastest algorithms currently known have a subexponential running time, and it is conjectured that there is no polynomial-time algorithm.  In particular, it looks related to the Diffie-Hellman problem, and in most fields the Diffie-Hellman problem is probably as hard as the discrete log problem.  I don't know of a reduction from discrete log or Diffie-Hellman to prove that finding an isomorphism is as hard as those problems, but I suspect there might be some relationship.

I do know that if you can compute the discrete log efficiently in $\mathbb{F}_{q^n}$, then you can exhibit an explicit isomorphism: pick a generator $g$ for the first field, and a generator $h$ for the second field; the isomorphism sends $g \mapsto g'$, and sends $g^k \mapsto h^k$, so given $x$, we compute the discrete log $k$ of $x$ to base $g$, then $x$ maps to $h^k$.

There's lots written about the discrete log problem in such finite fields.  For the case where $q$ is small and $n$ is large, see for example https://crypto.stackexchange.com/q/228/351 and https://crypto.stackexchange.com/q/22332/351.

What about when $f_1,f_2$ are not squarefree?  Then I think the problem is at least as hard.  We can reduce to the case where $f_1 = p_1^e$ and $f_2 = p_2^e$, where $p_1,p_2$ are irreducible and $\deg p_1 = \deg p_2$.  Then I think it might be possible to use Hensel lifting, though I haven't thought through the details.  In particular, here is what happens with the discrete log.  Consider the case where $e=2$.  Let $g=a_1 p_1 + b_1$ be a generator of $\mathbb{F}_q[x]/\langle p_1^2 \rangle$.  Note that

$$g^k = (a_1 p_1 + b_1)^k = k a_1 p_1 + b_1^k.$$

Therefore, to compute the discrete log of $x = a_2 p_1 + b_2$, it suffices to first find $k_0$ such that $b_1^{k_0} = b_2 \pmod{p_1}$ (which is the squarefree case of the discrete log considered above), then find $k$ such that $k \equiv k_0 \pmod{q^n-1}$ and $k \equiv a_2/a_1 \pmod{q^n}$, where $n = \deg p_1$.  Such a $k$ can be found through the Chinese remainder theorem; you end up with $k = k_0 q^n - (a_2/a_1) (q^n-1)$.  This shows how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1^2 \rangle$ if you know how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1 \rangle$.
I think the same will apply to any $e>1$, not just $e=2$.


minimizing the summed cardinality of set unions

Your problem is NP-complete. We show this by reducing Partition to it.

In Partition you are given a set of numbers $a_1, \ldots, a_k$ and have to decide, if this set can be partitioned into two sets that sum up to the same value.

We map an instance of Partition to your problem by introducing for each $a_i$ the set $(i, a_i, \{1\})$. Set the maximum size to $\frac 12\sum_{i=1}^ka_i$. The original instance can be partitioned if and only if the resulting one can be united to cardinality sum 2.


Can Shortest Job First Scheduling be subject to convoy effect?

I think you're not using the same terminology as the books and articles you're reading.  Non-preemptive schedulers suffer from priority inversion, not convoy effects.

Most scheduling disciplines (FIFO, SJF, LJF, Nearest-deadline-first, ...) can be reframed as highest priority first schedulers, where what changes from discipline to discipline is the priorities assigned to the jobs.  So first-in-first-out (FIFO) scheduling assigns priorities according to their order of arrival.  Shortest-job-first (SJF) assigns priorities according to the burst time.  In preemptive shortest-job-first the scheduler is always running the job with the highest priority.  In non-preemptive shortest-job-first scheduling if a short job arrives after a longer job already starts, then the scheduler will be running the lower priority job instead of the high priority job for a while.

A convoy effect is a different problem where jobs that need many different kinds of service get clumped up together because of decisions you have made elsewhere in the system.  It applies to things like schedulers that deal with jobs that have more than one burst (separated by time when those jobs are waiting for i/o, or when jobs are waiting for a lock).  For the lock case there's a wikipedia article: http://en.wikipedia.org/wiki/Lock_convoy.


Questions on the definition of polynomial time

You seem to be struggling with a lot of the fundamental concepts, here. All the NP-completeness stuff is cool and fascinating and I can absolutely see why you're attracted to it. But you really aren't going to get anywhere with this stuff until you have a good grasp of the basics. If you want to work on NP-completeness, you need first to get a good book on basic discrete mathematics and you need to study it until you understand it. I know that's kind of dull but there is no other way. There might be a question here already about recommendations for discrete maths books.

This is a technical, precise subject where every little part of every little sentence has some special meaning. It's not like, say, the rules of some sport that you can pick up more or less just by watching people play.  Yes, you can get a general, intuitive understanding of why, say, an NP-complete problem seems to be very hard to solve, in just the same way that you can get a general, intuitive understanding of how quantum tunnelling allows radioactive decay to happen.  But, if you want to discover new things about it, you need to understand the underlying mathematics.  There is no other way.

If all you want to do is talk about the running time of algorithms, you don't need to worry about polynomial expressions; just about polynomials. Polynomial expressions are generalizations of polynomials to be functions of things other than numbers.  Over numbers (integers, reals, complex, anything else), the polynomials are the functions of the form
$$f(x) = a_kx^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0\,,$$
where $k$ is an integer constant and the $a_{i}$ are constants of the same kind of number as $x$ will be.

1. Why do we have addition and multiplication but not division?The unhelpful answer is "Because that's the definition," just like CNF is defined using AND and OR rather than, say, XOR and NOR. The reason for forbidding division is that you might want to have a polynomial in a situation where division doesn't make sense (e.g., if you're working mod 2, or $x$ is an integer and you want to guarantee that $f(x)$ is also an integer). The kind of function you can make by dividing one polynomial by another is called a rational function and these are also widely studied and very useful in many situations. Why don't we use rational functions instead of polynomials in complexity theory? It's mostly because we don't need that level of detail: we already say that $4x^3 + 2x + 1$ is basically just some constant times $x^3$ so we wouldn't gain anything by bringing division to the party.

2. Why do we have both multiplication and addition, couldn't we express one with the other?Because there's no way to express all the multiplications in a polynomial as repeated addition, while still keeping the form of a polynomial. Sure, you could write $3x$ as $x+x+x$ but that would be hard to read and wouldn't gain anything. But there's no way to write $x^2$ using a fixed number of additions: there's nothing in the definition of a polynomial that lets you write
$$\underbrace{x + \dots + x}_{x \text{ times}}\,.$$

3. What is the difference between polynomial time and exponential time by definition?An exponential function is one of the form $k^x$ for some constant $k$. Note that this is different to a polynomial: polynomials are "variable-to-the-constant" and exponentials are "constant-to-the-variable". Exponentials grow much faster than polynomials. For example, see this plot. As G. Bach points out in his comment, if you're defining complexity classes around exponential functions, you need to take $k>1$.


Is non-determinism in a non-deterministic turing machine different from that of finite automata and push down automata?

Non-determinism is the same concept in all contexts – the machine is allowed several options to proceed at any given point. However, the semantics are a bit different since DFAs/NFAs and PDAs always define total functions, while Turing machines (deterministic or non-deterministic) in general define partial functions.

A partial function is one defined only on part of the domain. If $f$ is not defined on $x$ then we write $f(x) = \bot$. (So $f$ is really a total function, but there is a special element in the range signifying that the output is undefined.) A deterministic Turing machine $M$ defines a partial function as follows: if $M$ halts on $x$ then $M(x)$ is the contents of the tape when $M$ halts on $x$; and otherwise, $M(x) = \bot$.

A deterministic Turing machine decider has two kinds of halting states, accepting and rejecting, and defines a partial function as follows: if $M$ halts on $x$ at an accepting state, then $M(x)=1$; if it halts at a rejecting state, then $M(x)=0$; if it doesn't halt, then $M(x)=\bot$. If $M$ always halts then we say that it accepts the language $L = \{x : M(x) = 1\}$.

A non-deterministic Turing machine (which is always a decider) is allowed to "branch" (have several possible options at any given point in time), and has the following semantics:

$M(x) = 1$ if on input $x$, the machine $M$ halts on all branches, halting at an accepting state for at least one branch.
$M(x) = 0$ if on input $x$, the machine $M$ halts on all branches, always halting at a rejecting state.
$M(x) = \bot$ if on input $x$ there exists a branch on which $M$ doesn't halt.

Given this definition, it is hopefully clear how to simulate a non-deterministic Turing machine using a deterministic Turing machine decider: you try all branches, checking whether any of them leads to an accepting halting state. After all branches have halted, you can decide whether to go to an accepting state or to a rejecting state. If the non-deterministic Turing machine doesn't halt on some branch, then so would the deterministic one.

What about $\epsilon$-moves? They cause trouble in that the corresponding automaton might never halt. For finite automata (NFAs and PDAs) we silently ignore non-halting computations. Our reason for doing that is that the resulting languages are always computable, even though the naive algorithm for simulating them deterministically (simulating all computation paths) doesn't quite work. This is not so difficult for NFAs, which can be converted to DFAs. However, deterministic PDAs are strictly weaker than non-deterministic PDAs. Nevertheless, you can show that every PDA is equivalent to one without $\epsilon$-transitions (though the proof might go through context-free grammars).

You can simulate $\epsilon$-moves in Turing machines, but you have to be careful that there are no loops which cause non-halting computations. In some cases, however, we can use the same trick as above. For example, suppose that your Turing machine is space-constrained: we know an upper bound on the space that it uses (depending on the input length). In that case every non-halting computation necessarily cycles (since the Turing machine has finitely many states, including the tape contents), and so if we "ignore" non-halting computations as above, the resulting model of computation is still computable. More generally, this works as long as we are guaranteed that every non-halting computation cycles. (This is the case for NFAs but not for PDAs.)


Is this a generic way to convert any recursive procedure to tail-recursion?

Your description of your algorithm is really too vague to evaluate it at this point.  But, here are some things to consider.

CPS

In fact, there is a way to transform any code into a form that uses only tail-calls.  This is the CPS transform.  CPS (Continuation-Passing Style) is a form of expressing code by passing each function a continuation.  A continuation is an abstract notion representing "the rest of a compuation".  In code expressed in CPS form, the natural way to reify a continuation is as a function that accepts a value.  In CPS, instead of a function returning a value, it instead applies the function representing the current continuation to the being "returned" by the function.

For example, consider the following function:

(lambda (a b c d)
  (+ (- a b) (* c d)))

This could be expressed in CPS as follows:

(lambda (k a b c d)
  (- (lambda (v1)
       (* (lambda (v2)
            (+ k v1 v2))
          a b))
     c d))

It's ugly, and often slow, but it does have certain advantages:

The transform can be completely automated.  So there's no need to write (or see) the code in CPS form.
Combined with thunking and trampolining, it can be used to provide tail-call optimization in languages that do not provide tail-call optimization.  (Tail-call optimization of directly tail-recursive functions can be accomplished via other means, such as converting the recursive call into a loop.  But indirect recursion is not as trivial to convert in this manner.)
With CPS, continuations become a first-class objects.  Since continuations are the essence of control, this enables virtually any control operator to be implemented as a library without requiring any special support from the language.  For example, goto, exceptions, and cooperative threading can all be modeled using continuations.

TCO

It seems to me that the only reason to be concerned with tail-recursion (or tail-calls in general) is for the purposes of tail-call optimization (TCO).  So I think a better question to ask is "does my transform yield code that is tail-call optimizable?".

If we once again consider CPS, one of its characteristics is that code expressed in CPS consists solely of tail-calls.  Since everything's a tail-call, we don't need to save a return-point to the stack.  So all code in CPS form must be tail-call optimized, right?

Well, not quite.  You see, while it might appear that we have eliminated the stack, all we have done is merely change the way we represent it.  The stack is now part of the closure representing a continuation.  So CPS doesn't magically make all our code tail-call optimized.

So if CPS can't make everything TCO, is there a transform specifically for direct recursion that can?  No, not in general.  Some recursions are linear, but some are not.  Non-linear (e.g., tree) recursions simply must maintain a variable amount of state somewhere.


Optimal covering of 2D matrix elements given spatial constraints

Yes, this can be expressed as an instance of integer linear programming and then solved with an ILP solver.  I don't know if there's a better way (for instance, I don't know if the problem is NP-complete).

We'll define zero-or-one variables $x_{i,j}$ and $y_{i,j}$, with the intention that $x_{i,j}=1$ means that cell $(i,j)$ of the matrix is marked and $y_{i,j}=1$ means that cell $(i,j)$ is covered.  Let $A$ denote the matrix.  Then we have constraints to ensure that all 1's in the matrix are covered: $y_{i,j} \ge 1$ for all $i,j$ such that $A_{i,j} = 1$.  Also, we have constraints to ensure that the $x$'s and $y$'s are related appropriately:

$$y_{i,j} \ge x_{i,j} \qquad y_{i,j} \ge x_{i-1,j} \qquad y_{i,j} \ge x_{i+1,j}$$

$$y_{i,j} \le x_{i-1,j} + x_{i,j} + x_{i+1,j}$$

To impose the requirement that at most $N/2$ cells are marked in each row, add the constraints

$$\sum_j x_{i,j} \le N/2.$$

Finally, notice that $y_{i,j}-x_{i,j}$  is $1$ if cell $(i,j)$ is covered but not marked, and $0$ otherwise.  Therefore, the objective function is:

$$\sum_{i,j} y_{i,j}-x_{i,j}$$

Now feed this to an ILP solver, and let it do what it can to try to solve it.


I'd suggest using integer linear programming (ILP).  You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy.  ILP can express constraints (requirements that must be true).  The main limitation is that the objective function you are trying to minimize must be a linear function of the variables, but that can often be accomodated with auxiliary variables.  For instance, your rules about the fees for buying different stocks can be expressed with ILP.

You'll have to figure out how you want to quantify and formalize "allocation that is approximately close to the model", as currently that is rather vague.  Also note that anytime you say you have two goals, you aren't ready to formulate this as an optimization problem, because that leaves open how you plan to trade off the goals.  You need to identify a single objective function you want to minimize, which means you'll need to think how you want to combine fee minimization with approximate model allocation.  We can't tell you how to do that as that is a matter of what you want to achieve.  One way would be to sum up the absolute value of the deviations from the model, and require this to be no more than a certain maximum.  Another way would be to sum up the absolute value of the deviations, and add that to the objective function as an extra penalty.


Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction

It looks like you are trying to prove either that 2CNF-SAT is NP-Complete, or that 3CNF-SAT has a polynomial algorithm, by reducing 2SAT to 3SAT. But that's not how it goes! If you're trying to do what I think you're trying to do, then you should reduce 3SAT to 2SAT. Unfortunately, if you can reduce 3SAT to 2SAT, then that would imply P=NP, so that's probably very hard.

It's very easy to get confused about which way a reduction should go, and how you should make one. Please read my answer to this related question: Implications of Halting Problem being undecidable, in particular the 'cheat sheet' section, where I try to clear up some confusion around the topic, and let me know if you have questions after reading that, then I might edit this answer tailored specifically to whatever question you have afterwards.


What happens after the accept state if there are still letters in the string in a Turing machine?

In the nominal TM definition, the machine is a 7-tuple, $M=(Q,\Sigma,\Gamma,b,\delta,q_0,F)$, where $F$ denotes a set of final states. Wheneven the TM transitions to a state in $F$ it immediately halts, no matter what it did or didn't do beforehand.

From the way you wrote your TM, I believe you meant that your final states are $F=\{q_{accept},q_{reject}\}$, thus once one of them is reached, the TM halts.

Once the above is clear, there is the question of "what happens if the input string isn't fully consumed". Well, this question is a bit misleading, since it implies that the TM consumes the input string symbol-by-symbol (like a DFA or PDA), which is not the case for the nominal TM.

In a Turing machine, the input string appears on the tape at the start of the computation. It is fully there, and needs not be "consumed". Besides of the input string, the tape is empty, i.e., it contains the blank $b$ symbol (where $b\in \Gamma \setminus \Sigma$, so the input cannot contain blanks). Since the input is already there on the tape, there is no question of "consuming" it. The alternative question is reading the input - it is perfectly fine if the TM moves to a final state ($q\in F$) before "reading" the entire input, i.e, when the head of the TM never visits all the tape slots in which the input resides. Again, this is perfectly allowed.

A Note: Sometimes the input is given on a separate tape (which is usually, a read-only tape). This helps to count the memory actually used for processing the computation without counting the space used to hold the input. Such machines are especially relevant for computations that take sub-linear space. Yet again, the machine is allowed to terminate without reading the entire input.


Koenig and Moe's Accelerated C++ and Stroustrup's Programming: Principles and Practice Using C++ are using std::string and other components from the standard library from the start. If I remember correctly, they don't even present C arrays for Koenig and Moe and Stroustrup does it quite late in the book (perhaps even just in an annex).

That approach, qualified as modern, is the preferred one in my circles.  The other approach, often qualified as historic, follows more closely how C++ evolved, but doesn't take advantage of "newer" (relatively, they are 15 years old now) development and doesn't teach what is practised now (at least on projects not encumbered with too much legacy) but 10 years ago (there is always a lag before being mainstream).


First of all, what are we trying to prove here in other words? That
  the language L cannot be represented by a FSM, therefore cannot be
  considered "regular" because a regular language is only regular if it
  can be represented by a FSM?

Indeed. Although there are varying definitions for regularity (e.g., you may define the regular languages based on regular expressions), they are all equivalent. Hence, you only need to prove your language fails to satisfy one of the equivalent requirements to be regular. In the case of the pumping lemma, you argue on the basis of DFAs.

  Second, how am I supposed to find "n" which is the number of states in
  A? Is this also known as the pumping length?

You are not supposed to find anything. In the classical variant of the pumping lemma, the number of states only appears explicitly in its proof. In the statement itself, there is only mention that such a number $n \in \mathbb{N}_0$ exists.

  What is the proper way in which we are supposed to break up the string
  chosen string w >= n into 3 parts (xyz)?

The pumping lemma specifies what conditions should hold for $x$, $y$, and $z$. There are three of them. And, as $n$, when proving a language contradicts the lemma (to show it is not regular), you don't get to choose $xyz$; rather, you have to show your claim no matter what $x,y,z$ are (as long as they suffice the conditions from the lemma).

In your example, the word has prefix $a^n$, while one of the pumping lemma's requirements is $|xy| \le n$. Hence, there is no other option for $xy$ except for it to be a prefix of $a^n$, which is why you can extend this prefix to $a^{n + m|y|}$ for any $m \in \mathbb{N}_0$. (Remember: $y$ is the part that can be "pumped".)


Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution

As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$.

An input to the knapsack problem consists of a list of $n$ weights, a list of $n$ values and a maximum weight $W$.  Since each weight and each value must take at least one bit to write down, we know that $n<|X|$. But $W$ is written in binary and you can easily produce an instance where, say, $W$ has bit-length $|X|/2$. In such an instance, the running time of $nW$ is about $|X|2^{|X/2|}$, which isn't polynomial.

The key point that you've missed is that $n<|X|$ because, effectively, the input specifies $n$ in unary.  (That is, if the weights are $1,3,2,5,2,2$, then $n$ is basically the number of commas, modulo the usual off-by-one error.)


Exponential or polynomial in what? As stated, it's clearly polynomial in $M$ and $N$.

The complexity of algorithms is given in terms of the length of the input. If an algorithm receives $M$ and $N$ as input, written in binary, then $M+N = O(2^\ell)$, where $\ell$ is the length of the input in bits.

You should ask your professor for clarification. S/he knows what s/he actually said and what the context was; we're just guessing.


You can prove this by a reduction from the Hitting Set problem (which is NP-Complete):

  Given a base set $U$, a family $F = \{S_1,\ldots,S_\ell\}$ of subsets of $U$ and an integer $q$, decide if there exists a set $H$ of size at most $q$ which intersects every set in $F$ (this is called a hitting set).

So suppose given an instance of the Hitting Set problem. For every element in $u\in U$, create a new TA $T_u$. For every set $S\in F$, create a new class $C_S$ whose TAs correspond to the elements in $S$. Let $k = |U|-q$.

Then if you interpret the TAs being left out of the room as the elements chosen in $H$ it is not hard to see that there exists a hitting set of size at most $q$ if and only if you can put $k$ TAs in the room. That is because putting $k = |U|-q$ TAs in the room is equivalent to leaving at most $q$ outside of the room. And hitting every set in $F$ is equivalent to having at least one TA per class left out of the room.

(I leave the formal proof up to you)


Optimization Problem when calculating fitness is expensive

For starters I assume that you can't guess the impact the values of a solution have on its fitness, otherwise you could relax the fitness function to roughly estimate which solutions are promising, and try to find a good solution from there.

However you do know that similar solutions have a similar fitness, so let's work with that. I would suggest something along these lines:

Construct a function to measure the similarity of two solutions.
Using this function, heuristically group your solutions into 100 clusters.
For each cluster, calculate the fitness of the solution closest to its mean.

This will give you the fitness of the 100 most dissimilar solutions, which is a good sample of your search space (it should give you a good idea of the fitness found in most major peaks). As a bonus, you can recursively do this if you want to improve on the best solution found, i.e., divide the best cluster into k clusters and proceed in the same way.


Check if a relation is reflexive, symmetric and transitive

"If xRy and yRz": Look at the definition of R. You have x = 0 and y ≥ 0 because xRy. You have y = 0 and z ≥ 0 because of yRz. If you have xRy and yRz then you have x = 0 and z ≥ 0, therefore xRz. So R is transitive.
In total you know that x = 0, y = 0 and z ≥ 0, so you also have yRx, although nobody cares much about that.


3-SAT where variables occur equally many times as a positive literal and as a negative literal

It is NP-complete (but I don't know if it has a name): suppose that a variable $x_i$ appears as a positive literal $n$ more times than as a negative literal.

Then you can "balance" it adding $n$ new 3CNF clauses with $n$ new variables $y_1,...,y_n$:

$-x_i \lor y_1 \lor -y_2$
$-x_i \lor y_2 \lor -y_3$
...
$-x_i \lor y_{n-1} \lor -y_n$
$-x_i \lor y_n \lor -y_1$

If $x_i$ appears more times as a negative literal, apply the same expansion but using $x_i$ in the new 3CNF clauses instead of $-x_i$.

The $y_i$ are balanced and the resulting formula (that can be built in polynomial time) is clearly satisfiable if and only if the original 3CNF formula is satisfiable: whatever is the value of $x_i$ the new clauses can be satisfied setting $y_i = true$, so they don't "interfere" with the satisfiability of the original formula.


Following but not intersecting time segments to detect multiple accounts

I would sort all events (logins, logouts) in increasing order by time, then walk through the list.  For each logout event from user $u$ starting at time $t$ encountered during this walk, scan forward from that point until hitting time $t+15$, incrementing a counter for the pair $(\min(u, v), \max(u, v))$ in a hashtable whenever a login event for user $v$ occurs.  (You could alternatively increment two counters, $(u, v)$ and $(v, u)$, but this uses twice the memory and gains nothing.)

Afterwards, every large count in your hashtable corresponds to a "candidate pair" of users.  Walk through the hashtable, and for each counter above a threshold of your choosing, check whether the logged in intervals for this pair of users intersect.  If they don't, flag the pair as likely operated by the same human.

(BTW, I'm not confident that mutually exclusivity of login intervals will apply in practice: Users might run their two accounts simultaneously in different browsers, one in a phone, or one in a private window, etc.  Depending on your application, maybe a better criterion would be to check whether the two users actually interfere with each other to any significant extent -- e.g., for SO, whether the same questions and answers tend to be upvoted/downvoted.)

There will probably be large numbers of pairs in the hashtable with low counts, due simply to chance.  If you find that singleton counts are bloating the hashtable, you could reduce memory usage (at the cost of introducing a very small amount of inaccuracy) by using a Bloom filter to store all "first" encounters of any $(u, v)$ pair, and only creating counts in the main hashtable for a pair $(u, v)$ when $(u, v)$ is already in the Bloom filter.


Finding recurrence when Master Theorem fails

OK, try Akra-Bazzi (even if Raphael thinks it doesn't apply...)
$$
T(n) = 4 T(n / 2) + n^2 / \lg n
$$
We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a_1 = 4$, $b_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h_i(n)$ also check out. So we need:
$$
a_1 b_1^p = 4 \cdot (1 / 2)^p = 1
$$
Thus $p = 2$, and:
$$
T(n)
  = \Theta\left(n^2 \left( 1 + \int_2^n \frac{u^2 du}{u^3 \ln u} \right) \right)
  = \Theta\left(n^2 \left( 1 + \int_2^n \frac{du}{u \ln u} \right) \right)
  = \Theta(n^2 \ln \ln n)
$$
(The integral as given with lower limit 1 diverges, but the lower limit should be the $n_0$ for which the recurrence starts being valid, the difference will usually just be a constant, so using 1 or $n_0$ won't make a difference; check the original paper.)

[I've taken the liberty to add this to the Akra-Bazzi examples in the reference question, thanks!]


Algorithm chalenge: find minimum range to cover all houses with light

This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius
Key Idea: Binary search for the diameter, then use that to find the radius.


Estimation of the number of solutions by Counting

Consider a binomial random variable $X \sim \mathrm{bin}(n,p)$, and let $Y = (X - pn)^2$. A straightforward but long calculation shows that
$$
\frac{\mathbb{E}[Y]^2}{\mathbb{E}[Y^2]} =
\frac{np(1-p)}{p^3 + (1-p)^3 + 3(n-1)p(1-p)} = \frac{1}{3} + o(1).
$$
(This is to be expected, since a binomial random variable has roughly Gaussian distribution, and for Gaussian distributions the ratio is exactly $1/3$.)

Now let $Z = (S - M)^2$. It is still the case that
$$
\frac{\mathbb{E}[Z]^2}{\mathbb{E}[Z^2]} = \frac{1}{3} + o(1),
$$
since $Z$ is just a scalar multiple of $Y$ above, for an appropriate choice of parameters.

In view of applying the Paley–Zygmund inequality, let us estimate
$$
\theta = \frac{M}{\mathbb{E}[Z]} = \frac{M}{M(N-M)/k} = \frac{k}{N-M}.
$$
It follows that
$$
\Pr[|S-M| > \sqrt{M}] = \Pr[Z > M] \geq (1-\theta)^2 \left(\frac{1}{3} + o(1)\right).
$$
If we want the right-hand side to be bounded by some constant (in your case, $1/4$) then we need $\theta$ to be bounded from below by some constant $c$ (in your case, roughly $1-\sqrt{3/4}$). In other words, we need
$$
k = \theta (N-M) = \Omega(N-M).
$$
As long as $M$ is not very close to $N$, this is $\Omega(N)$.

(When $M$ is very close to $N$, less samples are needed. For example, only one sample is needed when $M = N$.)


Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow = min cut, that would indeed be the case (if all capacities are integers).

If you make all min-cuts larger. There may be more than one.

To be clear: if you increase the capacity of all edges in all min-cuts, the max-flow may increase by more than one. At least one (assuming integer capacities), but then yet another cut may be minimal.

If you increase the capacity of each min-cut by one, the max-flow increases by one (again assuming integer capacities).


invite 12 person from 24 that we have 6 men and 6 womens

Say the man invites 2 of his male friends so he has to invite 4 female friends to get to a total of 6. The female fills the gaps - she invites 4 male friends and 2 females. Now the guy has C(5,4) options to invite female friends and C(7,2) for his male friends in this example. The female has C(7,2) for the female part and C(5,4) for the male part.

Now you sum over all variants: