Sample compression scheme and bounding the VC dimension

Suppose that $H$ shatters a set $S$ of size $\ell$, and has a compression scheme of size $k$. For each of the $2^\ell$ labelings of $S$, the compression scheme associates a labeled subset of size $k$, in an injective way. There are $2^k \binom{\ell}{k}$ such labeled subsets, and so $2^\ell \leq 2^k \binom{\ell}{k}$. Using $\binom{\ell}{k} \leq (e\ell/k)^k$, this shows that $2^{\ell-k} \leq (e\ell/k)^k$, and so $2^{\ell/k} \leq 2e\ell/k$, implying $\ell < 5k$.
Here is an example showing that we cannot improve this to $\ell \leq k$. Consider the set of all functions from $[k+1]$ to $\{0,1\}$. We give a compression scheme of size $k$. Given a labelling $(\ell_1,\ldots,\ell_{k+1})$, we remove either $(1,\ell_1)$ or $(2,\ell_2)$ according to the parity of labels. This is injective, since we can reconstruct the missing label from the index of the missing point.


Detect whether one Turing machine invokes another

The notion of "one machine invokes another" is ill-defined. To emphasize the point of @AbdousKamel, let us observe an even trickier example:

function g():
   do_something;

And now:

function f():
   k = 0
   while not "k encodes a proof of Riemann hypothesis":
     k = k + 1
   "simulate the Turing machine encoded by k"

In order to tell whether f "invokes" g, you have to:

Decide whether Riemann hypothesis is provable, and
Calculate whether the smallest k which encodes a proof of Riemann hypothesis also happens to encode a Turing machine whose behavior is equivalent to the behavior of g.

Question: does f invoke g?


Consider the case that x is small. (1 + x) has a rounding error; the result that you get is not (1 + x) but (1 + x') for some x' close to x. If x is very small, the relative difference between x' and x can be quite large. Trying to calculate log (1 + x) will calculate log (1 + x') which can have a large relative error. Instead the better formula calculates log (1 + x') / x' * x.

You can just enter both formulas into a spreadsheet and compare with the Taylor polynomial ln (1 + x) = $x - x^2/2 + x^3/3 - x^4/4...$.

Note that it is easy to calculate ln (z) with very high precision when z is close to 1. The damage is done when 1+x is calculated with a small absolute rounding error which turns into a huge relative error, and that's what the modified formula compensates for.


How is deciding a problem not equivalent to finding a valid certificate for verification?

The problem is in the following excerpt:

  iterate through the entire set of certificates

There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.

Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.


Unambiguous but nondeterministic context-free language?

$\{ww^R\mid w\in\{a,b\}^∗\}$ should do the job. The rest is up to you regarding proofs, such as providing an unambiguous grammar.

From Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?
Third answer by Google.

Another one found similarly at Non-Deterministic CFLs:  $\{x^ny^n \;\mid\; n \geq 0\} \cup \{x^ny^{2n} \;\mid\; n \geq 0\}$


Solving or approximating recurrence relations for sequences of numbers

Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers.  Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort.  (Here, $k$ is the rank of the randomly chosen pivot.)  For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k<n$.  Recurrences of this form are called full history recurrences.

To solve this recurrence, we can transform it into a limited history recurrence, where $T(n)$ depends on only a constant number of previous values.  But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions.
\begin{align*}
n T(n) &= n^2 + 2\sum_{k=1}^{n-1} T(k)
\end{align*}
Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms:
\begin{align*}
(n-1) T(n-1) &= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k)
\\
\implies
nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1)
\\[1ex]
\implies
n T(n) &= (2n-1) + (n+1) T(n-1)
\\[1ex]
\implies
\frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n}
\end{align*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence
$$
t(n) = \Theta(1/n) + t(n-1).
$$
Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H_n) = \Theta(\log n)$, where $H_n$ is the $n$th harmonic number.  We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.


Why is $\Theta$ notation suitable to insertion sort to describe its worst case running time?

You are confusing two different notions.
The definition of $\Theta$ that you give is correct, and indeed the running time of insertion sort, in the worst case, is $\Theta(n^2)$, since it has a quadratic running time.

The fact that this is the worst running time is somewhat irrelevant here. You have some function, and you are classifying it as $\Theta(n^2)$, because you can.

Indeed, the runtime of the algorithm in the best case can be a different function, which may or may not be $\Theta(n^2)$.

It may make more intuitive sense to just say that in the worst case, the runtime is $O(n^2)$, which implies that in all the cases the runtime is $O(n^2)$, but observe that this is also implied by the stronger $\Theta$ notations.

As an illustrative example, consider this: You can get home in two paths, one takes 10 km, and the other 3 km, but the 3 km is only open on certain hours of the day.

You can say the following: when you walk home, in the worst case you will walk exactly 10 km. This is true, and it implies that you always walk at most 10 km. But the former is a stronger claim, so why not use it?


PSPACE-complete problems can't be in NL using the space hierarchy theorem?

This question is currently open, since a positive answer (i.e. no complete problems for PSPACE can lie in NL) would imply $\mathsf{P}\neq\mathsf{PSPACE}$. This statement is actually equivalent to $\mathsf{P}\neq\mathsf{PSPACE}$ (as a PSPACE complete problem in NL obviously implies P=PSPACE).

Examine the equivalent statement, that $\mathsf{P}=\mathsf{PSPACE}$ implies there exists a PSPACE complete problem in NL. To see why this holds, note that if $\mathsf{P}=\mathsf{PSPACE}$ then every non trivial language $L\in\mathsf{PSPACE}$ (i.e. $L\neq \emptyset,\Sigma^*$) is complete for PSPACE. Now let $L$ be some non trivial language in NL (which is a subset of PSPACE), then $L$ is a PSPACE complete problem which lies in NL.


Number of 5-cycles and 6-cycles in a simple graph

I'll suppose that you looking for $k$ -cycle, and in the following $f(k)$ is a computable function which belongs to $O(k!)$.

One simple algorithm is considering all possible k+1 vertices, to check whether they are part of a some cycle or not, this algorithm is $O(|V|^{k+1})$ (If we consider corresponding edge, running time can be improved on sparse graphs). This idea can be improved by using matrix multiplication algorithm, we know that in the level $m$ of (adjacency) matrix multiplication we have the number of paths of length $m$ starting from each node. Then we can calculate $M^k$, this can be done in $O(f(k)\cdot M^{\omega+1})$ (where $M^\omega$ is the lower bound for running time of matrix multiplication for adjacency matrix $M$ of input graph). But converting this to a cycle is a little bit tricky task and you can find one algorithm here, running time of exponential part still is independent of size of graph and is depend to $f$, but sure in the cycle case $f$ is bigger ($k!$ in the first paper). There are faster but more complicated algorithms like what described in this, all of them are consequence of these simple ideas.

P.S: I hope to be clear that the bound that I mentioned is not tight, e.g in both Monien and Alan's papers, upper bounds are better than general thing that I wrote.


A somewhat late response:

The formula $AX(p U q)$ is equivalent to the CTL formula $AXA(pUq)$: Consider a state that satisfies the former, then in all the paths from it, after one transition it holds that $pUq$. Thus, in all the paths after one transition, we reach a state from which all the paths satisfy $p U q$, so the state satisfies the latter. The converse is obvious, sine the second formula is harder to satisfy.

So an equivalent CTL formula is
$EF[p\wedge AXA(pUq)]$.


The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^* \setminus A$ to the same $w'' \in \Sigma^* \setminus B$). In fact, for every decidable language $A$, we have $A \leq_m B$ for every $B$ such that $B \neq \Sigma^*$ and $B \neq \emptyset$.


GPUs are highly specialized: they are very good at a very small number of things, but they are extremely bad at everything else.
CPUs are general: they are mediocre at everything.
GPUs are good at applying the same operation out of a small number of potential operations, and in particular, the same very simple operation to a lot of identical things. E.g. when you want to brighten up a picture, you need to apply the same extremely simple multiplication to all 3 colors of all 10million pixels of a 4K screen.
A CPU is almost exactly the opposite: the number of potential different operations is not small, it is almost endless. (Word processing, spreadsheet crunching, compiling, web browsing, emailing, controlling a robot, driving a car, …) The operations aren't simple, they are extremely complex. And you don't apply the same operation to a huge number of identical things, you apply a different operation to a number of different things.
GPGPU (General-purpose GPU) is a misnomer, really. They are not "general purpose" in the same sense that a general purpose CPU is. What is meant by that, really, is that they can be used for purposes other than creating pictures that still have the same characteristics as graphics. For example, modern graphics cards can do particle simulations for generating realistic rain or explosions. What "GPGPU" means is that you can use those same particle simulation features without generating a picture from it, and instead, say, generate velocity predictions for the fragments of an exploding asteroid.
But, reading your mail is a very different thing than simulating a billion particles.


How is verifying whether an assignment satisfies a boolean formula possible in polynomial time?

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a : X_\varphi \to \{0,1\}$ an assignment of all variables that occur in $\varphi$. Now we define the evaluation function $\operatorname{eval}_a$ on variable-free boolean expressions in the following way:

$\qquad \begin{align}
  \operatorname{eval}_a(\text{true})  &= 1 \\
  \operatorname{eval}_a(\text{false}) &= 0 \\
  \operatorname{eval}_a(x) &= a(x) \\
  \operatorname{eval}_a(\lnot \varphi) &= 1 - \operatorname{eval}_a(\varphi) \\
  \operatorname{eval}_a(\varphi \land \psi) &= \operatorname{eval}_a(\varphi) \cdot \operatorname{eval}_a(\psi) \\
  \operatorname{eval}_a(\varphi \lor \psi) &= \max(\operatorname{eval}_a(\varphi), \operatorname{eval}_a(\psi)) \\
 & \vdots
\end{align}$

Clearly, $\operatorname{eval}_a(\varphi) = 1$ if and only if $a(\varphi) \mathop{|\!\!\!==\!\!\!|} \text{true}$ (here, $a$ is continued on $\varphi$ in a syntactical manner: it replaces all variable occurrences $x$ in $\varphi$ with $a(x)$). If in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}_a$ performs about one operation per operator and literal; thus it runs in time $O(|\langle \varphi \rangle|)$.


Most Efficient Way to List All $n$-bit Permutations

Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists.  Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $\lceil log_2(2^n!)\rceil$ bits.

In practice, you can come arbitrarily close to this bound using arithmetic encoding, without having to manipulate very large integers.


Comparison of logics is  a complicated subject.

