If you need the optimal answer, the best solution I know is exhaustive search: try all ${|P| \choose 10}$ different subsets, and see which is best.  The running time of this will be $O(|P|^{10})$, though, which is probably too high to be feasible.

Given this, you will probably need to accept solutions that are heuristics or not guaranteed to give an absolutely optimal answer.

One standard approach is to use a greedy algorithm: you iteratively build up a set of properties, one by one.  At each step, if your set is currently $S$, you choose the property $p$ that makes $S \cup \{p\}$ as accurate as possible, and then add $p$ to $S$.  To turn this into a full algorithm, you need to decide how you want to measure/evaluate each candidate $S \cup \{p\}$.

For comparison, you can look also at the ID3 algorithm.  Rather than trying to pick a set of size 10, it tries to pick a decision tree of depth 10, so it's not solving exactly the same problem: but it is similar.  The metric used at each step to evaluate the candidates is the information gain; you could do the same, but for a set rather than a tree.

In the machine learning literature, there is a lot of work on feature selection: given a large number of possible features, the goal is to pick a subset of the features that makes the classifier as accurate as possible.  You could explore that literature and see if any of those methods are effective in your domain.


Why can Multilayer neural networks solve non-linear problems

A single-layer network is already nonlinear, but it's only a limited kind of nonlinearity.

Yes, the ability to have multiple layers and multiple hidden nodes is what allows multi-layer neural networks to express any function.

Let me give you an analogy that provides intuition but shouldn't be taken too seriously.  A single NAND gate can compute only a single, simple function.  However, when you consider circuits containing NAND gates, they can express any boolean function: the ability to have multiple layers of NAND gates, and multiple intermediate gates in the middle, allows you to express any boolean function.  Something vaguely similar happens with multi-layer neural networks: each individual unit provides a limited amount of nonlinearity, like a NAND gate, and the ability to compose them is what lets you express more complex nonlinear functions.


Using Queues for a Stack and Stacks for a Queue

To answer the question in the comment above-

Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty):

PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A.

POP: Dequeue from Queue A


Variable Capturing With Repetition of Variable Name

If you make the construction tree of the expression, a variable  $x$ of a leaf refers to that $\lambda x$ which is closest to $x$ in the path from $x$ to the root.

Another way to see it is with the use of scoping rules. The scope of each $\lambda$ is the body of the $\lambda$.

So, the scope of the inner-most $\lambda a$ is only $a$. This means that any occurrence of $a$ outside that parenthesis refers to a different variable than the $a$ inside the parenthesis (point 1).

The scope of the $\lambda b$ is $(λa.a)aba$, so similarly any $b$ outside this expression refers to a different variable (that just happens to have the same name).

The scope of the outermost $\lambda a$ is $\lambda b.(\lambda a.a)aba$. Here things are a bit more complex, because there's another $\lambda a$ inside. But according to point (1) the $a$ in $\lambda a.a$ is different than the $a$'s in the rest of the body. So, only the $a$'s in $aba$ refer to the outermost $\lambda a$.

Note that there are no lambda's to bind the $a$ and $b$ in subexpression $(ab)$ (on the right of the expression). Therefore, the $a$ and $b$ in $(ab)$ occur free.


What should I read to understand semantics of programming languages?

There are many depending on where you want to start and what exactly you want.
Usually textbook start with giving semantics to the While or IMP language and then give references to semantics of lambda calculus (typed untyped) unless you are reading Gunter. I am listing down a few below that I have referenced a number of times:

Operational Denotational and Axiomatic:

a. Formal Semantics of Programming languages by
Wynskell

b. Programming Language Foundations by Stump

c. Theories of programming languages by Reynolds
Denotational semantics:
Denotational Semantics by Stoy
Denotational and Categorical semantics: Semantics of Programming languages by Gunter
Categorical semantics: Category theory for computing science by Barr and Wells
Mostly operational semantics (may be with types involved):

a. Types and Programming languages

b. Semantics Enginnering with PLT redux

See also this question and this question on stackexchange.
and this further reading section of wikipedia article


Time complexity of insertion in linked list

The question only says that the target list needs to be maintained in sorted order. It doesn't say anything about any other data structure that you may choose to use. The proposed solution first does some preprocessing of the arguments to insert, then does the insertion proper. This is allowed by the problem statement.

