Dijkstra's shortest path algorithm without relaxation

This answer refers to a previous version of the pseudocode, which had a bug. Once reaching a vertex, it doesn't update its weight ever again.

Your algorithm isn't Dijkstra's algorithm. Worse, it doesn't calculate shortest paths. As a simple example, consider a graph with nodes $\{s,a,b,t\}$ and the following edges:

$s\to a$ with weight 1.
$s\to b$ with weight 2.
$a\to t$ with weight 9.
$b\to t$ with weight 1.

The shortest path from $s$ to $t$ is via $b$, but your algorithm will discover $t$ via $a$ and will therefore output a distance of 10 rather than the correct distance, which is only 3.

Finally, you mention that the space complexity is $O(E)$. In fact, since the heap and set contain vertices rather than edges, it is $O(V)$.


How to properly name the two types of RAM in a Paper?

I have usually heard "main memory" for the CPU-accessible RAM.
Wikipedia calls it "primary storage", with "main memory" listed as a synonym. Although honestly, I would have guessed that "primary storage" referred to the primary nonvolatile medium (SSD or HDD).


Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?

Let $f$ be any computable mapping such that $|f(x)| \geq c|x|$ for some $c > 0$. For every language $L$, if $L$ is computable then so is $f(L)$.

To see this, let us be given an input $y$. We go over all strings $x$ of length at most $|y|/c$. For each of them, we check whether $x \in L$ and $f(x) = y$. If we found such a string $x$, then $y$ is in the language, otherwise it isn't.


Find a quarrel-free seating order with a greedy algorithm

I don't know if i understood your exercise. But pick a arrangement with n students in n positions is a permutation, so there are n! possible arrangements. So, it's look like a Hamiltonian path problem, where each student is a graph's vertex and there's an edge i,j if the student i can sit next to student j, with no quarrel. If you can find some Hamiltonian path, you have a arrangement. For greedy algorithm you can   propose a heuristic that visit first the vertex with low degree (number of edges incident to the vertex), meaning that the most annoying student will be chosen to sit on the first place of the row.


A function like T id(T x){return x;} is actually a (parametrically) polymorphic function, and there are many frameworks that allow assigning a type to such beasts.

One of the most popular frameworks to talk about such things is system F, which allows expressing the type of the above statement as: $$\forall T:*.\ T\rightarrow T$$

This requires the ability to quantify over types to form other types, which is the main feature of system F. Note that because id is a value, it's type has itself a kind, that is
$$\forall T:*.\ T\rightarrow T\ \ :\ \ * $$

in keeping with the analogy with List, whose kind is, as you noted, $*\rightarrow *$, which makes it a type constructor.

Note also that the List type constructor is not a term in system F, for that you need to go further out to system ${F}_\omega$, which was designed in part to study how polymorphism and type constructors may interact.


Of course you can create artificial data.  Simply pick the inputs to the neural network randomly; that's an artificial instance.  You can run it through the neural network and tell what class the neural network will assign to it.  That doesn't mean you know what class it should be given, or what is the correct class; there's no way to get that (you can't get something from nothing).


Counterexample for simple parity automaton reduction

After some thought, I found a counter example. It has four states and there might be one with only three states, but this one works too.

States 1, 2, and 3 are language equivalent. 1 and 3 also have the same color, so they can be merged. If we merge 3 into 1, this is the result:

In the original automaton, $(aab)^\omega$ has the run $(103)^\omega$ which only sees color 1. In the reduced automaton, $(aab)^\omega$ has the run $101(201)^\omega$, which also visits color 0 infinitely often.


You've misread the definition of $Y$. $(\lambda x.f(xx))) (\lambda x.f(xx))$ is the body of the function. You can put an additional pair of parentheses in the definition:
$$ Y = \lambda f. \color{red}{\mathbf{(}} (\lambda x.f(xx))) (\lambda x.f(xx)) \color{red}{\mathbf{)}}$$
Beware that different authors use different conventions for parentheses. But under the most common convention, $\lambda$ has lower precedence than application, so the body of a lambda goes until the next enclosing closing parenthesis. If a text uses a different convention, make sure to put parentheses accordingly.

You can reduce $Y$, but the argument $(\lambda x.f(xx)))$ is applied to $(\lambda x.f(xx))$. The $\lambda f. \ldots$ doesn't change since it isn't applied to anything.
$$\begin{align}
Y \;\; = \; & \lambda f. (\lambda \color{magenta}{x}.f(\color{magenta}{x}\color{magenta}{x}))) \color{magenta}{(\lambda x.f(xx)))} \\
\rightarrow_\beta \; & \lambda f. f \left( (\lambda x.f(xx))) (\lambda x.f(xx))) \right) \\
\end{align}$$
Let $\Omega_f = (\lambda x.f(xx)) (\lambda x.f(xx))$, so that $Y = \lambda f. \Omega_f$. The reduction above is $\lambda f. \Omega_f \rightarrow_\beta \lambda f. f \Omega_f$. That's $\Omega_f \rightarrow_\beta f \Omega_f$ under the context $\lambda f. []$. There's an infinite chain of reductions
$$
Y = \lambda f. \Omega_f
\rightarrow_\beta \lambda f. f \Omega_f
\rightarrow_\beta \lambda f. f (f \Omega_f)
\rightarrow_\beta \lambda f. f (f (f \Omega_f))
\rightarrow_\beta \ldots
$$
This is how the recursion combinator works. But this won't do anything “useful” until $f$ is replaced by a lambda so that the $f \Omega_f$ part can be reduced.

If you apply $Y$ to a function $g$, a redex appears at the top level.
$$ \begin{align}
Y g \;\; = \;\; & \left( \color{green}{\lambda f}. (\lambda x.\color{green}{f}(xx))) (\lambda x.\color{green}{f}(xx)) \right) \color{green}{g} \\
\rightarrow_\beta \; & (\color{darkblue}{\lambda x}. g(\color{darkblue}{x} \color{darkblue}{x})) \color{darkblue}{(\lambda x. g(x x))} \\
\rightarrow_\beta \; & g \left( (\lambda x. g(x x)) (\lambda x. g(x x)) \right) \\
\leftarrow_\beta \; & g \left( \left( \color{brown}{\lambda f}. (\lambda x. \color{brown}{f}(x x)) (\lambda x. \color{brown}{f}(x x)) \right) \color{brown}{g} \right) \\
= \; & g (Y g)
\end{align}$$


Kleene star operation on the empty language

If you consider now the powers of a language $W$ you have
$W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N_0$,
i.e. the non-negative integers, you have to define
$W^0=\{\epsilon\}$. If you took it to be $\emptyset$ you would have
$W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others,
for $x=1$. Thus we would have $W^1=W=\emptyset$ for any $W$.
Thus this would clearly be inconsistent. A similar inconsistency arises for any other choice than $\{\epsilon\}$, which is the identity for language concatenation.

Hence, the only consistent consistent definition of $W^0$ for a non empty set $W$ is
$W^0=\{\epsilon\}$.

It is then convenient to extend the definition to the case when
$W=\emptyset$ as $\emptyset^0=\{\epsilon\}$.

This is just a consistent and convenient definition, often adopted in semi-rings but
it cannot be proved, unlike thw case when $W\neq\emptyset$ where there is no other consistent definition.

However, other definitions have then to be given in a consistent way, which
implies that

$$\begin{align}
\emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\
     &=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\
     &=\{\epsilon\}
\end{align}$$

The topic is discussed on many web pages. In the case of the semi-ring
of numbers (the lack of precision is intentional) this is discussed at
length on this page: Zero to the zero power - Is $0^0=1$?.

The semi-ring of languages is described in this answer.


How are all NP Complete problems similar?

Your question seems to come from the fact that you're not immediately convinced that the current problem can't be harder. The current problem can't be harder than any NP-complete problem because it is in NP.

If you want to be convinced that the notion of NP-completeness even exists (i.e. that you can reduce anything in NP to an NP-complete problem) you should study the Cook-Levin theorem which states that SAT is NP-complete.

Since NP-completeness states something about being the target of a reduction from any problem in NP, the proof works by encoding the Turing machine which was the verifier of the original problem as a formula. This formula is satisfiable if and only if there exists an input which lets the Turing machine accept. You could in principle use this proof to reduce your current problem to SAT, and after that to every other NP-complete problem via transitivity of polynomial-time reductions.


