Oracle Relations Between Complexity Classes

You seem to understand the concept even though you described it wrong.    Unless exactly one of {A,B} is uniform, an oracle separation of A from B either means  [showing that there is an oracle O such that  AO ≠ BO ] ,  or means [exhibitings an oracle O such that  AO ≠ BO ].

Yes, it is "not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle".  In particular, most hierarchy theorems relativize.  However, it is the case "that for any two complexity classes we can always construct" a class-oracle "such that they are equivalent in relation to that" class-oracle.  (For example, this one always does that.)  The triangle levels do not have complete sets with respect to syntactic subclasses of R, and each other non-computable level is not low for itself.

Given "two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$," it is indeed "not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$," even though "the arithmetic hierarchy doesn't collapse".  See two sentences before this sentence.


The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar
$$
S \to w_1 \mid w_2 \mid \cdots \mid w_n.
$$


Are there polynomial time reductions where the corresponding witnesses can't be translated in polynomial time?

The proof of the Cook-Levin theorem shows that any problem in NP can be reduced to SAT in such a way that witnesses to the original problem can be converted efficiently to satisfying assignments of the resulting SAT instance. The proof of the NP-completeness of 3-colorability goes via a series of reductions, each of which also has this property.


Computing set difference between two large sets

If you are willing to store the sets in a specialized data-structure, then you can possibly get some interesting complexities.

Let $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Then you can do set operations $A\cup B, A\cap B,A\setminus B$ and $A\Delta B$, each in $\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$ expected time. So essentially, you get the minimum size of the two sets, or, the size of the symmetric difference, whichever is less. This is better than linear, if the symmetric difference is small; ie. if they have a large intersection. In fact, for the two set-difference operations you want, this is practically output-sensitive, since together they make up the size of the symmetric difference.

See Confluently Persistent Sets and Maps by Olle Liljenzin (2013) for more information.


Prove: Every decidable set is Turing reducible to the empty set

You're trying to prove something, so you need to use something closer to an actual definition of Turing reducibility. The statement you quote from Sipser is an intuition about what reductions do, but it's not precise enough to let you solve problems.

Here's an informal definition of Turing reducibility that lets you start to reason about what it can do.

  A set $A$ is Turing-reducible to a set $B$ if, assuming the existence of a subroutine that determines whether its input is in $B$, we can write a program that determines whether its input is in $A$.

We're considering $B=\emptyset$, so we need to assume the existence of a subroutine that determines whether its input is in $\emptyset$. Well, that's not much to assume. Here's the subroutine:

 return false

OK – we don't need to assume anything: we know this subroutine exists.  So now, we just need to show that every decidable set is Turing reducible to $\emptyset$. That is, we need to show that

  For every decidable set $A$, we can write a program that determines whether its input is in $A$.

So... what's the definition of decidable?


NP-hardness proof, what is wrong with it?

No, you cannot prove that the unweighted problem is NP-hard in this way.  The error is that you cannot reduce WP to P in polynomial time (without proving P=NP).