Expressive power of logics can be 'measured' in various ways. The most well-known approach is that of conservative extensions. If $L$ is a logic with signature $\Sigma$, then a logic $L'$ over signature $\Sigma' \supseteq \Sigma$ is a conservative extension of $L$ provided every $\Sigma$-formula $\phi$ that is provable in $L'$ is already provable in $L$. In other words, conservativity means that by moving from $L$  to $L'$  we are not adding expressive power to the discourse about things that can be expressed in $\Sigma$.

Things become more complicated when you are looking at logics with signatures that are not comparable by $\subseteq$. When you want to compare e.g. set theories with type theories, then you won't get a nice match of signatures. In this case you need to look at encodings. This can be done in various ways. For example you can encode formulae, or formulae an proofs. You can study properties of those encodings (e.g. do they preserve formula/proof structure) etc?

An old example of encoding is Gödel's and Gentzen's double-negation translation that embeds classical logic into intuitionistic logic, and reduces the consistency of the former to that of the latter.

Comparison of programming languages is  even more complicated
 and -- kind of, sort of -- contains the comparison of logics as a special case by the Curry–Howard correspondence.


Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?

In a single linked list, every element has a pointer to the next element.  If you have an additional pointer to the tail element, it takes you a constant number og operations to add to the list at the tail:  get the tail pointer, add an element after the tail, put this new element as new tail.  Removing from the head also takes a constant number of operations:  make you new item new, head, point to old head.

However, removing from the tail demands a pointer to the predecessor to the current tail.  This takes you as many operations as there are elements, namely linearly many.

Another solution is to use a doubly linked list, then you can choose what you will, but it uses twice as much memory.


Can there be two different left most derevations for a grammar?

A leftmost derivation of a string in the language defined by a
grammar $G$ characterizes a parse-tree for that string. It is a way of
describing the parse tree, which is unique for each parse tree.

But to answer the specifics of your question, there is no lefmost
derivation of a language, only of the strings of a
language. Furthermore, since a leftmost derivation is a sequence of
grammar rules applications to produce the string, a leftmost
derivation is necessarily defined with respect to a specific
grammar. Indeed, the language does not really matter, only the grammar
and a string derived with that grammar.

If a string has only a single derivation for a grammar $G$, it is said
unambiguous for that grammar. When it has several, it is said
ambiguous for that grammar. When it has none, it does not belong to
the language generated by the grammar.

A grammar is ambiguous if it generate at least one ambiguous
string. It is unambiguous if every string in its language is
unambiguous.

The grammar in your question is unambiguous. Each of the derivations
you give is a leftmost derivation, but each for a different string in
the language of the grammar.

Actually, this grammar is so simple that it has only leftmost
derivations, because there is at most one non-terminal in each rule
right-hand side. But a grammar can have only leftmost derivations and be ambiguous.


Generating all equal-sized set partitions

Suppose $N=\{0,\dots,N-1\}$.
There are $\binom{N-1}{K-1}$ choices for which elements are equivalent to 0. For each choice of these there are $\binom{N-K-1}{K-1}$ choices for which elements are equivalent to the smallest number not equivalent to 0. And then $\binom{N-2K-1}{K-1}$ for which elements are equivalent to the smallest number not equivalent to any number chosen so far.
Continuing to iterate this way, we get through all the $\prod_{a=0}^{N/K-1}\binom{N-aK-1}{K-1}$ balanced partitions.


is size of maximum matching less than that of maximum k-parity k-set packing?

Consider the case $k=3$, and the following set system:
$$
(a_1,b_1,c),\ldots,(a_n,b_n,c) \\
(a'_1,b',c'_1),\ldots,(a'_n,b',c'_n) \\
(a'',b''_1,c''_1),\ldots,(a'',b''_n,c''_n)
$$
Every packing contains at most 3 sets, but $d=n+2$.


Showing that CLIQUE can be verified in polynomial time

What you're missing is the difference between decision problems and optimization problems.  "Finding the maximum clique" is an optimization problem.  The corresponding decision problem is "Does there exist a clique of size $\ge k$?".  The latter problem is in NP.  NP is a class of decision problems, so it doesn't make sense to ask whether an optimization problem is in NP; that's only meaningful for decision problems.  Any textbook or standard resource on NP should explain the difference between decision problems vs. optimization problems in more depth.


Python: A doubt on time and space complexity on string slicing