A practical reason to do this, rather than insert the elements then sort, would be if the linked list object is shared with another thread that requires it to always be sorted. (In such a scenario, you'd need to ensure that inserting one element is atomic.) So this question isn't just making strange requirements for the sake of being strange. It's the sort of requirements that come up often in the real world of programming.

Another solution with the same complexity would be to insert the elements into the target list as they come, and maintain a parallel data structure mapping element values to node pointers in the target list. To insert each element, find the preceding element in the mapping, and insert the new element after this node. This assumes that the insertion process creates the list nodes as it goes (as opposed to filling existing blank nodes).

This question is more about reading comprehension than about algorithms. The way it's worded, it's a bit of a trick question. It's somewhat poorly worded because it relies on precise reading, but fails to state some key assumptions, such as the fact that obtaining the elements to insert costs $O(n)$, comparing two elements can be done in $O(1)$, and the input domain is effectively unbounded (exercise: come up with an $O(n)$ algorithm if the inputs are integers in the range $[1,42]$). But the given answer is correct.

You made the assumption that there's no way to use an auxiliary data structure. Nothing in the problem statement forbids using auxiliary data structures. A simple way to forbid auxiliary data structures would be to require $O(1)$ memory overhead.

Note that even under this assumption, your reasoning is wrong, or at least imprecise. If you happened to know that the elements are given in the correct order, you could maintain a pointer to the tail of the list, and keep inserting there, which would take $O(n)$. The worst case is not if every element has to be inserted at the last position in the target list, but at the last position reached when traversing the list in some way. The worst case is indeed $\Theta(n^2)$, but to prove this, you have to prove that finding the insertion point in the list takes $\Theta(n)$ time, and this requires proving that the distance from any pointer you have into the list is bounded below by $\Omega(n)$. This is the case if you have a constant number $A$ of pointers (you implicitly assumed $A=1$, with a single pointer at the start of the list), so that you need to traverse at least $k/A$ nodes after $k$ insertions in the worst case.


A very similar well studied problem is the assignment problem. In essence, it seeks to find a matching in a weighted bipartite graph that has maximum weight. Such matching is not necessarily stable, but maximum weighted matching might be preferable than a stable one, depending on the application.

On the plus side, the well known Hungarian algorithm solves the assignment problem in an optimal manner. There are also other methods to solve it such as the Auction algorithms. As I said, the field includes well established methods.

Maybe you can think about representing your problem as an assignment one rather than stable marriage.


When does the product automaton of two NFAs A and B not decide L(A) U L(B)?

The culprit is the fact that, in the presence of nondeterminism, automata need not have transitions to other states for the same input symbols.

Consider two NFA over the input alphabet $\{a,b\}$:

$$N_1 = (\{q_1\},\{a,b\},q_1,\delta_1,\{q_1\})$$

where $\delta_{1}(q_1,a) = \{ q_1 \}$ and $\delta_{1}(q_1,b) = \emptyset$

and

$$N_1 = (\{q_2\},\{a,b\},q_2,\delta_2,\{q_2\})$$

where $\delta_{2}(q_2,a) = \emptyset$ and $\delta_{2}(q_2,b) = \{ q_2 \}$

– that is, each of these automata has a single state, which is accepting, and a single transition, which is a loop on $a$ or $b$, respectively.

Clearly, $L(N_1)= \{ a^n \mid n \geq 0 \}$ and $L(N_2)= \{ b^n \mid n \geq 0 \}$. But the product construction will give us an automaton

$$N_{12} = (\{ (q_1,q_2 \}, \{ a,b \}, (q_1,q_2), \delta_{12}, \{ (q_1,q_2)\})$$

where $\delta_{12}((q_1,q_2),a) = \emptyset$ and $\delta_{12}((q_1,q_2),b) = \emptyset$, since there is no symbol $x$ such that both $N_1$ and $N_2$ admit an $x$-transition from their sole state.

Therefore $L(N_{12}) = \{ \varepsilon \} \neq L(N_1) \cup L(N_2)$.


Dijkstra Partitioning Algorithm : Special Case

Short answer: No. Note that the worst case of this algorithm is when all elements are blue. In such case, you will need $2\cdot n$ swaps in the worst case. When all elements are blue the number of swaps can be zero.

Optimal algorithm:

I think that the following algorithm is the optimal one:

Count the number of Reds, Blues and Whites in the array.
Denote $n_{color}$ the number of elements of $color\in \{ Blue,Red,White \}$ in the array.
Define $i=0, j=n_{Red}-1$, and $k=n_{Blue}+n_{Red}-1$,  i.e., counters over the Reds,Blues and Whites arrays in the corresponding  , respectively.
Increase i,j,k until either the counter is lager than the size of the corresponding array (i.e., $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$), or that the corresponding element is not in the appropriate color (i.e., $a[i]$ is not red, $a[j]$ is not blue, $a[k]$ is not white). The algorithm stops iff when all counters are lager than the size of the corresponding array $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$.

Now, if $a[i]$ is blue and $a[j]$ is red, then we can swap between them, and increase the counters of $i$ and $j$ until possible.  The same can be said if $a[i]$ is white and $a[k]$ is red or  $a[j]$ is white and $a[k]$ is blue. Thus if there are two elements of  $(a[i],a[j],a[k])$  with the same color- we can swap the corresponding pair, and  increase the corresponding counters.

In the edge case where $a[i]$ is blue and $a[j]$ is white, and $a[k]$ is red, we must do $2$ swaps. The same happens if $a[i]$ is white and $a[j]$ is red, and $a[k]$ is blue.

The number of swaps in such algorithm is at most $\frac{2}{3}n$, in case the array begins with $\frac{n}{3}$ blues,  continues with $\frac{n}{3}$ whites, and ends with $\frac{n}{3}$ reds.

I think that this is the optimal algorithm, I will try to show later the correctness.

2.Is the algorithm applicable if there are 4 colors to be partitioned?
I think it does. In the worst case, you can use counting sort, which runs at $O(nk)$ given $n$ elements and $k$ colores.


An imperative program is analogous to how a Turing machine works?

At a high enough level and when contrasted with functional programming, sure. Turing machine models and imperative programs have in common that they start from an input and take a series of steps that change a state stored in memory, ending with some output.

This contrasts with lambda calculus and functional programming which generally and loosely do not have the above features.

I think reading any more into the comparison than this, or trying to take it any farther, is probably a mistake. As Yuval says, Turing machines are quite different from modern machines and program execution environments.


Regular expression for all binary strings avoiding 0110

A string avoids $0110$ regardless of any initial or final $1$-runs, so we it suffices to consider strings starting and ending with $0$. We can write every such string as follows:
$$
0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_\ell},
$$
where $a_1,b_1,a_2,b_2,\ldots,a_\ell \geq 1$. This string avoids $0110$ if $b_i \neq 2$ for all $i$.
The following infinite regular expression corresponds to the above:
$$
\epsilon + 0^+ + 0^+(1+111^+)0^+ + 0^+(1+111^+)0^+(1+111^+)0^+ + \cdots
$$
Here the first summand corresponds to the edge case $\ell = 0$. We can describe all of these cases using a single regular expression as follows:
$$ \epsilon + (0^+(1+111^+))^*0^+ $$
Bringing back the initial and final $1$-runs, this gives the following regular expression for your language:
$$ 1^* + 1^*(0^+(1+111^+))^*0^+1^* $$
Using some case analysis, we can simplify this into
$$ 1^*(0^+(1+111^+))^*0^*1^* $$


Compare asymptotic WC runtime with measured AC runtime

You can't, not really, for three reasons:

Number of operations and runtime do not compare well; too many factors (typically) left out in analysis influence actual runtime.
Asymptotic results (which hold in the limit) and a finite sets of observations do not compare.
Landau classes don't compare with "exact" functions. For instance, if you have $f \in O(n^3)$ and $g(n) = 3n^2$, you have no idea which grows faster.

All hope is not lost, though. With some additional work you can get to reliable statements.

Perform an (asymptotic) average-case analysis. That is, assume a random distribution on the input set and calculate the expected number of executed operations. That can be tough, but if you succeed you can compare the result to your worst-case asymptotic. (Note that you may need $\Theta$ to make meaningful statements.)
If you can, improve your analysis to yield constant factors (not only $\Theta$). That way, you can separate, say, a $2n^2 + 5n$ worst-case from $1.5n^2 - 3 \log n$ average-case.
Run the program for worst-case instances (you should know them from your WC-analysis) and compare the real measurements with the average case.

Note: This can only provide guesses for asymptotic behaviour.
Alternatively, run the program average and worst-case instances but count statements. That gives you more reliable measurements and removes platform-dependent artifacts from consideration. Still, you get only guesses for asymptotics.

Bottom line, you have to have the same "kind" of statement for both worst- and average-case if you want to compare them.


Implicit complexity and interpretation of total languages

As concluded via non-direct means in discussion interpreting a polytime program cannot be done in polynomial time in general. The following example shows this directly.

The trick is that for the interpreter to run in polynomial time there must be an polynomial that bounds the running time for every input. This pretty obviously isn't going to hold for System-$B$ because a small constant increase in program size can increase the order of the polynomial that bounds it by a constant amount. The trick you can fall into (and I indeed fell into) is to think that because for each program the running time is bounded a polynomial that the interpreter will run in polynomial time which is pretty embarrassingly obviously false when you write it out like this. It's running time on certain inputs will be bounded by some polynomial but that's the case for any program that always terminates.

So say there is a program, $I$ in System-$B$ that interprets System-$B$ and has running time in $O(n^k)$. Say I had another program, $P$, that ran in $O(n^K)$ with $K > k$. We could speed up P to $O(n^k)$ by simply running it though the interpreter first. So suddenly you have a huge speed up on $P$ that you shouldn't be able to get. In general $I$ could speed up any program slower than it.

I don't have a proof there is no $k$ such that every polytime function can be computed in $O(n^k)$ but it seems fairly obviously the case.


How to analysis the complexity of this LIS program?

The worst case running time of your first procedure satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + O(1).
$$
The worst case running time of your second procedure is $T(n) + \cdots + T(1) + O(1)$, which we can identify with $T(n+1)$. Thus it suffices to understand the first recurrence.
Let us assume replace $O(1)$ with $1$, obtaining the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + 1.
$$
Therefore
$$
T(n+1) = T(n) + [T(n-1) + \cdots + T(1) + 1] = 2T(n).
$$
Consequently, $T(n) = 2^{n-1} T(1) = 2^{n-1}$.
If we replace $1$ back with $O(1)$, we get $T(n) = O(2^n)$.


How can every regex be accepted by an infinite number of finite automata?

There are at least two ways of doing this.

The first is kind of trivial: there's no requirement that all states of an automaton be accessible from the start state. So, take your favourite automaton that accepts some language, and then add as many new states as you want, with arbitrary connections between them, as long as they're not connected to the original automaton.

A second way keeps the automaton connected. I'll give an informal description; I wrote a more formal one in response to another question. Take your favourite automaton and make $n$ copies of every state. Modify the transition function so that if, in the original automaton, $\delta(q,a)=q'$ then, in the new automaton, reading $a$ in the $i$th copy of state $q$ takes you to the $(i+1)$st copy of $q'$ (with addition modulo $n$). The start state is the first copy of the original start state; every copy of an accepting state is accepting. This isn't guaranteed to keep the automaton connected but you can delete the disconnected states and you are guaranteed to end up with an automaton with at least $n$ states.


Generating a adjacency matrix representing a DAG

Yes there is an easy way to generate a random DAG. If a graph is a DAG it can be separated into levels or ranks. The idea is to rank the nodes and randomly generate edges from lower ranked nodes to higher ranked nodes. A little bit of Googling finds the exact same question asked on stackoverflow a few months ago (with sample code!).

My only concern is that an adjacency matrix representation for a graph with billions of nodes/edges won't fit in memory. However, it's possible I misunderstood your intent in that part of the question.


Which queue does the long-term scheduler maintain?

I found an appropriate answer. I was asking about the job queue (which I already described). The diagram included in this answer comes from a  power-point that uses concise language to explain processes and schedulers and relates the topic to the diagram.

It may be of intrest to other users, also learning this topic, that sometimes time-sharing systems (such as UNIX) have no (or minimal implementations of a) long-term scheduler.

Check these sources for more information:

1.Wikipedia Article

2.Operating System Concepts (Pages 88-89)

 ©Bernard Chen 2007


reference request: solving problems by dynamic programming + quantization to avoid combinatorial explosion

This sounds like a reinforcement learning problem.
Construct the following MDP:

The states are the different values of $x$
The actions are $u_1,\dots,u_L$
The transition is given by $f$
The reward is given by $g$ of the current state.

Define it as a finite horizon problem.
Then, if the set of the values of $x$ is finite, use any RL technique to solve the problem (you can use a dynamic programming solution from there to compute the exact solution).
If the state space is infinite, or extremely huge, consider trying to use the equivalent techniques from reinforcement learning.
If you wish, leave here a comment and when I will be able to I will send the algorithms themselves.

Anyways, from my understanding of your solution - it looks correct. But you need to be cautious about the use of $B$ and $\epsilon$ since cutting the space into boxes increases the number of boxes dramatically with the increase of the dimensions


decision diagram and decision tree difference

Decision tree is a tree.

Discision diagram is not necessarily a tree.

A binary decision diagram is a directed acyclic graph.

See the diagram at https://en.wikipedia.org/wiki/Binary_decision_diagram


What is the difference between luma and luminance?

There are actually three related terms:

Luminance is a physical measure which represents the luminous intensity per unit area of light travelling in some direction. The units are candela per square metre. This is, if you like, an objective measure of how "intense" light is.
Relative luminance is a measure how "intense" light appears to a human; since humans can't see X-rays or infra-red, that doesn't register. The CIE standard defines a "standard observer" (more on this later) under various conditions. This is normalised into a range from 0 to 1 or 0 to 100, where the higher value is a reference white.
Luma is defined as the relative luminance calculation performed on a gamma-compressed video signal.

So if you take a real-world light source, and point an image sensor at it, the image sensor will output $R'G'B'$ values, where the prime denotes gamma compression.

If you were to uncompress those signals (i.e. convert the gamma-compressed $R'$ into its corresponding linear-space $R$, then:

$Y = 0.2126 R + 0.7152 G + 0.0722 B$ is the relative luminance
$Y' = 0.2126 R' + 0.7152 G' + 0.0722 B'$ is the luma

Relative luminance is exactly Y in CIE-XYZ. Y is calculated by calculating the inner product of the power spectral density of a light source with the luminosity function which represents the "standard observer".

(Note that CIE standard actually defines more than one luminosity function, because the human eye behaves differently in low-light condition; Y is defined in terms of the photopic luminosity function.)

The only reason why we define luma is for signal processing and compression reasons. It's easier to compress based on the luma signal than the relative luminance because the transformation is simpler; in fact, it's achievable using relatively cheap 1960s-era analog electronics. And since there's a more-or-less monotonic relationship between the two, luma key is close enough to keying on relative luminance.

OK, now to your questions:

When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?

High-quality image formats tell you. Along with an array of triplets of numbers (which are just numbers), there should be information about what colour space the image is in.

Unless you have been told otherwise, it's safe to assume that any standard dynamic range still image pulled off the Internet is in sRGB. This is gamma-compressed, although the gamma is not constant.

For video, there are lots of colour spaces in use. Broadcast television follows the ITU-R recommendations (e.g. Rec 601 is standard definition, Rec 709 is high-definition, etc), and film tends to use Cineon.

But each camera manufacturer typically defines its own colour space too, which represents the best approximation of the sensors in the camera. ARRI cameras, for example, output their own colour space known as ARRI Log C.

It's something of a mess.

When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?

"Gamma" is a confusing concept because it refers to two distinct things. Strictly speaking, "gamma" should refer to the nonlinearity of a hardware device, such as a sensor or display. All image data should be linear, intermediate work should be in a linear space, and gamma should only be applied when data is acquired or displayed.

"Gamma compression" refers to a technique for compressing linear data in a file format, so that fewer bits per sample are required.

It just so happens that a lot of modern display vendors and file format designers have agreed on the same standard, sRGB. So if you have data compressed in sRGB format and a display which works in sRGB, the operation of decompressing the file format and the operation of preparing the data for display cancel each other out. In general, that need not be the case.

For a properly calibrated display, yes, Y is relative luminance.

When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?

Answered above. Luminance is the physical measure of the intensity of light, and relative luminance is the perceived intensity of light (for a standardised human observer).

In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?

What I hope you can now see is that Y, relative luminance, is also defined on the human visual system.


How will I calculate the time and space complexity for this pyramid algo?

There is one major for loop in this case

for(m=0; m<len; m++)

It has a complexity of O(len)
Inside this loop, there are 4 other loops, but they are additive in nature and not nested. Each of those loops has a length of <=len. Thus the overall complexity of this program would be O(len*len)
The space complexity will be also be the same.


How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable?

This is a bit of a nit-picky question, since you really need to pay attention to the parity of the number of steps you TM does.

We'll show that the problem is undecidable by a reduction from $A_{TM}$. There are many ways to construct such a reduction. In my opinion, the following is the least technical.

Given input $(M,w)$ for $A_{TM}$, we will construct a new output $(M',\epsilon)$, such that $M$ accepts $w$ iff $M'$ accepts $\epsilon$ within an even number of steps.

We construct $M'$ as follows: given input $x$, if $x\neq \epsilon$, then $M'$ rejects.

Otherwise, if $x=\epsilon$, $M'$ works as follows: simulates the run of $M$ on $w$. If $M$ accepts, it clears the tape by going to the rightmost non-blank cell, and then writes blanks all the way to the left. It then simulates $M$ again, erases the tape again in exactly the same manner, and accepts.

If $M$ rejects, then $M'$ rejects as well.

The idea here is that if $M$ accepts $w$, then the operation of $M'$ on $\epsilon$ is to simulate $M$ on $w$ twice. Therefore, it will take an even number of steps.

Proving the correctness and computability of this procedure is not hard.


Since $k=n-m \ge 0$ you have that $n^2 < f(n,m) \le n^2 + (1/2)^0 = n^2+1$, showing that $f(n,m) \in \Theta(n^2)$.


The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

It doesn't make any sense at all to implement a heap as a linked list. (The most common kinds of) heaps are inherently binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at index K live at indices 2K+1 and 2K+2 if indices start at 0 (or at indices 2K and 2K+1 if indices start at 1). It's massively more efficient to find the Kth element of an array than the Kth element of a linked list.
Advantages of storing a heap as an array rather than a pointer-based binary tree include the following.

Lower memory usage (no need to store three pointers for every element of the heap).
Easier memory management (just one object allocated, rather than N).
Better locality of reference (the items in the heap are relatively close together in memory rather than scattered wherever the allocator put them).


FFT-less $O(n\log n)$ algorithm for pairwise sums

It would seem that this problem is equivalent to integer/polynomial squaring:

1. It is known that polynomial multiplication is equivalent to integer multiplication.

2. Obviously, you already reduced the problem to polynomial/integer squaring; therefore this problem is at most as hard as squaring.

Now I will reduce integer squaring to this problem:

Suppose you had an algorithm:

$$
F(\mathbf{\vec a})\rightarrow P^2(x),\\
\text{where } P(x)=\sum_{a_i \in \mathbf{\vec a}} x^{a_i}
$$

This algorithm is essentially the algorithm you request in your question. Thus, if I had a magic algorithm that can do this, I can make a function, ${\rm S{\small QUARE}}\left(y\right)$ that will square the integer $y$ (oh yes, I do love mathjax :P):

$$
\begin{array}{rlr}\hline
&\mathbf{\text{Algorithm 1}} \text{ Squaring}&\hspace{2em}&\\
\hline
{\tiny 1.:}&\mathbf {\text{procedure }} {\rm S{\small QUARE}}\left(y\right):\\
{\tiny 2.:}&\hspace{2em}\mathbf {\vec a} \leftarrow ()
  &&\triangleright~\mathbf {\vec a}\text{ starts as empty polynomial sequence}\\
{\tiny 3.:}&\hspace{2em}i \leftarrow 0\\
{\tiny 4.:}&\hspace{2em}\mathbf{while}~y\ne0~\mathbf{do}
  &&\triangleright~\text{break }y\text{ down into a polynomial of base }2\\
{\tiny 5.:}&\hspace{4em}\mathbf{if}~y~\&~1~\mathbf{then}
  &&\triangleright~\text{if lsb of }y\text{ is set}\\
{\tiny 6.:}&\hspace{6em}\mathbf{\vec a} \leftarrow \mathbf{\vec a}i
  &&\triangleright~\text{append }i\text{ to }\mathbf{\vec a}~\text{(appending }x^i\text{)}\\
{\tiny 7.:}&\hspace{4em}\mathbf{end~if}\\
{\tiny 8.:}&\hspace{4em}i \leftarrow i + 1\\
{\tiny 9.:}&\hspace{4em}y \leftarrow y \gg 1
  &&\triangleright~\text{shift }y\text{ right by one}\\
{\tiny 10.:}&\hspace{2em}\mathbf{end~while}\\
{\tiny 11.:}&\hspace{2em}P^2(x) \leftarrow F\left(\mathbf{\vec a}\right)
  &&\triangleright~\text{obtain the squared polynomial via } F\left(\mathbf{\vec a}\right)\\
{\tiny 12.:}&\hspace{2em}\mathbf{return}~P^2(2)
  &&\triangleright~\text{simply sum up the polynomial}\\
{\tiny 13.:}&\mathbf {\text{end procedure}}\\
\hline
&\end{array}
$$

Python (test with codepad):

#https://cs.stackexchange.com/q/11418/2755

def F(a):
    n = len(a)
    for i in range(n):
        assert a[i] >= 0

    # (r) => coefficient
    # coefficient \cdot x^{r}
    S = {}
    for ai in a:
        for aj in a:
            r = ai + aj

            if r not in S:
                S[r] = 0

            S[r] += 1

    return list(S.items())

def SQUARE(x):
    x = int(x)

    a = []
    i = 0
    while x != 0:
        if x & 1 == 1:
            a += [i]
        x >>= 1
        i += 1

    print 'a:',a
    P2 = F(a)

    print 'P^2:',P2

    s = 0
    for e,c in P2:
        s += (1 << e)*c
    return s

3. Thus, squaring is at most as hard as this problem.

4. Therefore, integer squaring is equivalent to this problem. (they are each at most as hard as each-other, due to (2,3,1))

Now it is unknown if integer/polynomial multiplication admits bounds better than $\mathcal O(n\log n)$; in fact the best multiplication algorithms currently all use FFT and have run-times like $\mathcal O(n \log n \log \log n)$ (Schönhage-Strassen algorithm) and $\mathcal O\left(n \log n\,2^{\mathcal O(\log^* n)}\right)$ (Fürer's algorithm). Arnold Schönhage and Volker Strassen conjectured a lower bound of $\Omega\left(n \log n\right)$, and so far this seems to be holding.

This doesn't mean your use of FFT is quicker; $\mathcal O\left(n\log n\right)$ for FFT is the number of operations (I think), not the bit complexity; hence it ignores some factors of smaller multiplications; when used recursively, it would become closer to the FFT multiplication algorithms listed above (see Where is the mistake in this apparently-O(n lg n) multiplication algorithm?).

5. Now, your problem is not exactly multiplication, it is squaring. So is squaring easier? Well, it is an open problem (no for now): squaring is not known to have a faster algorithm than multiplication. If you could find a better algorithm for your problem than using multiplication; then this would likely be a breakthrough.

So as of now, the answer to both your questions is: no, as of now, all the ~$\mathcal O(n\log n)$ multiplication algorithms use FFT; and as of now squaring is as hard as multiplication. And no, unless a faster algorithm for squaring is found, or multiplication breaks the $\mathcal O(n\log n)$ barrier, your problem cannot be solved faster than $\mathcal O(n \log n)$; in fact, it cannot currently be solved in $\mathcal O(n\log n)$ either, as the best multiplication algorithm only approaches that complexity.


Why reverse pipeline stages in cycle-level simulator?

This solves the problem that, if you put them in "forward" order, an instruction can stream all the way from fetch to writeback in a single cycle of the emulator. An other solution is explicitly emulating the clocked logic between the stages as it would exist in hardware, but it takes more effort that way. Running the stages in reverse is a simple trick that also ensures that instructions properly "wait" at the boundaries between stages.


Shortest path in a graph where edges are forbidden depending on the path taken

The decision version of the problem you describe seems to be coNP-complete (assuming that the weight function description is polynomial in the size of the description of the graph).

The language corresponding to the decision version would be $L=\{G,w,s,t,p : p  \text{ is the shortest path in G between s and t according to } w\}$

Lets take the complement of the language Hamilton Cycle, denoted by
 $\overline{HC}=\{G\big| \text{There is no hamiltonian cycle in G}\}$ (hamiltonian cycle is a cycle that visit every vertex of G exactly once).

It is well known that $\overline{HC}$ is coNP-complete.

Now we can reduce $\overline{HC}$ to $L$ (in polynomial time):

On input graph $G$:

Take an arbitrary vertex $u$, split it into two $u_{start}$,
$u_{end}$ and connect them to all neighbors of $u$.
Create a weight function w in which all edges connected to $u_{end}$ has
$\infty$ weight unless the path we have followed visits each vertex
in $V \setminus \{u_{end}\}$ exactly once, and all other edges has weight 1
(this condition can be checked by a "short code" therefore $|w|$ is
polynomial).
Add an edge $e'$ between $u_{start}$ and $u_{end}$ with a constant weight of $n+1$.
Output $(G,w,u_{start},u_{end},p)$ where $p$ is the path $u_{start} \underset{e'}{-}v_{end}$

The reduction is polynomial, and observe that there is no Hamiltonian cycle in $G$ if and only if $u_{start} \underset{e'}{-}v_{end}$ is the shortest path in $G$ between $u_{start}$ and $u_{end}$.

So there is no polynomial algorithm for your problem (unless P=NP).


How to properly solve this Hidden Markov Model problem?

The Viterbi algorithm solves the problem. It calculates the most probable state sequence for an HMM given an observation sequence. In your example, ring sizes are observations and temperatures are hidden states. I suggest to refer to the Wikipedia article about the Viterbi algorithm (http://en.wikipedia.org/wiki/Viterbi_algorithm). It contains an example of an HMM with 2 hidden states and observations with 3 discrete probabilities.


How to find out what are accept, loop and reject in this Turing Machine?

Yuval's answer applies to your machine T$_2$. With his assumptions, we have the following behavior for your T$_1$ on possible inputs:

It will reject the empty string, since there is no move defined on the "blank" symbol.
It will not accept any string consisting only of $a$ characters, since it won't reach the HALT state.
It will accept $a\dots ab$, since it will reach the HALT state.
If the input is a single $b$, it will enter the HALT state and will then fall off the left end of the tape. Whether that should lead to acceptance or rejection depends on your definition of "accept" and "reject".
Whether it will accept a string like $aba$ or $abb$ will depend on your definition of "accept", since in these cases it will enter the HALT state and will never process the characters beyond the first $b$.
There is no loop state, at least under Yuval's and my interpretation.

You need to look closely at your local definition of a TM, since there are several forms they might take and of course we have no way of knowing what definitions you're using.


This can be formulated as an instance of min-cost (or in this case, max-profit) flow.

Set up a network as follows. There will be four layers.

The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a capacity and a profit. The min-cost flow algorithm can be used to find the flow through this graph that produces the greatest profit.

For each agent, we create two edges connecting the source to that agent, one having capacity $n$ and large profit; the other having capacity 1 and profit 0.

We connect each task to the sink with two edges, one having capacity $m$ and large profit; the other having capacity 1 and profit 0.

We connect every agent to every task, with an edge having capacity 1 and profit given by the agent-task combination.

We now use a min-cost flow algorithm to find the optimum flow. Because the min-cost flow problem has an integrality property, the flow on each agent-task edge will either be 0 or 1. This gives the assignment of the agents to their tasks.

Because the profit on the source-agent edges with capacity $n$ is large, the optimal solution will always use these, ensuring that every agent has at least $n$ tasks. Because the other source-agent edge has capacity 1 (and profit 0), each agent can have at most $n+1$ tasks. Similarly, each task is assigned to either $m$ or $m+1$ agents.

The min-cost flow algorithm won't be practical if each agent needs $100,000$ tasks, though. Is that really what you meant by $n=100,000$? How many tasks and how many agents?


Introduction to complexity and computability

For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"):

1) Introduction to the Theory of Computation by Michael Sipser

It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references.

2) Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey

The "bible" of NP-completeness. Although the second part is a mere list of NP-complete problems (with hints on the reductions), the first part is a good introduction to computational complexity and is focused on the theory of NP-completeness (but there are no exercises).

3) Computational Complexity: A Modern Approach by Sanjeev Arora

... This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation....  It has plenty of examples/exercises (unfortunately some nice (advanced) topics like Kolmogorov complexity or Descriptive complexity are missing).

Finally, if you need more intermediate/advanced books on computational complexity, then take a look to Lance Fortnow's Favorite Computational Complexity books list on Amazon ...
without any doubt a bunch of "gems" :-)


Control flow graphs - Tree decomposition

There are many different kinds of control-flow constructs that only map to "structured programming" (tree decomposition) constructs when you add extra data variables and extra tests.  continue is usually okay (as long as its not nested any deeper), but break is one of the hard ones.  Another relatively painful case is short-circuit conditional evaluation.

A preprocessing step of converting while x stmt to if x repeat stmt until not(x) will make everything a little easier (and you want to do this anyway, because it lets you safely optimize loop invariants).  Example:

while i<=n:
  something
  if condition break
  something_else
  i = i+1

becomes

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
  until not(i<=n)

A second preprocessing step of saving the (possibly complicated) calculation of the loop condition as a boolean temporary variable will also help.  So:

if i<=n:
  repeat:
    something
    if condition break
    something_else
    i = i+1
    t0 = not(i<=n)
  until t0

Now we can convert our break into a if-else:

if i<=n:
  repeat:
    something
    if condition:
      t0 = false
    else:
      something_else
      i = i+1
      t0 = not(i<=n)
  until t0

So we've converted, but the result is kind of ugly: we now have to keep track of t0 and we have two tests where we only had one before.  "Structured programming" is not the panacea it is often made out to be.


the meaning of heuristics in artificial intelligence

Heuristics typically have very little to do with rigor. (But you can surely study them in a rigorous way). They are rule of a thumb methods for solving (usually computationally difficult) problems, and typically they perform quite well in practice. In other words, there might not be any formal guarantees on the solution quality you get by running a heuristic, but experience and empirical analysis shows they can be quite effective. Arguably, it is rarely the case we understand their behaviour well.

Sometimes, when heuristics are analyzed formally, they turn out be to approximation algorithms. That is, methods for solving a problem with a formal guarantee on the solution quality. For example, one might have observed a heuristic usually works well, and an analysis proves it will always give a solution which is at most twice the optimum.

Perhaps in your particular case, the section "Heuristics" contains explanations (more or less formal) as to why the heuristic behaves or is expected to behave in certain ways when run.


2d cellular automata Wolfram binary codes

The description given on the page you linked to is correct:

"In each case the base 2 digit sequence for the code number specifies the rule as follows. The last digit specifies what color the center cell should be if all its neighbors were white on the previous step, and it too was white. The second-to-last digit specifies what happens if all the neighbors are white, but the center cell itself is black. And each earlier digit then specifies what should happen if progressively more neighbors are black. (Compare page 60.)"

What you might be missing is that, if the rule number is odd, the empty lattice is unstable since white cells surrounded by other white cells will spontaneously turn black.  Specifically, any rules whose number is congruent to 1 modulo 4 (i.e. whose binary form ends in 01), like 465, are "strobing", i.e. the empty lattice will alternate between all white and all black in each successive generation.
In particular, this means that rule 465 cannot correspond to "adding a cell when exactly one neighbor is currently occupied".  (That would presumably be rule 686, or 1010101110 in binary.)
Instead, as you correctly note, 465 equals 111010001 in binary.  Written in five groups of two bits each, that gives 01 11 01 00 01.  In each of these groups the rightmost bit in group $k$ (numbered right-to-left from 0 to 4) is 1 if a white cell with $k$ black neighbors will turn black in the next generation, and the leftmost bit is 1 if a black cells with $k$ black neighbors will stay black.
This means that, under this rule, a white cell will turn black if it has 0, 2, 3 or 4 black neighbors (since the rightmost bit is 1 in groups 0, 2, 3 and 4 counting from the right) and a black cell will stay black if it has exactly 3 black neighbors (since the leftmost bit is 1 only in group 3).
And indeed, simulating this rule for 22 generations, starting from one black pixel on a white background, produces an image matching the one on the linked page.

Ps. It turns out that rule 465 is the "strobing equivalent" of the state-symmetric rule 558 = 010001011102, which differs from rule 686 by exactly one bit and can be described as "add a cell when exactly one neighbor is occupied, remove a cell when exactly one neighbor is empty".
Started from a single cell, it seems that rules 558 and 686 evolve identically, since from this starting point they apparently never generate a live cell with exactly three live neighbors.  Thus, on even-numbered generations, the strobing rule 465 also looks identical to both of them.


Approximate the order of summation of two vectors

Let's consider the problem of comparing the sums of two vectors $A$ and $B$ that have all their $N$ real values in the range $[0, c]$.

First, let's start with two facts.

Union Bound.
Let $Y_1, \ldots, Y_K$ be K events in a probability space. Then
\begin{equation}
Pr\left(\bigcup_{j=1}^KY_j\right) \leq \sum_{j=1}^K Pr\left(Y_j\right).
\end{equation}
(The inequality is equality for disjoint events $Y_j$.)

Hoeffding Bound (1, 2).
Let $X_1, \ldots, X_R$ be $R$ independent random variables, each taking values in the range $\mathcal{J} = [\alpha, \beta]$. Let $\mu$ denote the mean of their expectations. Then
\begin{equation}
Pr\left(\left|\frac{1}{R}\sum_{i=1}^RX_i - \mu\right|\geq \epsilon\right) \leq e^{-2R\epsilon^2/(\beta-\alpha)^2}
\end{equation}

Idea

The first idea is that we are going to approximate the values of the sums for the two vectors $A$ and $B$ within some precision $\varepsilon$ with high probability (high confidence if you prefer). Then the argument that the two expectations that we have for the actual sums of the vectors $A$ and $B$ are well separated will be a simple application of the Union bound assuming that we have very high confidence for both expectations.

Definitions

Let $S(A), S(B)$ be the actual sum for the vectors $A$ and $B$ respectively and $S^*(A)$ and $S^*(B)$ be the approximations of the two values that we are going to come up with. In particular,
$$\begin{array}{rcl}
S(A) &=& \mu_A\cdot N \\
S(B) &=& \mu_B\cdot N
\end{array}$$
where $\mu_A$ and $\mu_B$ are the true mean values of the entries of the vectors respectively.

We now reduce the problem of approximating the sums to that of approximating the mean values $\mu_A$ and $\mu_B$; let's call the approximations $\mu_A^*$ and $\mu_B^*$.

Well Separated Approximations of Sums.
We will say that the two approximated sums are well separated if the following holds:
\begin{eqnarray}
\left|S^*(A) - S^*(B)\right| &=& \left|\mu_A^*\cdot N - \mu_B^*\cdot N\right| \\
 &=& \left|\mu_A^* - \mu_B^*\right|\cdot N \\
 &\geq& 2\cdot\epsilon\cdot N
\end{eqnarray}
where $\epsilon$ is the accuracy within which we have approximated the means $\mu_A^*$ and $\mu_B^*$.

(The intuition is that the sums are well separated if their respective mean values are well separated.)

Continuation

By the Hoeffding bound, if we require that our estimate is incorrect bounded by some small probability $\delta/2$ (it will be apparent soon why I divide $\delta$ by two), then we need
$$R \geq \left\lceil\frac{(\beta-\alpha)^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil = \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$
samples (runs) so that we can come up with the real values $\mu_A^*$ and $\mu_B^*$ that approximate the true real values $\mu_A$ and $\mu_B$ respectively within $\epsilon$ with probability at least $1-\frac{\delta}{2}$. In other words, it is only with probability at most $\frac{\delta}{2}$ that we will not have good estimates for each of the $\mu_A^*$ and $\mu_B^*$.

Now, by the Union bound, either of our estimates is incorrect with probability at most $\delta/2 + \delta/2 = \delta$. Or, the other way around, with probability at least $1-\delta$ both of our estimates $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values.

Theorem

Drawing $R$ samples from each vector where
$$R \geq \left\lceil\frac{c^2}{2\epsilon^2}\cdot\ln\frac{2}{\delta}\right\rceil$$
it is guaranteed that with probability $1-\delta$
both of our estimates for $\mu_A^*$ and $\mu_B^*$ are within $\epsilon$ of their true values, and thus the approximations $S^*(A)$ and $S^*(B)$ that we have for the sums $S(A)$ and $S(B)$ are within $\epsilon\cdot N$ of their true values. Thus, it suffices to check if the inequality
$$\left|S^*(A) - S^*(B)\right| \geq 2\cdot\epsilon\cdot N$$
holds. If the inequality holds, then with probability $1-\delta$ (that's our confidence) the two sums are different and in fact we can say which one is bigger with the same confidence.

Concluding Remark

Just to note that with the approach above we need $\epsilon^{-1} = o\left(\sqrt{N}\right)$ so that the number of samples/runs $R$ is sublinear (btw, sublinear algorithms is an active field of research) and thus it makes sense to take samples from the huge vectors $A$ and $B$ rather than computing the sums directly. This also means that with this approach the separation bound between the two approximated sums should be $\Omega\left(\sqrt{N}\right)$.

References

[1] Wassily Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301):13–30, March 1963

[2] L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer, 1996.

Code

Below is some code that I wrote yesterday for playing around with the problem. The difference is I think that I did not divide by 2 the $\delta$, and moreover, for the approximations I am expressing $\delta$ as a negative power of $e$ ($\approx 2.71828\ldots$) so that I can simplify the calculations and not take logarithms.
Other than that, I generate two big arrays with slightly skewed entries; the first one with values between 0 and 9 and the other one with values between 1 and 10. In principle this needs a GMP implementation, but I guess the following will do for now. I really enjoyed the problem! Thanks! I am of course very interested in seeing different approaches to the problem.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <ctgmath>

#define SIZE 1000000
#define EPSILON 0.1
#define DELTA_EXPONENT 4

#define MIN_VALUE  0
#define MAX_VALUE 10

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high);
unsigned int trueSum (unsigned int * array, const unsigned long int size);
bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference);
unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);
long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent);