There are CPUs that can execute programs directly from secondary memory. (I'm kind of surprised at you not being able to simply search this: e.g.http://www.analog.com/media/en/technical-documentation/application-notes/EE363v01.pdf)

That being said, many CPUs cannot. It generally boils down to access speeds and/or I/O type. Secondary storage (flash, etc) can be slower and/or have more latency than RAM, and for a simple CPU (i.e. embedded system or similar, generally) the CPU may not be able to wait the length of time necessary to do an instruction fetch. (Or rather, it may assume that an instruction fetch will complete in  cycles as opposed to having a mechanism to wait until the instruction is actually fetched)

Also, unless you have memory-mapped I/O or a proper MMU you'll need explicit support by the CPU to issue the I/O instructions required, which increases the complexity of the CPU and may increase the critical path, limiting the speed of the CPU. (If you have a MMU you can just have a page fault handler that fetches the appropriate page from secondary memory on first access)

An elaboration:

Ultimately, a CPU has to be able to read the data for its next instruction. This is generally only a few bytes at most. However, many devices only support block-level access (e.g. 512 bytes, etc) of larger block sizes than the instruction size. Note that this includes many forms of RAM! (For instance, if you have DDR ram (64 bits transferred at a time) and an instruction set that isn't always 64 bits wide) There are a couple of ways to deal with this mismatch: you can fetch the block and toss away the data you don't need for that instruction, you can fetch the block into a small sliding window of the next few instructions (throwing away the rest of the block) so you only need to do a fetch every few instructions, or you can fetch the entire block into a buffer. Fetching every instruction is slow, and in particular is latency-sensitive. It also wastes memory bandwidth that could be otherwise used for DMA, for instance. Fetching into a sliding window can faster, but substantially more complex. It also introduces latency variations (if you have unpredictable branches you may not be able to keep the window filled, for instance) And fetching the entire thing limits you and requires a lot of die space for the buffer (you need to have a buffer at least as large as the block size), and is prone to problems (e.g. what happens when an instruction overlaps two blocks? There are a lot of edge cases.)


Exponential time local search heuristics for Weighted MAX-CUT-Flip

Check out the paper: On the Power of Nodes of Degree Four in the
Local Max-Cut Problem - Burkhard Monien and Tobias Tscheuschner.

In the paper they take a sub-graph of size 5 constructed from two types of vertices (they call them type-1 vertices and type-3 vertices). Then they build a graph from n sub-graphs concatenated, and show a specific initial start of the max-cut algorithm. In this initial start, there would be an exponential number of flips until the local optima would be obtained.


Sums of all pairs: possible less than quadratic?

Yes, it is possible using $O(n \log n)$ preprocessing and $O(\log n)$ query time.

Given the set $S$, construct the polynomial $P(x)=\Sigma_{s\in S}\textrm{ } x^s$. Then use the FFT multiplication algorithm to compute $P^2(x)=P(x)*P(x)$ in $O(n \log n)$.

A value $q$ s a sum-of-pairs of $S$ if and only if the coefficient of $x^q$ in $P^2(x)$ is non-zero. Use binary search to look up the coefficient in $O(\log n)$ time ($P^2(x)$ is a polynomial of degree $2m$).

There are also less complicated (and less efficient, but still better than $O(n^2)$) multiplication algorithms that use divide-and-conquer such as Karatsuba multiplication ($O(n^{1.585})$ preprocessing).


Find an edge that is completely visible from point outside a polygon (Convex Hull)

It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a convex polygon).

To find the intersection, you can use a binary search and find that is there any intersection or not.


Are DFAs with a unary alphabet strictly less powerful than DFAs with a binary alphabet?

Take the set $A=\{2^k \mid k \ge 1\}$. The language
$$ L=\{ \text{bin}(a) \mid a \in A\} = \{10^k\mid k \ge 0 \}$$
is clearly a regular language, whereas
$$L=\{ 1^a \mid a \in A\} $$
is not regular. Proving the latter is a standard textbook application of the regular pumping lemma.


Shortest common supersequence with Genetic Algorithm

As is usual, you will really have to think for yourself what makes sense for the
crossover function.  But here is the naive approach (without really knowing your
problem).

Let $s_1$ and $s_2$ be the strings you want to find the shortest common
supersequence for.  Let $\text{superseq}(x, s_1)$ be the number of characters in
$x$ that form a supersequence.

For individuals $x$, $x'$, define

fitness: $f(x) = \text{length}(x) - \text{superseq}(x, s_1) - \text{superseq}(x, s_2)$ (we want to minimize $f$)
mutation: $m(x) = \hat x$, where we obtain $\hat x$ from $x$ by randomly changing, deleting, or adding a character
crossover: $c(x, x') = x[i, j] + x'[i', j']$ for randomly drawn $i \leq j$, $i' \leq j'$.

In other words, the crossover simply picks a random (consecutive) substring of
each of the individuals and concatenates it to make a new.  There are many more
options, you can pick a string smarter (keeping only certain missing
characters), you can interleave the strings, e.g. shuffle the string $\chi =
0^{\text{length(x)}}1^{\text{lenth(x')}}$ and let the result of the crossover be

$$ \left[ x[i] \text{ if } \chi_i = 0 \text{ else } x'[i] \text{ for } i \in \text{range}(\text{length}(\chi) \right]. $$


Can't figure out how to make a grammar LL(1)

For context-free grammar to be LL(1), these two requirements have to be met for its every rule $ A \rightarrow \alpha |  \beta$:

$  FIRST(\alpha)  \cap FIRST(\beta) = \emptyset$
$ \epsilon \in FIRST(\alpha) \implies FOLLOW(A) \cap FIRST(\beta) = \emptyset$

  Does it make sense to look at FIRST+ in terms of each production that has the same left hand side?

No, as you can see, to decide if grammar fits those rules above, we have to calculate $FIRST$ function for the right-hand sides of the grammar's rules, not for the left sides.

For your grammar, we get these results:

$A: FIRST(Ba) = \{c,d\},\space FOLLOW(A) = \{\epsilon\}$

$B: FIRST(dabB') = \{d\},\space FIRST(cBbB') = \{c\}, \space FOLLOW(B)=\{a,b\}$

$B': FIRST(acbB') = \{a\},\space FIRST(\epsilon) = \{\epsilon\},\space FOLLOW(B')=\{a\}$

As you can see, there is a $FIRST/FOLOW$ conflict (violated second requirement from above) in $B'$. You can read here about how to solve this.


Intersection of O(n) expanding circles with line from the origin

The solution outline:

Step 1. Verify, that all the initial (at the moment $t=0$) wave circles don't contain your starting point $(0,0)$. If yes, then continue - otherwise exit, no escape.

Step 2. For each wave circle $W_i$ you need to find an escape sector - the range of directions, where the escape is guaranteed.

Imagine a circle of your possible positions at moment $t$ with center in $(0,0)$ and radius $pt$ - we'll call it the circle $C$. Let's consider what will happen with circles $C$ and $W_i$ with time. Originally (when $t=0$) the circle $C$ is just a point at $(0,0)$. Then, with time increasing, the expanding circle $C$ will at first touch the expanding circle $W_i$ at a single point, then intersect it at two points. Moving further, at some point of time the expanding circle $C$ will touch the circle $W_i$ again at a single point, then it will contain the circle $W_i$ completely (because $p \gt s_i$).

Two intersection points between circles $C$ and $W_i$ define a no-escape sector. This sector angle $\alpha$ grows from zero to some maximal value and then decreases to zero again. Cosine of this half-angle at the moment of time $t$ can be found from the triangle with all known sides:

$$\cos(\frac {\alpha} {2}) = \frac {(pt)^2+d_i^2-(r_i+s_it)^2} {2d_ipt}$$

where $d_i = \sqrt{x_i^2+y_i^2}$.

You need to find positions of intersection points, which will give you this maximal angle value. In order to do that you can take first derivative of the non-escape sector half-angle by time and set it to zero - that will give you the moment of time when the non-escape sector is maximally wide. This moment of time $T_i$ will be:

$$T_i = \sqrt{\frac{d_i^2-r_i^2}{p^2-s_i^2}}$$

Knowing the non-escape sector you'll easily find the escape sector.

Step 3. If intersection of all the escape sectors is non-empty, then the escape is possible.

The algorithm time is obviously $O(n)$.


You should implement rational numbers yourself. Store number as two integers. Use the greatest common divisor to factor out superflous representation. Literally write school algorithms for rational numbers - find common denominator for addition and then normalize number. At the end convert it to decimal representation with fixed precision. Namely use symbolic calculation as long as you can.

From your example:
$\frac{1}{3} + \frac{1}{5} = \frac{5}{15} + \frac{3}{15} = \frac{8}{15} \approx 0.5333$

If your task really requires to convert it to string at the first step, then you have to assume some precision, e.g. four numbers in decimal expansion, and then write your own code to operate on numbers. The exact decimal expansion is not always possible, as you have already realized, so $\frac{1}{3}$ would expand to "0.3333" (arbitrary length from my example. It may seem weird at first, but the floats are also inexact, with precision given by fixed length representation (e.g. 64, 80, 128 bits).

$\frac{1}{3} \approx 0.333; \frac{1}{5} \approx 0.2000$
So
$0.3333 + 0.2000 = 0.5333$
It gives the same approximate result.


Inserting at the head of a linked list is O(1), but this involves moving pointers, and they are not constant size

We usually analyze algorithms using the RAM model, in which basic operations on machine words cost $O(1)$. On an input of length $n$ bits, the size of a machine word is $\log n$. In your case, a pointer should fit into one machine word, and so moving a pointer should take $O(1)$ time.

A different issue is how much time is required to maintain the heap. One way around this is to work in the "heap-enabled RAM model", in which heap operations are for free. Probably many papers on algorithms implicitly work in this model.

Finally, a few words on the RAM model. It extends the Turing machine model in two ways. First, it allows indexing. This matches the way actual computers work. Second, it allows constant time arithmetic on machine words, which are usually chosen as indicated above. The size of machine words is chosen so that operations on indices take $O(1)$. For example, consider the following program for summing an array $A$:

sum = 0
for i from 1 to n:
  sum = sum + A[i]
return sum

If we want this algorithm to run in $O(n)$, we need the operation $i \to i + 1$ to run in $O(1)$. Since $i$ could be $\log n$ bits long, we need machine words to be at least $\log n$ bits long. Practice shows that it is not necessary to consider larger machine words. Note that machine words of size $C\log n$ can be simulated using $O(1)$ machine words of size $\log n$ using a multiplicative overhead of $O(1)$; since we don't care about constant factors, increasing the machine word to size $C\log n$ doesn't affect the power of the model.


This is the standard procedure for converting NFAs to DFAs. The first row should be read as "If you know you're in one of the states $0$, $1$ and $4$ and you read an $a$, you'll have to be in one of the states $1$, $2$ and $4$; if you read a $b$, you'll have to be in one of $1$, $4$ and $5$." The other rows are similar.


Is It Possible For a Data Structure to Have Constant Time Access/Insertion/Deletion?

How do we get lower bounds?

As D.W. noted, lower bounds are hard. But that doesn't mean that no progress can be made. To get a lower bound, it is required (well, not strictly, but you won't get very far without one) that you make a (possible restrictive) model of all algorithms or data-structures that can solve your problem.

For example, the $\Omega(n\log n)$ lower bound for sorting holds only for the restrictive 'comparison based sorting' algorithms. (this is why counting sort can 'beat' this time in some cases: it isn't comparison based)

Lower bounds for data structures

For the case of data-structures, the cell-probe model seems a good place to start. This model is similar to the more common RAM-model, but can be useful for lower bounds as it 'only counts' the number of accesses to stored data (i.e. the number of 'probes' to a cell).

For example, in the paper by Yao that introduces this model, lower bounds are calculated for the data structure supporting INSERT, DELETE and MEMBER (test for membership) queries. I think that a similar technique could work for your data-structure as well.

Do note that the paper by Yao is a bit outdated. I mostly mentioned it because the problem it considered is relatively simple and similar to yours. More modern techniques are covered in the dissertation of Kasper Green Larsen.


Can a shortest-path tree be a also maximum spanning tree?

Let A-B-C be connected graph with edges like shown (AB and BC) the shortest path (the only possible) from A to C is through B. To include all vertices in the maximum spanning tree all vertices are needed, so this is small example (the smaller, A-B is also valid).

Maximum spanning tree have maximal weights, but may be not unique for given graph. The shortest path tree (which I assume is the weighted one) have path weights but also is not guaranteed to be unique.

From the definitions finding graph with cycles will be harder - taking minimal example, a full graph with vertices D, E, F and distances |DE| = 3, |EF| = 2, |DF| = 3, the shortest path from E to F is 2, but the maximal spanning tree will not contain this edge.
The two structures may overlap when there are no cycles or weights are equal, otherwise they will get opposite edges when possible.


Why do floating point values have infinity?

Because sometimes there just isn't an exponent high enough.

First of all, there is no way to effectively represent all real numbers in a reasonable computational model: it is sufficient to observe that the set of configurations of e.g. a Turing Machine is countably infinite, and the set of real numbers is uncountably infinite. Floating point numbers, are ultimately an approximation of what the "actual" computation would be; models for exact real computation exist but as we said before they necessarily "miss" some numbers.

INF and NaN are part of the IEEE standard for rather practical reasons, namely to give meaning to computations that should fail, for a reason or another, and handle such cases in a safe way. We could, as you are basically suggesting, take a floating point model that is finite but unbounded, dynamically adding more space as we need it. As others have already commented, this kind of generalization is actually missing the point: the strength of floating point computations is that they can be performed very efficiently on hardware, and a dynamic solution would be infeasibly more complex.

But even assuming such a model, we aren't really addressing the core of the issue. Let's say that at a certain point we ask the machine to perform the computation $\log(0)$. Mathematically, it doesn't make any sense, because $\log$ isn't defined on $0$. If we didn't have a special value like -INF to return, we would have to abort the computation (or have the program diverge, or terminate in some kind of error state). You might think that such a thing is reasonable: after all, if we had the machine compute $\log(0)$ the program must be wrong in a way or another.

But it gets worse. In any floating point model, there is a smallest positive number that we can distinguish from zero, let that number be $\varepsilon$. Now, we ask the machine to compute $\delta = e^{-10}\varepsilon$ and then $\log(\delta)$. Observe that all those operations are mathematically legit, for instance we can easily see that $\log(\delta) = \log(\varepsilon)-10$. However $\delta < \varepsilon$, which means that our model literally cannot tell $\delta$ and $0$ apart, by definition of $\varepsilon$. It is much less reasonable to make the entire program fail, now.

Special values like NaN and INF manage to at least salvage the "logical" aspect of the computation, correctly handling equality/inequality checking and the sign, if applicable (i.e. +INF is greater than everything else, NAN is not equal to NAN and so on).


What is the formal, rigorous definition of a programming language?

To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no less, any convention that is used for describing instructions for computers to execute. This includes, for example, not just C++ and Python, but also things like Nondeterministic programming, where we actually don't tell the computer exactly what to do, but give it several alternatives and allow it to choose any one of them; declarative logic languages like Datalog where we give the computer a set of logical axioms and ask it to deduce all the true statements from those axioms; and even very low-level descriptions like Turing machines and electrical circuits, where we give the program explicitly as electrical or mechanical components. All of these are ways of describing instructions to computers, so all are valid programming langauges at very different levels of abstraction.
However, programming languages researchers do generally agree on some common formal components of programming languages that should always be present, and these serve as a general definition. Namely:
every programming language is defined by a syntax and a semantics.

Syntax. This is a formal grammar which gives the set of programs that can be written. Importantly, the formal grammar consists of finitely many syntax elements, which are described in terms of other syntax elements. For example a simple grammar is:
Variable := x | y | z
Term := 0 | 1 | Term + Term | Variable
Program := set Variable = Term | return Term | Program; Program

In this simple language, we have three syntax elements: Variables, Terms, and Programs. In a formal grammar, each syntax element has finitely many cases for how it can be constructed via other syntax elements. For example, a program is either an assignment (setting a variable to equal a term, e.g. set x = x + 1), a return statement, or a sequence of two programs which should be executed one after the other.

Semantics. Syntax is just describing the set of valid programs; but it doesn't say anything about what those programs mean. Semantics is a way of assigning meaning to programs. Unlike syntax, which is almost always given as a formal grammar as above, semantics can be given in at least two different ways: these include "denotational semantics", where we assign a mathematical object such as a function to each program, or "operational semantics", where we describe the execution of a program in a more true-to-life way as a sequence of steps.
To illustrate this, starting with denotational semantics: we would say that the term 3 + 5 + 8 is assigned the meaning of 16. More interestingly, the program set x = x + 3 + 5 is assigned the meaning of the mathematical function mapping every integer to that integer plus 8.
Operational semantics, on the other hand, is very different. We would say that the term 3 + 5 + 8 evaluates to 8 + 8 which in turn evaluates to 16. We would also say that the program set x = x + 3 + 5 in a context where x = 5 evaluates to a context where x = 13. So, instead of giving a meaning to each term or program itself, we give a meaning between terms called "evaluates to": we give a formal definition of what it means for A to evaluate to B in the context C.
In any case, the semantics of a language, whether denotational or operational (or something else) gives meaning to the symbols and allows us to make sense of what programs compute, not just what they look like.

Putting these together, we get the following definition.
Definition:
A programming language consists of (1) a syntax, given as a formal grammar; and (2) a semantics, given either as denotational semantics which gives a meaning to each syntax element, or an operational semantics which says when two programs or program contexts relate.


Are there lambda-calculus functions which always output booleans, but are not constant functions?

That is not possible. By the "genericity lemma" (Barendregt book, lemma 14.3.24), if $C[M] = N$ with $M$ unsolvable, and $N$ normal form, then $C[L] = N$ for any term $L$.

So, if $x$ is an unsolvable term (like $\Omega=(\lambda w.ww)(\lambda w.ww)$) and $f x = {\sf true}$ (normal form), then $f y = {\sf true}$ for any term $y$. The same holds for $\sf false$ or any other normal form.

The intuition here is that an unsolvable subterm will make the whole term diverge as soon as it is needed for the computation, much like while (true) {} hangs the program in imperative programming as soon as the loop is executed.


Express a number as a sum of consecutive primes (How many ways?)

I assume that n is large, and that we only want the answer for one single n. In that case, we would avoid creating a sieve of all the primes up to n, if possible, because it would take O (n); I think we can do this faster.

Create a list of all primes p ≤ M, using a sieve, with a cleverly chosen M. This takes about O (M) and finds about $M / \ln M$ primes. Then we find all solutions involving primes up to M by adding up primes starting with p = 2 until the sum is ≥ n, recording a solution if the sum equals n, removing the first primes until the sum is < n, adding primes until the sum is ≥ n etc. This only takes O ($M / \ln M)$ which is less than O (M) for the sieve, so we can ignore it.

This part of the algorithm finishes when we would need to add a prime p > M
to the list (which we don't have). At that point we know that the sum of the K largest primes ≤ M is less than s, for some K, and that we have found every possible way to write n as the sum of more than K primes. Now we have to find ways to write n as the sum of k ≤ K consecutive primes; in addition k is odd if n is odd, and k is even if n is even.

For every k, we do this by creating a sieve of primes around n / k; this sieve should be large enough to contain more than k primes. When we have the sieve, we find the first k/2 primes > n/k and k - k/2 primes ≤ n/k. If the sum is less than n then we add the next larger prime and remove the smallest one until the sum is ≥ n; if the sum is > n then we add the next smaller prime and remove the next larger one until the sum is ≤ n. If the sieve turns out to be to small we create a bigger one. If the sum is n, we have a solution.

Creating the sieve takes at least O ($(n/k)^{1/2} / \log n$) steps for trial divisions. Instead of creating the sieve around n/k, we could have made the original sieve larger, choosing M ≈ n / (k - 2) instead of M ≈ n / k, which would have cost about $n / k^2$ steps.

Both costs balance when $n / k^2 = (n/k)^{1/2} / \log n$ or $n^{1/2} = k^{3/2} / \log n$ or $n \log^2 n = k^3$ or $k = (n \log^2 n)^{1/3}$ or $M = n/k = (n \div \log n)^{2/3}$

The estimate for creating the small sieves may have been a bit generous; if we use this method with $M = n^{2/3}$ then it should run in $O (n^{2/3})$.


Regular expression with out the substring bab or abb?

There are a couple tricks required to get this right.

First, this particular problem is a lot easier if you approach it backwards, starting at the end of the sting.

(abb,bab) is an exhaustive list of all the cases in which b is preceded by 2 different letters.  If you want to exclude these cases, you just have to ensure that b is preceded by less than 2 letters, or a double letter.

Second, notice that these rules imply that if there are 2 bs in a row, then they must be preceded by b all the way to the start of the string.  Otherwise the second-to-first b will be preceded by ab.

Working from the end, then, we can have a free mixture of a and aab, and then there are only a few ways to get to the beginning of the string when we encounter a b outside of that pattern:

(ab|b*)(aab|a)*


NP-completeness of a spanning tree problem

Seems this question has been bumped by the system because it has no answer yet:

The idea JeffE proposed is to reduce the Hamiltonian Path problem (a known NP-complete problem) to this version of the spanning tree problem.

This is not hard to do: given a graph and two nodes we want to find an HPath between, we can set S to the set containing those two nodes and ask for a spanning tree with those nodes as leafs. Since a tree with just two leaves is a path, and a spanning path (that goes through all the nodes) is a Hamilton path, we can see how its possible to use an algorithm for the spanning tree eproblem to solve any Hamilton Path problem.

This proves that the spanning problem is NP-Hard. Since the problem is also clearly in NP, we thus can conclude that its NP complete.


What is the difference between control flow graph & interprocedural control flow graph?

CFG (Control Flow Graph): representing control flow for a single procedure
IPCFG (Inter-Procedural Control Flow Graph): representing control flow for a program

source: http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf


How does a cache handle overwriting between 2 addresses in the same block?

Your program will work exactly as if there was no cache, and as if each single memory operation was completed before the next one is started.

Typical implementations will first make sure that the complete data for a cache line is stored in the cache. So for example writing four bytes may first read the complete 64 byte line from memory.

With a line of data in cache, accessing it can be done very quickly. If there are multiple instructions reading or writing, you can expect one to be executed completely in each cycle. If instructions access different cache lines, a powerful processor may allow simultaneous access to two different cache lines. A powerful processor may also allow simultaneous access to clearly separate parts of a cache line. 4 bytes at location 2 and 4 bytes at location 6 may not count as “clearly” separate.

If you access different cache lines, the one that is accessed by a later instruction may be available in the cache earlier, and the actual access may happen earlier.


When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity?

There are several different concepts here. Let's start from the most general. A tree is a data structure that consists of a root and a collection of children, each of which is a tree. A node of the tree is either the root of the tree itself of a node of the children, i.e. it's the root, or the root of a child, or the root of a child's child, etc. The nodes of a tree can contain information of any type. Here are a few examples of trees:

One that you encounter everyday when working with computers is the filesystem¹: there's a root directory, subtrees are subdirectories, and there are subtrees which have no children and which are regular files; the children of a node are identified by a name (so it's not “first child”, “second child”, etc. but “child named hello.txt, child named pictures”, etc.).
An example from real life is the section structure of a book: there's the book, which is divided into chapters, which are divided into sections, which are divided into subsections, etc.
One type of tree data structure is the trie, which stores information indexed by a string. Each node has one child per character in the alphabet. The information corresponding to a string is located by starting from the root, going to the child corresponding to the first character of the string, then to the child of that child corresponding to the second character, etc. For example the string abc would be stored three levels deep, going down from the root to the a child, then to its b child, then to its c child.

You'll notice that in the filesystem and in the book sections example, information can be inserted anywhere. I can store my files in whichever directory I want; I can add a section to the chapter of my choice. In contrast, the structure of a trie is completely rigid: there's only a single place in the tree where abc can go.

A binary tree is a tree where each node happens to have at most two children. The two children are typically known as the left and right child. There is a common variation on this definition that defines a binary tree to have two types of nodes: internal nodes which must have exactly two children, and leaves which have no children.

A binary search tree is a type of tree data structure. Like a trie, it imposes a constraint on where the information must be stored. A trie indexes information by a string; a search tree indexes information that is ordered: it can be numbers, strings, etc. In a binary search tree, the data in the left subtree of a node is always smaller than the datum in the node itself, and the data in the right subtree of a node is always smaller than the datum in the node.

If you try to add element into an existing search tree, there's a single way to do that without changing the current structure of the tree: going down from the root, take the left child if the node is larger than the element to add, take the right child if the node is smaller, and keep going until you get to a child that doesn't exist, and create that child.

However, the structure of search trees is less rigid than the structure of tries: there are different search trees that contain the same data. For example, here are three binary search trees containing the integers 2, 4, 5, 8, 9 (there are of course many more):

      8            4          2
    /   \         / \          \
   4      9      2   5          4
  / \               / \          \
 2   5             8   9          5
                                   \
                                    9
                                   /
                                  8

In the worst case, inserting an element in a search tree requires traversing the whole height of the tree, which as the last example above show can be as much as the number of elements of the tree.

The leeway in the tree structure allows one to reshape the tree when adding or removing elements from it. This is called balancing. Balancing is done in order to keep the height small, which keeps operations such as search, insertion and deletion efficient. There are several variants of balanced search trees, where the balancing operations is designed to keep the height of the tree logarithmic in the number of elements of the tree: $h = O(\log(n))$. The basic principle of a balanced search tree is to keep some information about the height of the subtree in each node; when the height difference between the two children of a node is too large, some nodes are moved from the deeper subtree to the shallower subtree to rebalance. The rebalancing operation costs $O(1)$ at each node and is performed over the path to the element that's being inserted or removed, so its cost over the whole tree is $O(h) = O(\log n)$. This way, search, insertion and deletion in a balanced search tree cost $O(h)$ to find the target location, plus $O(h)$ to rebalance, which is $O(h) + O(h) = O(\log n)$ total.

¹  In practice filesystems can be more complex than what I'm talking about here. Filesystems with hard links aren't even trees.


Would removing the branch delay slots change the instructions set architecture?

The instructions set architecture (ISA) is the contract between the hardware designer and the software designer.  Anything that changes the contract, changes the ISA.

The question you have to answer is: given every possible program written with this particular ISA, do any of them have different behavior (give a different answer) if we remove the branch delay slots.


I don't really understand the algorithm you're trying to use to count. It seems rather complicated and, instead of trying to correct it, I'm just going to start from scratch.

Really, everything is just like decimal, only there are fewer choices for each digit.  Just like decimal, leading zeroes don't alter the value of the number (0123 is the same number as 123 and 0000123) so we can always add leading zeroes if that helps us.

To add 1 in decimal, we just increase the last digit by 1, if it's not already the biggest possible value. If it is the biggest possible value, we replace it with 0 and "carry 1" to the second-to-last digit. What does that mean? Well, it just means that we increase that digit if we can and, if we can't, we reset it to 0 and carry the 1 to the previous digit. Eventually, if we started with something like 999, we'll have to say that 999 is the same thing as 0999 when we need to the 1 past the left-most 9

So, to add 1 in binary, we increase the last digit by 1, if it's not already the biggest possible value, which is 1.  If the last digit is 1, we reset it to zero and "carry the 1", which we do just like we did before.

This means that it goes as follows:

0
1 (Increase the last digit)
10 (We can't increase the last digit, so we reset it to zero and carry the 1. We've run out of digits, so we put a new zero on the left. Then, to carry the 1, we add 1 to that new digit.)
11 (Increase the last digit)
100 (Reset the last digit to zero, carry the 1. Reset the second-to-last digit to zero, carry the 1. No digits remain, so put a new zero on the left and carry the 1 to it.)

Perhaps it was overly complicated to say that we put a zero on the left-end of the number and then increase it; I could have just said that we put a one on the left end and we're done. I used the slightly longer formulation because you can keep using that when you start adding numbers bigger than one.


How to XOR two binary numbers having different lengths?

There are multiple ways to interpret this XOR.

The most common one is that you XOR bit-wise, and that these strings represent numbers, so adding 0 to the left doesn't change their value.

Then $5 \equiv 101 \to 0101$  and then you XOR bit-wise.

x 1101
y 0101
------- XOR
  1000

which gives 8, if we are talking about unsigned numbers.
However, the above depends on my understanding of your system. Change the assumptions, change the results.


Abstract Data Types and their Implementation

I would say Algorithms by Robert Sedgewick and Kevin Wayne is a classic book which explains quite well the basics of these concepts.

However you could also find a lot of resources on the web for free.


No finite automaton can simulate a Universal Turing machine, so finite automatons are not Turing complete. This falls out immediately from them having a finite number of states. Universal Turing machines require an unbounded amount of space to work.

The source code of an Jot program can be recognized with a finite automaton. That automaton doesn't evaluate the program (and thus doesn't play the role of a Turing machine), it just determines whether or not it is well-formed enough to be run.

This is in contrast with most programming languages. For example, because JavaScript has nested () and {}, it's necessarily not regular (but is, at least approximately, context free). Indentation sensitive languages like Python aren't even context-free (without preprocessing of identation).

This isn't that interesting of an observation. For example, the following is a Turing-complete a subset of syntactically-valid JavaScript programs that is recognizable with a regular expression:

/^eval\("[^\n\"]+"\)$/

...just most of these will immediately throw a runtime error because eval will not parse its single argument -- essentially we can define a programming language to treat all inputs as "syntactically valid" by just defining a new runtime behavior for all the syntactically invalid ones.

What is maybe more interesting about Iota is that its grammar also naturally parallels the actual structure of programs, instead of being a weird encoding trick like the above.


What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?

Approximating volume of convex bodies

In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17.
a $O(n^{19})$ approximation algorithm was proposed.

The work of Lovász et al.: Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^*(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).

Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/


Is the NP-hardness Proof with One Way Implication Correct and Why?

Consider the following two wrong "reductions" from $SAT$ to $L = \{1\}$.  Let $\phi$ be a $SAT$ instance.

We "reduce" every $\phi$ to 1, i.e. $f(\phi) = 1$. Now we have $\phi \in SAT \Rightarrow 1 \in L$. But $L$ is clearly not NP-hard.

Next we "reduce" every $\phi$ to 0, i.e. $f(\phi) = 0$. Now we have $ 0\in L  \Rightarrow \phi \in SAT$. But again $L$ is clearly not NP-hard.

Thus we can see that for a correct reduction we need a proper if and only if condition: $x \in \Pi' \Leftrightarrow f(x) \in \Pi$.

If we have a reduction as above, and if we know that SAT is NP-complete (in other words a hard problem), we have two corollaries from this.

1) Any language can be reduced to SAT. So every language can be reduced to SAT and then to $L$, so $L$ is also NP-complete (now we know that $L$ must also be a hard problem).

2) Any algorithm for membership of $L$ can be used to solve membership to SAT. So if we have an "algorithm" for $L$ then so do we have an "algorithm" for SAT. The algorithm will work this way. From $\phi$ we will construct $f(\phi)$ and then apply our "algorithm" to $f(\phi)$. If answer is YES then $\phi$ is also satisfiable, and if answer is NO then $\phi$ is not satisfiable.

So from 2) we can see that an algorithm for $L$ is applicable for $SAT$. But vice versa is not true. Any algorithm for $SAT$ (polynomial or exponential) can not be used for $L$ using this reduction (there might be other ways but not using just the above reduction). Notice the uncovered region in $L$. So this is what is meant by cryptic comment: solution of $L$ $\Rightarrow$ solution of SAT.


How does storing encrypted password provide secure authentication?

Actually, storing an unencrypted password can be OK in certain circumstances, depending on what the password is used for and the threat model you are trying to defend against.

In any case, if you are authenticating to a remote system, you probably should be using public-key cryptography instead of a password if you possibly can.

Some relevant readings:

https://security.stackexchange.com/q/12332/971
https://stackoverflow.com/q/2283937/781723
https://security.stackexchange.com/q/184021/971
https://security.stackexchange.com/q/20294/971
https://security.stackexchange.com/q/143338/971
https://security.stackexchange.com/q/129776/971
https://security.stackexchange.com/q/22760/971


Why does functional map() operation not permit operating on two elements of a list at a time?

Conceptually, 1-argument map should be able to work on unordered collections, because each application of a mapping function doesn't know anything about the element's index.

Your proposed version does know something about the elements' indices, so treats its argument as an ordered sequence of elements. That's the difference.

For regular lists, we can recover the indices by zipping the list with the (infinite, unbounded) sequence [1..]. So, the ability to zip assumes the sequence is ordered - not in values, but positionally.

Mathematicians can have some specific terminology for this, but I think that's the gist of it.

Such sequences you can always split into a special so-called head i.e. "first" element, and the rest of them, deterministically. But e.g. for truly non-deterministic sequences this is not possible, yet mapping is still a well-defined operation.


Equivalence rules for LTL - Getting stuck working with $ \square \lozenge $ & Until ($\textsf{ U}$ ) operators

In order to prove the equivalence of two formulas $\phi,\psi$, it is enough to show that for every computation $\pi$, it holds that $\pi\models \phi$ iff $\pi\models \psi$. This is semantic equivalence.

Let's look at (1). You got to the formula $true{\bf U} (\psi\vee \neg \phi)$. Now, this holds in a computation $\pi$ iff there exists $i\ge 0$ such that $\pi^i\models \psi\vee \neg \phi$. Assume now that $i$ is minimal with respect to this property, and consider the computations $\pi^j$ for $j<i$. If $\pi^j\models \neg \phi$, then $i$ is not minimal, so $\pi^j\models \phi$, which means that $\pi\models \phi {\bf U} (\psi\vee \neg \phi)$. Since the converse implication is trivial, we get that the two formulas are equivalent.

For (2) you should indeed show that the formulas are not equivalent. To do so, you need to show that there exists a computation $\pi$ that satisfies one but not the other.

Hint: It could be the case that $\phi$ holds only finitely many times, but $\psi$ does not hold after $\phi$.


Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

Let us start with the original approach. We compute the hash values of all input elements, and choose the minimal one $h$. If the leading bit is at position $k$, then we estimate that the number of distinct inputs in the output is roughly $2^k$.

The idea behind this is that we think of the minimal hash as a minimum of $N$ random strings, where $N$ is the number of distinct inputs. We expect the leading bit of such a minimum to be at position roughly $\log_2 N$.

When using $D$ different hash functions, the corresponding experiment is

  Choose $N$ random strings for each of $D$ many bins.

We then calculate the leading bit of the minimal string in each bin, and use this to estimate $N$.

Now suppose that we use the top $B$ bits to choose one of $2^B$ buckets, and compute the minimum value in each bucket. As before, this should be similar to the following experiment:

  Distribute $N$ random strings into $2^B$ bins at random.

As before, we then calculate leading bits and use them to estimate $N$, but since this step is identical to the corresponding step in the multiple hash method, we just concentrate on the first part of the experiment (putting random strings into bins).

We expect each bin to get roughly $N/2^B$ random strings, and so this experiment is very similar to the following one:

  Distribute $N/2^B$ random strings for each of $2^B$ many bins.

This is the same as the experiment for multiple hash functions, with $D = 2^B$ and $N$ reduced by a factor of $2^B$.

You might be put off by the difference in $N$. However, this difference disappears when we calculate the number of hash function evaluations. If we have a quota of $M$ hash function evaluations, then in the multiple hash case we can only use $M/D$ inputs, whereas in stochastic averaging we can use $M$ inputs.


Are Linear Bounded Automatons Turing Complete?

A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.


Here is Euclid's algorithm.
The input is two integers $x \geq y \geq 1$.
While $x > y$, the algorithm replaces $x,y$ with $y, x\bmod y$.
The final output is $x$.
In order to prove that this algorithm correctly computed the GCD of $x$ and $y$, you have to prove two things:

The algorithm always terminates.
If the algorithm terminates, then it outputs the GCD (partial correctness).

The first part is proved by showing that $x + y$ always decreases throughout the loop. The second part is proved by induction, using the equation $$ \mathit{gcd}(x,y) = \mathit{gcd}(y,x\bmod y). $$
Both parts also use the loop invariant $x \geq y \geq 1$.
What you call the "deductive proof" is only part of the proof of partial correctness. It forms the main technical part inside a proof by induction on the number of iterations.


Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

Let $n$ be the number of integers and $t$ be the target integer.
You can solve your problem in $O(n \log n)$ time as follows:

For every $i=0, \dots, n-1$, let $p = A[i] \cdot A[i+1]$ and compute, in $O(\log n)$ time, the number $\eta(t/p)$ of integers in $A$ that are equal to $t/p$ (more on that later).
Then the number $\gamma_i$ of triplets formed by $A[i]$, $A[i+1]$ and a non-adjacent element is $\gamma_i = \eta(t/p) -  |\{A[j]=t/p \, : \, i-1 \le j \le i+2 \}|$.

It follows that the number of triplets of interest is $\sum_{i=1}^{n-1} \gamma_i$.

To find the values  $\eta(\cdot)$ do a preprocessing in which you create a copy $B$ of $A$, sort $B$ in $O(n \log n)$ time, and append an element with value $+\infty$ to $B$ (this is just to avoid edge cases, $+\infty$ can actually be any integer greater than $t$).

If $x \not\in\mathbb{Z}$, $\eta(x)=0$. Otherwise $\eta(x)$ can be found in $O(\log n)$ time by binary searching for the smallest indices $i$ and $j$ in $B$ such that $B[i]\ge x$ and $B[j] > x$, respectively. Notice that $i$ and $j$ are always well defined and that $\eta(x) = j-i$.


Finding a winning strategy for toads and frogs

Ultimately, unless you can prove something very interesting, you're stuck with exponential backtracking.  For at least one natural encoding of positions, Toads and Frogs is NP-hard.

Jesse Hull observed that the position $T^n\Box TFT^m \Box TF$ has the game value $\{m+n-1\mid \{ n\mid 2 \}\}$, which means

If $T$ moves first, $T$ gets $m+n-1$ free moves.
If $F$ moves first and then $T$, then $T$ gets $n$ free moves.
If $F$ moves twice, $T$ gets $2$ free moves.

By combining this position with positions of the form $T\Box^x$ and $\Box^y F$, we can set up a position whose value is $\{a\mid\{b\mid c\}\}$ for any integers $a,b,c$.

Yedwab and Meows proved that determining which player wins a sum of games with values $\{a_i\mid\{b_i\mid c_i\}\}$ is NP-hard.  A sum of games is a set of games that are being played simultaneously; each player can choose which game to play in on their turn; and the first player unable to move at all wins.  Toads and Frogs positions often decompose into sums; for example, a position that contains $TTFF$ is equivalent to the sum of the pieces to the left and the pieces to the right.

These two results imply that playing Toads and Frogs optimally is NP-hard if positions are run-length encoded.  That is, any string of $n$ frogs should be encoded using only $O(\log n)$ bits, encoding the integer $n$ in binary, not using $O(1)$ bits per frog.

It is possible, although I think very unlikely, that an optimal move in Toads and Frogs can be computed in polynomial time if the input position is encoded as a simple string over the alphabet $\{T, \Box, F\}$.  (Yedwab's NP-hardness proof is a reduction from PARTITION, which is only weakly NP-hard.)


Fitting a regular grammar to strings from a PCFG: how big does it get?

The question, if understood in the simplest naive way, might be uninteresting.

Here is a simple example. Let $G$ be the regular language $\{a^n\mid n\ge0\}$ over the alphabet $\{a\}$.

Consider the strings $\epsilon, a, a^2, \cdots, a^n$ in $G$. What are the regular languages that contains those strings?

The minimal such language, i.e., which contains no other strings, will need $n+1$ generation rules $S\to a^i$ for $0\le i\le n$.
The language with the least generation rules is $G$ itself, which has two generations rules $S\to \epsilon$ and $S\to aS$.

However, once we start to twiddle with the ways how to approximate context-free grammar by regular grammar, there are tons of research.

Here is a related question that links to many related stuff, Is there a known method for constructing a grammar given a finite set of finite strings?.

This paper considers approximating CFG from above by a regular
grammar.

You can browse the google search result for approximate context-free grammar by regular grammar or the google scholar.


The main reason why computers are complicated is because they are really optimized to deliver the maximum speed. There are a lot of places in a computer where information is stored:

processor registers: here the speed of memorization is really high, but this memory is very expensive;
random access memory: slower and cheaper then processor registers, but more expensive and faster then hard disk memory
hard disk: one of the cheapest and slowest kinds of computer memory

There are also cache mechanisms in between of these levels.

The first definition of computer is that of a person computing some arithmetical operation. So a person could be seen as a very familiar kind of computer, or a biologically very complex one.

Not all computer models are complicated. It has been proved that the following models can compute the same types of problems:

Turing machines: just a tape and a finite state automata;
lambda calculus: few definitions are enough to achieve a system to manipulate symbols;
Godel's general recursive functions


Where does the FLP impossibility proof depend on allowing a single process failure?

The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no steps". p taking no step means it has died/failed.

From case 1 of lemma 3, we know that there exists a pair of messages, called e and e' which affect the decision process, and if they are received by different nodes (p and p') the nodes will decide on different values. This means that these "important messages" must be received by a single node p only.

Case 2 tests this further with the possibility that node p, the recipient of the "important messages", fails (or "takes no steps"). If a "totally correct in spite of one fault" algorithm exists, it needs to tolerate the scenario where node p fails after configuration C0. Of course, p might just not fail, and the algorithm must be correct in both scenarios: p failing and p not failing.

Since the algorithm must decide on some value, if p is failing it has to proceed through some run called sigma and arrive at a deciding configuration A.

The problem here is that if p is actually still functional, it will accept e and e' and decide on its own. As we know from case 1, node p can decide on 0 (e arriving before e') or decide on 1 (e' arriving before e). So node p is making a decision on its own with no regard for what the rest of the nodes (through sigma) are deciding and ultimately there will be a case where the 2 set of nodes decide on different values.

As for your proof, since p takes no steps (it dies after C0), it invalidates your definition of a 0-admissible run.


How do you compute the time complexity of distributed algorithms?

Time complexity is always measured relative to some model. For example, the $\Theta(n \log n)$ bound on sorting is the number of comparisons performed. If comparisons are not constant time, then the total number of operations will be higher.

Because of the high variability, and the overall time taken, often distributed algorithms are measured in terms of the number of messages sent. So in your example, you'd only solve it in $O(n^2)$ time if you assume that there is no cost to sending messages. If you're sending each possibility to a node, a good model will incorporate that cost, and you won't get magically fast solutions to $NP$-hard problems.

Also, for parallel computing, you model (approximately) how many nodes you have. It's a safe-bet to assume that you don't have more than $O(\log n)$ nodes for an input of size $n$. You certainly won't be able to scale your nodes exponentially, so brute-forcing doesn't always work.

Often, the computation done in distributed algorithms is minimal, or the computational content itself is intense, but orthogonal to the distributed nature of the algorithm (i.e. the algorithm is written over some abstract, computationally intensive task). In these cases, you usually only care about the messages sent or some other cost metric, since you might never know how many steps your computation takes.


What's the difference between the concatenation and union of symbols within a language

Simply put,

the kleene star of concatenation gives
$$(ab)^* = \{\epsilon, ab, abab, ababab, ...\} $$

while the kleene star of union gives
$$(a+b)^* =\{\epsilon,a,b,aa,ab,ba,bb,\ldots\}$$

so you got it correctly, and indeed all the words you write belong to the language.

Recall that for any two sets $L,K$ we have
$LK = \{xy \mid x\in L, y\in K\}$,
$L+K = L \cup K$,
$L^* = \{\epsilon\} \cup L \cup L^2 \cdots$.

and recall that the regular expression "a" corresponds to the set $\{a\}$ and operations between regular expressions correspond to the above operations on sets.


How to find the number of intervals containing a point when given a static set of intervals?

It is a very strong assumption that the time it takes to preprocess is not a concern.

Assume each given interval contains both of its endpoints. Otherwise, the solution below can be adapted easily.

Sort all $b_i$ and $r_i$ into an increasing sequence $A=(a_1, \cdots, a_{2n})$.

Let $c_1=1$. For $i$ from 2 to $2n-1$, let
$$c_{i}=\begin{cases}
c_{i-1}+1&\text{ if } a_{i}\text{ is a starting point of a given interval,}\\
c_{i-1}-1&\text{ if } a_{i}\text{ is an ending point of a given interval.}
\end{cases}$$
$c_i$ is the number of the given intervals that contain the open interval $(a_i, a_{i+1})$ for $1\le i\le 2n-1$. Let $C$ be the sequence $(c_1, \cdots, c_{2n-1})$. The combination of $A$ and $C$ is what we wanted from preprocessing.

Given any number $p$, if $p \gt a_1$ and  $p\lt a_{2n}$, we can find the largest index $i$ such that $p\ge a_{i}$ by binary search in $O(\log n)$ time. Then the number of given intervals that contain $p$ is given by
$$\begin{cases}
0&\text{ if } p<a_1,\\
1&\text{ if } p= a_1,\\
c_{i}&\text{ if } a_i<p\lt a_{i+1}\text{ or } p=a_i\text{ and } c_i>c_{i-1},\\
c_{i}+1&\text{ if } p=a_i\text{ and } c_i<c_{i-1},\\
1&\text{ if } p=a_{2n},\\
0&\text{ if } p>a_{2n},\\
\end{cases}$$
In other words, we can get the answer in $O(\log n)$ time once $A$ and $C$ are known.


How Intersection of Regular Language and a CFL is a CFL?

Every CFL language can be describes as a PDA. Every regular language can be described as a DFA.

The orthogonal product of a DFA and PDA can be defined as follows:

The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \in F_{DFA}$.

Given the transition of the PDA defined as $\delta_{PDA}(q_{PDA}, stack_{PDA}, a) = (q'_{PDA}, stack'_{PDA})$ and transition function of the DFA $\delta_{DFA}(q_{DFA})$

The transition function $\delta(q, a)$ for the new Automaton is where the transition function of the PDA is defined defined as $\delta((q_{PDA}, q_{DFA}), stack_{PDA}, a) = ((q'_{PDA}, \delta_{DFA}(q_{DFA})), stack'_{PDA})$

(in laymans terms, split out the states simulate the DFA and PDA independently and only accept the language when both are in a final state)

There is only 1 stack in this automaton. Thus it is a valid PDA. Therefor the language described by the intersection of a CFL and a regular language is a CFL.

The reason this does not hold for the intersection of 2 CFLs is because you need a second stack for second PDA.


Origin of using ">" to represent child in a tree

It comes from set theory. To see that these ideas were around before computers and that they were explicitly called trees consider the following famous tree. The convention set theorist sometimes use (some use use the convention you gave) is the opposite (the root $\hat{0}$ is the smallest, i.e. $\hat{0}<x$ for all $x\neq \hat{0}$, not the biggest ... this is keeping in line with the equivalence of the principle of induction and the well-ordering principle and is more natural ... i.e. a "zero-like" object is the root ... I will keep that convention so just replace all of the $<$ with $>$ in the proceeding discussion) The idea is the following:

  Theorem From any partial (well)-order we can construct a tree and from any tree we can construct a partial (well)-order.

Remark Partial (well)-order is a name I made up so as to artificially distinguish between trees and the relation I am about to define:

Let $P =  (V, E) =(V, \leq_E ) $ be a partial (well)-order then it satisfies the following

$(\forall x) \ x \leq x$
$(\forall x,y) \ x \leq y \implies y \leq x $
$(\forall x,y,z) \ x \leq y \land y \leq z \implies x \leq z $
$(\exists \hat{0} )(\forall x) \ \hat{0} \leq x$
$(\forall x) \ (\exists 0_{x} ) \ y \in \{ t \in V \ | \ t \leq x\} \implies  0_{x} \leq y $ ,

The first 3 state that $\leq$ is a partial order and the last states that the predecessor sets are well ordered.

(Proof of Partial implies Tree) Let $P =  (V, \leq_E ) $ be a well partial order then connect $v$ to $w$ if $w$ is the least element such that $v \leq w$, i.e. $ w = \min \{x \in V \ | \ v \leq x\}$ or $w$ covers v. It is easy to see that there are no cycles (because of rule 3) and that the graph is connected (there is always a path from $\hat{0}$ to any $v$ by induction because $\leq$ is a well order)

(Proof of Tree implies Partial) Let $x \leq y$ if there exists a path from $x$ to $y$, it is tedious but easy to see that all of the rules above are satisfied.

You may thinking, "man I didn't want an explanation involving set theory"

Let me help you dispel those heretical thoughts with the following observations

  Most of the famous early famous computer scientists got most of their
  techniques from set theory

The solution to the halting problem is an adaptation of a very beautiful proof by Georg Cantor that there are different sizes of infinity
Similarly so is the Entscheidungsproblem
Similarly, the proof that exponential time does not equal polynomial time
Von Neumann (Von-Neumann architecture) also came up with the Von-Neumann Universe of sets

This should come as no surprise set theory is concerned with the ontological status of the mathematical universe and the idea that all of the objects of our mathematical experience can be constructed via recursion ... and isn't that the big idea behind every algorithm/computer program ... some recursive construction ... trees are the simplest recursively constructed objects other than the natural numbers ... set theory is like a programming language for the platonic realm.

  We can take this whole idea further and prove that every set is a tree and every tree is a set (because of Von Neumann's axiom of regularity) but I will just leave you with the following: set data structures are tree data structures which hopefully will have you convinced of the truly inexorable relationship between the two.

I hope that I have whet your curiosity towards the beauty of sets. Good luck on your mathematical voyages! Bon Voyage!


What type of formal notation is being used here to represent functional algorithms?

The language is pretty-printed Haskell.

In regular source code, it would look like this:

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter (<= n) xs) (repeat True))
               where n = length xs

countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) -- Not actual code
as \\ (bs ++ cs) = (as \\ bs) \\ cs
(as \\ bs) \\ cs = (as \\ cs) \\ bs


first order logic resolution unification

Assuming $X$ here is a variable, rather than an atomic proposition, then first you must specify what is the quantification for 2 and 3. I assume that it should be

$\forall X,Y \neg p1(X)\vee p2(Y)$, and similarly for 3.
In this case, what can be done is to replace $X$ and $Y$ with each atomic proposition available, in order to obtain a propositional knowledge base, and work on that.

What you suggest to do with 2,3 is sound only under universal quantification, but if you have only universal quantification, it is useful indeed.

For your second question: the name of the variable means nothing, so your substitution is sound also there. Indeed, the claim $\forall Y, P(Y)$ is equivalent to $\forall Z, P(Z)$. You can first change the names, if it makes you happy :)

I'll remark that usually, in resolution-guided proofs, it is more useful to resolve a concrete expression with a quantified rule. For example, resolving $P(a)$ with $\forall X P(X)\to Q(X)$ in order to obtain $Q(a)$. This is more likely (heuristically) to get you towards the proof of a claim.


Proof that $P\subseteq NP$ without nondeterministic TM

The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$.
Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing machine, it follows that $\Pi \in \mathsf{NP}$, i.e., $\mathsf{P} \subseteq \mathsf{NP}$.
However $\mathsf{NP}$ can be equivalently defined as the set of decision problems $\Pi$ for which there exists a poly-time verifier (a Turing machine) $V$ and a polynomial $p$ such that if $x \in \{0,1\}^*$ is an instance of $\Pi$, then there exists a certificate $c \in \{0,1\}^*$ of length $|c| \le p(|x|)$ such that $V(x,c)$ accepts if and only if $x$ is a yes-instance for $\Pi$.
Using this definition every problem $\Pi \in \mathsf{P}$ is also in $\mathsf{NP}$, since it suffices to choose $p(|x|)=0$, $c(x)=\varepsilon$ (where $\varepsilon$ denotes the empty word), and $V(x, c)$ as the Turing machine that simulates any poly-time decider $T$ for $\Pi$ and accepts iff $T(x)$ accepts.


Left recursive grammars are not necessarily a bad thing. These grammars are easily parsed using a stack to keep track of the already parsed phrases, as it is the case in LR parser.

Recall that a left recursive rule of a CF grammar $G = (V,\Sigma,R,S)$  is of the form:

$\alpha \rightarrow \alpha \beta$

with $\alpha$ an element of $V$ and $\beta$ an element of $V \cup \Sigma$. (See the complete formal definition for the tuple $(V,\Sigma,R,S)$ there).

Usually, $\beta$ is actually a sequence of terminals and non terminals, and there is an other rule for $\alpha$ where $\alpha$ does not appear in the right hand side.

Whenever a new terminal is being received by the grammar parser (from the lexer), this terminal is pushed atop the stack: this operation is called a shift.

Each time the right hand side of a rule is matched by a group of  consecutive elements at the top of the stack, this group is replaced by a single element representing the phrase newly matched. This replacement is called a reduction.

With right recursive grammars, the stack may grow indefinitely until a reduction occurs, thus limiting rather dramatically the parsing possibilities. However, left recursive ones will let the compiler generate reductions earlier (in fact, as soon as possible). See the wikipedia entry for more information.


What are common techniques for reducing problems to each other?

The Special Case

Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity  function. The intuition behind this is clear: the general case is at least as hard as the special case.

In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.

Simple Example

Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.

Simple exercise problem

Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.

   3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.

Example

Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.

We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate

$\qquad \displaystyle f(A) = \begin{cases}
  \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\
  \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else}