The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes $O(1)$ or $\Theta(|\text{new_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using.

In contrast, it is quite clear that the procedure uses $\Theta(|\text{word}|+1)$ space, since it builds new_word from scratch, not reusing the memory of word. This has nothing to do with the loop; the statement new_word = word[:], which makes a copy of word, also uses up $|\text{word}|$ space. Space consumption is the amount of memory used. If you're constructing a new string of length $|\text{word}|$, then it uses up memory proportional to $|\text{word}|$.

I suggest forgetting about what you call the "mathematical perspective", and focusing instead on the intuitive meaning of time and space complexity. Time complexity is the number of instructions executed by the program. Space complexity is the amount of memory that needs to be allocated in order to run the procedure. You are stating some rules for calculating these quantities, but it's much more important for you to understand what you are calculating rather than specific tricks which are dubious when applied mechanically.


Amortized analysis of virtual, dynamic array using potential function

What am I doing wrong here? You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.


Example of inductive sets that are neither least nor greatest fixed point

Here's a non-trivial example:

Suppose we want to define inductively a subset of reals, so we work on the complete lattice $\mathcal{P}(\mathbb{R})$ ordered by inclusion.

Then, consider the rules
$$
\dfrac{\qquad}{0} \qquad \dfrac{x}{x+1}
$$
This induces the (monotonic, Scott-continuous) function $f : \mathcal{P}(\mathbb{R}) \to \mathcal{P}(\mathbb{R})$ given by
$$
f(X) = \{0\} \cup \{ x+1 \ |\ x\in X\}
$$

All of the following are fixed points of $f$:

$\mathbb{N}$ (least)
$\mathbb{Z}$
$\{x/2 \ |\ x\in \mathbb{Z}\}$
$\{x/3 \ |\ x\in \mathbb{Z}\}$
etc.
for any natural $k \geq 1$, the set $\{x/k \ |\ x\in \mathbb{Z} \}$
$\mathbb{Q}$
$\mathbb{R}$ (greatest)

If we want our definition to be well-formed, beyond specifying the rules, we need to single out one the fixed points. This is typically done by taking the least (induction) or the greatest (coinduction).


Constructing Noneterministic Finite Automata (NFA) with a "not" condition

First construct the DFA which accepts any string that DOES contain "abaa".  Then interchange final vs non-final!  (note: this only works with a DFA, not an NFA)  The rest you have already figured out.


Proving NP completeness of maximal length path

I think here is a pitfall due to inaccurate notation.
Notation for me:

A trail is a sequence of distinct connected edges.
A path is a trail with distinct vertices.

In the problem instance $MNPL$ (maximum neighbor path length) the sets $(G,N^+, N^-)$ and the weight function $c_e$ are given as input(and hereby fixed).
Since $N$ is partitioned, for two vertices $u,v$ either $\{u,v\}\notin E$ or $u$ is a positive neighbor of $v$ or vice-versa. Especially $u$ and $v$ cannot be a positive neighbor of each other by definition ($N$ would not be partitioned). Hence $G$ must be a directed graph.
Now, for any path  $s \rightsquigarrow (u,v,w) \rightsquigarrow t$(not way nor cycle nor walk!) the neighbor-condition is fullfilled.

Maybe this was the real challenge of this exercise?

So, claim: $MNPL$ is $NP$-complete.

Proof: $MNPL \leq_p LPP$ (longest path problem)
Consider the reduction $f$. For $(G,N^+,N^-,c_e)$ construct $G'=(V',E',c_e')$ as the following:

$c_e'$ = $c_e$
$V' = V$
$E' = \bigcup_{v \in N^+(u), u \in N} (u,v) \cup \bigcup_{u \in N^-(v), v \in N} (v,u)$

Clear: $f$ is computable and runs in poly-time ($O(|E|)$). By construction and with the observations above $f$ will construct a digraph from $N$ and the neighbor sets.

So $f$ is a reduction and $MNPL \in NP$ is obvious using "guess and check".
Since $LPP$ is strongly $NP$-complete, $MNPL$ is as well strongly $NP$-complete.
This is no decision problem but a maximization problem.


Selection sort proceeds by finding the smallest unsorted element and adding it to the end of the sorted section of the array. You can't use binary search to find the smallest unsorted element, because binary search only works on sorted lists.

Your question seems to be based on the mistaken understanding that selection sort takes the first unsorted element and inserts it into the correct place in the sorted list. The correct place could then be found by binary search but the problem with that attempt at an algorithm is that you need array-like access to the sorted portion for binary searching it, and list-like access for inserting in the middle.


Class of the language only containing the empty string?

This issue is covered in wikipedia's article on noncontracting grammars. Such grammars do not allow deriving the empty string, which is no problem when one considers languages $L\subseteq A^+$. When one wants to allow the empty string, a special case is made and the rule $S\to\lambda$ is allowed with ugly side conditions ($S$ cannot appear in a right-hand side).

So the situation is that there are several available, mostly equivalent, definitions, that offer different tradeoffs between elegance, generality, ease of use, etc. This is a typical situation in mathematics. When you scratch the surface, the different definitions are there and they come with extra terminology, like "essentially noncontracting".

This may look confusing for newcomers but the good side is that it separates the important from the not-so-important details.

BTW your reasoning has a flaw. You say that the language is CSL (correct) and $S\to\lambda$ is a grammar for it (correct), thus that grammar is CS. That implication is incorrect. You can only deduce that there exists a CS grammar for it. But you are right in thinking that any such grammar must have a contracting rule.


Would a class in Linear Optimization/Programming be useful for a CS degree?

I think it depends on what do you want to do after graduating. Linear Optimization/Programming is more theoretical  than practical, it will definetly be useful (take it) if you want to work as an academic/researcher but it won't be that helpful if you want to be a software developer.


Is it possible to use dynamic programming to factor numbers

You can try to find the smallest divisor $d>1$ of $N$ by trial divison. Then the factorization of $N$ is given by that of $d$ and that of $N/d$. Since $N$ is either a prime number or has a divisor $1 < d < \sqrt{N}$, this would solve the problem. Of course, this is a dynamic solution in a very vague sense only - the table of partial results is only used as a cache, not like in "real" dynamic programming algorithms.


Can I speed up Insertion Sort by using a tree for finding insertion positions?

Would my complexity for the whole code be still maintained in $O(n \log n)$?

Let's check where we're coming from: Insertion Sort runs in time $\Theta(n^2)$ (worst and average case) if you implement findInsertionPosition (fIP) with a simple loop that scans the array.

Second, let's check what we can possible achieve. Assume that fIP runs in time $O(1)$. We still get $\Theta(n^2)$ since insert alone takes times linear in i in each iteration (worst and average case), adding up to $\Theta(n^2)$.

Third, why use a tree? You can easily achieve running-time logarithmic in i for fIP (for a total of something in $\Theta(n \log n)$) by using binary search. That would still be dominated by the cumulative cost of insert, of course.

If you did use a tree, it would make the most sense to not throw it away between iterations; fIP would be obsolete. You would effectively have sorting by creating a search tree (which we don't really call Insertion Sort) but, yes, that would have running-time in $\Theta(n \log n)$, provided you use a balanced search tree.

In summary, no, it does not make sense to try and tweak Insertion Sort by using search trees.


You can keep two tables with $n$ rows and $C$ columns:

$DP_{even}$ that saves the best knapsack solution with an even number of itens.
$DP_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP_{even}$ you look at the previous best solution of $DP_{odd}$ plus a new item, or of $DP_{even}$ if you don't take the item:
  $$DP_{even}[i, j] = max(DP_{odd}[i - 1,j - c[i]] +  v[i], DP_{even}[i - 1, j]) $$
The same idea goes for $DP_{odd}$
$$DP_{odd}[i, j] = \max(DP_{even}[i - 1,j - c[i]] +  v[i], DP_{odd}[i - 1, j]) $$

Your solution will be in $DP_{even}[n, C]$


LR parsers and ambiguous and non deterministic grammars

The grammar is really ambiguous.

$\textbf{ if  } expr \textbf{ then   if }expr \textbf{ then  } stmt \textbf{ else  } stmt$

has two possible parses with that grammar. (The $ \textbf{ else }$ can attach to either $\textbf{ if }$.)

As you say, determinism and ambiguity are orthogonal. Certainly, there are unambiguous grammars which are not LR. But no ambiguous grammar is LR and this is one such example.


Why does taking a gamma value > 1 make the image darker?

Because pixel intensity in any professional task is measured between [0; 1].

The most representations are 8bit per pixel but there are for example 16bit representations.
So with [0;1] intensities there is always good representation device independent.

Another important thing is chaining operations (multiply, add pixels etc.), floating points are better because they store fractional values.
If you have RGB from 0-255 it is one way of representing it, very common, discrete but device dependent.
In such representation operations on pixels like gamma needs normalisation by division: divide by 255, apply operation, then cut to [0; 1] and then multiply by 255.
In floating point operation this is not needed.
Also look out for shifted gamma corrections, in colour space conversion for example.

Summing it up [0; 1]$^\gamma$ is going counter-intuitive.


No, probably not, if you care about theoretical worst-case running time.  The problem is as hard as the subset containment problem: given sets $S_1,\dots,S_n$, check whether there exists sets $S_i,S_j$ such that $S_i \subset S_j$.  It's known that there is no algorithm with $O(n^{2-\epsilon})$ running time, assuming the SETH conjecture is true.  Thus, any faster algorithm would imply a disproof of SETH, which is a famous open problem -- so you shouldn't expect any easy algorithm that does significantly better than $O(n^2)$ in worst-case running time.  (I don't count a $\log n$ factor speedup as significant.)  See https://cstheory.stackexchange.com/q/9896/5038.

If you only care about the "average case" it might be possible to do better.  The answer might also depend on the model of computation and the size of the integers, so it's possible there might be some choice of those that lets you evade this hardness result.

For instance, if your numbers are "random" in a particular specific way, you can use a divide-and-conquer algorithm.  First recursively solve the problem for $A[1..n/2]$, and recursively solve the problem for $A[n/2+1..n]$.  Then for each $i \le n/2$ such that $B[i]=-1$, we'll find the smallest $j > n/2$ such that $A[j]$ divides $A[i]$ and overwrite $B[i]$ with $j$.  Suppose we can do that last step in $U(n)$ time.  Then the total running time will satisfy the recurrence $T(n) = 2 T(n/2) + U(n)$, i.e., $T(n) = O(U(n) \log n)$.

OK.  So how will we do that last step?   We'll solve that problem in turn using a separate divide-and-conquer algorithm.  Pick a prime number $p$ that hasn't been picked yet, and construct the sets $S^0 = \{i : p \not| A[i], i \le n/2\}$, $S^1 = \{i : p | A[i], i \le n/2\}$, $T^0 = \{i : p \not| A[i], i > n/2\}$, $T^1 = \{i : p | A[i], i > n/2\}$.  Now for each $i \in S^0$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$; and for each $i \in S^1$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]$ divides $A[i]/p$), and find the smallest $j \in T^1$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]/p$ divides $A[i]/p$).  Those are three subproblems each of size $n/2$ (heuristically, assuming the numbers are random and half are divisible by $p$ and half aren't), and then you can combine them to get a solution to the original problem in $O(n)$ time, so the total running time to do this last step is $U(n) = 3 U(n/2) + O(n)$, which solves to $U(n) = O(n^{\lg 3}) = O(n^{1.585})$.

So, heuristically the total running time of this approach is $O(n^{1.585} \log n)$ under a particular assumption on the distribution of the numbers.


Create a shallow logic circuit that increments a binary number

You are on the right track with a parallel-prefix circuit.  You already have the key when you said

  The carry has to ripple through the first sequence of consecutive bits set to 1.

Now suppose you are figuring out the output for, say, the 5th bit.  What function of the first 4 bits tells you whether the 5th bit should ripple?  That's the function you need to make a parallel-prefix circuit for.


Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

I will try to lift some of the confusion you have.
Let $G$ be some graph, with $n$ vertices and $m$ edges. Then what is $|G|$? Lets say we encoded it as adjacency matrix, so it takes up $n^2$ space. Therefore, $f(|G|)=f(n^2)$ and $g(|G|)=g(n^2)$. There won't be a "gap" here.
What about if we encode it with $m\log(n)$ space? then we would have $|G|=m\log(n)$ and thus $f(|G|)=f(m\log(n))$ and $g(|G|)=g(m\log(n))$.
So what went wrong with your calculations? The difference here is that you used max once and min once to represent the same quantity. You probably did this to "give a bound" only, but notice the following interesting thing: why would we want max? we can always encode the graph in the smallest way possible, so essentially $|G|=\min \{n^2,m\log(n)\}$. Substitute this and get $g(|G|)=g(\min \{n^2,m\log(n)\})$. In the same way, $f(|G|)=f(\min \{n^2,m\log(n)\})$.
Notice I didn't give the bounds in terms of $\Omega$ and $O$, but we could. In any case, the transition $g(\min \{n^2,m\log(n)\})=\Omega(g(n\log(n)))$ is not strict, since there are many times that $\min \{n^2,m\log(n)\}> n\log(n)$. The same goes with the transition $f(\min \{n^2,m\log(n)\})=O(f(n^2)))$ (making this a min automatically made the bound better).
I hope this helped you understand a bit more how the bounds behave with respect to the size of the graph and its different encodings.


Can all optimizations be expressed in source code?

The key to remember is that, at its core, a compiler is just a translator between two languages. One is often machine code, and there may be some intermediate steps, but translation is the key.

With that in mind, an optimization is one of three things:

A transformation from source programs to source programs, that is (hopefully) observationally equivalent to the original program, that is (hopefully) faster
A transformation from source programs to target that takes advantage of some property of the source program to generate code that is equivalent to, but faster than, the "vanilla" compiled version of the code.
A transformation from target programs to target programs that produces equivalent but faster code.

(3) could happen after compilation, since it doesn't rely on source input at all, and (1) could happen in an interpreted language as much as a compiled one.

Naturally, (2) can encompass programs that can't necessarily be expressed in the source language. It all depends the properties of your transformation. Is it a surjection between your source and target languages?

If it's not surjective, and both languages are Turing Complete, then:

There must be some programs in the target language which are never the result of compilation
Each "unreached" target program is equivalent to some source program (since both languages are Turing Complete)

Some of these will likely be optimizations.

For some practical examples:

Tail-call elimination is not expressible as a source-to-source transformation in any language with higher-order functions lacking GOTO
Any optimization using a "special" CPU instruction can't be expressed as a source-to-source transformation, since there's no way to access that instruction from the source language.

There are likely many more. (Community: feel free to add examples as you see fit!)


Proving that quantum circuits not involving entanglement are inefficient

A general state of $n$ qubits can be written as follows :

$|\psi\rangle = \sum\limits_{x=0}^{2^{n-1}}\alpha_x|x\rangle$

Which means you need $2^n$ complex numbers to describe an arbitrary state of $n$ qubits.

A non entangled state on $n$ qubits can be written in the following way:

$|\psi\rangle = \bigotimes\limits_{i=1}^{n}\left(\alpha_i|0\rangle + \beta_i|1\rangle\right)$

Which means we only need $2n$ complex numbers to describe it. If we assume that we only deal with circuits such that two different qubits are never entangled, this property holds throughout the entire computation.

This is enough to see how to simulate the circuit, always remember the $2n$ complexes describing your non entangled state, and apply the desired operators on specific qubits (remember that it is garunteed that applying cnot will not result in entanglement).

That said, don't take this as evidence to the fact that quantum computing without entanglement doesn't extend classical computation in any way. For example, see this paper (Quantum computation without entanglement, Eli Biham et al). They reproduce some known results in the blackbox model (which are impossible on a classical computer) without entanglement.


Efficiently inserting into list keeping number of inversions minimal

This is an elaboration on on trevore's answer. It's too long to fit in a comment and contains the proofs of his solution (or at least how I understand it).

You can show that in any optimal solution, the elements of $s$ will appear ordered. If not, assume $s_1 < s_2$ and they appear in reverse order in an optimal solution. Let $\sigma_1$ be the number of elements between $s_1$ and $s_2$ that are less than $s_1$ and $\beta_1$ be the number of those that are bigger than $s_1$. Define $\sigma_2$ and $\beta_2$ similarly for $s_2$. Note that $\sigma_1 \leq \sigma_2$ and $\beta_2 \leq \beta_1$. Swapping $s_1$ and $s_2$ will change the number of inversions by $-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$ which is at most -1.

It is not hard to see that elements of $s$ can be inserted independently. Since they appear ordered, the elements of $s$ do not "feel" each other's presence. That is, pairs of elements from $s$ do not contribute to the inversion count. To do that, insert the median of $s$ optimally in linear time. Then, recursively, insert elements of $s$ less than the median to the left of the median and elements bigger than the median to its right.

Let the median be inserted in position $k$, the runtime of this satisfies, $T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$, the linear $|s|$ factor is for finding the median and shuffling the elements of $s$. It is easy to show by induction that $T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$.

Note that the dependence on $|s|$ here is optimal. Since solving the problem with empty $u$ is equivalent to sorting $s$ using only comparisons. The dependence on $|u|$ is also optimal, since the problem for a singleton list $s$ and a list $u$ must require linear work.


Searching a sorted array to find the $k$ closest values to a target value $T$

You can do it in two binary searches. For simplicity I assume that all numbers are distinct and, even more, absolute differences between $T$ and all other elements are distinct too. The solution is easily adapted if it is not the case.

What means that a selected subrange is optimal? That means that we can't move it neither right ($|A_{j+k} - T| > |A_{j} - T|$) nor left ($|A_{j+k-1} - T| < |A_{j-1}|$). That looks like a binary search as well!

Look at the function $h(j) = \mathbb{1}\{|A_{j+k} - T| > |A_{j} - T|\}$ (that is, $h(j)$ is 1 iff the answer does not become better if we move the subrange to the right). Now you have to find minimum $j$ s.t. $h(j) = 1$. As the function is monotonous, it can be done by a binary search by $j$ in $O(\log n)$ time. (Actually, it is $O(\log (n-k))$ because $j < n - k$).

If there are identical values in the array, we need some case handling. Whenever $|A_{j+k}-T| = |A_j-T|$, there are three cases possible: Either $A_{j} = A_{j+k}$ and the segment is to the left of $T$; in this case we should move right. Or, $A_{j} = A_{j+k}$ and the segment is to the right of $T$, and we should move left. Or the segment contains $T$, in this case we've found the optimal answer.


Compilation with a witness / certificate

In theory, what you are asking about has been studied, under the name "translation validation".  See, e.g., the following classic paper:

George C. Necula. "Translation validation for an optimizing compiler." PLDI 2000.

In practice, compilation is such a complicated messy process that I doubt there will be any easy-to-verify certificate that proves the entire compilation process was done correctly (including lexing, parsing, front-end, optimization, back-end, assembly, linking, etc.).  Academic work typically focuses on just one or two phases of the process (e.g., some of the stages of optimization).

One should separate two separate issues: can the verifier be simpler than the compiler?  can the verifier be faster than the compiler?

Simpler is interesting, because it means the verifier can potentially be more trustworthy (e.g., less likely to have bugs).  Classic work on translation validation focuses on that case.

Faster is a different question.  Some optimizations are deterministic and won't benefit, but there are certainly plenty of optimizations that involve a search over some space of possibilities.  An extreme version of that is the concept of "superoptimization", which optimizes a short code sequence by searching over all possible optimized versions and finding the one that is the fastest while remaining semantically equivalent to the original.  See, e.g., the following papers:

R. Sausnauskas, Y. Chen, P. Collingbourne, J. Ketema, G. Lup, J. Taneja, J. Regehr.  "A Synthesizing Superoptimizer."

Sorav Bansal, Alex Aiken. "Automatic Generation of Peephole Superoptimizers."  ASPLOS 2006.


Finding maximum of $n$ many $m$-bit integers

Hi I make this post because this question is quite challenging for me and I want to know if my solution will pass "peer-review". Consider following algorithm for a RAM machine (// denotes integer division):
algorithm ArrayMax
Input: array $A$ of size $n$; $A[i] \in [1,2^m-1]$
Output: $max(A)$
left  <- 1
right <- 1
max   <- A[0]
while right <= A[0]: right <- 2*right
left <- right // 2
for i = 1...n-1:
    if A[i] <= left:
        continue
    if A[i] >= right:
        max <- A[i]
        while right <= A[i]: right <- 2*right
        left <- right//2
        continue
    while left-right > 1:
        mid <- (left+right)//2
        if max < mid:
            right <- mid
        else:
            left <- mid
        if A[i] < left:
            break
        else if A[i] >= right:
            max <- A[i]
            delta <- right-left
            left  <- right
            right <- left+delta
            break
return max

The algorithm operates by keeping $left \leq max < right$ and uses the bounds to make comparisons. Notice that if the bounds of $max$ aren't sufficient they are extended via binary search. How can one proof that this algorithm runs in $O(n+m)$? (This is not a rigorous proof; more an idea; if you have improvements please edit or write a comment)
I'll try to outline a proof using a potential function $\Phi(S_i)$ ($S_i$ is the state of the algorithm at iteration $i$). The Potential Method is usually used for data structures. We define:
$$\Phi(S_i) = \log2(left-right) \geq 0$$
There are two things that can happen between $S_i$ and $S_{i+1}$ (We only consider the worst case so we'll ignore the first "if" in the loop and focus on the second "if" and the while loop).
If the second "if" is triggered the following change occurs in the potential function:
$$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx \log2(A[i]))$$
Also the cost of the operation is $T_i \approx \log2(A[i]) - \log2(right) \leq \log2(A[i]) - \log2(max)$
In the second case a binary search occurs which goes to depth $k$ (does $k$ bisections).
$$\Phi(S_i) = j \rightarrow \Phi(S_{i+1}) \approx j-k$$
Notice that the cost of bisecting is roughly $4*k$ comparisons. Thus the cost including the Potential Function is:
$$T_i = O(1) + 4k + 4(\Phi(S_{i+1})-\Phi(S_i)) = O(1) + 4k - 4k = O(1)$$
So basically the second case is for free. Lets now focus one the first case only. Consider that it happens $h$ times in a row. It is easy to see that for the second case to not occur $A[i+1] \geq 2A[i]$  Meaning we can approximate the cumulative cost with:
$$\sum_{i=1}^h \log2(2^{i+1}) - \log2(2^i) + (\Phi(S_{i+1})-\Phi(S_i)) = \sum_{i=1}^h 2(\log2(2^{i+1}) - \log2(2^i)) = \sum_{i=1}^h2(i+1-i) = 2h$$
Notice that since the the numbers are limited by $2^m$ we have $h \leq m$. Thus we obtain $O(m + n)$, where $m$ is accounting for the first cases and n is accounting for the second cases. Also the first while loop finding bounds for $A[0]$ runs at most $m$ times. I hope you get my idea, despite the fuzzy argument.


----I'm not sure if this should be my answer. Many thanks to hengxin. It does explain my confusion, and may be helpful to others seeing the question----

I failed to realise that there are 2 types of unreliable messages,
- some are different for each lieutenant, (eg 'eX' in round 1)
- others are the same for all lieutenants (I will denote these as 'S')

the amended example is,

<(b1) ,c0   ,d0   ,eX   ,f1   ,g1   >

<     ,(cb1),(db1),(ebX),(fb1),(gb1)>   1
<(bc0),     ,dc0  ,ecX  ,fc0  ,gc0  >   0
<(bd0),cd0  ,     ,edX  ,fd0  ,gd0  >   0
<(beS),ceS  ,deS  ,     ,feS  ,geS  >   S
<(bf1),cf1  ,df1  ,efX  ,     ,gf1  >   1
<(bg1),cg1  ,dg1  ,egX  ,fg1  ,     >   1

now the result from 'round 2' is different to 'round 1', and allows agreement.
however, we could have acheived the same result with:

<(b1) ,c0   ,d0   ,eX   >

<     ,(cb1),(db1),(ebX)>   1
<(bc0),     ,dc0  ,ecX  >   0
<(bd0),cd0  ,     ,edX  >   0
<(beS),ceS  ,deS  ,     >   S

Remember we have a traitor commander, but it seems more than coincidence that there is 1 traitor lieutenant out of 4 lieutenants (3t+1)?


Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?

The first thing to note is that this isn't necessarily true. For example, depending on the language a function with that type, besides being the identity function, could: 1) loop forever, 2) mutate some state, 3) return null, 4) throw an exception, 5) perform some I/O, 6) fork a thread to do something else, 7) do call/cc shenanigans, 8) use something like Java's Object.hashCode, 9) use reflection to determine if the type is an integer and increment it if so, 10) use reflection to analyze the call stack and do something based on the context within which it is called, 11) probably many other things and certainly arbitrary combinations of the above.