Remember what the input to each problem is. For WP, you are given a list of $w_i$ and $p_i$ and must choose a setting of the $x_i$. So once I am given a fixed list of $w_i$ and $p_i$, I would need to come up with an instance of P (which is just a list of $p'_i$) so that the solution tells me the solution to WP.

The key point is that you seem to say that we can just take all $w_i = 1$ to reduce WP to P, but we can't change the $w_i$: They are given as part of the input. It is true that P is the special case of WP where all $w_i = 1$, but the issue is, when we are given an instance with $w_i \neq 1$, we have to solve this instance and we can't change the $w_i$ we are given.


What is the LTL expression for "there is a value of y whose next value is 8"?

The important thing that is missing from your question is how you model your program, and specifically, what are the atomic propositions you allow.

If your atomic propositions are "y=0",...,"y=8", and your transition system is modeled accordingly, then the formula $FX y=8$ means the eventually, the next position would have "y=8". Note that this is equivalent to the formula $XF y=8$, which basically says that y=8 sometime after the first position.

However, you phrased your requirement as "there is a value of y whose next value is 8", and it's not clear what this means. What is the "next value of y"? LTL does not recognize y as an entity, only the propositions mentioned above. So you cannot really talk about values of variables in LTL, without first adding all possible values as propositions.


Witness length independent $\exists$-Operator

You don't need a witness at all. You can allow the Turing machine to make a non-deterministic "guess" at any time. A string is accepted iff there is a sequence of guesses that make the Turing machine accept it, otherwise it is rejected.

Edit: If you want a definition which does not rely on the machine model, then it would be a bit awkward. Here is one example, which includes a cheat - using the associated function class. Given a (time) complexity $C$ and its associated function class $FC$, the allowed witness lengths are parametrized by $f \in FC$: the lengths are given by $n \mapsto |f(0^n)|$.


The running time of a library function depends on the way the library function is implemented. Moreover, oftentimes it is worthwhile to code non-optimal algorithms, since for practical $n$ they might be more efficient. One good example is matrix multiplication, where the fancy algorithms are slower in practice than optimized versions of the trivial one.

In your specific case, my guess would be that they implemented the textbook solution. You can always try looking at the source code. Another possibility is timing the function for various $n$, and see if the running time scales like $n^3$.


If you want a practical answer: with Intel SGX, the answer seems to be a qualified yes, but software development is likely to be more painful.  (Similar with a TPM, though that will be even more annoying.)  See, e.g., https://security.stackexchange.com/q/2459/971.

If you want a theoretical answer: in theory, you could use various cryptographic schemes for outsourcing computation (e.g., fully homomorphic cryptography, secure multiparty computation, SNARKs, outsourcing computation, and so on).  As a general theorem, any computation you can do in polynomial time, could also be done on the remote server in polynomial time, with ability to verify that the result it gives you back is correct in polynomial time.  However, in practice right now these schemes include an enormous performance overhead (a factor of a million slowdown or more), except for certain special tasks, so they're not at a stage where you could actually use them in practice today.


I assume you want the fingerprint to be as small as possible. Then this is the Hitting Set problem: For each person, make a list of all books liked by X but not by this person. Then, the goal is to select at least one book from each list. The problem is NP-hard, so you can't expect to find an algorithm that always solves it optimally in polynomial time. The greedy algorithm has a bad theoretical worst-case bound, but often works quite decent in practice. If you want to solve it optimally, an Integer Linear Programming solver should be able to solve instances of up to 1000 or maybe 10000 books. If you give more details on the size and structure of your instances, we could suggest other approaches.


Does an abstract syntax tree have to be a tree?

The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.

The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and processor speed, but also because it is simpler to reason about. Then subsequent phases decorate the parse tree with additional information.

There are such things as graph grammars, though I don't know whether they are used for parsing programming languages.


How to get the expected time complexity of while loop?

You should calculate the probability that the while loop runs exactly $k$ times, for $k\in\mathbb{N}$.
Then the expected number of loops is $\sum\limits_{k=0}^{\infty}k\times\mathbb{P}(\text{loop runs }k\text{ times})$.


L = { | M is a TM and halts on every input after 5 steps exactly } - is L decidable?

It is NOT NECESSARY to read the whole input for a Turing Machine to halt.

Imagine a Turing Machine M that receives any input such that it reads anything and moves right exactly 5 times. On fifth step it reaches the accept state and halts.

M belongs to L.

Contrary to what I was thinking before, L is indeed decidable.

Consider all Σ $^5$ configurations of the first 5 cells of the tape. For each of these configurations execute 5 steps. If TM is nondeterministic execute 5 steps for all possible paths. If TM does not halt for some configuration (or execution when TM is nondeterministic) reject. Otherwise, accept.

As  Σ $^5$ is finite, L is decidable.


Someone explain the Venn diagram for the logic equation (A+B)(B+C)

The misunderstanding here is the same as in your previous question. If $B$ is true, the formula is true whatever the values of $A$ and $C$ are. This means that the whole of the $B$ circle needs to be shaded.  Shading just the part at the top corresponds to saying "The formula is true if $B$ is true and $A$ and $C$ are both false." That is certainly true, but it's not the whole story.

For example, your proposed shading says that the formula is false if $A$ is true, $B$ is true and $C$ is false. But the formula is true in that case! You must shade every region of the diagram that makes the formula true. In this case, that means every region in the $B$ circle, and also the intersection of the $A$ and $C$ circles.  (Corresponding to, "The formula is true if $B$ is true, or if $A$ and $C$ are true, or both.")


what is the significance of the word "Sub-problems" in Greedy Method?

Here is a concrete example, the problem of Set Cover:

  Set Cover

  Input: Sets $S_1,\ldots,S_m$ whose union is $U$

  Output: Minimal-size subset of $\{S_1,\ldots,S_m\}$ whose union is $U$

The well-known greedy algorithm for this problem (which gives a $\ln n$ approximation) proceeds as follows:

While $U \neq \emptyset$:

Add to the solution the largest set $S_i$.
Remove all elements of $S_i$ from all sets and from $U$.

Having chosen a set $S_i$, we are effectively moving to another Set Cover instance, in which the sets are $T_j := S_j \setminus S_i$, and the universe is $V := U \setminus S_i$.

This new instance is the sub-problem mentioned in your statement. The greedy choice — largest set — is the local choice mentioned in your statement.

To check your understanding, show that this view is appropriate for other well-known greedy algorithms such as Huffman encoding and the greedy algorithm for interval scheduling.


How can I solve this constrained assignment problem?

This can be formulated as an instance of minimum-cost flow problem.  Have a graph with one vertex per agent, one vertex per task, and one vertex per category.  Now add edges:

Add an edge from the source to each agent, with capacity 1 and cost 0.
Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.
Add an edge from each task to the category it is part of, with capacity 1 and cost 0.
Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks.  There are polynomial-time algorithms for that.


Each program in the system is in one of three states: running (currently using the cpu), waiting (for i/o), or ready (not waiting for i/o, but not currently using the cpu).  When discussing scheduling disciplines jobs are not programs, rather each burst of cpu usage  between i/o requests in a program is a job.

First-in-first-out (FIFO), round-robin (RR) and shortest job first (SJF) are scheduling disciplines for choosing the next job to run from the ready queue of the operating system.  So in all three cases the jobs under discussion correspond to the set of processes that are currently in the ready state.

In FIFO as each job reaches the head of the queue it gets the cpu, when the job requests i/o then it is done.  The process (not the job) enters state waiting.  When the i/o is done the process is moved from state waiting to state ready, and the job corresponding to its next burst of cpu is put on the back of the FIFO queue.

A cpu bound process is one where the average cpu bursts (the jobs) are much longer than the average time spent waiting for each i/o.  Since FIFO is non-preemptive when a long cpu-burst gets to the head of the queue and starts running, all of the ready processes in the queue behind that job are stuck.

In round-robin we are also referring to jobs, not processes.  When a job requests i/o it is done.  When the process goes from waiting to ready the next job (cpu burst) from that process joins the round-robin queue.

Non-preemptive shortest job first is only practical if you really have future knowledge about exactly how long the jobs are.  If some jobs are taking longer than you expected and you aren't preempting them, then you're not really running the shortest one first.

In general scheduling disciplines are only looking at the jobs in the ready queue.  One of the points of SJF, though, is to make sure that the i/o system is kept as busy as possible.  Jobs usually end with an i/o request, so by scheduling the shortest job first you are getting to the next i/o request the soonest.

This insight about shortest job first is what is behind the multi-level feedback queue scheduling used in most modern operating systems: you are using past behavior to predict future job lengths, and then scheduling (expected) shortest job first (but preempting the job if it goes much beyond its expected length.)  The classic paper is Corbató, F. J., M. M. Daggett, and R. C. Daley, “An experimental time-sharing system”, AFIPS Conference Proceedings, Vol. 21, pp. 335-344, 1962.


I think your best bet is probably to get an introductory text on the theory of computation and/or take a course on the subject. I think the typical courses teach quite a lot before getting to polynomial time reduction, so you are most likely skipping over a lot prerequisite material. I'll try to give a common language understanding of what a polynomial time reduction is without too many details.

First you have to understand what a reduction is, so I would start here. To quote the linked wikipedia page:

  In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

If you want to understand it precisely you should carefully read the definition section of the page. The situation where we are interested in reductions can be roughly described as attempting to encode problems that we know are "hard" or complete for a class as a newly defined problem that we are unsure about. This will prove that the new problem is at least as hard as the one that we know to be hard.

In the vaguest sense you can think of a polynomial time reduction as a reduction that requires $O(n^k)$ steps (for a fixed k). So we require polynomial time in order to transform any instance of the "hard" problem into an instance of the new problem. Again the wiki page gives a description of different types of polynomial time reductions.


Explanation of implementation of an algorithm for Dominating Set

This algorithm just tries every subset of the vertices and calculates whether it is a dominating set.  It tries the subsets in increasing order of size, and halts whenever it finds one.

Note that the running time is $O(2^n n)$ so it is exponential, and quite badly so.  There are faster algorithms that compute dominating sets in $O^*(1.7^n)$ or even $O^*(1.5^n)$ time, but I don't recall whether they are implementable.

By the way, dominating set, being W[2]-complete, is not expected to have an algorithm running in time $f(k) \cdot \text{poly}(n)$ for any function $f$ where $k$ is the size of a minimum dominating set.


design cache system using queuing theory

You first need to establish the access speed of the cache, depending on the cache size (usually larger cache -> slower speed, because of physics). You also need to determine the energy consumption of a larger cache, which will lead to increased heat, which will lead to lower clock speed (again, because of physics). Then you need to find the cost of a larger cache - if I can gain more for less money using different methods than increasing the cache size, I'm not going to increase the cache size (because of economics).

Histograms of existing applications are of limited use, since there are plenty of algorithms that adapt to the cache size - with a cache four times the size you would have completely different access patterns. So you are going to use simulations.

I wonder why I didnt't mention queuing theory here.


Processing weighted points of interest. Is there a name for this task/algorithm?

Solution to your algorithm problem

There's a simple solution to your algorithmic problem.  Treat the $a_0,a_1,\dots,a_{k-1}$ as a probability distribution.  Apply kernel smoothing to turn this into a smooth probability distribution.  At this point, you have a probability density function (pdf).  Now compute a cumulative density function (cdf), and find the $n+1$ quartiles of the cdf.  These endpoints of your new bins.

This is "optimal", in the sense that given all of the information available to you, it gives the optimal bin-sizing for a particular distribution.  We could prove this by proving that for a particular pdf, this definition of bins ensures that each bin has exactly $1/n$ probability mass falling within it.

Other approaches to your computer vision task

The Hough transform might not be optimal.  There are other approaches you could also try.  For instance, there are algorithms for detecting lines that are approximately horizontal.  So, the following approach might be better:

Find one long line and approximately find its angle.
Rotate the image so that it is approximately horizontal (since the lines are all approximately parallel, that means all the lines will now be approximately horizontal).
Find all long, approximately-horizontal lines.

The problem of finding long, approximately-horizontal lines has been studied in the literature on image processing and deskewing scanned documents.  Or, if you want a free tool, take a look at existing tools, e.g., Leptonica, pagetools, ImageMagick (convert -deskew), and others.

Another standard approach is to apply the Hough transform twice:

First use the Hough transform to get a rough estimate of the angle.  For instance, you might sweep over some range of possible angles, sensitive to 1 degree or 0.1 degree increments.
Then, use a second Hough transform to get a rough estimate of the angle.  Now you have a much narrower range of possible angles (1 degree or 0.1 degree wide); do the Hough transform over this narrower range, sensitive to 0.01 degree increments (say).

This is more efficient then doing a single Hough transform sensitive to 0.01 degree increments.


What you read is total nonsense, except for the most primitive of compilers. First, comparison with an integer is as fast, possibly even faster than comparison with a constant. Second, a good optimising compiler will take a loop written using some common pattern and turn it into the best possible code; it may not recognise your obfuscated pattern and produce less good code for it.
And lastly, you shouldn’t replace readable with unreadable code unless there is an actual need for it. If you spend an hour making the change, it needs to produce 20 hours saved CPU time at least. When you are at that level, better algorithms are very likely to give better savings.


Can a context free grammar for $L$, generate a string not in $L$?

By definition, the language generated by a grammar $G$ is the set of all strings generated by $G$. So a grammar generating a language $L$ can generate only words in $L$ (and conversely, it can generate all words in $L$).


Iteration vs Recursion question in Lisp method

Since deep-reverse and iter call each other, they are (mutually) recursive.
Their combination is not tail recursive however, so deep-reverse is not iterative in the scheme parlance (IOW, does not admit tail call optimization).

PS. A proverbial sufficiently smart compiler (and, in fact, many real ones) can compile this function into an iteration (i.e., not using the function call stack).


Let $\mathcal{S}$ be the state space of your Markov chain, and assume that we start at some state $i \in \mathcal{S}$. Let $\mathcal{Y}_i$ be the set of states (pages) that are ranked lower than $i$ by two of the three engines. According to your description, the probability of transition to state $j$ can be defined as follows:

\begin{equation}
P_{ij} =
 \begin{cases}
  1 - \frac{|\mathcal{Y}_i|}{|\mathcal{S}|} & \text{if } j = i, \\
  \frac{1}{|\mathcal{S}|} & \text{if } j \in \mathcal{Y}_i, \\
  0 & \text{Otherwise}
 \end{cases}
\end{equation}

If I have understood your question correctly, this Markov chain does not always produce credible results due to the following issues. First, your chain allows repetitive comparisons. In other words, it is likely that a state $i$ is compared against some state $j$ multiple times. This, of course, does not make trouble as long as your chain is irreducible. However, in some cases, you will not get the correct result. For example, consider the following scenario.

Imagine for some state $i \in \mathcal{S}$, no state (page) can be found that is ranked lower than $i$ by two other engines, that is $\mathcal{Y}_i = \varnothing$. Therefore, $P_{ii} = 1$ making $i$ an absorbing state. In this case, your chain will be trapped in state $i$ in finite time, and from then on, it will only compare state $i$ against other states repeatedly. If chain is trapped in such a state and you let it run for a long enough time, then your results would clearly be wrong. Similar problem occurs if your chain contains recurrent sub-classes.

Assuming that no such states exist, then you would have an irreducible chain. In that case, if you let the chain run for sufficiently long time, the counting process would result in a good approximation of correct rankings (according to your algorithm).

P.S. This answer is just based on my understanding of your problem and may not be 100% correct.


How to solve a recurrence relation with a sum?

Here are several ways to solve your recurrence relation.

Guessing

Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then

$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-1} 2^m = 1 + (2^n-1) = 2^n.
$$

Computing the first few values

Another approach which is very  useful is to compute a few values of the sequence:
$$ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... $$
If we're lucky, as in this case, we might spot a pattern. If not, it's always a good idea to consult the on-line encyclopedia of integer sequences. A quick search would reveal the sequence A000079.

Creative telescoping

In the method of creative telescoping, we try to find a combination of terms that results in major cancellation. In our case, we can try $T(n+1)-T(n)$:

$$
T(n+1)-T(n) = \sum_{m=0}^n T(m) - \sum_{m=0}^{n-1} T(m) = T(n),
$$
and so $T(n+1) = 2T(n)$. Unrolling this rule, we deduce $T(n) = 2^n T(0) = 2^n$.

Back-substitution