\end{cases}$

where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.

Exercise Problem

Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

Show that LONGEST-PATH is NP-hard.

   HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
 Note in particular how reducing from HAMILTON-PATH requires more work.


Understanding the definition of Positivity Constraints in Coq

Take $l = k = 0$, the matrix of $b_{ij}$'s has size $0 \times 0$, hence we do not have to defined any $b_{ij}$, and take $g = \mathbf{nat}$.


How do you apply Context-Free Pumping Lemma to these problems, and how do the approaches differ?

Not all three languages are in fact non-context-free. Try to spot those that have a CF-grammar, and apply pumping to the remaining example(s). That is the difference you mean, I presume?

(added) The grammars you give in a comment seem correct to me. General hints for applying the pumping lemma are given in various answers at this site, see in particular How to prove that a language is not context-free?


Showing that a language is NP Complete (advice)

Typically, yes, it's a matter of finding a known NP-complete problem that's somehow similar to the one you're trying to work with. So if you're dealing with a problem about formulas, you probably want to reduce some version of SAT or 3SAT to it.

For graph problems, you probably want to reduce some other graph problem. Problems about long paths and cycles probably come from Hamiltonian path/cycle. Problems about classifying vertices into types sound like colouring problems. Problems about graphs containing or not containing some structure might come from clique or independent set. Problems about dividing graphs in two might be Max Cut, or Subset Sum.