So the property that leads to this, parametricity, is a property of the language as a whole and there are stronger and weaker variations of it. For many of the formal calculi studied in type theory, none of the above behaviors can occur. For example, for System F/the pure polymorphic lambda calculus, where parametricity was first studied, none of the above behaviors above can occur. It simply doesn't have exceptions, mutable state, null, call/cc, I/O, reflection, and it's strongly normalizing so it can't loop forever. As Gilles mentioned in a comment, the paper Theorems for free! by Phil Wadler is a good introduction to this topic and its references will go further into the theory, specifically the technique of logical relations. That link also lists some other papers by Wadler on the topic of parametricity.

Since parametricity is a property of the language, to prove it requires first formally articulating the language and then a relatively complicated argument. The informal argument for this particular case assuming we're in the polymorphic lambda calculus is that since we know nothing about t we can't perform any operations on the input (e.g. we can't increment it because we don't know if it is a number) or create a value of that type (for all we know t=Void, a type with no values at all). The only way to produce a value of type t is to return the one that is given to us. No other behaviors are possible. One way to see that is to use strong normalization and show that there is only one normal form term of this type.


Bayes theorem probaility doesn't make sense

The problem is your data! For example, the last row shows that $\mathbb{P}(A) = 1$ and $\mathbb{P}(B|A) = 0.8$. If $\mathbb{P}(A) = 1$ means $A$ is equivalent to all possiblities of event world. Hence, $\mathbb{P}(B|A)$ couldn't be anything except 1.


proving the error bound for a hypothesis

Consider a case where the actual label is $1$ for all $x\in [0,1]$.
Suppose $H$ consists of two classifiers: one that realizes this (i.e. $\forall x\in [0,1], h(x)=1$), and one that is almost entirely wrong: $g(x)=0$ except for some finite set of numbers $S$.

If the sample is exactly $S$, then both classifiers have the same error on the sample set (0), so you may choose $g$. However, you'll get that $err_D(g)=1>\epsilon$.

As mentioned in the comments, this doesn't really prove anything useful, since the probability that the sample will be exactly $S$ is $0$.


Need an algorithm to find the input factors that are most affecting the output

Fundamental limitations on what you can achieve

The principled answer is: No, you can't reliably deduce such causal connections.  When you have only observations of the data, you can use statistical analysis to look for correlations, but you can't deduce causation.  Correlation does not imply causation.  You are looking for causality, but you cannot infer causality from field data (from external, uncontrolled observations of a system).  To test causality you need a controlled experiment.

This is a problem not just in principle, but often in practice as well.  In practice, we might have correlations among your "independent variables" or confounding factors you haven't accounted for, which causes correlations that aren't an indication of causality.