Another way to look at the preceding trick is to try to "back-substitute" the recurrence inside itself:

$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{n-2} T(m) + T(n-1) = 2T(n-1),
$$

from which we can proceed as before.

Generating series

A very general method is that of generating series. Let $G(x) = \sum_{n=0}^\infty T(n) x^n$. Since $1/(1-x) = \sum_{n=0}^\infty x^i$, multiplying by $1/(1-x)$ is like computing "running sums":
$$
\frac{G(x)}{1-x} =
\sum_{n=0}^\infty \sum_{m=0}^n T(m) x^n =
\sum_{n=0}^\infty (T(n+1)-1) x^n = \\ \frac{G(x)-T(0)}{x} - \sum_{n=0}^\infty x^n = \frac{G(x)-1}{x} - \frac{1}{1-x}.
$$
From this it is not hard to deduce
$$
G(x) = \frac{-1/x-1/(1-x)}{1/(1-x)-1/x} = \frac{-(1-x)-x}{x-(1-x)} = \frac{1}{1-2x} = \sum_{n=0}^\infty 2^nx^n,
$$
and so $T(n) = 2^n$.

Recursion tree

It is also possible to deduce the value of $T(n)$ using a recursion tree. Each path in the recursion tree for $T(n)$ corresponds to a sequence of decreasing numbers $n_0 = n, \ldots, n_\ell$, where $n_\ell \geq 0$ (possibly $\ell = 0$); this is because all leaves are labeled by $1$. The set of possible decreasing sequences is in one-to-one correspondence with subsets of $\{n-1,\ldots,0\}$, because once we know which numbers appear, we also know their order. The number of subsets of $\{n-1,\ldots,0\}$ is exactly $2^n$.


In this context, $F^+ = \{ X \rightarrow Y \mid F \models X \rightarrow Y \}$ is the set of all the dependencies that semantically (logically) follow from $F$ as you wrote.
You also have a syntactic closure, defined as $F^\star = \{ X \rightarrow Y \mid F \vdash X \rightarrow Y \}$ where $F \vdash X \rightarrow Y$ means that $X \rightarrow Y$ can be deduced from $F$ according to an inference system, in this case, Armstrong's axioms.

Armstrong's system is both sound and complete so $F^+ = F^\star$, but the concepts are different. To illustrate the difference, let $\Sigma = \{A \rightarrow B, BC \rightarrow D\}$ and prove the following:

$AC \rightarrow D \in \Sigma^+$ (semantic proof). Let $r$ an instance such that $r \models A \rightarrow B$ and $r \models BC \rightarrow D$. Assume $t_1, t_2 \in r$ with $t_1[AC] = t_2[AC]$ this implies $t_1[A] = t_2[A]$ which implies $t_1[B] = t_2[B]$ because $r \models A \rightarrow B$. Thus we have $t_1[BC] = t_2[BC]$ and we can conclude $t_1[D] = t_2[D]$ because  $r \models BC \rightarrow D$. Thus $t_1[AC] = t_2[AC]$ implies $t_1[D] = t_2[D]$ for arbitrary tuples $t_1$ and $t_2$ so $r \models AC \rightarrow D$. We have shown an arbitrary instance model of $\Sigma$   is a model of  $AC \rightarrow D$ too, so $\Sigma \models AC \rightarrow D$.
$AC \rightarrow D \in \Sigma^\star$ (axiomatic proof). From  $A \rightarrow B$ we obtain  $AC \rightarrow BC$ by augmentation. Now using $BC \rightarrow D$ we obtain $AC \rightarrow D$ by transitivity.


Hint: If the height is $k$, then the search complexity should be $O(kn^{1/k})$ (so the best choice is $k = \log n$, giving logarithmic time). Each level should contain every $n^{1/k}$th element of the lower level. Do the obvious thing - find the two elements bracketing your element in the first level, then the two elements bracketing it in the second level, and so on.


Finding the longest repeating subsequence

Here is a dynamic programming solution.

Suppose that the input string is $x_1\ldots x_n$. Create a table $T$ whose rows and columns are indexed by $0,\ldots,n$ (where $n$ is the length of the string), populated by the rule
$$
 T[i,j] =
\begin{cases}
0 & \text{if $i = 0$ or $j = 0$}, \\
T[i-1,j-1] + 1 & \text{if $x_i = x_j$ and $i \neq j$}, \\
\max(T[i-1,j],T[i,j-1]) & \text{otherwise}.
\end{cases}
$$
The answer is $T[n,n]$.


Here's how to reduce your problem to cycle detection. Your array is a mapping $f$ from $[n]$ to $[n]$. From each starting point $x$, you can iterate $f$. Using a cycle detection algorithm, you can either find out that the iterates of $x$ form a cycle, or find two iterates that map to the same point (your duplicate). For some starting point, you will find a duplicate.


Two way communication using asymmetric encryption

The first source is being imprecise when they say "need".  What they mean is that this is one way to accomplish it.

The second source doesn't say what you claim it says.

I suggest studying key exchange protocols and learning how SSL works.


Polynomial Time Algorithm for Steiner Tree Problem

Yes, given a weighted graph $G$ with $n$ nodes and a subset $T$ of nodes whose cardinality is no less than $n−1$, there is a polynomial time algorithm that finds a minimum weight tree that spans all nodes in $T$.

Here is a simple algorithm.

Find a minimum-weight spanning tree $M$ of $G$. This is can be done by Kruskal's algorithm in $O(E\log E)$ time-complexity.
If $|T|=n$, return $M$.
Otherwise, $|T|=n-1$. There is exactly one node of $G$ that is not in $T$. Let it be node $v$. Removing node $v$ and all edges incident to $v$ from $G$, we obtain a graph $G'$. Note that $T$ is the set of all nodes of $G'$. Find a minimum-weight spanning tree $M'$ of $G'$,  using Kruskal's algorithm again. If the weight of $M$ is smaller than that of $M'$, return $M$; otherwise, return $M'$.

I will let you check that the above algorithm is correct with polynomial time complexity. It should be easy enough.

Exercise. When $|T|=n-1$, what does it mean if $M$ is returned instead of $M'$?

Exercise. Show that if $|T|\ge n-k$ for some constant $k$ instead of $|T|\ge n-1$, the same conclusion holds.


Prove that checking if context free grammar generates word with all symbols is NP-complete - unclear statement about encoing probem in exercise

What the remark is trying to tell you, I think, is that the alphabet of each different grammar $G$ can grow and is not fixed.

For instance. say that you have a language $L$ that you want to reduce to your language, let´s call it $L'$, then, you are allowed to make the alphabet of the different context free grammars inside $L'$ grow as the instances inside $L$ grow. For a bigger instance a bigger alphabet


Brute force method to solve the 0-1 knapsack problem

You can't. Landau notation does not hold enough information.

You don't know the constant factor(s).
With only $O$, you don't have a lower bound.
It's only a worst-case bound; different runs with the number of items can have wildly different runtimes.
Such bounds only hold in the limit, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can realistically run the algorithm for.
The quantity bounded is not runtime but some abstract measure.

In particular, effects like operation reordering, memory hierarchy and branch mispredictions routinely skrew with runtimes.

The best you can do is assume that the runtime behaves like $\approx c \cdot 2^n$, run experiments with $n_1$ and $n_2$ items and estimate the constant factor -- then it's simple rule of three. But given all the caveats listed above, the prediction is unlikely to be worth much.


Randomly filling an $n$-length array with values from $0$ to $k$ that total to $0 < m < nk$ - is a linear-time algorithm possible?

Once you know how to count  the number of such arrays, you can turn that into a procedure to generate a random such array, using ranking/unranking procedures.

Let's see how to count them.  Let $f(k,m,n)$ denote the number of such arrays.  Note that we have

$$f(k,m,n) = \sum_{x=0}^k f(k,m-x,n-1)$$

by enumerating all possibilities for $A[0]$.  So, this gives a dynamic programming algorithm to count the number of such arrays.

How does this lead to a way to generate a random array?  Well, in counting such arrays, we've implicitly established a bijection $\varphi$ from the set of such arrays to the set of integers $\{0,1,2,\dots,f(k,m,n)-1\}$.  So, we just need a way to compute $\varphi^{-1}$, and then we have a way to pick a random array: we pick a random number between $0$ and $f(k,m,n)-1$, then apply $\varphi^{-1}$ to obtain the corresponding array.

Now the recurrence above establishes such a bijection.  In particular, the arrays that start with $A[0]=0$ correspond to integers in the range $0 .. f(k,m,n-1)-1$, the arrays that start with $A[0]=1$ correspond to integers in the range $f(k,m,n-1)..f(k,m,n-1)+f(k,m-1,n-1)-1$, and so on.  So, given a random integer $y$, we find the smallest $x_0$ such that

$$y < \sum_{x=0}^{x_0} f(k,m-x,n-1),$$

and then set $A[0]=x_0$ and continue recursively to fill in the rest of the array (replacing $y$ with $y' = y - \sum_{x=0}^{x_0-1} f(k,m-x,n-1)$ and using $y'$ to fill in the array $A[1..n-1]$).


Algorithm to extract line-like contour in 3d

Here is a generic approach:

Find a point on the intersection of these two curved planes, i.e., on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$.  Call that point $\vec{x}_0$.
Trace along the intersection curve, starting at $\vec{x}_0$, and continuing as far as you can.  Then do the same starting from $\vec{x}_0$ in the opposite direction.
Find a new point $\vec{x}_0$ on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$ that's not part of what you've traced so far, and go back to step 2.

To instantiate this, we need to know how to implement each of these steps.

To find a point on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$, you can use any method for solving a system of nonlinear equations.  There are many.  If you're not familiar with the subject, one simple approach is to minimize the objective function