Reductions from one type of problem to another are typically more difficult. If you ahve to do that, think about how you can use your target problem to encode things that are needed in the known NP-complete problem. For example, when you reduce 3SAT to independent set, being in or out of the independent set corresponds to being true or false; when you reduce 3SAT to 3-colourability, the three colours you use are "true", "false" and "er, the other colour".  But, in these cases, the reduction gadgets tend to be quite fiddly.

Another thing to bear in mind is that, if problem $A$ looks like problem $B$, which you already know to be NP-complete, it might be possible to modify that proof to make it work for $A$. For example, consider 4-colourability. The easy reduction is from 3-colourability: given a graph $G$, add a new vertex, connect that to everything and the new graph is 4-colourable if, and only if, the original graph was 3-colourable. But, if you didn't see that and you knew the reduction from 3SAT to 3-colourability well, it probably wouldn't be very hard to modify that reduction so the four colours were "true", "false", "er, the other colour" and "gee, there are a lot of colours today".


What exactly is a linear function, and what is a nonlinear function?

A linear function is a function of the form
$$
\ell(x_1,\ldots,x_d) = \sum_{i=1}^d a_i x_i + a_0,
$$
where sometimes the constant term isn't allowed.

A linear classifier is a classifier which is of the form "$\ell(x_1,\ldots,x_d) \geq 0$", where $\ell$ is linear.