For instance, you might find that ambient temperature is correlated to display brightness (because at night it is cooler and darker, so phones turn down display brightness, whereas at day it is warmer and brighter, so phones turn up display brightness to compensate for the daytime light).  Now we'd expect that when the display brightness is higher, the battery will be drained faster.  Can you deduce this causal connection from statistical inference applied to some observations?  Well, you might observe a correlation between display brightness and battery drain rate, which sounds good.  But if display brightness is correlated to ambient temperature, then when you do a statistical analysis, you might also discover a correlation between ambient temperature and display brightness -- and that's a spurious correlation that doesn't indicate any causal connection.

Pragmatic, engineering answer

That said, the pragmatic answer is to use statistical analysis of your data to look for correlations, and then hope that at least some of the correlations will represent something real.  You have to go into it with eyes open knowing that some of the correlations will be spurious, for the reasons explained above, but maybe that's OK.  Maybe statistical analysis can still be useful to you.

So, how should you do the statistical analysis?  There are many possible ways.  It's best to say what is the best; that probably depends upon what relationships between the input and output you think are plausible.

But a very simple approach that I suspect will work well for you is to use linear regression.  Try to find a linear model that expresses an output variable (e.g., the battery drain rate) as a weighted linear combination of the input variables.  Linear regression can find the best weights for you that minimizes the prediction error.

Then, the size of those weights tells you exactly what you want to know.  Suppose you are predicting the battery drain rate, and in your linear model the weight for the screen brightness input variable is 0.7.  This means that if you increase the screen brightness by adding $\Delta$, then the battery drain rate is predicted to increase by adding $0.7 \Delta$.

Tricky details

There are a few things about your specific problem that might be a bit tricky.

One tricky aspect is the business about apps, and how to code that into a linear regression framework.  One way is to pick a few categories of apps, and then have a separate indicator input variable for each category (0 if that app is not present, 1 if it is present).  However, you don't want to have too many input variables, because that will require a lot more data to reliably form a linear model.  A few dozen app categories might be fine, but thousands of input variables for the thousands of different possible apps probably would not be.

Another tricky aspect arises if you expect there to be non-linear dependencies, and you want to find them.  For instance, you mention in a comment the possibility that low cellphone signal strength combined with running a 3D game might increase battery drain rate in a way that neither alone would.  If you expect those kinds of non-linearities, one standard way to deal with them is to introduce new input variables for "interaction effects": e.g., you introduce a new input variable which is the product of the signal strength times the indicator variable that indicates whether a 3D game is running.  (These new input variables are derived from the other input variables, but in a non-linear way.)  You can introduce one new "interaction" input variable for each pair of original input variables that you think might exhibit a combined effect of this sort (where the effect of their combination is greater than the sum of their individual effects).  This is a standard technique that you can find described in good tutorials on linear regression.

Ultimately, there's lots more to say on statistical data analysis, linear regression, and applying it to practice -- more than I can write in a single answer.  I recommend you read a good tutorial or two on linear regression and maybe the relevant chapters of some statistical textbooks.  If you still have more questions after all of that, it's also worth knowing about Cross Validated, a Stack Exchange site on statistics.


Time complexity of Dynamic Array via repeated doubling

Both are correct but you're using $n$ to mean two different things:

when you say that $1 + 2^1 + 2^2 + \dots + 2^n  =  (2^{(n-1)} - 1)  \sim  O(2^n)$, you're using $n$ to mean the number of times you had to increase the size of the array;
when you say that $1 + 2 + 4 + \dots + n/4 + n/2 + n  \sim  O(n)$, you're using $n$ to mean the total size of the array after you've extended it some number of times.

So, you should never just say "$n$", without saying what it means. Normally, $n$ refers to the size of the input to a problem. In this case, that would probably be the number of things you want to insert into the array. This is closest in meaning to the second case above since, when you've inserted $n$ elements, the total size of the array will be somewhere between $n$ and $2(n-1)$ (i.e., it will be $O(n)$).


Minimax is actually applied on a 2D matrix like:

3  5  6  13  8
7  9  2  4   6
4  12 15 16  10

Generally, you have a choice to do, let say it corresponds to one of the columns in the exemple (5 choices). And there is an unpredictable choice (random, opponent choice ...), the row in the example (3 choices). Minimax minimizes the risks by assuming this unpredictable choice will be the worst for you.

In the example, you first compute the minimum on all colums:

3 5 2 4 6

So you finally pick the 5th choice, which guarantees at least 6.

In your problem you have 1 dimension, then minimax has no sense on it. Or you can degenerate it saying there is no unpredictable variable and just pick the maximum.


prove every language got a language that is harder

The halting problem for a class of machines that can decide $L$ is always harder than $L$. You already know this when $L$ is computable and the proof of the more general result is essentially the same. For every $L$, you need to think of a class of machines that can decide $L$.


Load balancing. Why not use priority queues?

You are correct that using a priority queue is a good idea.  It doesn't give an optimal answer though.  (Assuming that what you are trying to optimize is the time that the last processor finishes executing the last job.)  This scheduling problem is NP-complete, and the priority queue based method gives an answer that is within a factor of 2 of optimal.  See, for example, http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/11approx-alg.pdf.  The wikipedia page on Job Shop Scheduling also gives some information.


Let's apply Branch and Bound to Knapsack, hopefully this will make the concept clear to you.

We have $n$ items, labelled $1$ through to $n$. $v_i$ is the value of the $i$th item, and $w_i$ its weight. We try to fit them in a knapsack that can contain up to $T$ weight in total, and we try to maximize the sum of the values of the item we put in the knapsack.

The ordinary backtrack approach is our basis. We first put $v_1$ in the pack, and then solve the problem for the remaining $n-1$ items with recursion. We then remove $v_1$ from the pack and solve the problem for the remaining $n-1$ items again, and we return the best configuration that we've found.

This backtracking is the 'Branch' part of Branch and Bound. You branch on (in the case of Knapsack) two cases: 'item $i$ is part of the solution' and 'item $i$ is not part of the solution'. You can visualize this as a binary tree, where the left child is one case and the right child is the other case. This tree is the search tree (or search space): its depth is $n$, and it therefore has $O(2^n)$ nodes. The algorithm therefore has a running time exponential in the number of items.

Now we get to the 'Bound' part: we try to find criteria such that we can say 'this configuration never work out, so we might as well not bother computing this'. An example of such a criterion is 'the weight of the items we've already put in the knapsack exceeds $T$': if we've added, say, the first $n/2$ items to the knapsack and it is therefore already full, there's no point trying to put items $n/2+1$ through to $n$ in the knapsack as well, but there's also no point in trying to fit any subset of $n/2+1$ through to $n$ in the knapsack, as it's already full, so we save about $2^{n/2}$ cases. Another example is 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far'.

These criteria essentially cut away parts of the search tree: at some node, you say for instance 'the left subtree will not give me a better configuration, because X', so you forget about that subtree and you don't explore it. A subtree of depth $d$ that you cut out this way saves you $O(2^d)$ nodes, which can be quite a bit of a speed increase if you're lucky.

Note that this is called 'Bounding' because it usually involves some kind of lower or upper bound: for the criterion 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far', the value of your best configuration so far is a lower bound on the best configuration, so anything that will never make it past this lower bound is doomed to fail.

You can make the 'Bounding' part as complex as you like. For instance, integer programming problems are often solved using relaxations: you relax your program to a linear program, which you can solve in polynomial time, and then you can throw away a lot of cases for your binary variables that will never work out anyway. You then branch on the remaining options.

Note that Branch and Bound usually only gives you a speed increase in practice, but not in theory: it's hard to say exactly how much of the search tree is cut out using your heuristics. This is testified by the number of different heuristics used in practice on such problems. If you're unlucky, the remaining search tree remains huge even with a lot of bounding.


The expression $O(\max(n,m))$ is meaningful, and we even have $O(n) + O(m) = O(n+m) = O(\max(n,m))$.


Runtime analysis of a recursive algorithm with a tricky amount of work per recursive call

I can see three issues with what you have.

There are some inaccurracies in your sums. The outer one needs rounding of the upper boundary, the inner needs a $-1$.
$\displaystyle \sum_{i=1}^{\log(\sqrt{n})} \frac{1}{i} \neq \log(\log(\sqrt{n}))$

The true value of the sum is $H_{\log(\sqrt{n})}$ (will change slightly if you fix the sums). It's true that the difference vanishes in $\Theta$ if you go that route, but better not write equality where it does not hold.
You dropped the recursion at the end! You should have

$\qquad \displaystyle T(n) = T(2/3 \cdot  n) + \dots$

From there, unfold the recurrence:

$\qquad\begin{align*}
  T(n) &= T(2/3 \cdot n) + f(n) \\
   &= T(4/9 \cdot n) + f(2/3 \cdot n) + f(n) \\
   &\dots
\end{align*}$

Spot a pattern, guess the solution and prove it correct by induction! This part is well covered by our reference question in case you have trouble.


How to check equality between any two 2-dimensional arrays (dense matrices) with time complexity less than O(n*m)?

Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

It seems it would be easiest to store the previously seen matrices in a Trie. You can then test whether the given input matrix is equal to any of the previous matrices in $O(nm)$, regardless of how many previous matrices there are. This is the best you can do, since you must examine each element of the matrix at least once. You can't get an individual comparison to run faster than $O(mn)$, but you can test for equality among the entire set faster.


It's not clear to me what you want.

An OS can query the processor about its cache structure as long as the processor have the feature (for instance, X86 has this possibility tied with the CPUID instruction).

An OS could deduce the information from any mean of identifying the processor (nowadays something like CPUID, but in a given processor family there always had been more or less precise means to deduce which member your were running on, especially if you have access to privileged instructions as an OS does) and having hardcoded tables giving the sizes for each model.

Any program can try to measure the number of cache levels, their size, associativity, line size and latency.  What you have to do is measure the latency of memory accesses using well-thought-out patterns and plotting the the latency versus the total memory touched by the pattern.  You get some plateaus giving the latency of the cache, and the jumps positions give the cache sizes.  Comparing the results of different patterns give the associativity and the line sizes.  The more the cache is advanced (eviction buffers, pre-loading, ...) the more you have to be careful in the way the patterns are computed (a common technique is implementing the pattern as a pointer chase so that it is more difficult for the processor to guess the next address to be loaded) or you'll measure something different from what you want. Other factors to take into account is the effect of TLB, the presence of shared cache between cores and processors the load on the other cores, the effect of process migrations between cores by the OS, the effect of throttle by the OS or the hardware due to temperature or battery load.  In conclusion such measurements are pretty technical, and although you can deduce a lot of things it is better to have a preconceived notion of the memory structure and of the external factors which may have an influence.


Smallest DFA that accepts given strings and rejects other given strings