$$\Phi(\vec{x})= \|F(\vec{x})-l\|^2 + \|G(\vec{x})-s\|^2$$

using, e.g., gradient descent.

To trace along the intersection curve, you can use the gradient to help you.  Suppose that $\vec{x}_0$ is a point on the intersection curve, and expand the Taylor series for $F$ and $G$.  We get

$$F(\vec{x}) = F(\vec{x}_0) + \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0) + \dots \approx l + \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0)$$

and similarly

$$G(\vec{x}) \approx s + \nabla G(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0).$$

So, for $\vec{x}$ to be on the intersection curve, we require $ \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0) = 0$ and $\nabla G(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0)=0$ (assuming $x$ is very near $x_0$).  Since $\nabla F(\vec{x}_0)$, $\nabla G(\vec{x}_0)$, and $\vec{x}_0$ are known and computable, this gives us two linear equations in three unknowns, so we can solve for $\vec{x}$ using a linear equation solver.   In particular, compute the two vectors $\nabla F(\vec{x}_0)$ and $\nabla G(\vec{x}_0)$, then find a unit vector $\vec{d}$ that is orthogonal to both of them.  Now you can trace out the intersection curve from $\vec{x}_0$ by preceding in the direction $\pm \vec{d}$; in other words, the line $\vec{x}_1=\vec{x}_0 + c \vec{d}$ is approximately on the intersection curve, when $c$ is close to 0.  (If you want, you can generate $\vec{x}_1$ in this way, then "fine-tune" it by using it as the starting point for gradient descent with objective function $\Phi$ to compute $\vec{x}_1$ more precisely and to make sure you stay on the intersection curve.)  This gives you a way to step along the intersection curve, one point at a time.

How to implement step 3?  This might depend on the specific functions $F,G$.  One approach is to modify the objective function $\Phi$ to penalize points that are near the part of the curve you've already found, e.g.,

$$\Phi(\vec{x}) = \|F(\vec{x})-l\|^2 + \|G(\vec{x})-s\|^2 + \sum_i {1 \over \|\vec{x}-\vec{x}_i\|^2},$$

where the $x_i$'s are points you've previously found (or some well-spaced-out subset of them).  Another approach might be to do step 1 (gradient descent on $\Phi$, without the penalty term) starting from many different starting points (e.g., spaced on a coarse grid).  There may be a better way in your specific situation; I don't know.

I expect this should be more efficient than enumerating all grid points and evaluating $F,G$ at every grid point, especially as the spacing of your grid points gets small.  It does require you to be able to compute the gradients of $F,G$, but in your situation that seems to be no problem.


Retrieving the shortest path of a dynamic graph

The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these paths can be already very long. Dynamic graph algorithms distinguish between edge deletions only (decremental dg algorithms), edge insertions only (incremental dg algorithms) and edge insertions and deletions (fully-dynamic dg algorithms). Thus you are interested in incremental algorithms.

The algorithms mentioned in the post of AJed, are slightly outdated. There are newer results by Thorup, see here, on page 8 for a short survey. The currently best fully-dynamic exact APSP algorithm by Thorup (for distance queries, not the path), needs $O(n^2(\log n +\log^2 (1+m/n))$ amortized update time, while supporting $O(1)$ worst case query time. Notice, that if you have $O(n\log n)$ edges, then you could just recompute from scratch with Dijkstra and Fibonacci-heaps and get the same running time as in Thorup's algorithm. So if your graphs are not to dense, I would recommend using Dijkstra.

I am not aware of any better incremental algorithm. But you should do a web search if there exist newer results for this specialized problem.


Basic second-order logic example contains a mistake?

Yes, the example contains a mistake. The statement $\forall X (\mathcal{R}(X,P)\rightarrow P(a))$ is in fact equivalent to $P(a)$, under the assumption that $\mathcal{R}(X,P)$ is true for at least one $X$.

So indeed, the example should be $\forall X (\mathcal{R}(X,P)\rightarrow X(a))$, as you state. Perhaps the author would not have made this mistake if they had chosen a class of people that would be described by another letter than $P$.


number of connected induced subgraph in a tree

Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r_1,\ldots,r_\ell$, and let the corresponding subtrees be $T_1,\ldots,T_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:

The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T_i$.
The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T_i$, or its intersection with $T_i$ is a connected induced subgraph of $T_i$ containing $r_i$.

Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences:
$$
\begin{align}
A(T) &= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\
B(T) &= \prod_{i=1}^\ell (1 + B(T_i))
\end{align}
$$
Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).


BIT: What is the intuition behind a binary indexed tree and how was it thought about?

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation.  This answer goes into one possible derivation.

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements.  You could start off by writing out seven buckets into which the numbers will be distributed:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Now, let's suppose that the cumulative frequencies look something like this:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards.  For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

One way that we can think about improving this operation would be to change what we store in the buckets.  Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket.  For example, in our case, we would rewrite the above buckets as follows:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket.  However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence?  If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes.  Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node.  For example, suppose we construct the following binary tree from these nodes:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree.  For example, given our values, we would store the following:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

Given this tree structure, it's easy to determine the cumulative sum up to a point.  The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question.  As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

For example, suppose we want to look up the sum for 3.  To do so, we do the following:

Start at the root (4).  Counter is 0.
Go left to node (2).  Counter is 0.
Go right to node (3).  Counter is 0 + 6 = 6.
Find node (3).  Counter is 6 + 15 = 21.

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root.  Any time you follow a right child link upward, add in the value at the node you arrive at.  For example, to find the frequency for 3, we could do the following:

Start at node (3).  Counter is 15.
Go upward to node (2).  Counter is 15 + 6 = 21.
Go upward to node (4).  Counter is 21.

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree.  To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree.  Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

For example, to increment the frequency of node 1 by five, we would do the following:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

Starting at node 1, increment its frequency by 5 to get

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

Now, go to its parent:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We followed a left child link upward, so we increment this node's frequency as well:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We now go to its parent:

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

That was a left child link, so we increment this node as well:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

And now we're done!

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers.  Let's rewrite each bucket index in this tree in binary:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Here, we can make a very, very cool observation.  Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it.  You are now left with the following:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number.  For example, node 5 has binary pattern 101.  The last 1 is the final bit, so we drop that to get 10.  Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links.  For example, during a lookup, we just care about the right links we follow.  During an update, we just care about the left links we follow.  This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key trick is the following property of this perfect binary tree:

  Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

For example, take a look at the access path for node 7, which is 111.  The nodes on the access path to the root that we take that involve following a right pointer upward is

Node 7: 111
Node 6: 110
Node 4: 100

All of these are right links.  If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

Node 3: 011
Node 2: 010
(Node 4: 100, which follows a left link)

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

Write out node n in binary.
Set the counter to 0.
Repeat the following while n ≠ 0:

Add in the value at node n.
Clear the rightmost 1 bit from n.

Similarly, let's think about how we would do an update step.  To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward.  We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore.  We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly.  In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

Hope this helps!


What is the complexity for the universality problem for a NFA with all states accepting?

You problem is PSPACE-complete. I prove that it's PSPACE-hard by reducing universality of NFAs to universality of NFAs with all states accepting.

Let $A$ be a NFA. Add a new final state $q_\$$ to it and for every accepting state $q$, add a transition $q\overset{\$}{\to}q_\$$ where $\$$ is a fresh letter. For every letter $a\in \Sigma\sqcup \{\$\}$, also add a transition $q_\$\overset{a}{\to}q_\$$. And then make all states accepting. The new automaton accepts $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ for some $L'\subseteq \Sigma^*$.