Using the "kernel trick", you can masquerade non-linear classifiers as linear classifiers; SVM with a non-linear kernel is linear in that sense. In brief, we fix a mapping $\Phi\colon \mathbb R^d \to \mathbb R^D$ (where $D$ is possibly infinite), and then use a classifier of the form "$\ell(\Phi(\vec{x})) \geq 0$". The kernel trick is a way to evaluate the classifier (and train the model) without actually computing $\Phi$.


If there are $k$ distinct heights, you can sort in $O(n \log k)$ time using a heap or balanced binary tree.  Even better, you can sort with expected time $O(n + k \log k)$, if you use a hashtable.

This leads to a solution to your problem with the corresponding complexity.


Quantum computers and computable functions

You are correct, a quantum computer defined properly: with a finite gate set and rational (you can relax this to algorithmic, but that can be bit circular) transition probabilities will get you only the computable (by a classical Turing machine) functions. Although it might compute them faster than a classical computer.

To get a hyper-computer (something that computes functions that are not computable by a classical Turing machine), you need to sneak something that usually feels 'non-finitary' into the model -- the most common suspect is a non-computable real number -- which your model then extracts its power from. You can make these sort of models of computation from modifying classical or quantum systems. If I recall correctly, the first definitions of quantum TMs were actually accidentally hyper-computing because they allowed non-algorithmic phases in their operators.