There is a lot of literature on learning DFAs given positive and negative samples. If $A$ and $B$ are finite I don't see how the problem would ever be undecidable though. If $A \cap B = \emptyset$ then obviously the DFA that accepts only the strings in $A$ satisfies your requirement and one can simply enumerate all smaller DFAs. If $A \cap B \neq \emptyset$ then clearly no such DFA exists.

Finding the minimum DFA consistent with a given set of strings is NP-complete. This result appears as Theorem 1 in Angluin's paper On the complexity of minimum inference of regular sets. So clearly your problem is also NP-complete.

For lots of good links and discussion on learning regular languages check out the CSTheory blogpost On Learning Regular Languages.


A number with k binary digits has at most k prime factors. That's because the smallest number with k prime factors is 2^k.

So given a number m with k binary digits you can easily be given a list of the prime factors of m. You can check that the product of these prime factors is indeed m in polynomial time easily. You can easily calculate the number of factors from the prime factors in polynomial time.

But what you also need to do is that the purported list of prime factors is actually a list of primes. Here comes another theorem that shows for every prime p, there is an easily verifiable proof that p is indeed a prime.

The oracle should contain a list of the prime factors, and for every item in the list an oracle for proving that it is prime.

For being in NP, there is absolutely no need that you are able to provide the oracle in polynomial time. You only need to be able to check it in polynomial time.


Polynomial time verification of Graph Isomorphism problem

The choice of function is done in nondeterministic polynomial time which is something you shouldn't try to "make sense of" in the real world.
It is a mathematical model of computing where we assume that the machine can perform many simultaneous operations, kind of in parallel, and if any of these operations "succeed", you get one of those answers out.

The point of this exercise is however that you show that Graph Isomorphism is contained in the complexity class NP by showing that you can solve the problem in nondeterministic polynomial time; by giving a nondeterministic algorithm for the problem.
The algorithm works as follows.  Nondeterministically pick the correct permutation $\pi$, and then in deterministic polynomial time we can verify that $\pi$ is indeed a witness or a certificate for the fact that the two input graphs are isomorphic, by checking that $\pi(v)\pi(u) \in E'$ if and only if $uv \in E$.
If $\pi$ is not a permutation that proves that the graphs are isomorphic, you can therefore conclude that the graphs are indeed not isomorphic.

It is important to stress that this does not give rise to an algorithm you can actually implement  in the real physical world, not without enumerating every permutation, at least, which as you correctly point out, cannot be done in polynomial time.


Does the following transformation preserve context-freeness?

Counter-example:

$L_1 = \{a^n b^n c^m \mid m,n \ge 1 \}$

$L_2 = \{a^m b^n c^n \mid m,n \ge 1 \}$

$L = (L_1 \cdot L_2^*) \cup \epsilon$ is context-free.

Any nonempty word $x \in L^\#$ has a prefix $p = a^n b^n c^m \in L_1$. It must be $n = m$, because due to $L_2$, any pair of a $b^+$ and a directly succeeding $c^+$ in $x$ (after $p$) must share the same exponent. Therefore:

$L^\# = (\{a^n b^n c^n \mid n \ge 1 \} \cdot L_2^*) \cup \epsilon$, which is not context-free.


Proof that {$a^m b^n$ | m!=n} is not regular

Suppose $L = \{ a^m b^n : m \neq n \}$ were regular. Then $a^*b^* \setminus L = \{ a^n b^n \}$ would also be regular.

There is a variant of the pumping lemma in which you mark certain symbols of your choice (at least as many as the pumping constant $p$), and then the pumped part is certain to contain at least one of these symbols (and at most $p$). Now consider $a^p b^{p+p!}$ for large enough $p$, and mark the $a$ part. We arranged things so that whatever the length of the pumped part (which must consist solely of $a$s), you can pump it to exactly $a^{p+p!} b^{p+p!}$.

Another possibility is to use the Myhill--Nerode theorem. The words $a^n$ ($n \in \mathbb{N}$) are an infinite set of pairwise inequivalent words: if $n \neq m$ then $a^n b^n \notin L$ yet $a^m b^n \in L$.

Take your pick...


Implementing primitive recursive functions in a programming language

You can prove by induction that the number of instructions executed by any given program is bounded (essentially since no command can create instructions). In particular, the number of arithmetic instructions executed by a program is bounded. This means that the output of a univariate function is polynomially bounded. Since the factorial function is not polynomially bounded, you cannot compute factorial.

If, however, we add a pget instruction which is similar to nget but gets a subroutine rather than a number then we can compute factorial, for example with the following program:

(postfix 1 1 (3 nget 3 nget mul 4 nget 1 sub swap 2 nget (3 pget 1 pget exec) () sel exec) 1 pget exec)


Term rewrite system is non-confluent, but cannot find different normal forms of term

$t(o,l)$ has two normal forms: $t(o,l)\to s(o)$ and $t(o,l)\to t(o,s(o))$.


Converting a greedy algorithm to a dynamic programming algorithm

The example you specified is not turning a greedy algorithm to a dynamic programming solution. You reduced a problem to another using a greedy argument and solved the other problem using dynamic programming. That is why it is still not clear to me what do you mean by converting greedy to dynamic programming. However, that being said I have three points to comment on this area, you might find the answer you are looking for among which.

The first one, which is not an answer, but an important notice, is that even though you suggested a (dynamic programming) solution of independent sets, this dynamic program has to consider all partitions of the vertices to find an optimal set. There is probably no dynamic programming solution to this problem that runs in polynomial time, since this will mean that P=NP due to the fact that the maximum independent set problem is NP-complete. However, even though we expect the running time to be exponential, you can solve the problem using only polynomial memory using for example the inclusion exclusion principle (refer to Parameterized algorithms book by Cygan et. al.).

Now back to your question, dynamic programming is usually used to solve generalized versions of greedy problems. For example maximum independent set, maximum matching and minimum dominating set can be found in linear time on trees using greedy algorithms. Greedy algorithms fail however, if the tree is weighted and we are looking for the structure optimizing the total weight. However, these problems can easily be solved in a bottom up dynamic programming manner in linear time, where the dynamic programming states are the subtrees of the given tree.

The third and probably the more interesting part, many problems (even some NP-hard ones) in general graphs admit a dynamic programming solution on the tree decomposition of the given graph. The optimal solutions still  have exponential dependence on the tree width. However, they have only polynomial/linear dependence on the size of the input. Usually these problems admit greedy/dynamic programming algorithms on trees, since these algorithms use the fact that a tree decomposition decomposes the graph into small separators, which is trivial in trees. (Again refer to Parameterized Algorithms book by Cygan et. al.)


Fundamental idea of this memory denial of service simulation using array copy?

The idea is that this code does not copy the complete array, but due to the design of the memory hardware it takes just as much time as if it would. Reading and writing a single byte will move a whole cache line. So the code reading and writing does very little work, but causes the memory subsystem to perform a whole lot of work.


Reducing optimization problem to decision problem

Given the formulation of your decision problem, first of all notice that you can do binary search to find the max-cut weight $k$, rather than linear search. Secondly, when you test each edge, you get that either the two end points are in the same set, or the two end points are in different sets. Let $S$ be a set on one side of the cut, and let $x_u,x_v$ be boolean indicator variables for whether $u,v$ are in $S$. Then if edge $(u,v)$ crosses the cut, you want $(x_u,x_v) = (1,0)$ or $(0,1)$, and otherwise you want $(x_u,x_v) = (0, 0)$ or $(1,1)$. You can formulate this as a 2-sat problem and solve it in linear time (linear in the number of edges) to determine membership in set $S$. For example, if $(x_u,x_v) = (0, 0)$ or $(1,1)$ then you would add the two clauses $(x_u \vee \neg x_v) \wedge (\neg x_u \vee x_v)$ to your 2-sat formula.


reducing $CLIQUE$ from decision to search problem

Keep removing vertices until the graph no longer contains a clique of size $k$, and let $v$ be the last vertex that you removed. It follows that there is some $k$-clique which contains $k$. Remove all vertices from the graph other than neighbors of $v$ (so $v$ itself is also removed), and recursively find a $(k-1)$-clique in the new graph. Add $v$ to this clique to create the desired $k$-clique.

The algorithm can also be formulated iteratively:

Let $C = \emptyset$ (this will be the clique).
Let $\ell = k$ (the current size of the clique).
Go over all vertices $v$ in the graph:

Check if after removing $v$ from the graph, the new graph still contains an $\ell$-clique.
If so, continue to the next vertex.
Otherwise, add $v$ to $C$, decrease $\ell$, and remove from the graph all vertices other than the neighbors of $v$.

Return $C$.


Solving membership problem for a PDA-generated language without converting the PDA to a CFG

Yes, it is possible.   Given a pushdown automaton $P$ and a word $x$, you can easily construct a new pushdown automaton $P'$ such that $L(P') = L(P) \cap \{x\}$.  This works by using a product construction to expand the finite-state control of $P$ by a factor of $n$, where $n$ is the length of $x$.