Now, add some automaton (with all states final) that recognizes the language $\Sigma ^*$ (i.e. the language of words that don't contain $\$$) in parallel. The new automaton will recognize $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$.

Now, notice that we have $L(A)=\Sigma^*$ iff $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$. I.e. the process I described is a reduction from universality of a NFA to universality of a NFA with all states accepting. Since the reduction is polynomial, your problem is PSPACE-hard.


How do I reconstruct the forest of syntax trees from the Earley vector?

I am using terminology and notations from Earley's paper. It is possible that the description you read is different.

It seems frequent that general CF parsing algorithms are first
presented in the form of a recognizer, and then the information
management needed to actually build parse trees and parse forests is
sort of added as an afterthought. One reason may be that keeping the
information needed to construct the shared forest require cubic space
$O(n^3)$ where $n$ is the length of the input string being parsed, but
the space requirement is only square $O(n^2)$ for recognition, when this information is
not preserved. The reason for this space complexity increase is quite
simple: the parse forest size can be cubic.

The worst case time complexity is $O(n^3)$, as is well known.

The best reference for Earley's algorithm is of course Earley's paper,
but it is not very explicit about building the parse forest. This can
actually be a messy business, much more so than the fast talk of
section 7 page 101 will let appear. To be true, Earley does not talk
of parse forest, or of forest, but of "a factored representation of
all possible parse trees". And there is a good reason for that: if he
tried to produce a forest according to his grammar, his space (hence
time) complexity bound would climb to $O(n^{s+1})$ where $s$ is the
size of the longest rule right-hand-side. This is why other algorithms
use grammars in binary form (not necessarily Chomsky Normal Form (CNF)).

Actually, Earley uses binary form implicitly, because that is
necessary for the cubic time complexity. This is one of the major
roles of the rule dot in states. But this implicit binary form
produces parses and forests according to the binarized grammar, not
to the original one, which, I fear, is a major source of obscurity. This is detailed further below.

One good way to understand how the forest is obtained is probably to
look at it in a simpler case, the CYK algorithm. It is also often
described as a recognizer, and the parser aspect is added at the end.
You can look at the description in wikipedia. The information needed
to build the forest is what they store in the table of "backpointers".
Backpointers are essentially pointers to substrings (an associated
symbol) that form the constituents of a string according to some
rule. They give all possible ways of parsing a substring. Recall that
CYK uses binary form, usually CNF, so that things are simpler. The CYK
parser has fundamentally the same dynamic programming structure as
Earley, but is much simpler. So understanding it well can be a
significant help.

Going back to Earley's algorithm, I do not believe you need Earley
vector to decide acceptance or to build parse trees and forests.  What
Earley calls vector in his paper appears only in page 97, in third
paragraph of implementation. It is only a device to speed up the
search of states pointing back at some given string position k, in
order to get a better complexity. But all the information is in the
state sets, implemented as lists of states. However, this information
is not sufficient to build the forest of parse trees, because the
algorithm does not keep track of the way(s) a state may be
obtain. Indeed, the vector is even used to efficiently discard a state
already found, independently of how it was found.

In section 7 of Earley's article, he explains that in order to "make
the recognizer into a parser", i.e. to be able to recover parse trees,
it is necessary to keep track of the way completions are done.

  Each time we perform the completer operation adding a state
    $E\rightarrow \alpha D.\beta \; g$ (ignoring lookahead) we construct a pointer from the instance of $D$ in
  that state to the state $D\rightarrow \gamma. \; f$ which caused us to do the
  operation. This indicates that $D$ was parsed as $\gamma$. In case
  D is ambiguous there will be a set of pointers from it,
  one for each completer operation which caused $E\rightarrow \alpha
D.\beta \; g$ to be added to the particular state set. Each symbol in
  $\gamma$ will also have pointers from it (unless it is terminal),
  and so on, thus representing the derivation tree for $D$.

Note that in this text, $f$ and $g$ are indices in the parsed string,
pointing where the recognition of the rule left-hand side started (as
the right-hand side symbol had been predicted. So $f$ is the string
index where the recognition of $D\rightarrow \gamma$ started, and it
ended at index $g$. These "completion pointers" are the Earley
equivalent of the backpointers described (not too well in
wikipedia) for the parser version of CYK.

From such a pointer (as described in the quote) we know that the $D$
in the rule instance $E\rightarrow \alpha D.\beta \; g$ can itself be
developped into a tree (or forest) that parses the input string $w$ from
index $f+1$ to index $g$, which we note $w_{f+1:g}$. The nodes immediately below $D$ are given by
the rule $D\rightarrow \gamma$. By looking for the completion that lead
to $D\rightarrow \gamma. \; f$ we can then find other such pointers
that tell how the last symbol of $D$ was obtained, and hence more
information on the possible parse trees. Also by looking at the
completion that recognized the symbol before last in an earleir state
sets, you find how it was obtained, and so on.

Assuming you kept all the needed pointers as indicated in the paper,
you can get all the shared tree representations starting from the last
symbol recognized by the parser, which is of course the initial symbol
of the grammar.

But I also skipped the messy part. Suppose you have a rule
$U\rightarrow XYZ$, which I choose with a right hand side longer than
2 symbols, and another rule $W\rightarrow UV$, for an ambiguous
grammar.

It may well happen that the parser will parse $w_{f+1:g}$ into $X$,
$w_{g+1:h}$ into $Y$ and both $w_{h+1:i}$ and $w_{h+1:j}$ into
$Z$. So, with the rule $U\rightarrow XYZ$, Both $w_{f+1:i}$ and
$w_{f+1:j}$ parse into $U$.

Then it may also be that both $w_{i+1:k}$ and $w_{j+1:k}$ both
parse into $V$. Then, with the rule $W\rightarrow UV$, the string
$w_{f+1:k}$ parse into $W$ in two different way, which correspond to
an ambiguity of the grammar.

Of course, to avoid repeating computations, Earley's algorithm will
attempt to share as much as possible of the two parsing computations.
What it will actually share is obviously the recognition (and parsing)
of $w_{f+1:g}$ and $w_{g+1:h}$ into $X$ and $Y$. But it will actually
do a bit more: it will also share the beginning of the two distinct
parses that recognize $U$ with the rule $U\rightarrow XYZ$. What I
mean is that the state $U\rightarrow XY.Z \; f$ will be found only
once (with respect to what I am describing), in state set $S_h$. It
will be a common part of the two parses. Of course, things will
temprarily diverge while parsing the $Z$ since they correspond to
distict substrings, until they converge again when everything parses
into W, when the state $W\rightarrow UV. \; f$ is produced twice in
state set $S_k$.

So the forest of syntax trees can be a very strange one, with kind of
siamese twin subtrees that may share the first two edges of some node, but
not the third edge. In other words, it may be a very awkward
structure. This may explain why Earley calls it "a factored representation of
all possible parse trees", without being more specific.

Any attenpt to surgically separate the siamese twins, without changing
the grammar will result in increased complexity. The right way to do it
is to binarize the grammar.

I hope this will help you. Let me know.  But I do insist that a good
understanding of CYK parsing can help. There are other algorithms, simpler than Earley's, that can parse all CF languages efficiently.

You may find more general info on this parse forest issue in two other answers I gave: https://cstheory.stackexchange.com/questions/7374#18006 and https://linguistics.stackexchange.com/questions/4619#6120. But they do not go into specific details of Earley's algorithm.


Dynamic programming VS Greedy Algroithms

Sounds about right, however informal the statement; dynamic programming is more powerful than greedy algorithms so if a problem should require it, a greedy algorithm won't be enough. And in the case in which a greedy algorithm can solve the problem, there will also be a correct dynamic programming solution since dynamic programming involves solving problems by optimizing overlapping subproblems. Suppose a greedy algorithm suffices, then the local optimal decision at each stage leads to the optimal solution and you can construct a dynamic programming solution to find the optimal solution. However, greedy algorithms are generally faster so if a problem can be solved with a greedy algorithm, it will typically be better to use.


What does tilde mean, in big-O notation?

It's a variant of the big-O that “ignores” logarithmic factors:

$$f(n) \in \tilde O(h(n))$$

is equivalent to:

$$ \exists k : f(n) \in O \!\left( h(n)\log^k(h(n)) \right) $$

From Wikipedia:

  Essentially, it is big-$O$ notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the “nitpicking” within growth-rates that are stated as too tightly bounded for the matters at hand (since $\log^k n$ is always $o(n^\varepsilon)$ for any constant $k$ and any $\varepsilon > 0$).


A reference for pseudocode for Monge-Elkan algorithm?

There are apparently several different variants of the Monge–Elkan metric. You can check out Cohen, Ravikumar and Fienberg, A comparison of string metrics for matching names and records, which describes several different metrics (not only Monge–Elkan). Many other online references also exist.


Simplifying an upper O-bound in two variables

I assume that $n\ge 2$, which implies $1/(n-1)\le 2/n$. Then

$$ \frac{nm-1}{n-1} \le \frac{nm}{n-1} \le 2  \frac{nm}{n} \le 2m.   $$

Thus your expression is bounded by $O(m)$.


Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine?

Pick any model of computation, say a class of Arbitrary Automata $\mathcal{A}$, so that $F_{\mathcal{A}} \subseteq \mathrm{RE}$, i.e. this model is sub-Turing-complete.

Since TMs are an admissible numbering and $\mathcal{A}$ is a numbering of some set of (semi-)computable functions, for every $A \in \mathcal{A}$ there is a Turing machine $f(A)$ with $F_A = F_{f(A)}$ -- and we know that this compiler $f$ is computable.

By the existence of a universal Turing machine $U$, we get that $U(\langle f(A) \rangle, x) = A(x)$ for all $x$. Applying the s-m-n theorem gives us a TM $T$ with $T(\langle A \rangle, x) = U(\langle f(A) \rangle, x) = A(x)$.


Why is the number of comparisons in a BST missing key lookup about 2 ln N?

The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.


How can can I find out if the two disks intersect in the plane?

I am not sure if I should answer such a question, but here we go:

Let the first disk be $D_1 = \langle R_1, (x_1, y_1)\rangle$ and the second disk be $D_2 = \langle R_2, (x_2, y_2)\rangle$, where $R_1$ and $R_2$ is the radius of the first and second disk respectively, as well as $(x_1, y_1)$ and $(x_2, y_2)$ is the center of the first and second disk respectively. Further, let $d$ be the distance of the two centers; that is, $$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}.$$ Then, the two disks intersect if $$d \leq R_1 + R_2$$ and do not intersect otherwise.

Note that if $d = R_1 + R_2$, then the two disks have only one point in common.


Why does a Turing Machine need at least two states?

TL;DR: technically, there need to be an accepting and rejecting state and they need to be different; but it's not a big deal and, at an intuitive level, one-state machines work just gine.

A Turing machine is typically defined to be a tuple $M=\langle Q, \Sigma, \Gamma, \delta, q_0, q_\mathrm{acc}, q_\mathrm{rej}\rangle$ where the items are the state set, input and tape alphabets, the transition function (or relation for a nondeterministic machine), and the initial, accepting and rejecting states, respectively.

The accepting and rejecting states must be distinct because the machine cannot simultaneously accept and reject. Therefore, there must be at least two states.

In principle, you might want to define a Turing machine that has only one state: the initial state would be the accepting state and there'd be no rejecting state, or vice-versa. There's nothing morally wrong with that but it would make the definition more complicated.  Instead of saying "A Turing machine has distinct accepting and rejecting states", you'd have to say "A Turing machine either has distinct accepting and rejecting states, or it has just one state which is either the accepting state or the rejecting state." That's more complex, and it doesn't buy you anything, so people don't do it.

But note that this isn't really an important point. You can perfectly well think of Turing machines with just one state and it won't hurt you in any way, unless you try to write down a formal definition. Any machine that you want to think of as having one state, you can easily rewrite as having two states: just add the second state, which will be inaccessible.


Proof that $G$ is a yes-instance of IDS $\iff$ $f(G)$ is a yes-instance of SAT

Yes, your proof of $\Rightarrow$ is correct, but note that you still have to prove the second direction to complete the reduction.

  Now we know that IDS is NP-hard

Unfortunately, we don't. We'd need a reduction from SAT to IDS and not the other way around.
To convince yourself of why it makes sense, a reduction from $A$ to $B$ means that if we had an algorithm that solves $B$, we could use it to trivially solve $A$. So, in your case - if we had an algorithm that solves SAT we would be able to solve IDS, but that's not what we want to show. We want to claim that if we could solve IDS then we could solve SAT, which means IDS is "at least as hard as SAT".

Also, notice that you need a karp reduction and not just a  many-one reduction. That is, a many-one reduction which can be computed in polynomial time (your reduction achieves that)

  Furthermore we have to provide an efficient algorithm which uses non-determinism to show that IDS is a member of NP, correct?

Correct.
Assuming we have provided a karp reduction from SAT to IDS, or equivalently - we proved that $\text{SAT}\le_p \text{IDS}$, then all we know is that IDS is NP-hard, and we need to prove that $\text{IDS} \in \text{NP}$ to get that IDS is NP-complete.


Finding the Regular Expression of a language

It's better to think of $L$ as strings of length $3n+2$. You already have an expression for strings whose length is a multiple of 3, so use that and append all strings of length 2.


Yes, each input value is weighted before being fed into the nodes in the next layer.  Each input/output pair of "neurons" has its own weight and it is these weights that are adjusted by the neural network training process.  The initial weights are typically random values before training begins.


Greedy algorithm for submodular optimzation

The claim isn't true in general. Given a monotone submodular function $f$ and a positive constant $C$, let $g = f/C$. The algorithm is oblivious to the change from $f$ to $g$, and on the other hand $1 + \ln g(N) = 1 + \ln f(N) - \ln C$. In particular, by choosing $C$ large enough, you can get that the approximation ratio is any small enough number (even smaller than one or smaller than zero!).


I feel like i am memorizing the proofs rather than learn how to prove

You can't learn "how to prove". "Proving" is not a mechanical process, but rather a creative one where you have to invent a new technique to solve a given problem. A professional mathematician could spend their entire life attempting to prove a given statement and never succeed.

I can easily deal with any type of proofs that i saw before ( eg. once i saw the proof of a recurrence question i became pretty good at prooving them). My problems start when i face an unusual question.

That is normal. Any mathematics "proofs" course isn't designed to teach you how to take an arbitrary problem you've never seen before and be able to solve it (since nobody, not even the best mathematics professors can do that). Rather, your learning goals are

Learn how to "read" proofs and judge their correctness

Learn how to "write" down a proof in the right mathematical language

Learn about known proof "techniques" and how to apply them

If you are working on a new, unknown problem, it is normal that you might not be able to solve it. However, knowing and having memorized other proof techniques may help you. Often proofs involve combining a new idea with existing known proof techniques. The more, and the more varied the proofs you already know are, the better your chance of being able to solve the given problem.
You are on the right track. You should simply keep studying proof techniques. The exercises you are doing are good. Don't worry if you get stuck. As you get more experienced and your "toolbox" of techniques grows, you will be able to solve exercises that are less "alike" the previous ones you have seen.


Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$

As HendrikJan stated, we can for example obtain the following languages with above CFG
$$01, 0001,\dots$$
which do not meet the required conditions.
Instead, we need to make sure that the ends are always the same. We can do that by the following production rules.
$$
S\rightarrow 0S0$$
$$S\rightarrow 1S1$$
$$S\rightarrow \epsilon$$


What is the difference between Simulated Annealing and Monte-Carlo Simulations?

Monte Carlo simulation is a method for computing a function. Simulated annealing is an optimization heuristic. Other than that, the only common thread behind these two methods is the use of randomness.

In Monte Carlo simulation, we are aiming at computing some quantity $A$ by finding an easily samplable random variable $X$ whose expectation is $A$. We estimate $A$ by averaging many samples of $X$. More sophisticated versions of this are rejection sampling and MCMC.

Simulated annealing is a heuristic for optimizing an objective function $f$ over a domain $D$. We start with an arbitrary point $x \in D$, and then try making local changes which improve the value of $f$; this is local search. In simulated annealing, we also allow making local changes which worsen the value of $f$, with some small probability. The probability is smaller the more the change makes $f$ worse.


When did "regular" start referring to Type 3 languages/grammars?

I found an answer, at least a partial one, hinted at in Footnote 10 of Chomsky's paper where he refers to a 1956 paper by Kleene in which Kleene describes "regular events" -- a language recognized by finite state machines.
So it would seem the common usage of "regular language" today traces back to Kleene's "regular events" rather than to Chomsky's "regular grammar".
Furthermore, as renierpost pointed out in a comment, what Chomsky called a "regular" grammar in 1959 is now known as Chomsky normal form.
Edit: I asked Professor Chomsky via email whether he intended his "regular grammar" to have a connection to Kleene's "regular events". He replied: "Long time ago and I don't recall. I suppose just a coincidence."


Compute several histograms with multiple filter conditions

I'm going to assume that each filter is a predicate on rows that identifies whether that row should be kept or discarded.  If so, then yes, this can be solved with many fewer than $O(Z^2)$ applications of the filters.  I'll describe two algorithms with different tradeoffs between time vs space: the first applies $O(Z)$ filters but uses $O(ZK)$ memory; the second applies $O(Z \lg Z)$ filters and uses just $O(K \lg Z)$ memory.  In both, let $F_1,\dots,F_Z$ denote the filters.
Algorithm 1: minimizing computation time
Here is an algorithm that applies $O(Z)$ applications filters and uses $O(ZK)$ memory.  (This corresponds to something like $O(ZK)$ time and $O(ZK)$ memory.)  Roughly speaking the algorithm computes a "prefix sum" and a "suffix sum", using two linear scans.  In more detail:

For each $i$, compute the subset $S_i$ of rows that are retained if you apply filters $F_1,\dots,F_i$.

For each $j$, compute the subset $S'_j$ of rows that are retained if you apply filters $F_j,\dots,F_Z$.

For each $i$, compute the intersection $S_{i-1} \cap S'_{i+1}$; this is the set of rows that are retained if you apply all the filters except for $F_i$.

Note that step 1 can be done in a linear scan using a total of $Z$ applications of filters, as you can obtain $S_{i+1}$ from $S_i$ using a single application of $F_{i+1}$.  Similarly step 2 can be done using $Z$ applications of filters, for a total of $2Z=O(Z)$ applications of filters.  Unfortunately you have to store all of $S_1,\dots,S_Z,S'_1,\dots,S'_Z$, which takes $O(ZK)$ memory.
Algorithm 2: minimizing memory usage
A divide-and-conquer algorithm can solve the problem with $O(Z \lg Z)$ applications of filters and $O(K \lg Z)$ memory.  (This corresponds to approximately $O(ZK \lg Z)$ time and $O(K \lg Z)$ memory.)  The algorithm works like this:

If $Z=1$ or $Z=2$, the problem is trivial; this is the base case.  Otherwise:

Compute the subset of rows that are retained if you apply filters $F_1,\dots,F_{Z/2}$.  Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_{Z/2+1},\dots,F_Z$.

Compute the subset of rows that are retained if you apply filters $F_{Z/2+1},\dots,F_Z$.  Then, recursively apply the algorithm to this reduced set of rows and to the filters $F_1,\dots,F_{Z/2}$.

Notice that you can compute the subsets of rows in steps 2,3 with $O(Z)$ applications of filters.  So, if we let $T(Z)$ denote the number of filter applications used by this algorithm when running on $Z$ filters, we have the recurrence relation
$$T(Z) = 2 T(Z/2) + O(Z),$$
which has the solution $T(Z) = O(Z \lg Z)$.  The claimed running time follows; and it's not too hard to see that the amount of memory used is as claimed, too (as there are $O(\lg Z)$ levels to the recursion tree, and you store $O(K)$ records per level of the recursion tree at a time).
Can we do better?
A natural question is to ask whether it is possible to find an algorithm that is optimal in both time and memory usage: e.g., $O(Z)$ applications of filters and $O(ZK)$ memory.  I don't know whether that is possible or not.


Difference between "data dependence graph", "data dependency graph", and "data flow graph"

Dependence and dependency are interchangeable terms.  In my experience, dependency (with a "y") is more common.  In my own writing I try to consistently use dependence (without a "y") for aesthetic reasons (I think it sounds better).  If you look at a dictionary you'll see that the two words are almost synonyms.  The only difference I'm aware of is that dependency (with a "y") means something specific in the field of political science (it means a territory that is controlled, or owned, by some other sovereign state.)  (This leads to my aesthetic dislike: the political dependency relation is asymmetric, while the dependence relation we use in program analysis is not.)

There are lots of minor variations between dependence graphs.  The dependences can be must dependences ("a always depends on b") or may dependences ("a could depend on b").  The graph might show control dependences in addition to data dependences (in which case it will be called a program dependence graph, and almost certainly will not be called a data-flow graph).  The dependence graph might or might not be superimposed on top of a control-flow graph.

Whether something is called a dependenc(e/y) graph or data-flow graph is pretty much also a matter of taste.  I try to avoid data-flow graph in my own writing, unless I am specifically talking about someone else's research and they have used the term data-flow graph.  (In particular, research on Dataflow computer architectures.)


Maximum degree of concurrency in task dependency graphs

If you turn an activity-on-node task graph into a partial order (by taking the transitive closure), then the largest independent set of tasks is what you are looking for.

(Taking a topological sort, as suggested in another answer, does not work in general.  Consider the series-parallel task graph $((a|b)c)|(d(e|f))$, where $\alpha|\beta$ means parallel composition of task graphs and $\alpha\beta$ means every task in task graph $\alpha$ precedes every task in task graph $\beta$.  Here $\{a,b,e,f\}$ is the largest independent set, yet the topological sort will produce $\{a,b,d\}$.)

Although finding largest independent sets is NP-complete in general, it can be done quickly for partial orders.  This starts by noting the equivalence of an independent set in a poset with a set of witnesses that realise the width of the poset, and applying König's theorem to compute the witnesses by a perfect matching.

Some of these basic algorithms are already part of software toolkits, like the Graph CPAN module for Perl, and the Boost Graph Library for C++.


Difference between Parallel and Concurrent programming?

Distinguish parallelism (using extra computational units to do more work per unit time) from concurrency (managing access to shared resources). Teach parallelism ﬁrst because it is easier and helps establish a non- sequential mindset.

From " A Sophomoric∗ Introduction to Shared-Memory Parallelism and Concurrency" by
Dan Grossman (version of November 16, 2013)


Once you get the hang of these, they are quite easy, so the first thing is not to over think things.

To prove containment in NP (in this manner) you need (as you mention):

A witness. This is just a "string" that proves an instance is a Yes-instance. So it can just be the solution. When we say "string", typically we don't define how the string is encoded, or even really that the witness is a string. What we give is a format for a solution.
A verifier. This is a Turing Machine that takes a witness (hence why the witness is a string, formally) and the original input, and checks that the witness is correct. So really the verifier is a set of steps to perform this check, given a witness in the correct format. For NP, we have the additional restriction that the verifier has to run in deterministic polynomial time.

So for this problem we can represent a solution as a collection of sets of boxes. We can assume that the boxes have a unique ID. This is the witness. You should, to cement this, try to write done a more precise format for this.

The verifier then should take such a string and check the following:

There are at most $s$ sets (or exactly, depending on the exact problem specification).
That each box appears exactly once, somewhere.
That the total weight of each set is at most $t$.

It should, hopefully, be clear that this verifiers that the solution is correct. The only thing that remains to do, is show that the verifier runs in deterministic polynomial time. Again this should hopefully be fairly clear. Even if we do each step separately, it's three passes over the list  (we can, for convenience, assume that the verifier is a multitape machine, so we can more easily represent data structures), and this is certainly polynomial.


Is “A -> aAA” convertible to regular grammar?

You can prove inductively that any word $w$ generated by your grammar satisfies $$\#_b(w) + \#_c(w) = \#_a(w) + 1.$$
Also, you can prove inductively that for every $n$, your grammar generates a word having $a^n$ as a prefix.
You can now use the pumping lemma to show that the language generated by your grammar isn't regular.
Variant: intersect the language generated by your grammar with $a^*b^*$ to get an explicit language which is not regular.


Creating a CFG that connects lengths of three blocks

Here comes the grammar based on your part of the answer and the comments of Raphael and Rick Decker (including $l\ge 1$). At first, your part:

$S\to aA_1abA_2$
$A_1\to aA_1ab\mid\varepsilon$

Secondly, we create rules for $A_2$ such that we get words of the form $c^kA_3e^k$

$A_2\to cA_2e\mid A_3$

Finally, we create rules for $A_3$ such that we get words $c^ld^l$ with $l\ge1$:

$A_3\to cA_3d\mid cd$


Dynamic programming doesn't necessarily mean that your solution will be efficient. It just means that your problem can be defined using a recursive function, for which you can use memoization.
To understand what this function is, take a look at the proof. The invariant is "after $i$ iterations, we've found all shortest paths of length at most $i$". Therefore, we can define our function $f(v, \ell)$ - the length of the shortest path to vertex $v$ with length at most $\ell$ - in the following way:
$$f(v, \ell) = \min_{u \ \in\  in(v)} (f(u, \ell-1) + d(u,v))$$
What Bellman-Ford does is slightly different (e.g. it can compute all shortest paths in a single iteration, if our order is lucky), but it can only help us, so we don't mind.


Does Thompson's algorithm produce optimal NFAs?

Minimizing NFAs is known to be PSPACE-hard: Meyer and Stockmeyer showed that given an NFA, it is PSPACE-hard to find the size of the minimal equivalent NFA, and Jiang and Ravikumar showed that given a DFA, finding the size of the minimal equivalent NFA is PSPACE-hard. Later some hardness of approximation results were proved, showing that it is even hard to approximate the size of the minimal equivalent NFA. See these lecture notes by Artem Kaznatcheev for more details.

Since a regular expression can be converted to an NFA of comparable size using Thompson's algorithm, these hardness results show that we can't expect any efficient algorithm to convert an regular expression to a minimal-size NFA.


Probably you should ask questions about how to ask on MathStack on their meta site! Each site on Stack Exchange has a Meta site to ask questions about asking questions! They even have a tutorial there: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference

However, learning how to typeset mathematics is something Computer Science students and researchers have to learn how to do, so perhaps it could be considered just about on-topic!

MathJax is based on LaTeX which is a page description language used for writing documents which happens to be quite good at writing maths. LaTeX (created  by Leslie Lamport) was built upon TeX which was created by Donald Knuth. Both Computer Scientists.

The simplest way of using MathJax is to just use the dollar symbol $ to quote or surround your formula. If we take your first formula:

((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)

Put it with the dollars, we get:

$((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

which displays this:

$((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))/(4)$

Now perhaps you want that to be a bit neater. They you can replace the slashes by some better arrangement and make them fractions. In MathJax w can invoke layout function by using the backslash \ to indicate a layout function name and give its arguments within curly braces {}. We want the \frac function like this:

$\frac{((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

$\frac{((50^A)*((((50^B)(((50^C)+1)/(4)))+1)/(4)))}{(4)}$

We can do that again for each fraction:

$\frac{((50^A)*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

$\frac{((50^A)*(((\frac{(50^B)((\frac{(50^C)+1)}{(4)}))+1)}{(4)}))}{(4)}$

Which can be tidied up further, but that gives you the basics!


Do NFAs with $\varepsilon$-moves never terminate?

Sipser proposes an operational intuition for non-determinstic machines. As you have experienced, it's not very useful. In particular, it doesn't relate a lot to the formal definition, and there are more problems down the road¹.

I recommend sticking to the definition: an NFA accepts an input if there is a path from a starting to a final state labelled with the input. That really tells you all you need to know, and all there is to know.

Try to think mathematically instead of computationally.

Parallelism and non-determinism are not the same; you can not build non-deterministic machines in a meaningful sense; cost models (e.g. in complexity theory) for non-deterministic machines don't make sense if you have the split/fork intuition; ...


How to represent a recurrence that increments by one at each tree level?

As each time $n$ is divided by $2$ and $2$ multiplied by 2, it should be:
$$
T(n) = 2T(\frac{n}{2}) + 2^n
$$
Now, if you expand it:

$$
T(n) = 2(T(\frac{n}{2^2}) + 2^{\frac{n}{2}}) + 2^n = 2T(\frac{n}{2^2}) + 2 \times 2^{\frac{n}{2}} + 2^n
$$

How can we guess $T(\frac{n}{2})$? Because $i$ is changing from $0$ to $\log{n}$. If we suppose $T(0)$, when $i = 0$, it will be the not recurrent part of the equation. Hence, we found that it is $2^n$. How did we find we should multiply by $2$? Because each time the relation is multiplied by $2$ and we have a power of it in each iteration. Hence, it should be multiplied by the recurrent part of the relation, which is $T(\frac{n}{2})$ here.

Eventually, form the mater theorem, we can conclude that $T(n) = \Theta(2^n)$.


Given a λ-term, can I decide which machine model I need to express it?

Paraphrasing, this seems to be your question:

  Given an unrestricted λ-term, can I determine what kind of automaton/machine model I need to express it?

Such properties are inherently undecidable (usually).
Starting with a Turing-complete formalism, Rice's theorem immediately tells you that what you are asking is impossible.

The set of TMs/λ-terms corresponding to any non-empty, non-Turing-complete machine model forms a non-trivial index set and is thus is never decidable.

Of course, if you restrict yourself to a less than Turing-complete base set of terms, Rice's theorem does no longer apply. This is still a tough question to ask, though, even at lower levels of the hierarchy. For instance, it is undecidable if an NPDA accepts a DCFL, if a context-free grammar describes a regular language, or even if a context-free grammar is equivalent to a fixed regular grammar.


How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

This algorithm can be re-written like this

Scan A until you find an inversion.
If you find one, swap and start over.
If there is none, terminate.

Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the pattern-matching approach many succumb to!

Nota bene: One has to be a little careful: some inversions appear early, some late, so it is not per se trivial that the costs add up as claimed (for the lower bound). You also need to observe that swaps never introduce new inversions. A more detailed analysis of the case with the inversely sorted array will then yield something like the quadratic case of Gauss' formula.

As @gnasher729 aptly comments, it's easy to see the worst-case running time is $\Omega(n^3)$ by analyzing the running time when sorting the input $[1, 2, \dots, n, 2n, 2n-1, \dots, n+1]$ (though this input is probably not the worst case).

Be careful: don't assume that a reversely-sorted array will necessarily be the worst-case input for all sorting algorithms.  That depends on the algorithm.  There are some sorting algorithms where a reversely-sorted array isn't the worst case, and might even be close to the best case.


$P \subseteq RP $, $BPP \subseteq PSPACE $.
So $PSPACE \subseteq P $, $-->$ $BPP \subseteq RP $.


given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}?

What is the question?

A vertex v ∈ G.V can have shortest paths from other vertices u ∈ G.V - {v}. What is the minimum of all these paths to v? This is *(u, v). You  have to calculate this minimum value for all the vertices

Why the solution works?

To get to a vertex v you have 2 options:

Take minimum incoming edge from u to v i.e. w(u, v)
Get to u and then take the edge from u to v i.e. u.d + w(u, v)

You have to find the minimum of these 2 options. So min(w(u, v), u.d + w(u, v))

In either of the cases the v.pi will be u


Is there an equivalent of lambda calculus for object oriented languages?

So what is the equivalent for object oriented languages?

Lambda calculus.

I mean, there is Cardelli's object calculus (and a handful of derivatives), but in general, there's nothing fancy about object oriented languages that requires a new approach to computation.

It's well known (see TaPL for example) how to extend/encode Records and Mutation (and sub-typing/dispatch) onto/in lambda calculus. The underlying structures don't need to change, even though there are often layers above it that add semantic restriction and make things more usable (member access, implied this, object layouts, etc).


Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language
$$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$
is context-free (indeed, regular).
The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; this will be checked on-the-fly by the parser. This idea is implemented by representing identifiers as a single token in the grammar of Pascal or Algol.


Combination with a minimum number of elements in a fixed length subset

For each particular $m,k$ you can get a recurrence formula and solve it. Perhaps this way you can obtain a general formula. Here is how to find the recurrence formula:

The language of all valid sequence is regular. Construct a DFA (deterministic finite automaton) that accepts the language. (An optimization: construct a "partial" DFA in which sometimes there is no outgoing edge labeled $0$.)
Suppose the transition matrix is $A$, the initial state is $s$, and the accepting states are $F$. Then the number of sequences of length $n$ is $\alpha_n = 1_F A^n 1_s$.
Compute the Jordan normal form of $A$, decompose $1_F,1_s$ according to the Jordan basis, and so obtain a formula for $\alpha_n$.

Instead of using DFAs, you can use generating functions, which really amounts to the same.

Here is a very simple example: $m = 2$ and $k = 1$. The regular language here is all words not containing $00$, that is $1^*(10)^*1^*$. The minimal partial DFA has two states $s_0,s_1$ which correspond to the two possible "histories" (we can assume that the part of the sequence before it actually starts consists entirely of 1s) - in general there will be $2^{m-1}$ states (if $k < m-1$ then actually less, since some of them would be invalid). The transitions are: On $0$, transition from $s_1$ to $s_0$; On $1$, transition from $s_0,s_1$ to $s_1$. The starting state is $s_1$. All states are accepting (this will always be the case with a minimal partial DFA). The transition matrix is
$$ A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}. $$
Therefore
$$ \alpha_n = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}. $$
The matrix $A$ has two eigenvalues $(1 \pm \sqrt{5})/2$, and furthermore
$$ A = \begin{pmatrix} 1 & 1 \\ \frac{1-\sqrt{5}}{2} & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1}{2} + \frac{\sqrt{5}}{10} & -\frac{\sqrt{5}}{5} \\ \frac{1}{2} - \frac{\sqrt{5}}{10} & \frac{\sqrt{5}}{5} \end{pmatrix}. $$
Thus
$$
\begin{align*}
\alpha_n &= \begin{pmatrix} \frac{3-\sqrt{5}}{2} & \frac{3+\sqrt{5}}{2} \end{pmatrix} \begin{pmatrix} \frac{1-\sqrt{5}}{2} & 0 \\ 0 & \frac{1+\sqrt{5}}{2} \end{pmatrix}^n \begin{pmatrix} -\frac{\sqrt{5}}{5} \\ \frac{\sqrt{5}}{5} \end{pmatrix} \\ &=
\frac{5-3\sqrt{5}}{10} \left( \frac{1-\sqrt{5}}{2} \right)^n +
\frac{5+3\sqrt{5}}{10} \left( \frac{1+\sqrt{5}}{2} \right)^n.
\end{align*}
$$
The first few numbers (starting with $\alpha_0$) are $1,2,3,5,8,13,\ldots$, and we recognize the Fibonacci sequence: $\alpha_n = F_{n+2}$.

An alternative to following these steps is noticing that $\alpha_n$ is always defined by a recurrence relation of length at most $2^{m-1}$. So for general $m,k$, all you have to do is calculate enough of the sequence $\alpha_n$ to determine the coefficients: you need to calculate $\alpha_0,\ldots,\alpha_{2^m-1}$, which will give you $2^{m-1}$ equations.

Here is how to do it for $(m,k) = (2,1)$: $\alpha = 1,2,3,5$. If $\alpha_n = c_1 \alpha_{n-1} + c_2 \alpha_{n-2}$ then $3 = 2c_1 + c_2$ and $5 = 3c_1 + 2c_2$. We deduce that $c_1 = c_2 = 1$ and so the recurrence is $\alpha_n = \alpha_{n-1} + \alpha_{n-2}$.

Having recovered the recurrence relation, we solve it as usual. It will usually be the case that all roots of the characteristic polynomial are distinct, and that the asymptotics of the sequence are given by the largest root (though in principle it depends on the actual sequence).


How will the value, A(2) be available in, line 2, if A(2) is being calculated in, line 3?

The point is that it doesn't use the new value, it uses the old value. You want to take the current value of A[i+1] and use it to calculate a new value for A[i]. If you do each operation in order, you'll always do the operation which uses the old value, before overwriting it with a new value.

The problem is, when you vectorize this, you might end up changing A[i+1] at the same time as you're trying to read its old value. But ideally vectorization shouldn't change the result of a process, only how fast it runs. This is why you need the TEMP array, to keep the result the same.


How to interpret parametric formulation of information bottleneck?

The notation stands for the maximum value of $-I_{\phi}(t;x) + \lambda I_{\phi,\theta}(t;y)$, where the maximum is taken over $\phi,\theta$. The result will be a function of $t,\lambda,x,y$.
Often in such a notation, the possible values of the variables being maximized over is restricted, and sometimes this forms part of the notation (say, $\max_{0 \leq \phi,\theta \leq 1}$). In other times, the possible values are restricted, but this is not reflected in the notation, and should be gleaned from context.


"At least one" clause in Relational Algebra

A first hint toward a solution is to think about "what's the result of a natural join between $Author$, $Publication$ and $AuthorPublication$?"
The answer is "the universal relation" $R(BookID,AuthorID,Title,Year,Name)$ describing who wrote a book and when. Note that a book without any author or an author without any book written won't appear in $R$. So an author in $R$ as written at least one book. The following query gives the authors who wrote at least a book in year 2008:
$$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 =  year)}(Publication))$$

For the final answer, compute the intersection of this query with its variants:
$$ \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2008 =  year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2009 =  year)}(Publication)) \cap \pi_{Name}(Author \Join AuthorPublication \Join \sigma_{(2010 =  year)}(Publication))$$