To turn to your last question of "Does this mean it will never be computable?", what you are asking about is the Church-Turing thesis. It states, in its vaguest form, that anything that is computable is computable by a Turing Machine. Most people believe this thesis.

  Even if we change the axioms which our mathematical system is based on or we find a contradiction in it?

Here you are asking about Kleene's variant of the Church-Turing thesis. Since the CT-thesis cannot be 'proven' (we can always continue to disagree about the first 'computable' in the vague definition), we have to rely on mathematician's beliefs and philosophical discussion. Most mathematicians believe that in any reasonable axiomatic system, any 'finite-feeling' model of computation will be at most Turing-complete.

  Are we never be able to find something in the universe which can calculate these functions?

It is important to note that here you are asking a completely different (but related) question than the previos. You are asking about the physicalist variant of the Church-Turing thesis. Although historically this was not the preferred interpretation of the CT-thesis, from my experience it is now the most common way of reading the thesis. Again, here most computer scientists and physicists familiar with CS believe that all functions computable by machines in the physical world are Turing-computable.


Is there a general pattern/structure/format to most (if not all) computer functions?

A method is just a precise sequence of instructions (in the ordinary English-language sense of the word) of how to perform some specific task. It's certainly true that many tasks – and I mean this in a completely general sense, not just computer programs but things like recipes, travelling to work, repairing a bicycle, building a house – follow a general pattern of "get things ready, do the main part of the work, then tidy up." However, there's no reason that all tasks must follow this pattern, and certainly not at the level you suggest of looping, then doing conditionals, then returning something.  In general, methods do whatever it is that they need to do to accomplish the specific task at hand: ultimately, everything really is its own unique snowflake.