/************************************************************************************/

int main () {
    unsigned int * a1, * a2, s1, s2, s1Approx, s2Approx, difference;
    bool flag;
    time_t timer;

    // Randomize
    timer = time(NULL);

    // Print the basic properties
    std::cout << "Timer seed: " << timer << std::endl;
    std::cout << "Size      : " << SIZE << std::endl;
    std::cout << "Epsilon   : " << EPSILON << std::endl;
    std::cout << "Delta exp : " << DELTA_EXPONENT << std::endl << std::endl;

    // Reserve memory
    a1 = new unsigned int [SIZE];
    a2 = new unsigned int [SIZE];

    // Generate the arrays
    assignRandomValues (a1, SIZE, MIN_VALUE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 + 4);
    assignRandomValues (a2, SIZE, MIN_VALUE + (MAX_VALUE - MIN_VALUE)/2 - 4, MAX_VALUE);

    // Find and print the true values
    s1 = trueSum (a1, SIZE);
    s2 = trueSum (a2, SIZE);
    std::cout << "The true sum value for a1 is: " << s1 << std::endl;
    std::cout << "The true sum value for a2 is: " << s2 << std::endl;

    // Find and print the approximate values
    s1Approx = approximateSum (a1, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    s2Approx = approximateSum (a2, SIZE, MAX_VALUE, EPSILON, DELTA_EXPONENT);
    std::cout << "The approximate sum value for a1 is: " << s1Approx << std::endl;
    std::cout << "The approximate sum value for a2 is: " << s2Approx << std::endl;

    // Print the approximate difference and indicate if they are sufficiently separated
    difference = static_cast<unsigned int>(fabs(static_cast<long double>(s1Approx) - static_cast<long double>(s2Approx)));
    std::cout << "The approximated difference is: " << difference << std::endl;
    flag = areTheApproximationsSufficientlyDifferent(SIZE, EPSILON, difference);
    std::cout << "The approximated difference is sufficiently big (w.h.p.): ";
    std::cout << (flag ? "YES" : "NO") << std::endl;

    // Deallocate memory
    delete [] a1;
    delete [] a2;

    return 0;
}

/************************************************************************************/

void assignRandomValues (unsigned int * array, const unsigned long int size, const int low, const int high) {
    unsigned long int i;

    for (i = 0; i < size; i++) {
        array [i] = low + (rand() % (high - low + 1));
    }
}

/************************************************************************************/

unsigned int trueSum (unsigned int * array, const unsigned long int size) {
    unsigned long int i, sum = 0;
    for (i = 0; i < size; i++)
        sum += array[i];
    return sum;
}

/************************************************************************************/

bool areTheApproximationsSufficientlyDifferent (const unsigned long int size, const long double epsilon, const unsigned int difference) {
    unsigned int bound = static_cast<unsigned int>(ceil(2.0*size*epsilon));
    if (difference > bound)
        return true;
    return false;
}

/************************************************************************************/

unsigned int approximateSum (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    long double mean = approximateMean (array, size, maxValue, epsilon, deltaExponent);
    return static_cast<unsigned int>(round(mean * size));
}

long double approximateMean (unsigned int * array, const unsigned long int size, const int maxValue, const long double epsilon, const int deltaExponent) {
    unsigned long int samples, i, sum, pos, integerPart;
    long double floatingPart, mean;

    samples = static_cast<unsigned long int>(ceil(maxValue * maxValue * deltaExponent / (static_cast<long double>(2.0) * epsilon * epsilon)));

    std::cout << "Requiring " << samples << " samples for the approximation." << std::endl;

    sum = 0;
    for (i = 0; i < samples; i++) {
        pos = rand () % size;
        sum += array[pos];
    }

    integerPart  = sum / samples;
    floatingPart = static_cast<long double>((sum - integerPart * samples)) / static_cast<long double>(samples);
    mean = static_cast<long double>(integerPart) + floatingPart;
    return mean;
}

/************************************************************************************/

Wrapping Up for the Original Question

In the original question we want to approximate values of the form $i\cdot a_i$ or $i\cdot b_i$ and this means that these new values are now in the range $[0, c\cdot N]$ assuming that $a_i, b_i \in [0, c]$ for $i\in{0, 1,\ldots, N}$.

Above, I assumed that $c \ll N$. However, since the number of samples that is required has quadratic dependence on the maximum value that can be found in these new vectors, we really need to draw $R \geq \Omega\left(\frac{c^2\cdot N^2}{\epsilon^2}\ln\left(\frac{1}{\delta}\right)\right)$ samples. On the other hand, a direct summation will perform $O(N)$ additions of $O(N)$ multiplications. Thus, sampling would make sense in terms of savings if we could say that $R=o\left(N\right)$. In other words, ignoring the logarithmic dependence on $\delta$, we want
$$\frac{c^2\cdot N^2}{\epsilon^2} = o(N)\;.$$
This would be true if
$$\epsilon = \omega(c\cdot N^{1/2})$$
thus yielding $R=o\left(N\right)$.

The question is if this $\epsilon$ is meaningful for comparisons. The answer is yes when the two vectors are significantly different (contrary to the helper that original vectors have values that add up to the same number). Let's see what I mean by an example.

Example

Let $c=N$. Moreover, let
$$
\begin{array}{rcl}
A &=& \left\langle 1, 1, \ldots, 1, \ldots, 1\right\rangle \\
B &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle
\end{array}
$$
be two vectors with $N$ elements. Then, the requested summation of the products $i\cdot a_i$ and $i\cdot b_i$ can be seen as the summation on the vectors
$$
\begin{array}{rcl}
F &=& \left\langle 1, 2, \ldots, i, \ldots, N\right\rangle \\
G &=& \left\langle 1^2, 2^2, \ldots, i^2, \ldots, N^2\right\rangle
\end{array}
$$
Note that $S(F) = \sum_{i=1}^N f_i = \Theta\left(N^2\right)$ and $S(G) = \sum_{i=1}^N g_i = \Theta\left(N^3\right)$. Similarly, their mean values are significantly different, since $\mu_{F} = \Theta\left(N\right)$ while $\mu_G = \Theta\left(N^2\right)$

The accuracy $\epsilon$ that we are talking about involves the estimate of these last true mean values $\mu_F$ and $\mu_G$. Thus, if we set
$$\epsilon = \Theta\left(c\cdot N^{1/2+\xi}\right) = \Theta\left(N^{3/2+\xi}\right)$$
for some $\xi\in(0,1/2)$ there will be cases (like in this example) where the mean values will be significantly far away on the real line and thus we will be able to tell which one is bigger than the other with few samples (and as a consequence we will be able to separate the two sums on the real line with that many samples).

Concluding the Wrap-Up

Now if we revisit our definition for well-separated sums, we are going to require the following inequality for our definition:
$$\left|S^*(F)-S^*(G)\right| \geq 2\cdot N^{5/2+\xi}$$
for some $\xi\in\left(0, 1/2\right)$. Actually any $\xi\in\left(0,1/2\right)$ will do. The larger the $\xi$ the fewer samples that we draw. However, the catch is that the larger the $\xi$, the more restrictive our inequality is for separating the two sums. In other words, the closer $\xi$ is to $1/2$ the more unlikely it is to encounter vectors that can be separated using our method, since we require the gap between their true values to be even larger.

I believe the above clears up everything, but in case it does not, just drop me a line and I will try to explain more the details.


Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?

The complete bipartite graph $K_{k,k}$ has $2k$ vertices, each of which has degree $k$.


Is this reduction from 3D-MATCHING to PATH SELECTION invalid?

The "additional constraint" is part of the problem definition:

  for a given directed graph and a set of paths we ask if it is possible to select at least k paths so that no pair of paths share any node.

The key is "and a set of paths". The Path-Selection Problem has a set of paths from which you are allowed to chose as part of its input.

Note that the definition is kind of strange, since the fact that a graph is involved seems irrelevant (we could always take the graph to be a clique, which doesn't change the answer). However, if the graph has special structure, then the problem can become tractable (e.g., if the graph is a tree the problem is polynomially solvable).


Efficient Algorithm Linear Temporal Logic to Deterministic Rabin Automata

There is a very recent tool to translate from LTL directly to deterministic Rabin automata. It can be obtained here:

https://www7.in.tum.de/~sickert/projects/ltl2dra/

The page not only contains a link to the downloadable implementation, but also has link to a technical report that describes the construction for the translation. Apparently, a peer-reviewed paper about the construction has not appeared yet. Note that the construction is rather involved - the paper has 50 pages, and there is a reason why for many years, the detour though Büchi automata was (and somewhat still is) state-of-the-art.

Note that the computational complexity of the direct translation is not better than the one that one can obtain by translating LTL to non-det. Büchi automata and then applying Safra's method.


Complexity analysis of while loop with two conditions

As Patrick87 pointed out. The first loop is $\min(m,n)$.  As for your extended question,   it's unclear if you want best, worst, or average case.  We typically look at worst case.  Either way, you seem to be focused on a single execution when you really need consider all possible $i$ and $j$ values.  So, let's do that:

$m = n$.

In this case the additional conditional does no work, so the total run time is still $O(\min(m,n))$.

$m < n$.

When this is true, then the first loop terminates due to $j$. The conditional will then carry out the first case $i < n$ and terminate after $O(n-m)$ iterations.  The total number of operations is then $O(n-m+m)= O(n)$ operations.

$m > n$.

This case is equivalent to the second case but the result is $O(m)$.

Now observe that cases 1,2, & 3 are all equivalent to $O(\max(m,n))$. This is the running time for your code.

So back to your "how to" question. You need to do a good, thorough case analysis for multi-conditional loops just like you need to do with conditionals.  Then analyze the running time of each case and, assuming your doing worst case analysis, take the largest running time.


Doubt regarding foreign key and referential integrity

In general the “referential integrity constraint” is a constraint that states that a foreign key must always be equal to some primary key of a tuple in the referred relation (so establishing a correspondence between a tuple in the first relation and another (and only one) in the other relation. If the constraint is violated, that is if the value of the foreign key of a tuple is not equal to the value of the primary key of another tuple, this means that the foreign key has lost its integrity, since it “does not refer anything”, like a “dangling reference” in a programming language.

It is a duty of the Database Management System to enforce this constraint, and prevent any violation of it through some policy, that can be specified by the database administrator (“on delete cascade, no action”, etc.)

In the book that you cited, it is in fact said that:

  a referential integrity constraint requires that the values appearing in specified attributes of any tuple in the referencing relation also appear in specified attributes of at least one tuple in the referenced relation.

The comment related to the example explains that, even if, according to the rules of the university, each section should be taught by at least one instructor, it is not possible to express such constraint in the database designed, since it is not possible to define the attributes of section as foreign key for the relation teaches (since they do not form a primary key in such relation).

Note that this depends on the fact that the only way to represent a 1-n relationship between two sets of data in the Relational Data Model is to use a foreign key in the relation where there is only one element (at maximum) in the other relation, not vice-versa. So the foreign key is from teaches to section, since a tuple in teaches can be related only to one tuple in section.


I would like to comment this, but reputation...

What you are looking for is a Tessellation.

  A tessellation of a flat surface is the tiling of a plane using one or more geometric shapes, called tiles, with no overlaps and no gaps.

For example, the Penrose Tiling, the Pithagorean Tiling, Domino Tiling or Polyomino Tiling.


I understood your confusion

firstly here C,B,A,S all approach ε at one point

so solving in the method you solved previous example put ε one by one in S then consider all combinations like this

S-->ABCa/bD/BCa/ACa/ABa/Aa/Ba/Ca/a

A-->Bc/b/c

B-->b

C-->c

D-->d
firstly in S for (ABCa) put ε in A then B then C later BC,CA,AB,ABC
so if you follow this fashion you get the answer


If the timestamps can take $T$ different values, then it is simple to implement the new, update, and delete operations in time $\Theta(T)$ and the query in time $O(1)$, by maintaining two arrays $val[ ]$ and $q[]$ of size $T$. The array $q[]$ is initially filled with zero values.

new(x, v): set $val[x] = v$ and increment each $q[y]$ with $y\ge x$ by $v$;
update(x, v): let $v' = val[x]$; increment each $q[y]$ with $y \ge x$ by $v-v'$, then set $val[x]=v$;
delete(x, v): let $v' = val[x]$; decrement each $q[y]$ with $y \ge x$ by $v'$;
query(x): return $q[x]$.

Note that $n$ (number of data items, that is, the number of total calls to new) is unrelated to $T$ (range of the timestamps). Whenever $T=o(n)$, the above implementation satisfies your requirements. For example, if a timestamp is a day of the year, $T$ will be a constant, even though $n$ can be arbitrarily large (because you can have arbitrarily many new and deletes).

If, on the other hand, $T$ can be larger than $n$, then as D.W. noted in his comment your requirements may be too strict.


Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$?

The authors give a reduction $x \mapsto f(x)$ from some NP-hard problem $X$ to MAX-CUT with the following properties:

If $x$ is a YES instance then $OPT(f(x)) \geq c$.
If $x$ is a NO instance then $OPT(f(x)) \leq s$.

Here $OPT(y)$ is the optimal value of the MAX-CUT instance $y$.

Suppose now that you had an algorithm for MAX-CUT with approximation ratio $\rho > s/c$, which means that for every instance $y$, $ALG(y) \geq \rho OPT(y)$, where $ALG(y)$ is the value of the instance produced by the algorithm. We can use this algorithm to solve $X$, since $x$ is a YES instance of $X$ iff $OPT(f(x))>s$ (I'll let you verify that).

This informally explains the statement in the paper. Any more formal explanation requires a definition of "NP-hard to approximate". One possibility is as follows. Let $Y$ be a maximization problem. We say that $Y$ is NP-hard to approximate within a factor of $\rho$ if for every problem $X \in \mathsf{NP}$ there exists a polytime computable reduction $f$ which on input $x$ produces a tuple $(y,v)$, where $y$ is an instance of $Y$ and $v$ is a number, with the following properties:

If $x$ is a YES instance of $X$ then $OPT(y) \geq v$.
If $x$ is a NO instance of $X$ then $OPT(y) < \rho v$.

This generalizes the usual definition of NP-hardness for optimization problems, which corresponds to the choice $\rho = 1$.
Under this definition, if $Y$ is NP-hard to approximate within a factor of $\rho$ and there is a polytime $\rho$-approximation algorithm for $Y$, then $\mathsf{P} = \mathsf{NP}$.
Finally, according to this definition, MAX-CUT is indeed NP-hard to approximate to within any factor strictly larger than $s/c$.


Creating a large tuple from smaller tuples via a monad or applicative

(Note, this requires a more sophisticated type theory such as System Fω to encode)
This idea is captured by the concept of an indexed monad (and in turn indexed applicative/functor).
Using Haskell as lingua franca, we talk about a typeclass:
class IxMonad (m :: n -> n -> * -> *) where
  ireturn :: a -> m i i a
  ibind :: m i j a -> (a -> m j k b) -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  ireturn :: a -> m i i a
  ijoin :: m i j (m j k a) -> m i k a
  -}

An action m i j a makes a connection "from" an index i "to" an index j, and wraps some type a. Actions can be composed only if the respective indices "line up". Sort of like how horizontal oidification turns a monoid into a category: morphisms can be composed only if their endpoint objects "line up".
Analogous definitions of an indexed functor and an indexed applicative can be made:
class IxFunctor (m :: n -> n -> * -> *) where
  ifmap :: (a -> b) -> m i j a -> m i j b

class IxApplicative (m :: n -> n -> * -> *) where
  ipure :: a -> m i i a
  iap :: m i j (a -> b) -> m j k a -> m i k b
  {- alternatively, if it's an IxFunctor, the categorical version:
  iunit :: () -> m i i ()
  iprod :: (m i j a, m j k b) -> m i k (a, b)
  -}

Say we wanted to "output" entries of some type, while keeping a type-theoretic witness of how many entries there are, we could define an indexed writer monad.
Here's definitions of natural numbers used to track length, and a length-indexed "log" datatype:
data N = Z | S N

data Vec (n :: N) (a :: *) where
  Nil :: Vec 'Z a
  Cons :: a -> Vec n a -> Vec ('S n) a

In an indexed monad, the usual intuition is that the indices i/j describe the "state" of the system: an action brings the system from "state i" to "state j". Here we'll be using the index to track how many entries we've written to the "log", and for completely technical reasons (to do with making the typechecker happy in an easy way), the left index will be the output log length, and the right index will be the input log length:
type family Add (n :: N) (m :: N) :: N where
  Add 'Z m = m
  Add ('S n) m = 'S (Add n m)

data IxWriter w i j a where
  IxWriter :: Vec k w -> a -> IxWriter w (Add k i) i a

instance IxMonad (IxWriter w) where
  ireturn x = IxWriter Nil x
  ibind (IxWriter xs x) f = case f x of
    IxWriter fs y -> iwappend xs fs y
    where
      iwcons :: w -> IxWriter w i j a -> IxWriter w ('S i) j a
      iwcons p (IxWriter qs z) = IxWriter (Cons p qs) z

      iwappend :: Vec k1 w -> Vec k2 w -> a -> IxWriter w (Add k1 (Add k2 i)) i a
      iwappend (Cons p ps) qs z = iwcons p $ iwappend ps qs z
      iwappend Nil qs z = IxWriter qs z

Then we can define the "logging" action, and an interpreter for our effect:
itell :: Vec k w -> IxWriter w (Add k i) i ()
itell ps = IxWriter ps ()

runIxWriter :: IxWriter w i 'Z a -> (Vec i w, a)
runIxWriter (IxWriter Nil x) = (Nil, x)
runIxWriter (IxWriter (Cons p ps) x) = case runIxWriter (IxWriter ps x) of
  (qs, r) -> (Cons p qs, r)

With this we can keep track of exactly how many entries we've logged:
case runIxWriter $
  itell (Cons 1 Nil) `ibind` \_ -> itell (Cons 2 Nil) `ibind` \_ -> itell (Cons 3 Nil)
of (Cons a (Cons b (Cons c Nil)), x) -> (a, b, c, x)
{- pattern match is valid and complete because we
   statically know it's a Vec ('S ('S ('S 'Z))) Integer -}

Here we used the graded monoid of finite sequences (and thus all our logs are of the same type). In theory we could have used any monoid graded by any other monoid, (for example the monoid of heterogeneous lists, graded by the monoid of lists of types -- if we wanted to be able to talk about heterogeneous tuples)


What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?

The short answer is no. No quick algorithm for this problem is known.

A big open problem (for at least 50 years) in algebraic graph theory asks about  the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.

However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = (x-57)(x+8)^{1520}(x-7)^{1729}$ [1, Proposition 1].

So if there would be a quick solution to your problem, this big open problem would  be solved already.

In fact, the theorem that you stated can be further generalized. The $i$'th coefficient of the characteristic polynomial of $G$ is given by $$(-1)^{i}c_i = \sum (-1)^{r(H)} 2^{s(H)}$$ where the summation is taken over all subgraphs $H$ of $G$ that have order $i$ and whose connected components are $K_2$ and cycles. The function $s(H)$ counts the number of components of $H$ that are cycles while $r(H)$ denotes the rank of $H.$

[1] M. Macaj, J. Siran. Search for properties of the missing Moore graph, Linear Algebra Appl., 432 (2010), 2381–2398.


How to do a reverse topological sort using depth first search?

In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.

Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the files to be deleted in order (starting from the top of the stack). Due to the nature of DFS/BFS on trees, every node will be pushed to and popped from $S$ before its children. Therefore, every time we pop a node from $S$, we add it to the stack $T$. At the end of the search $T$ will maintain the property that all nodes appear deeper in the stack than their children. Keep in mind this only works if the file node structure is a tree not a DAG.


unambiguous context-free languages and complementation

Both questions turn out to have negative answers, as shown in [this][1] article.
In particular, the authors construct

An unambiguous context-free language whose complement is not context-free.
An inherently ambiguous (i.e., non-unambiguous) context-free language whose complement is context-free.

Consequently, there is no relationship between the notion of unambiguity for context-free languages and the complementation operation.

[1] The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages" by Hibbard and Ullian, JACM, Volume 13 Issue 4, Oct. 1966, Pages 588-593
 https://dl.acm.org/citation.cfm?doid=321356.321366


Let's do the case $N = 1$.
Suppose that $G$ is a connected graph, and assume first that $G$ is bipartite, with bipartition $X,Y$. Let $X_1,X_2,Y_1,Y_2$ be the two copies of the two parts in $G'$. Note first that the edges in $G'$ either connect $X_1$ to $Y_2$ or $X_2$ to $Y_1$, and so $G'$ has at least two connected components.
Conversely, any path from $X$ to $Y$ in $G$ gives rise to a similar path in $G'$ from $X_1$ to $Y_2$, implying (after a short argument) that $X_1 \cup Y_2$ form a connected component; and similarly for $X_2 \cup Y_1$. Thus $G'$ has exactly two connected components.
Now suppose that $G$ is a connected non-bipartite graph. As before, the vertices in $X_1 \cup Y_2$ are all in the same connected component of $G'$, as are the vertices in $X_2 \cup Y_1$. We will show that $X_1$ is connected by a path to $X_2$, implying that $G'$ is connected.
Since $G$ is not bipartite, there is some odd cycle in $G$. Let $x$ be a vertex on this odd cycle. Lifting this cycle to $G'$, we obtain a path from $x_1$ to $x_2$.


Deleting vertices so that largest connected component has at most $n/2$ vertices

Hint: Try working backwards, adding vertices to the graph in reverse order $n,\dots,1$.


Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for head movement - whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.)

Note that this is a particularly natural thing to allow: it's basically a "while" command.

However, as with many aspects of Turing machines, tweaking the definition to rule it out isn't significant: Turing machines which prohibit states from looping to themselves are no weaker than Turing machines which allow states to loop to themselves. This is a good exercise.


"... is it always a given Cellular Automaton is a computer?"...

I interpret "is a computer" as "being capable of universal computation" or in other words "being capable of simulating an arbitrary Turing machine".

The answer is clearly NO; a trivial example is a CA that doesn't modify the input:

0[0]0 -> 0
0[0]1 -> 0
0[1]0 -> 1
0[1]1 -> 1
1[0]0 -> 0
1[0]1 -> 0
1[1]0 -> 1
1[1]1 -> 1

(rule 204)

According to Wolfram's (qualitative) classification, only type-4 CAs exhibit a behaviour that can potentially be "universal". But it is an informal statement (like many others in Wolfram's NKS) ... in order to say that a particular CA is/is not Universal you must prove it formally.

For a more rigorous introduction to the argument I suggest you to read some research articles on the subject, for example: Kristian Lindgren, Mats G. Nordhal. Universal Computation in Simple One-Dimensional Cellular Automata. Complex Systems 4 (1990) 299-318

Or - for a good, more general, introduction to computational universality - read Chapter 7: The Grand Unified Theory of Computation of the (IMO excellent) book:  Cristopher Moore, Stephan Mertens. The Nature Of Computation (2011)


The derivatives are applied over time in a continuous fashion.

Here is an example:

Assume that we want to find out whom of two runners wins a running tournament. They run for 100 meters each, and the one reaching a goal first wins.

We can model the position of the two runners using two variables $x$ and $y$. We do not quite know the exact speed of the runners, as it depends on how well they feel at the tournament day. But we know some boundaries on their speed, i.e., how $x$ evolves over time. Let's assume we know that
$\dot x \in [9.8,9.9] \ \frac{m}{s}$ and that $\dot y \in [9.7,9.78] \ \frac{m}{s}$

So a rectangular hybrid automaton would have one "running" state in which the variables evolve like this, and then there are two states for the cases that runner $x$ has reached the goal and that runner $y$ has reached the goal. You can see from the numbers above that player $x$ will win, but let's assume that this is not obvious, and we want to use a rectangular hybrid automaton for this:

   | x:=0, y:=0
   V
+- -------------------+    x >= 100       +---------------------+
| 0.98 <= x' <= 0.99  |------------------>| x' = 0              |
| 0.97 <= y' <= 0.978 |                   | 0.97 <= y' <= 0.978 |
| x < 10, y<10        |                   +---------------------+
+---------------------+
   |                       y >= 100       +---------------------+
   +------------------------------------->| 0.98 <= x' <= 0.99  |
                                          | y' = 0              |
                                          +---------------------+

If we always "reset the value to one value in the interval", then the two runners would never reach the 100 meter mark and hence one of the two goal states on the right is never right.

But it is also not the case that "one value chosen out of the interval and added to the value". Because adding is a discrete actions. You could, for example, add x' to x until one of the two conditions have been reached. But then, it takes exactly 11 steps for both runners to reach the goal, and hence, they both win at the same time. But that makes no sense, because time is continuous. Rather, if you plot the evolution of x over time, you would use x' as the steepness of the line, and the positions of the runners are really continously updated as time progresses, as in real life.

In rectangular hybrid automata, it doesn't really matter whether $\dot x$ can change at every moment of time to a different value in the interval or not. The reason is that we use these automata for checking the properties of model. In the example above, this would be whether the bottom-right location is ever reached (which is not the case). And for this analysis, whether the first derivatives has to stay constant (within their defined interval) or not does not matter.


$P/Poly \setminus P$. What langugage does reside there?

One example is the language
$$\{ 1^n : \text{the $n$th Turing machine halts on the empty input}\}.$$
This language has constant size circuits, but isn't computable.


I've added brackets to disambiguate $$\lambda x.(\color{red}y (\color{green}{\lambda y}.(\color{blue}yx)))$$ the red $y$ is free and the blue one is bound by the green abstraction. I don't think it makes sense to say that the green $y$ is bound, but it together with the lambda is a binder.

We can beta reduce the term once

$$\begin{array}?
&& \lambda x.(y (\lambda y.(yx)))ab \\
&\to_\beta& (y (\lambda y.(ya)))b
\end{array}$$

but no further, as there are no remaining redexes left.


stable marriage/residency problem with multiple matches

Suppose you have a doctor that you want to assign to three hospitals.  Replace that doctor by three copies of him.  In other words, instead of a single vertex for Dr. Smith, you have three clones, Dr. Smith #1, Dr. Smith #2, and Dr. Smith #3.  They all have the same preference list.

Suppose you have a hospital that wants two doctors.  You can do the same thing: instead of a single hospital, you have one entity per open position at that hospital.  They all have the same preference rankings.

Now use the standard stable marriage algorithm on the resulting set of clones and open positions.  This will find a stable matching that obeys the multiplicity constraints you identified; that follows directly from the correctness property of the standard algorithm.


If one shows that UNIQUE k-SAT is in P, does it imply P=NP?

This is still an open question; UP is not known to be equivalent to NP.  In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under which P contains UP but P is still not equivalent to NP.


Consider, for instance, $A = \{ \varepsilon \}$. Then $X = AX$, so $X = AX \cup B$ holds for any $X$ with $B \subseteq X$.


On proving NP-completeness by reduction to 3-partition problem

No, that doesn't prove NP-completeness.

The thing you describe isn't a reduction.  It must be that the instance of $X$ has a solution if, and only if, the instance of 3-partition has a solution.
Reducing $X$ to 3-partition just proves that $X$ is in NP.  To prove completeness, you need to reduce an NP-complete problem to $X$.

I suggest that you revise the basic concepts from your class notes, textbook or online resources.


"The Big-O notation describes the limiting behavior of a function when
  the argument tends towards a particular value or infinity, usually in
  terms of simpler functions."-Wikipedia

If you see the formal definition, then the only restriction is that the domain of functions must be $\mathbb{R}$. Hence, by definition the range of the functions can at least be any vector space.
In the most common use in CS, the range of the functions is also taken to be $\mathbb{R}^+$.

To answer your question, by definition, the left side can be any real positive value.


Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are:

Is $\mathsf{P} \neq \mathsf{NP}$?
Is $\mathsf{P} = \mathsf{BPP}$?

In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity classes. For example, people came up with oracles relative to which $\mathsf{P} = \mathsf{NP}$, and other oracles relative to which $\mathsf{P} \neq \mathsf{NP}$. This type of activity seems less popular now. Diagonalization is another common proof technique that used to be more popular in the past, but is somewhat less popular today.
Another common pursuit is proving conditional results. For example, Buhrman, Chang and Fortnow show that if $\mathsf{coNP} \subseteq \mathsf{NP/1}$ then the polynomial hierarchy collapses. Since it is conjectured that the polynomial hierarchy is strict (doesn't collapse), it follows that probably $\mathsf{coNP} \not\subseteq \mathsf{NP/1}$.
What are some similar results that are not considered structural complexity theory? Here are some examples:

Results in circuit complexity. For example, $\mathsf{AC^0} \neq \mathsf{P}$ is not classical structural complexity theory.

Results about specific problems, for example NP-completeness of specific problems.

Other results could in principle be considered structural complexity theory, but because the techniques used are so different than classical results in structural complexity theory, they are not usually thought of as structural complexity theory. Conspicuous examples include:

$\mathsf{IP} = \mathsf{PSPACE}$, which uses algebraization. This is a borderline example.
The PCP theorem, which uses ideas from coding theory.

The above is just my own opinion. Other people might have very different opinions. Structural complexity theory is not a codified area of research.


Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

Let $\mathsf{P^k}$ be the class of problems solvable in polynomial time on deterministic Turing machines with $k$ tapes. Then
$$
\mathsf{P^1} = \mathsf{P^2} = \mathsf{P^3} = \mathsf{P^4} = \mathsf{P^5} = \cdots
$$
Let $\mathsf{PD^{d}}$ be the class of problems solvable in polynomial time on deterministic Turing machines with access to a $d$-dimensional infinite tape. Then
$$
\mathsf{P^1} = \mathsf{PD^1} = \mathsf{PD^2} = \mathsf{PD^3} = \mathsf{PD^4} = \mathsf{PD^5} = \cdots
$$
Similarly, $\mathsf{P}$ is also the class of problems solvable in polynomial time on RAM machines, which have a random-access memory (i.e. you can implement indexing $A[i]$ without needing the head to scan to the $i$th position of the tape).

The definition of $\mathsf{P}$ is very robust to the particular machine model used, and this makes $\mathsf{P}$ a very natural complexity class. This is similar to the class of all decidable languages, which can be defined in countless ways. The exact way you define $\mathsf{P}$ is arbitrary, since all definitions amount to the same complexity class.

The story gets a bit more complicated when we consider computation models other than deterministic machines (of any kind). For example, are probabilistic polytime algorithms stronger than deterministic ones? The answer might depend on the error. Probabilistic polytime algorithms with constant error probability define the complexity class $\mathsf{BPP}$, which is believed (by most) to be the same as $\mathsf{P}$. If we allow unbounded error we get $\mathsf{PP}$, which contains $\mathsf{NP}$, and so such algorithms are probably more powerful than deterministic ones. Similarly, quantum algorithms with bounded errors form the complexity class $\mathsf{BQP}$, which contains problems such as factoring which are not believed (by most) to be solvable in classical polynomial time.


Two "bubble" loops in pseudocode; would they return the same thing?

In the first code, the values taken by $(c, d)$ are in the set $\{(c, d)| 1 \leq d < c \leq x\}$. In the second code, the set is $\{(c,d)|1\leq c < d \leq x\}$. Since $c$ and $d$ play symmetrical roles in the boolean test, it is expected that you obtain the same result.
Note that if $c$ and $d$ would not play symmetrical roles, the result could be different (for example, if the test was a, c * d, a = prod).


Define the time complexity of Kruskal's algorithm as function

After sorting the edges, which takes $O(E \log E)$ time, Kruskal's algorithm adds the next cheapest edge which doesn't cause a cycle.  The question is what data structure can be used to check if a given edge causes a cycle.

At any given point during the execution of the algorithm, the set of edges chosen by the algorithm forms a forest.  Initially, the forest contains $n$ trees, where $n:=|V|$.  If the next cheapest edge is $ab$, and vertices $a$ and $b$ belong to different trees in the forest, then the two trees can be combined into a larger tree.

A data structure for storing the above tree information is to store a parent value for each vertex.  Following the parent pointer leads to the root node of the tree. If vertices $a$ and $b$ have different roots, then they belong to different trees.  One can merge the two trees by making $b$ the parent of $a$.  This allows us to maintain a collection of disjoint sets (each set is the vertex set of a tree), whose union is the vertex set of the graph.

So that the merging of two trees into one tree is done efficiently, the smaller tree can be put under the larger tree (i.e. the one with the smaller rank has its root node point to the other root).  This ensures that the trees have small heights, and the path that is followed from a node to find its root has small length.  Also, in order to not have to follow the same long sequence of parent pointers in subsequent iterations, one can store the root node's value after it is found.  These are the "union-by-rank" and "path compression" heuristics, which efficiently implement Kruskal's algorithm, so that it runs in $O(E \log E) = O(E \log V)$ time.


Let's do products first.
The usual cartesian product $A \times B$ is also called a binary product because we are making a product of two sets. We could make a ternary product $A \times B \times C$. What is the most general case? Well, to have an index set $I$ and a family of sets $X_i$, one for each $i \in I$, and then we make the product of all these $X_i$'s. This is written as $\prod_{i \in I} X_i$. When $I$ is infinite, it is called an infinitary product. Other products are a special case, for example if we take $I = \{1, 2\}$, $X_1 = A$ and $X_2 = B$ then $\prod_{i \in \{1,2\}} X_i = A \times B$, so a binary product is a special case of the general product.
We can do the previous paragraph in type theory, as there is nothing specific to sets there. Given a type family $i : I \vdash X(i) \ \mathsf{type}$, we may form the type $\prod (i : I) X(i)$. To get a binary product $A \times B$ as a special case, take $I = \mathsf{Bool}$, set $X(\mathsf{false}) = A$ and $X(\mathsf{true}) = B$.
Now let's try sums. I will assume you understand the sum of two sets or types, $A + B$. We could have a ternary sum, $A + B + C$. Again, there is a general case: take a family of sets $(X_i)_{i \in I}$ and form their sum. In set theory it is written as $\coprod_{i \in I} X_i$ and called coproduct, while in type theory it is written as $\sum (i : I) X(i)$ and called dependent sum. One way to see why people call it a sum is to consider how many elements it has. If $A$ has $a$ elements and $B$ has $b$ elements, then $A + B$ has $a + b$ elements. In general, if $X_i$ has $x_i$ elements, then $\sum (i : I) X_i$ has $\sum_i x_i$ elements.
We saw that the binary product is a special case of a general product. But it is also a special case of a dependent sum. Suppose $A = \{0, 1, 2\}$. Then $A \times B = B + B + B$. In general, if we want $A$-many copies of $B$, then that's
$$A \times B = \underbrace{B + B + \cdots + B}_{A}$$
Of course, such notation is silly, so we prefer to take $I = A$ and $X_i = B$ and then the same thing is written as
$$A \times B = \sum_{i \in I} X_i$$
or to confuse beginners
$$A \times B = \sum_{a \in A} B.$$
This just says that $A$ times $B$ is the same thing as adding $A$-many $B$'s together. It's the first thing we're told about multiplication, except that here it's about sets, not numbers (but that's irrelevant, really).


Complexity of a naive algorithm for finding the longest Fibonacci substring

Say that $F(n)$ occurs at some position if the substring starting at that position is compatible with either $F(n)$ or its complementation. How close can occurrences of $F(n)$ be? Take as an example $F(4) = abaab$. If $F(4)$ occurs at position $p$ then it cannot occur at position $p+1$ or $p+2$, but it can appear at position $p+3$. We let $\ell(n)$ be the smallest number such that two occurrences of $F(\ell)$ can occur at distance of $\ell$. You can prove by induction that for $n \geq 4$ we have $\ell(n) = |F(n-1)|$ (for example, $\ell(4) = 3$).

Given a string of length $N$, for each $n$ let $P(n)$ be the set of positions at which $F(n)$ occurs. We can upper bound the running time of your procedure roughly by $\sum_n |P(n)| |F(n)|$, where the sum runs over all $n$ such that $|F(n-1)| \leq N$ (say). Since occurrences of $F(n)$ are separated by at least $|F(n-1)|$, we see that the running time is bounded by order of
$$ \sum_n |F(n)| \left(\frac{N}{|F(n-1)|} + 1\right). $$
Since the lengths of the Fibonacci words increase exponentially, $\sum_n |F(n)| = O(N)$. The remaining term is $\sum_n O(N) = O(N\log N)$, since the sum contains $\log N$ many terms. We conclude that the running time is $O(N\log N)$.

Conversely, the running time on $F_n$ is $\Omega(|F_n|\log|F_n|)$, as can be proved by induction. We conclude that the worst case running time on strings of length $N$ is $\Theta(N\log N)$.


Why does the Java grammar have a StatementExpression that resolves to just Expression? Why have this and other redundant rules in the grammar?

StatementExpression is described in the same specification document as Expression Statements.
I would like to quote this passage specifically:

Certain kinds of expressions may be used as statements by following them with semicolons.
ExpressionStatement:
    StatementExpression ;

StatementExpression:
    Assignment
    PreIncrementExpression
    PreDecrementExpression
    PostIncrementExpression
    PostDecrementExpression
    MethodInvocation
    ClassInstanceCreationExpression

and this:

Unlike C and C++, the Java programming language allows only certain
forms of expressions to be used as expression statements.

ParExpression is described as Parenthesized Expressions and  Primary Expressions.

A parenthesized expression is a primary expression whose type is the
type of the contained expression and whose value at run time is the
value of the contained expression. If the contained expression denotes
a variable then the parenthesized expression also denotes that
variable.
The use of parentheses affects only the order of evaluation, except
for a corner case whereby (-2147483648) and (-9223372036854775808L)
are legal but -(2147483648) and -(9223372036854775808L) are illegal.

About your question:

Why have this and other redundant rules in the grammar?

They are not redundant, that is a mistake in the document, they are different types of expressions. See the grammar for the next version:
StatementExpression:
  Assignment
  PreIncrementExpression
  PreDecrementExpression
  PostIncrementExpression
  PostDecrementExpression
  MethodInvocation
  ClassInstanceCreationExpression


Asymptotic notation between two sets of variables

Unfortunately, there is no standard interpretation of $f(n,m) = O(g(n,m))$ in common use in computer science. Here are some possible interpretations:

There exists a constant $C > 0$ such that for all natural $n,m$, $f(n,m) \leq Cg(n,m)$.
There exist constant $C,N,M > 0$ such that for all natural $n,m$ if $n \geq N$ and $m \geq M$ then $f(n,m) \leq Cg(n,m)$.
Some combination of the two.

In your case, you are describing a different use of asymptotic notation. Suppose that algorithm $A$ works in time $O(n+m)$ (under the first interpretation above).
Claim. If $m = O(n)$ then $A$ works in time $O(n)$.
What this really means is the following:

For every constant $C > 0$ there exists a constant $D > 0$ such that if $m \leq Cn$ then algorithm $A$ works in time at most $Dn$.

The proof is quite simple. Since $A$ works in time $O(n+m)$, there exists a constant $E$ such that the running time of $A$ is at most $E(n+m)$. If $M \leq Cn$ then $E(n+m) \leq E(1+C)n$, so we can choose $D = E(1+C)$.

This kind of "elided quantifier" is common in theoretical computer science. For example, consider the following statement.
Claim. Some Boolean function on $n$ bits requires circuits of size $\Omega(2^n/n)$.
What this statement really means is one of the following:

There is a sequence of Boolean functions $(f_n)_{n=0}^\infty$ such that $f_n$ is a Boolean function on $n$ bits and if $M(n)$ is the minimum circuit size of $f_n$, then $M(n) = \Omega(2^n/n)$.
There is an infinite set $N \subseteq \mathbb{N}$, for each $n \in N$ a Boolean function $f_n$ on $n$ bits, and a constant $c>0$, such that for all $n \in N$, every circuit for $f_n$ has size at least $c2^n/n$.

Once you get used to this sort of statement, such interpretations become automatic, though unfortunately, there is often some ambiguity and vagueness involved.

Your example of $m = O(n)$ probably comes from the world of graph theory. We say that a graph is sparse if $m = O(n)$, where $n$ is the number of vertices, and $m$ is the number of edges. Graph algorithms such as BFS and DFS run in time $O(n)$ on sparse graphs.
What this really means is that if we have a collection of graphs satisfying $m \leq Cn$ or some constant $C$, then BFS and DFS run in $O(n)$ on this collection of graphs. For example, it is known that planar graphs contain at most $3n-6$ edges. Therefore BFS and DFS run in $O(n)$ on planar graphs.


What course in CS deals with the study of RAM, CPU, Storage?

The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on a course From Nand to Tetris originating in the Hebrew University. The Amazon page on the book links to other popular textbooks on the topic.
Generally speaking, this area is at the intersection of computer science and electrical engineering. Some aspects are much closer in spirit to electrical engineering, for example the physics behind memory and storage architectures. Other aspects, such as cache coherence algorithms and error-correcting codes, are more likely to be considered an integral part of both disciplines.


Does there exist a undecidable infinite language with only a finite undecidable subset?

Let $S$ be the set of elements on which the decider $T$ answers MAYBE. We can construct a new decider $T'$ which correctly decides $L$ as follows:

If the input is in $S$, answer the hardwired correct answer.
Otherwise, run $T'$.

Hence $L$ is decidable.
This actually shows that if $L$ is undecidable, then every decider for $L$ must make infinitely many mistakes.


Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$

You used the optimisation of calculating q * r only once. Maybe someone considered that "cheating" and is insisting that it must be calculated twice. I wouldn't agree with that at all, but it would explain the different answers.


Determining whether a CFG is $LL(k)$ for any $k$?

This is undecidable. It is theorem 11 in Properties of deterministic top down grammars by Rosenkrantz and Stearns. Theorem 12 in the same paper however states that the problem becomes decidable if the grammar is known to be $LR(k')$ for some (possibly different) $k'$.


One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex equals the number of vertices of $G$, which not necessarily at least $N$. But this is a minor issue that I leave for you to fix (along with proving correctness).