You may provide other equivalent answers with outer $Author \Join$.


Convert finite automata to regular expression

You have an error in your regular expression. The correct one is $(ab)^*ab c^*dd^*$ (notice that after reading $(ab)^*$ you are in state $A$ and that the edge from $B$ to $C$ is labelled $b$).
This can be rewritten as $(ab)^+ c^*d^+$ since $(ab)^*ab = (ab)^+$ and $dd^* = d^+$.
Another equivalent expressions is $a(ba)^*bc^*dd^*$ since $(ab)^+ = a(ba)^*b$.


N 3d integer points in box with maximum average distance

Note that maximizing the average distance between every pair of points is the same as maximizing the total distance between every pair of points.

Let's look at an m x m square first. When N = 4, it is clear that the optimal solution is placing a point in each corner.

For N = 5, the next picture explores two alternatives of placing the 5th point when the other 4 are in the corners. It appears it is optimal to place the 5th point also in a corner. Note that in the right picture, which is already sub-optimal, the total solution does not improve when moving any of the other four points (which are in the corners).

This solution does not work for all N, but it generalizes to cubes when N is a multiple of 8. Then all points are in the eight corners in an optimal solution.


Possible to develop a game using assembly language?

Yes, most definitely!

Would you want to these days? No, probably not, unless you were doing it for educational purposes.