Having said that, we should note that we could, in principle, force everything to have a particular pattern. The CPU itself is essentially a loop of "read the next instruction, obey that instruction" where a particular effect of obeying an instruction might be to change what the "next instruction" will be – that would be a jump or goto. So, in principle, we could write every program in this style. However, people find this kind of program extremely difficult to write, understand and debug so, in practice, we use higher-level languages, and use compilers and/or interpreters to translate them into terms that the CPU understands.


What is the time complexity of a linear search performed using 2 pointers?

$O(n)$, since you still will go through the entire array.
And yes, this is a linear search since $O(n)$ is linear.


Your protocol is not very clear. What do you mean at step 3 by "it chooses one variable, re-computes the formula"?

I assume the verifier just sets that variable to 1 and re-computes the formula without that variable.

Then, this protocol still has some problems. Let's say that there are two sets of variables that satisfy the formula: $\{x\}$ and $\{y,z\}$. The minSat is $x$.
But what happens if the prover says it is $y,z$?
the verifier checks this proposed set, and  sees that the set satisfies the formula; then the verifier removes one variable, say $y$, and sends the formula back to the prover. The prover will then reply with $\{z\}$ and the verifier will accept it.

Even if the verifier renames the variables in a random way, (say, replace $x$ with $a$ and $z$ with $b$), it's not clear that this protocol works.
Still, maybe the prover is able to identify the variable that previously was $z$ from the structure of the formula, and repeat the faulty behaviour described above.

So although in the suggested protocol the prover cannot reply with a set that doesn't satisfy the formula, the prover can give a non-minimal set, and the verifier will (wrongly) accept it.


Circuits vs Turing Machines in the "nonuniform model of computation"

You can think of Turing machines as a finite description of a function whose domain is $\mathbb{N}$. When you want to specify a different behavior for each member in a collection of finite sets which covers the entire domain, Turing machines are not the natural object to discuss.

You could obviously talk about a sequence of machines $M_n$, where $M_i$ knows how to handle strings of length $i$, and you don't care about how it behaves on different strings (such a definition of nonuniform classes would be equivalent). However, in this case, you don't really use the power of Turing machines. What you care about is only $M_k|_{\{0,1\}^k}$, which is completely determined by a computation table of size $T_k\times T_k$ where $T_k$ is the maximal running time of $M_k$ on length $k$ inputs. This table corresponds to a circuit of size $\le T_k^2$ (this can be improved), which now becomes the more natural object to discuss.


Number of words in the regular language $(00)^*$

For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is

$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$

which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.


Internal tangent intersection of two point sets in linear time

I found a way to solve the problem in my case -- maybe that only applies to the special conditions found in the paper. There, the two point sets can be assumed to be non-collinear and always separable by a line parallel to one of the coordinate axes, and we always know that $A$ is "left of" (or "above") $B$.

In this case, we can represent a line simply by $y = kx + d$, and get one internal tangent by minimizing the function $F(k, d) = k$ subject to
$$
\forall v \in A: v_y \leq k  v_x + d\\
\forall v \in B: v_y \geq k  v_x + d.
$$
The other one can  be found by swapping $A$ and $B$ (or the relations) and maximizing.


The problem is equivalent to deciding whether the complement graph of $G$ has a bipartition $(A,B)$ such that $|A|=|B|$. In order to check if such a bipartition exists, one can first compute an arbitrary bipartition $(A,B)$. If no such bipartition exists, we are finished. If it does exists, we must check whether we can flip single connected components of this bipartition (which mean all vertices in $A$ of a particular connected component are moved to $B$ and vice versa) such that we obtain a new partition where $A$ is equal to $B$. Using a dynamic programing approach similar to the partition problem, this can be decided in polynomial time. Thus the original problem is also in P and not NP-hard unless P equals NP.


With a grammar, does precedence and associativity change the accepted language?

Precedence and associativity declarations are common in parser generators, but they are not part of the theory of context-free grammars. And nor are they part of the working of the LL(k) parsing algorithms (or, for that matter, the LR(k) algorithms).  So there is no real way to answer that question in terms of the theory of formal languages.

On a practical level, you could perhaps look at popular parser generators and ask if the precedence and associativity declarations can alter the language recognised by the generated parser. In most cases, the answer will be "yes", but it depends considerably on how the precedence declarations are used to modify the generated parser.