Now, you can test whether $P$ accepts any non-empty word.  One way to do this is by computing the set of all reachable configurations of $P$.  This set is an infinite set, but it turns out to be a regular set, and you can construct a finite automaton that represents the set of reachable configurations.  One way to do that is using an algorithm for computing post*; see Section 2.2.2 of Analysis Techniques for Information Security, by Anupam Datta, Somesh Jha, Ninghui Li, David Melski, and Thomas Reps.  (You can view this as an improvement to Tomita's algorithm that works for arbitrary PDAs, not merely the ones that arise from a LR(k) parser.  Cycles are not a problem.)

This may be morally isomorphic to converting $P$ to a context-free grammar, intersecting that grammar with the regular language $\{x\}$ using the product construction, and then using standard algorithms to test whether that generates a non-empty language.  That in turn may be morally isomorphic to converting $P$ to a context-free grammar and then using CYK parsing.

The running time of all of these methods is $O(n^3)$, so while the algorithm looks different on paper, it does not lead to any improvement in running time.  The PDA-based approach does have the advantage that it is easily adapted to on-the-fly processing of the word $x$.


The board you want to draw is a planar graph whose faces (enclosed areas between edges) are the polygonal tiles: call this $G_\mathrm{b}$. The data structure you have in memory is a graph $G_\mathrm{m}$ whose vertices are the tiles and whose edges are the adjacency relation on the tiles. This graph is known as the dual of $G_\mathrm{b}$.
So, you need to compute the dual of $G_\mathrm{m}$ and use one of the algorithms for drawing planar graphs to draw that.

One possibe headache is that duals are not uniquely defined, as the Wikipedia article shows, so you might need to be careful to get the "correct" dual for your application. If you can't get that to work, another option would be to use a graph drawing algorithm to draw $G_\mathrm{m}$ and then obtain the board by using the perpendicular bisector of each edge.


I don't know the relative sizes and the nature of your problem, these details could completely change the view. But generally, if the only thing you have at your disposal is a small set of test documents, I would not recommend using that for term weighting at all. A small set of documents would give you an illusion of coverage, a skewed set of weights that would not accurately cover the domain.
If you do have general access to the IR system, though, you could try using the system itself for obtaining statistics by hitting it with random words and recording the number of search results, for example.


The bitwise and of the bet and result is nonzero if and only if the bet is winning.
Further, the bitwise and has exactly one bit set if the bet wins.

To see this, note that the encoding of a bet has bit $1$ set iff it wins if the home team wins, bit $2$ set iff it wins if the game is a draw, and bit $4$ set iff it wins if the away team wins.

For example, if our bet is 6 - draw or away team wins, its binary encoding is 110. Then if the away team wins, the result is encoded as 100 and the bitwise and is 100. If the home team wins, the result is encoded as 001 and the bitwise and is 000.

In the word-ram model this can even help us calculate the result asymptotically faster: if the encodings of the bets and results are stored consecutively in binary with 3 bits per number, then counting the number of bits in the bitwise and of these two sequences gives the number of won bets in $\mathcal{O}(\frac{n}{w})$ with $w$ bits per word. Similarly all winning bets could be found in $\mathcal{O}(\frac{n}{w} + r)$ where $r$ is the number of winning bets. Of course this assumes the representation of the data is convenient for us, if it isn't, we need $\mathcal{O}(n)$ work to change its representation.

For example, the bets [3, 6, 1] and results [4, 2, 1] would be represented as 110011100 and 001010100 respectively, the bitwise and of which is 000010100. This indeed has two set bits corresponding to the two winning bets.


Can product DFA for intersection of two disjoint languages be minimal?

No.

Counterexample:

Let alphabet $\Sigma = \left\{ 0, 1 \right\}$, languages $L_1 = \left\{ w0 \,\middle|\, w \in \Sigma^\ast \right\}$ (i.e. the last digit is $0$), $L_2 = \left\{ w1 \,\middle|\, w \in \Sigma^\ast \right\}$ (i.e. the last digit is $1$). Note that $L_1 \cap L_2 = \emptyset$.

Then the following DFAs $M_1$ and $M_2$ are minimal for $L_1$ and $L_2$ respectively:

And the cross product of $M_1$ and $M_2$ (for the intersection of languages) is:

But this is not minimal for the empty language. A minimal DFA for the language is:

In fact, cross-product DFA of $M_1$ and $M_2$ recognizes an intersection of languages $L(M_1) \cap L(M_2)$ (if a state of cross-product DFA is accepting when the original two states are both accepting on original DFAs). So in this case a generated cross-product DFA always recognizes the empty language. Since a minimal DFA for the empty language has only one state and cross-product DFA has ((#states of $M_1$) × (#states of $M_2$)) states, almost all cross-product DFAs are non-minimal.

Also, even though if you define a state of cross-product DFA is accepting when either of the original two states is accepting, the above $(L_1, L_2)$ is a counterexample. Since $L_1 \cup L_2 = \Sigma^\ast$, the minimal DFA has only one state.


Derive a while loop runs in $\Theta( \sqrt{n} )$

Each time add $i$ to $s$ and increase $i$ by one, up to reach to $n$. Hence, if you find the $k$ such that $s = 0 + 1 + 2 + ... + k$ be equal to $n$, you can find the number of running loop. As $1 + 2 + \ldots + k = \frac{k(k+1)}{2}$, you need to solve this equation $\frac{k(k+1)}{2} = n$.

$$k^2 + k -2n = 0 \Rightarrow k = \frac{-1 + \sqrt{1+8n}}{2} = \Theta(\sqrt{n})$$


Is it possible to achieve greater than perfect compression using machine learning and big data?

Is it possible to achieve greater than perfect compression...

No.  Any lossless compression scheme that makes at least one string shorter must make at least one string longer. This is an unavoidable consequence of the simple fact that there are more long strings than short ones.

The best you can do is be smart about what strings get made shorter, and I guess that's what you're trying to do with machine learning, big data, and any other applicable buzzwordstechnologies. Effectively, though, you're trying to use a big global dictionary.  This is probably less efficient than standard dictionary compression which builds up the dictionary from the data that's being compressed (a dictionary containing lots of Spanish and Chinese isn't going to be useful for compressing Stack Exchange, for example). Also, if you're going to cut network traffic, that big global dictionary needs to be already sitting on your computer, taking up huge amounts of space for dictionary entries you'll probably never use.
Indeed, if that huge dictionary comes as part of my next Chrome update, it's not even obvious that there'll be a net saving in data transfer.


Finding a $g(n)$ so that $f(n) = O(g(n))$

For any $f$ we have $f \in O(f)$ i.e. trivial answer to your question is $g=f$.  Presumably  you need  to clarify more exactly conditions on $g$. On other hand if we change all members of sum with maximum one, then we have $f \in O(n^{28})$.
Now about questions:

$c$ is independent from $n$ by definition
outgoing from 1. you cannot consider $c = (n-1)n^{5}$


If a sparse language is NP complete, then are all languages in NP in P/poly?

Yes, see Mahaney's theorem. It states that if a sparse language is $\mathbf{NP}-$complete, then $\mathbf{P=NP}$, and since $\mathbf{P\subseteq P_{poly}}$, then $\mathbf{NP\subseteq P_{poly}}$


Finding maximum rectangular frame in array of zeros and ones

Yes, it is solvable in $O(\max(m,n)^3)$ time.  In fact, it should be solvable in $O(\min(m,n)^2 \max(m,n))$ time -- e.g., if $m<n$, it should be solvable in $O(m^2 n)$ time.

Let $N_\text{down}(i,j)$ denote the number of cells that you can go down, starting from $(i,j)$, without encountering a zero.  Similarly, let $N_\text{right}(i,j)$ denote the number you can go right.  You can precompute all of these values in $O(mn)$ time.  Do you see how?

Now, I'm going to give you some hints, to help you solve this on your own.  Hint #1:

   Suppose I told you that the left side of the rectangle is at column $j_0$ and the right side is at column $j_1$.  Could you find the top and bottom sides of the rectangle with maximum perimeter?  How efficiently could you find it?

Hint #2:

   Continuing from Hint #1 -- can you identify some necessary and sufficient conditions to recognize the upper-left corner of the rectangle, $(i_0,j_0)$?  What would have to be true about the $N_\text{down}$ and $N_\text{right}$ values?  Similarly for the lower-left corner.

Hint #3:

   Try a linear scan downwards in those two columns.  In fact, all you need are the $N_\text{right}$ values.


Why aren't computables used for numerical calculations?

It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased precision. But, for almost all applications, 64-bit floating point is more than enough and the speed of being able to do calculations with single CPU (or GPU!) instructions is a huge win.


In order to express $x = \lnot y$ in CNF form, you add the clauses
$$
x \lor y, \lnot x \lor \lnot y.
$$
In order to express $x = y \lor z$ in CNF form, you add the clauses
$$
\lnot y \lor x, \lnot z \lor x, \lnot x \lor y \lor z.
$$
In order to express $x = y \land z$ in CNF form, you add the clauses
$$
\lnot x \lor y, \lnot x \lor z, \lnot y \lor \lnot z \lor x.
$$


A vector-like data structure with allocation table; O(1) indexing time required

The indexing time is always O(1) for an array whether you reallocate or not! Reallocating is not a bad idea if the table size doubles each time the array overflows, insertion takes constant time amortized.

Your idea is no different from a linked list of arrays of fixed size (correct if I'm wrong). If the list gets really large, looking for an element will take a lot of time.


LL(k) Prediction Techniques (and Insight on method applied)

It turns out someone wrote half a book about LL(k) parsing, which wasn't mentioned on Wikipedia until I added it a coupe of minutes ago.

Parsing Theory: LR(k) and LL(k) Parsing by Seppo Sippu; Eljas Soisalon-Soininen (1990).

I've looked briefly through it and it does have LL(2) examples too.

EDIT: As rici says below, this is the 2nd volume of a two-book series by the same authors; the first volume in the series is titled Parsing Theory: Languages and Parsing (1988).

And you can obviously find some level of info on LL(k) in most compiler books, but Sippu and Soisalon-Soininen have the most extensive treatment I found of LL(k). More recent introductory textbooks generally punt the proofs on anything to do with LL(k) with to Sippu & Soisalon-Soininen's 2nd volume.

LL(∗) however is not covered by Sippu & Soisalon-Soininen (as far as I can tell), but that's probably understandable given the book's age. For LL(∗) the 2011 ANTLR PLDI paper is probably the best reading.


Use the pumping lemma to prove that {www} is not context-free

You could take $w = a^m b a^m$, then you have that $uvxyz = a^m b a^m a^m b a^m a^m b a^m$
$vy = a^l$ with $1\le l\le m$ since there can't be more than one $b$, so you can't pump the $b$.
Since $vy$ can only contain $a^m$ without any $b$'s, it will obstruct the balance between the other $a^m$'s.
We've found a contradiction while applying the pumping lemma so the language is not Context-Free.


Finding a Hamilton path in a Complete Euclidean Graph is in P

This assertion is, in fact, true. A complete graph (which doesn't even have to be Euclidean) always has a Hamiltonian path: number the vertices in an arbitrary order, start at the first one, then proceed in order to the last (and then back to the first to make a cycle if you want). Since the graph is complete, the edges you need will always exist.

Thus, the problem can be decided in $O(1)$, which is polynomial, so it is in $P$. The algorithm is trivial:

define doesThisCompleteGraphHaveAHamiltonianPath(G):
    return Yes


How much bits need to add to 100bit of data in order to correct up to 10bits?

This seemingly innocent question, is actually quite difficult to answer. Let me try to give some more information on the parameters that get into the game here, and give a partial survey of common results and bounds.

As mentioned in Qalnut's answer, to deal with $10$ bits of errors (in the worst case) we must have distance at least $d=2\cdot 10+1$. This is given. Another parameter that is implied by your question is that the basic unit is a bit. You ask, what is the minimal length $n$ of a (binary) code that has distance $d$ and contains, at least $2^{100}$ codewords.

The lower Bound

Let's first try to ask a slightly more general question:

  Given an alphabet of size $q$, what is the maximal number of codewords in code of length $n$ that has minimal distance $d$. [Let's denote this number by $A_q(n,d)$].

The answer to this question is not simple at all, but there are several well known bounds. One very useful bound is the singleton bound, which states that
$$ A_q(n,d) \le q^{n-d+1}$$

This immediately tells us that in order to have $2^{100}$ codewords with distance $d=21$, you must take $n>120$, that is, to add at least 20 bits. But this is only a bound, it never says that such a code (with length 21) actually exists, or how to find it.

More generally, this bound tells us that the relation between the rate of the code $R=n/k$ and the relative distance of the code $\delta=d/n$ behaves, for $n\to \infty$, as
$$ R \le 1-\delta + o(1)$$

Since you wished the relative distance of your code to be $d/n =0.175$, the maximal rate is $\approx 0.825$, which is exactly what we got ($k/n = 100/120 = 0.833 = 0.825 + 1/n)$. The moral of this story is: if you aim for distance $\delta$ (which can correct $\approx \delta n /2$ errors), you will have to add at least
$$(n-k) = n-Rn \approx \delta n $$
more symbols. This is a nice rule of thumb. In the asymptotic case (that is, when $n$ is very very large) that would be approximately the answer.

As said, this bound is, in many cases, not really tight. For other lower bounds, look for the Plotkin bound (for binary codes) and the Johnson bound.

The upper bound

So we know we can't get $n$ smaller than, say, 120. But this is not very helpful from a practical point of view, since we don't even know if a code with $n=120$ exists, or maybe in this case the first code with $d=21$ and $k=100$ shortest $n=137$??

Gilbert and Varshamov come to our help, and show that there always exists a code for which
$$ A_q(n,d) \ge \frac{q^n}{\sum_{j=0}^{d-1}\binom{n}{j}(q-1)^j}$$

So now you just need to plug in $A_q(n,21)=2^{100}$ and find $n$. Let me WolframAlpha this for you, it gives $n<189$ (actually, a tighter version of the GV bound for binary code will gives $n\le 185$. The GV bound even tells you how to find this code, in a greedy way (thus, doesn't expect it to be efficient).

The "answer"

As I said, the real answer may be difficult to find, and depend on $q$ (why are you so fixed on binary codes? maybe considering the message as symbols of a larger alphabet would give a better code? But then the noise pattern need to be properly defined, so I'll skip this explanation here), and on $k$ (why 100 bits? ain't 127 bits make much more sense?), and on efficiency (which you asked, but I will not get into), etc.

The bottom line, is that many people thought on such questions over the last century, for various parameters. The problem is to find the code you need. For this purpose you can look at some Code tables that aggregate codes of various parameters.

For instance, for short binary codes, there is this work,
"Bounds for binary codes of length less than 25" (IEEE Trans. Inform. Theory 24:81-93, 1978).
A more extensive list can be found, for instance, at
Code Tables: Bounds on the parameters of various types of codes. Searching in Table of Nonlinear Binary Codes for a code with the parameters you gave in your question, I found that the shortest code for distance 21 that has at least $2^{100}$ codewords has length $n=191$. The reference is H. J. Helgert and R. D. Stinaff. "Shortened BCH codes", IEEE Trans. Inform. Theory, 19:818--820, 1973. Damn, this is worse than the GV bound, but it allows you to code messages of up to $k=116$ bits!
instead, If you are willing to settle with messages of length $k=91$ bits, you will be able to do that with $n=173$ bits. (M. Kasahara, Y. Sugiyama, S. Hirasawa, and T. Namekawa., IEEE Trans. Inform. Theory, 22:462--468, 1976). Using this table for linear binary codes, there is a constructive code with $k=100$ and $n=176$. There references are inside this link.

So back to you innocently looking question: the answer(1) is 76.

(1) At least, the best answer I was able to google.   (ADDENDUM, found a better one:) and re-google.


Yes, it can.

You have $n-1$ edges, which means $2n-2$ holes for node-pigeons. If every node is supposed to have degree two (or more), we have to place (at least) two pigeons for each node, that makes a total of $2n$ pigeons.

By said principle, (at least) two pigeons do not find a solitary hole, which means (at least) one node is isolated or (at least) two nodes have only one edge. As no node is isolated by assumption, you have (at least) two nodes with degree one.


What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?

Every problem in NP can be decided in exponential time (and so it is recursive). Recall that one of the definitions of NP goes via witnesses:

  A language $L$ is in NP if there is a polynomial $P$ and a predicate $f$ computable in polynomial time such that $x \in L$ if and only if there exists a "witness" $y$ of length at most $P(|x|)$ such that $f(x,y) = \mathrm{True}$.

(A predicate is a function which returns True or False.)

Let's suppose that $y$ is in binary.
Given an input $x$, in time $2^{P(|x|)}$ we can go over all potential witnesses $y$, and for each of them calculate $f(x,y)$. If $f(x,y) = \mathrm{True}$ for any of them, then $x$ is in $L$, and otherwise $x$ is not in $L$.


number of random sets needed to generate subset

The sets $B_i$ can be independent but still have an intersection; just because they are generated independently doesn't prevent them having an element in common (in fact, it ensures that possibility exists).  If you assume that the sets $B_i$ are generated independently, then they are independent, period.  If you don't assume that, you have to define how you assume that they are generated before you can calculate any probabilities.

Regarding your updated question: "But doesn't ... ?"  - Answer: No, it doesn't.  If the r.v.s $B_1,B_2$ are independent, then the events $B_1 \not\subseteq A$, $B_2 \subseteq A$ are independent.

If you want a formal proof, here is one.  If $B_1,B_2$ are independent random variables and $f$ is any function, then $f(B_1),f(B_2)$ are independent random variables.  (You should try to prove it; it is not hard.) Then let $f(X)$ be true if $X \subseteq A$, or false otherwise, and the claimed result follows.


Recommender System - Binary Ratings without explicit dislike

You can use one-class classification, in which the learner is given only positive examples, but must later on classify new instance into positive and negative. An example is intrusion detection – the learner is given the network in its working state, and tries to identify outlying behavior.


Representing a network with two types of connections: A fishing application

Sure, of course.  You can define a matrix to contain whatever numbers you want it to contain.  There's nothing that prevents you.  The real question is whether the result has the properties you want it to have, but since you haven't listed any properties, there's nothing to answer here.


Research on evaluating the performance of cache-obliviousness in practice

You've already covered background research on cache-oblivious algorithms quite well. In terms of benchmarking and practical results, I see this recent paper by Intel as an interesting read:

A Synergetic Approach to Throughput Computing on x86-based Multicore Desktops


So, you have to be very careful to distinguish values, and the types of those values.

We say $v : T$ when $v$ is a value with type $T$.

The type Number

When people say "Number" is a type, usually they're referring to the type of natural numbers. But each number isn't a type, it's a value, and $Number$ is their type. So we can say $1 : Number$, $2 : Number$, etc.

Notation isn't always consistent. Sometimes people will refer to $Number$ as a type class that contains $Nat, Int, Float$ etc. But that's more complicated.

Now, as for each number being a type, in a language like Haskell (or any Hindley-Milner lanugage), this isn't the case, because numbers are values, and types and values are separate.

But there are a few ways we can look at this

Numbers as singletons

But using dependent-types or GADTs, in a Haskell, Agda, Idris, or other languages with advanced types, you can form a type like this (using Agda-like pseudocode):

data TypeNat : Nat -> Set where
  TZero : TypeNat Zero
  TSucc : {n : Nat} -> TypeNat n -> TypeNat (Succ n)

For any number n, TypeNat n is a type, containing exactly one value, the TypeNat representation of n.

So here, the number isn't the type, but there's a 1:1 correspondence between the numbers and the types.

Numbers to Quantify other things

We can use numbers to quantify things, but in a dependent-type system, usually this is done by indexing types.

So you can have a type like Vec a n, which is the type of Vectors containing exactly n elements of type a. So here, our types are indexed by numbers, but the number itself is not a type.


Why is this language a regular language?

This is not an union of two regular languages! It's a concatenation. Note the difference,

Union: $L_1 \cup L_2$
Concatenation: $\{ab : a \in L_1 \wedge b \in L_2\}$.

That said, your other observations are correct, and indeed the concatenation of two regular languages is also regular itself. You can prove this by  constructing two NFAs for the regular languages and connecting the accepting states of $L_1$ to the starting states of $L_2$ by an $\epsilon$-transition.


Has anyone seen a NP graph problem like this before?

This is known as the distance-$d$ independent set, i.e., you are looking for an independent set of size $k$ where the distance between every two elements in the solution is at least $d$.

The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids.

Regarding reductions, you can probably take the $d$'th power of the graph and find a (distance-1) independent set in that. The claim is that any solution here is a distance-$d$ independent set in the original, but you need to verify this.

[1] Eto, Hiroshi, Fengrui Guo, and Eiji Miyano. "Distance-$d$ independent set problems for bipartite and chordal graphs." Journal of Combinatorial Optimization 27, no. 1 (2014): 88-99.


Yes, or maybe no, depending on your definitions. Commonly some small 8-pin SPI NOR-Flash ROM is used, for example my slightly older motherboard has a W25Q64FV. This replaces the older non-flash based EEPROM technology since Flash is cheaper, but it fills the same role, and often the flash versions are still called EEPROM. Since it's Flash memory, you could call that "not ROM", if your definition of ROM excludes Flash.
An other problem with relying on a disk is that a disk cannot come pre-programmed correctly. It needs to contain code specific for the motherboard, and be pre-loaded with microcode for the various diffent CPU models supported by that motherboard (which is why recently AMD motherboard manufacturers had some trouble). A disk does not know which motherboard it ends up in, so it cannot fill this role.


Finding a graph where the edge set satisfies a set of integer equations

You are asking two questions.  I will answer the first one.  Your first problem is NP-hard, by reduction from exactly 1-in-3 positive 3-SAT.

Let $\varphi$ be a positive 3-CNF formula with $m$ clauses and at most $n^2$ variables $x_i$.  Label each edge $(v_i,v_j)$ with a distinct variable $x_{ij}$.  Each set $S_i$ will correspond to a clause of $\varphi$ as follows: the set $S_i$ contains one edge $(v_i,v_j)$ for each variable $x_{ij}$ that appears in that clause.  Let $k_1=k_2=\cdots = k_m=1$.

Now the resulting system of linear equations has a solution if and only if $\varphi$ has an assignment where every clause has exactly one of its three variables set to true.


$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

A proof technique is (informally) relativizing if the results it generates also hold relative to an oracle. Not all proof techniques are relativizing. Perhaps the best known example is $\mathsf{IP}=\mathsf{PSPACE}$, which uses the technique of algebraization. Although $\mathsf{PSPACE} \subseteq \mathsf{IP}$, there is an oracle $O$ such that $\mathsf{PSPACE}^O \not\subseteq \mathsf{IP}^O$ (see this question on cstheory).