The first games on computers were coded in Assembly language, because when computers first came out there wasn't anything else to program in. The most recent example of a popular game that I know of which was written in Assembly is RollerCoaster Tycoon: http://en.wikipedia.org/wiki/RollerCoaster_Tycoon

The are a lot of limitations of writing a game in Assembler code.For example, in assembler you are writing individual instructions to the CPU. This takes a lot of thought and a lot of time. Chances are you won't be doing it as efficiently as you could be too! A modern programming language, like C++ for example, would be far easier to code a game in these days. It allows you to think about how you want to program things in at more complex level without having to think about the very basics of how it will actually run on your computer.

Plus, different computers will have their own versions of Assembler code, so writing your game on one computer may mean it won't run on a whole other line of computers! But when you write a game in something like C++, there's a special program you run that will turn it into assembler code, specifically for what ever machine type you run it on!

To sum this up, I'd say there really is no point writing a game in assembler, unless you are doing it to learn assembler. You will get much faster and better results when making a game if you do it in a higher level language. If you want to get up and running quickly I'd say you should go for something like Java, specifically using a special IDE & library called 'Processing', take a look at it and see how easy it is to get up and going, pretty good if this is your first time programming something and want to get a hang of it:

http://www.processing.org/


Validity of list of articulation points in a graph after a node is deleted

Yes and yes. Look at this graph:

$V=\{1,2,3,4\}$
$E=\{\{1,2\},\{2,3\},\{3,4\},\{4,1\}\}$

There is neither articulation point nor bridge. But if you delete any node/edge...


trace vs. computation vs. run vs. execution vs. walk

There is no set terminology for this. Check the definition/use of the term where it appears.

Personally, I'd call it "computation", meaning the sequence of configurations the automaton goes through. And try to be consistent with this usage.