I don't know enough about LL parser generators to answer that question for any of them, but it's quite clear precedence declarations for Yacc-based parser generators which use the mechanism described in the Dragon book can affect the set of recognised sentences. First, most such precedence declarations include the "nonassoc" declaration, which specifies that a particular operator cannot be used in a way which might require associativity. For example, a language in which a < b < c is illegal might declare < to be nonassociative, thereby removing the illegal construct from the language.

But even without "nonassoc", there are certainly cases in which forcing a reduction in a particular context can eliminate valid sentences. If, for example, you invert the precedence order used to resolve the "dangling else" ambiguity, you will make it impossible for the parser to recognize conditionals with "else" clauses.


Running time of sparse matrix multiplication

The question doesn't make any sense. It doesn't make sense to ask for the running time of a computation, unless you specify an algorithm for that computation. So how would you calculate this product? That's the first thing you need to do: Specify an algorithm how you calculate the product.

The next step: Assuming that many array elements are zero, can you reduce the amount of work that this algorithm would be doing? For example, if you know that x = 0, then it's pointless to multiply xy because you know the result is 0. And it's pointless to add xy to z, because that doesn't change z. So how can you take advantage of many array elements being zero? What's the runtime if you do that?

The next step: Assuming that many array elements are zero, can you reduct the amount of work further? Would you need some clever data structures? If yes, which ones?


What is the equation for a spiral path in 3D?

I have just found this correct answer on the web (by someone else):

A helix is a circle that moves up with time.  Hence, the equations for one helix are:

x(t) = sin t

y(t) = cos t

z(t) = t

A double helix include two helices that are offset by half a turn.  So, the equations for the second helix would then be :

x(t) = sin t

y(t) = cos t

z(t) = t + \pi


Proving that two sets of strings are equal

It is not totally clear what are your main obstacles to get the proof done.

Note that $L_{i,j}^k$ is the set of all strings $w$ on a path $\pi$ from $q_i$ to $q_j$ such that for each intermediate state $q_x$ we have $x\le k$; i.e., all intermediate states have index at most $k$.

Consider state $q_k$.
Now either the path $\pi$ does not enter $q_k$ at all: then all indices are at most $k-1$ meaning that $w$ belongs to $L_{i,j}^{k-1}$. Or it may enter $q_k$ one or more times. Thus the path is of the form $\pi: q_i \leadsto q_k \leadsto \dots \leadsto q_k \leadsto q_j$, where the subpaths may start and end in $q_k$, but do not pass that state. So the string $w$ can be partitioned into strings that belong to $L_{i,k}^{k-1}$, $L_{k,k}^{k-1}$, ..., $L_{k,k}^{k-1}$, $L_{k,j}^{k-1}$.

That should prove that $L_{i,j}^{k} = L_{i,k}^{k-1} ( L_{k,k}^{k-1} )^*L_{k,j}^{k-1} \cup L_{i,j}^{k-1}$ (or at least the inclusion from left to right, the other inclusion follows similar argumentation).

With this knowledge the induction is on the subscript $k$, and the induction step is

If $L_{i,j}^{k-1} = M_{i,j}^{k-1}$ for all $i,j$ then $L_{i,j}^{k} = M_{i,j}^{k}$ for all $i,j$.

This should be obvious, just plug in the equations we have.


If you see your position from left=0 to right=length(pipe), you can simply cover your holes from left to right.

When adding a new tube, put the leftmost remaining hole at the leftmost covered position by the tube. Then you cannot waste tube.

For instance with radius 2, a tube centered on pos k covers [k-2, k+2]. Then a tube with leftmost on k covers [k, k+4].

With holes at {2, 4, 5, 7, 9, 11}:
- first hole at 2 => first tube at [2, 6] centered on 4
- next hole at 7 => next tube at [7, 11] centered on 9


Using the property $X+YZ = (X+Y)(X+Z)$, you can silmplify $C' + B'CD$ as $C' + B'D$.


Techniques to create a PDA for a language that is the conjunction of two languages

The intersection of a CFL and a regular language is itself a CFL.  There is a standard construction for computing this intersection.  It's documented in automata theory textbooks; look in your favorite automata theory textbook, and you should find it there.


Which optimization algorithm would you recommend for this small multidimensional problem?

This problem is effectively knapsack, where the size of the knapsack is $L_{max}$. The items are $1,\ldots,n$, and for each item $i$ we can select a quantity (to include in our knapsack) of $j\in\{2,\ldots,M_n\}$. Taking quantity $j$ of item $i$ gives reward $p_{j,i}$ and takes up $l_{j,i}$ space in the knapsack.

Let $D(n,r)$ be $max_s \sum_{i=1}^{n} p_{s_i,i}$ under the constraint that $\sum_{i=1}^{n} l_{j,i} \leq r$. $D(N,L_{max})$ (which is the value you're after) can be computed in $O(L_{max}\cdot NM)$ time (where $M$ is $max_i M_i$) using dynamic programming.

Effectively $D(n,r)$ represents the best way (mean probability) to represent the first $n$ words using at most $r$ space. The best way to represent $D(n,r)$ is to combine some choice of representing word $n$ with the best way to represent the remaining $n-1$ words in however many characters are left. This is expressed by the recurrence relation:

$$D(n,r)=max_{s_n\in\{2,\ldots,M_n\}} p_{s_n,n} + D(n-1,r-l_{s_n,n})$$

Where $D(*,r)=-\infty$ if $r<0$ and $D(0,*)=0$.

What is very important is that you store (and reuse) the intermediate values of $D(n,r)$ during the computation, as this will save significantly on computation time. Reusing these values will also allow you to deal with the growing input requirement, since the values encountered when computing $D(n,*)$ can be reused when computing $D(n+1,*)$.


You are right: it is easy to miss corner cases, so whatever you choose to define, you will need to prove that you defined the right thing.

To do so, you need to first define what you actually want, i.e., the language of $\overline{M}$.

From what I can tell, you want
$$\mathcal{L}(\overline M) = \{ (w^I_0 ,w^O_0) (w^I_1 ,w^O_1) \ldots \in (\Sigma \times \Omega)^\omega \mid (w^I_0,w^O_0) (w^I_1 ,w^O_1) \ldots \not\in \mathcal{L}(M)\}$$

If you just just invert the set of possible outputs along an edge, then get an automaton $\overline M$ for which you can then try to prove that it has the right language, i.e., that (1) every word accepted by the automaton is in the language that we defined for it, and (2) vice versa.

Because this seems to be connected to your research, I will not give you the answer whether such a proof works (as I don't want you to force to give non-citation credit to the work of others, which you would need to do if someone else gives you a solution), but rather let you try this out on your own.

Should this approach not work, here is an idea that allows you to cover all corner cases:

Translate the Mealy automaton to a DFA (deterministic automaton over finite words) that
accepts all prefix traces of the Mealy automaton's language
Complement the DFA
Conjunct the DFA with with a DFA accepting all words from $(\Sigma \times \Omega)^*$.
The resulting automaton accepts the words that you want your Mealy automaton to have. So define a suitable translation to a non-deterministic Mealy automaton.

The idea here is the complementation part is done by a well-known and known-to-work algorithm, so you avoid parts of your problem. The last step is still non-trivial, but probably easier than before.


Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition

If all of $D$ divide $P$, then $P$ is also multiple of $\gcd(D)$.
Any sum like $S$ is a multiple of $\gcd(D)$ too, so you can divide everything by $\gcd(D)$ and consider just the case where the $D_i$ are relatively prime. For definiteness, take $D$ sorted in increasing order.
In that case you have just:

$\begin{equation*}
  P
    = c \cdot \prod_{1 \le k \le n} D_k
\end{equation*}$

For the Frobenius problem sums like $S$ with non-negative $C_i$ can represent all numbers greater than a function $g(D)$, and it can be shown that $g(D) < D_n^2$ (computing the exact value of $g(D)$ is NP-complete). So, if $P > D_n^2$ (the other $D_k$ would have to be small indeed for this to be false), any number $S \ge P$ can be represented, and also any number $S - D_i$, pick say $S = P + 1$ to satisfy your condition.

To get a set of $C_i$, you can now use the greedy algorithm: Take $C_n = \lfloor S / D_n \rfloor$ (as large as possible), $S \leftarrow S - C_n D_n$, and repeat for the next largest.


Best data structure for high dimensional nearest neighbor search

Here is a closely related question (although different enough that I wouldn't call this a duplicate): https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data

As you said, all known structures degrade to linear search as the dimension grows. More specifically, the efficiency degrades as the dimension approached the number of points in the feature space (binary search doesn't help with two points, K-D trees are useless on three points, etc.).

However, if the time to create the data structure does not matter at all, you can create a complete graph with sorted edge lists. That is, every node keeps track of its neighbors in nearness order. This would take $O(n^2 \log n)$ time to create, but would give you the kNN of any point in $O(1)$.


Find member of CFL that is Levenshtein-closest to non-member string

Yes.  This can be done, using Levenshtein automata.

Let $S_k = \{y \in \{0,1\}^* : d(x,y) \le k)\}$.  Then the set $S_k$ is regular, and one can construct a finite-state automaton for it, called a Levenshtein automaton.  Now the intersection of a CFL and a regular language is another CFL.  Also, given a CFL, you can efficiently determine whether it is non-empty or not, and if not, you can efficiently find an example of an element of it.

So, we obtain the following simple algorithm:

For $k:= 1,2,3,\dots$, do:

If $L \cap S_k$ is non-empty, find $y \in L \cap S_k$ and output it.

This can be sped up by using binary search to find the smallest $k$ such that $L \cap S_k$ is non-empty.

The same approach can handle your proposed restrictions as well, as those simply amount to intersecting with another regular language.  It also works if $L$ is regular, as any regular language is necessarily context-free.


How can I find this code block's execution time t(n) and big O notation?

fact(n) runs at $O(n)$.
So, each iteration of funcQ2 runs at $O(i)$, assuming log runs at constant time.
(There are several algorithms to calculate the log)
Then the question turns into calculating $\sum_{i=1}^n O(i)$, and the answer is $O(n^2)$.
Now suppose your log(n) runs at time $O(f(n))$.
Then the answer to your question should be $\sum_{i=1}^n O(f(i))$.
You should calculate that on your own as I don't know the $f$.


Minimum cost circulation problem with bounded number of edges

After I posted the question in cstheory, I received an answer there.

  Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.