Dijkstra complexity analysis using adjacency list and priority queue? I just got to look at the Implementation of Dijkstra using adjacency list and priority queue. The time complexity is $O(E\log V +V)$, I tried looking for the proof but couldn't find one. Any help will be appreciated.

Dijkstra's algorithm visits every node once ($=O(V)$), and tries to relax all adjecent nodes via the edges. Therefore it iterates over each edge exactly twice ($=O(E)$), each time accessing the priority queue up to two times in $O(\log V)$.

Therefore the complexity is $O(E \log V + V)$.

For a proof of the correctness, just look it up at any basic algorithms book, like CLRS.


Number of "hamiltonian tours" from upper left to lower left corner of a grid graph? I got the following as an interview question:

Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction.  This is the number of Hamiltonian paths from upper left to lower left: a path such that every vertex is visited only once, and (this follows from the first statement) such that each edge is used at most once.

The grid world is a 4x10 matrix (4 rows and 10 columns).

Is it really this hard?

Matrix method for counting Hamiltonian cycles

And:

Number of Hamiltonian Paths from Lower Left to Upper Right

These papers seem dated--94, 97--but are they really asking a question that qualifies for publishing in a combinatorical journal?

Then I ran into this:
SO question: number of Hamiltonian paths

And am thinking dynamic programming, or divide and conquer...but it is really not clear how one would go about doing this. Is there a way to solve this problem in reasonable time?

I think a divide and conquer strategy is going to work here. The asymptotic runtime isn't great, but fortunately our graph is of fixed size. Pick some arbitrary node, $v$, and partition the rest of the nodes into two sets. The number of hamiltonian tours is the number of paths that start at the upper left, go through all nodes in the first side of the partition and end at $v$ multiplied by the number of paths that start at $v$, go through every node in the second half and end at the bottom left corner summed over every possible such partition. Recursively do this for each partition.


What is the complexity of recurrence $T(n) = T(n-1) + 1/n$ What is the complexity of the follwoing recurrence? $$T(n) = T(n-1) + 1/n$$

I highly suspect the answer to be $O(1)$, because your work reduces by $1$ each time, so by the $n$th time it would be $T(n-n) = T(0)$ and your initial task reduces to 0.

By unfolding $$T(n) = T(n-1) + \frac{1}{n} = T(n-2) + \frac{1}{n} + \frac{1}{n-1} = \dots=T(0) + \sum_{k=1}^{n} \frac{1}{k}$$
Now we can easily approximate the sum on the RHS using that
$$\sum_{k=1}^{n}\frac{1}{k} \le 1 + \int_{1}^{n}\frac{1}{x} dx = 1+ \log{n} - \log{1} = 1+ \log{n}$$
Therefore $T(n) \equiv O(\log{n})$


Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=\infty$ with preserving polynomially-same accepting times? I know that for every $k$-tape DTM that runs in time $O(t(n))$, there exists a 1-tape DTM that runs in $O(t^2(n))$, no matter how large the $k$ (the $k$-part is a formulation from Wikipedia). But what if $k=\infty$?

If I understand it right, if $k=\infty$, then the alphabet of the $\infty$-tape DTM is infinite and therefore the transition function will be infinite as well. That is why it is not NTM by definition, however it should be much more powerful than a DTM (based on the argument that we can encode a countable infinitely long input into one symbol of countable infinitely large alphabet).

So, is it known if a NTM can be simulated by $\infty$-tape DTM (with preserving polynomially-same accepting times)?

This is a very nice question, which rises often in computability courses.

Once you allow infinitely many tapes, with infinitely many read/write heads, then the model becomes way too powerful. Formally, consider any language $L\subseteq \Sigma^*$, here is an algorithm in your model that decides $L$ deterministically, and in linear time:

Scan the input tape, and write every letter on a new tape, move to state $q$.
We define the transition function as $\delta(q,w)=q_{acc}$ if $w\in L$, and $\delta(q,w)=q_{rej}$ otherwise.

By $\delta(q,w)$ we mean that the state is $q$, and the letters that are read by the infinite number of heads form the word $w$.

As you can see, we decide $L$ "by definition", and this definition is legitimate, since the transition table is infinite.

So your model can decide every language, which means that it provides no differentiation of language classes. So theoretically, we just showed that it's "not interesting".


Can Von Neumann bit extraction be made more efficient? I want to develop a previous question regarding Von Neumann debiasing /randomness extraction.

The typical solution (as posted) is to take pairs of throws and output a bit based on a comparison of the two throws.  This is the most simple solution.

My problem is that it's very wasteful of input entropy.  The biased die can have values 1 - 6, but only a single bit is output.  So 2 x log2(6) bits in, produce 1 bit out.  It's actually less as the throws may be discarded if identical.  What happens if the die is a D & D D120 (Disdyakis triacontahedron - 120 sides)?  You'd be inputting 13.8 bits of entropy, and getting (practically) less than 1.  That's incredibly wasteful of precious entropy.  Is there a clever variant of Von Neumann that can output more than a single bit at a time?

My particular interest is actually not a bigger die, but more of them.  For example you simultaneously throw 6 biased regular dice.  Can you get better than 1 purely random bit out per pair of throwing rounds?

Suppose you are going to throw a 6-sided die N times.  You can convert that to an integer in the range $[0,6^N-1]$, by viewing the sequence of N outcomes as a base-6 representation of an integer.  This gives you a random number chosenly uniformly at random from $[0,6^N-1]$.

Now pick a value of $k$ such that $2^k < 6^N$.  Let $Y = \lfloor 6^N/2^k \rfloor \times 2^k$.  You can now use the following algorithm to output a $k$-bit number (much of the time):

Generate a random number from the range $[0,6^N-1]$ by tossing a 6-sided die $N$ times.  Suppose the number you get is $x$.  If $x < Y$, then output the value $x \bmod 2^k$ (which can be viewed as $k$ bits).  Otherwise, output nothing -- you will have to re-roll.

This produces a uniform random distribution on $k$-bit values.  It produces output on any given attempt with probability $Y/6^N$; on average, the expected number of times you'll have to repeat this procedure is $6^N/Y$, which is a bit more than $1$ (but not much more than $1$, as long as you're not too greedy and don't pick $k$ too large).

It's possible to do a bit better, by saving information about the value of $x-Y$ when you repeat the process, but this might not make a big difference in practice.

See also Generating uniformly distributed random numbers using a coin and Is rejection sampling the only way to get a truly uniform distribution of random numbers? and How to simulate a die given a fair coin and Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator.


What does an input string of epsilon mean? I am currently reading Introduction to the Theory of Computation (Sipser), and after introducing epsilon labeled transition arrows, the book shows the following NFA:

I was following it until I read the following :

Practice with it to satisfy yourself that it accepts the strings ϵ, a, baba and baa...

What does an input string of ϵ mean?

In the context of NFAs, $\epsilon$ marks state transitions that do not consume input. These transitions thus express the non-determinism of the automaton.

When discussing the acceptance of $\epsilon$, the symbol marks the empty string (this is equivalent to the condition that an accepting state is reachable by a sequence of $\epsilon$-transitions from the start state). to avoid confusion, some authors use a different symbol for the empty string (often $\lambda$).


Need to understand signals received vs sent What is meant by in the following statement (from the paper titled "Implementing Lightweight Threads"):

  As in singlethreaded processes, the number of signals received by the
  process is less than or equal to the number sent.

Why is the number received less than or equal to the number sent. I don't have enough background in singlethreaded processes I guess.

Suppose I sent you 10 letters. Then the number of letters that you have received is at most 10 (some might still be en route).

The reason that this is stressed is that some of the signals could potentially be received by several threads. The operating system guarantees that each signal is received by at most one thread, chosen arbitrarily among threads which have not masked the signal.


What is the theory behind testing fixes for intermittent bugs? I ask this question because I deal with alot of intermittent bugs and want to be able to answer the question "Can I be at least 95% sure that my changes to the code fix the bug?".  I've got some ideas on how one could formalize the problem, but I'm guessing that someone else has done this.

I'm particularly interested in theory where we do NOT already know a value of $p$ - the probability that a bug will hit.  This means we'll likely have to assume some distribution on $p$.

It seems like this should be a known thing, especially within TDD.  Some problems are just so hard that we have to rely on testing results.  Thanks for any direction you can give me.

You juggle with "probabilities" without defining any. There are two different questions here.

  For practical programs, can I use random testing to establish that any given execution has close to 100% success probability?

Not in the strict sense, no. Even if input spaces are finite, they are typically huge. Without further information, you'd have to test a lot of inputs (and/or contexts), which is not feasible. As in, solving most NP-complete problems is faster.

You could try to perform statistical testing, that is get some bound on the error for some statistical significance -- but that would assume that you have a model for the error distribution. Which I would be surprised to hear if you had. And even if, it's probably not one of those that mathematicians have bothered to explore. So, ballpark guess, statistical tests are impossible (or meaningless, if you went ahead and did the numbers assuming a normal model or something).

  Can I formalize programs and their execution so that I can make meaningful statements about (stochastic) bug-freeness?

Yes, sure. What you need are

formal semantics,
formal specifications, and
a distribution of inputs.

Then, you can (in principle) prove (not test!) what the expected error rate is. I've never seen it done, though -- probably because it's at least as hard as proving the program correct in the first place.

If you ask me, you are better served with reasonable heuristics and solid processes. Specification testing may be helpful in certain contexts, just because it makes it easy to test many different variants.


How does Paxos maintain the promise that future proposal will not break the current chosen value without knowing the future? I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was trying to understand page 4, specifically, the following paragraph:

"To maintain the invariance of $P2^c$, a proposer that wants to issue a proposal
numbered n must learn the highest-numbered proposal with number
less than n, if any, that has been or will be accepted by each acceptor in
some majority of acceptors. Learning about proposals already accepted is
easy enough; predicting future acceptances is hard. Instead of trying to predict
the future, the proposer controls it by extracting a promise that there
won’t be any such acceptances. In other words, the proposer requests that
the acceptors not accept any more proposals numbered less than n. This
leads to the following algorithm for issuing proposals."

Where condition $P2c$ is:

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

I was specifically confused about the section I have in bold. I was confused why, if we want to develop some hypothetical consensus distributed algorithm, why do we need to know about higher sequence numbers that have not happened? What is the intuition behind that?

Sorry if my title is a little strange, I was not sure what was a good title for the question.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

The bold section is saying that before proposing a value know if a value is accepted or if there is a higher proposal number that is chosen by one of the majority. If there is a higher proposal number, the proposer needs to propose a higher number than that is already proposed. If a value is already accepted then majority should know if a value is accepted. The proposer accepts the value. The majority is because two majorities always overlap.


Exact Value of Denormalised number related to floating point numbers I faced with the following issue:
if the value of a floating point format number is in the range of underflow,
it must be 0 or a denormal number.If the value is not 0 than what is the exact value of it?Is it conventional constant value or depend on different architectures?
I am sorry but could not understand through wiki's article

Some -- not all but the most common one are -- binary floating point representations are using a trick to get one more bit of precision.  First, let's define the normal representation for non-null floating point values as the representation where the exponent is chosen so that the most significant bit of the value is the most significant bit of the value is the most significant bit of the significand (also known as mantissa).  The trick is to notice that when the normal representation is used, the most significant bit of the significand is always set for non null values, and thus those format mandate the representation to be normalized so that they can avoid to represent it in the format.

This has two undesirable characteristics.

Some values which would have been representable if normalization was not mandated are now no more representable as normalization would implies a non representable exponent.
The difference between 0 and the first representable value is bigger than the difference between the next representable value and the first.

Some formats (again not all but the most common one are) are trying to avoid those properties by allowing non-normalized values if normalization is not possible.  Those are called denormal or subnormal.

So when a computation result in a number which is smaller (in absolute value) to the smallest normal representation -- also known as underflow --, the main choices are:

use as result a denormal if the representation allow it and the number is not smaller than the smallest denormal
use zero as result

Note that some other possibilities exist:

use as result a NaN marking the result as underflow
generate an exception or an interrupt of some sort
set a sticky bit somewhere meaning that an underflow has been met in addition to returning one value of some kind.

Underflow are usually considered as too common for those other possibilities, excepted the last one, to be considered as useful for most code.


Can this Arrow-Ring puzzle be encoded as an integer programming problem? I would like to write a solver for these kind of Arrow-Ring puzzles.  However, I can't encode all the constraints correctly.

I noticed that Sudoku can be solved using integer programming and I am hoping it can be done for this kind of puzzle as well.  Let's take a look at the rules:

  Draw a line to make a single loop.
  Lines pass through the centers of cells, horizontally, vertically, or turning.
  The loop never crosses itself, branches off, or goes through the same cell twice.
  The numbers show how many black cells there are in the direction of the arrow.
  The loop does not pass through the black cells or the cells with numbers, and black cells cannot touch horizontally or vertically.

The first constrant seem the most difficult, that we should require a single closed loop.  And I wonder if integer programming is even the best way to solve these, but it's a start.

The third constraint (with numerical hints) is the most clear and for simplicity, they could also be replaced by black squares.  However, if you already know how to encode these as integer programming problems, go for it.

Lastly, are there other algorithms that are efficient for finding loops in graphs with constrants?  Wikipedia suggests this could be a Hamiltonian Path or an SAT problem.

You can encode this problem using a SMT solver like z3, which translates it to a SAT instance.

Let each $c_{x, y}$ be a free variable for a cell that isn't an arrow. A cell can be one of the following (encode them as integer states or as one-hot states).

Black.
Horizontal.
Vertical.
Top-right turn.
Right-bottom turn.
Bottom-left turn.
Left-top turn.

If you can find an assignment of the above for each $c_{x, y}$ variable, you've found a solution.

Obviously we still need to encode all requirements. First introduce four helper variables for each $c_{x, y}$ to see if it is connected to its top/left/bottom/right neighbour. This is a bit laborious, but it comes down to logic statements such as "I'm vertical and bottom neighbour is either vertical, top-right turn or left-top turn".

Introduce a requirement that each cell $c_{x, y}$ must be connected to at least one neighbour.

Introduce a requirement for each arrow block to say that the number of cells equal to black in the direction it's pointing in must match its number.

Introduce a requirement that no two adjacent $c_{x,y}$ are black.

With all these requirements you know that each free cell is either black, or part of a connected loop. The final struggle is to ensure that there is a single connected loop. This can be done by assigning a single free variable to denote a leader cell, and then using the previous established connections to ensure that each cell is either black or the leader cell, or connected to the leader cell, or connected to a cell connected to the leader cell.

All in all this is quite a tricky and laborious translation into an SMT solver. If you intend to implement this I strongly suggest reading through some example problems from this excellent z3 guide. It has a ton of translations of various problems into a format a SMT solver can understand.


How can I compress data that represents a number's change over time? I have a value that increases by unknown increments at unknown times.  Given a time, I need to check how much it has increased between that time and now.

I could simply store every time/increase pair whenever the value is increased, but this would be too much data to reasonably store.

For example:

DATA:
Value = 0 @ 0:00
Value = 2 @ 0:04
Value = 7 @ 0:05
Value = 52 @ 0:07 (Current time)

RESULT:
1 Second: 52
3 Seconds:  2 + 7 + 52 = 61

I am not sure what I am trying to do is even possible.  But, is there a way I can store the increments such that I can keep the file size reasonably small, and still find a decent approximation of the increase in the value?  It does not need to be exact - a margin of error less than 5% would be acceptable.

In the case of storage and querying from the storage i.e. if you can first get all time:value pairs, you can use curve fitting (regression) to get the polynomial function v=f(t), where v = value and t = time which will not be accurate, may even be outside 5% error margin; but would the  get the work done in a very low file size and acceptable(?) margin of error.


When do the gradients exist in a Reinforcement Learning setting? I am getting properly stuck into reinforcement learning and I am currently reading the review paper by Kober et al. (2013).

And there is one constant feature that I cannot get my head around, but which is mentioned a lot, not just in this paper, but others too; namely the existence of gradients.

In section 2.2.2. they say:

  The approach is very straightforward and even applicable to policies
  that are not differentiable.

w.r.t. to finite difference gradients.

What does it mean to say that the gradients exist and indeed, how do we know that they exist? When wouldn't they exist?

The gradient doesn't exist / isn't well-defined for non-differentiable functions.  What they mean by that statement is that there is an analogous version of gradients that can be used, instead of the gradient.

Discrete functions

In the discrete case, finite differences are the discrete version of derivatives.  The derivative of a single-variable continuous function $f:\mathbb{R} \to \mathbb{R}$ is $df/dx$; the partial difference (a discrete derivative) of a single-variable discrete function $g:\mathbb{Z} \to \mathbb{Z}$ is $\Delta f : \mathbb{Z} \to \mathbb{Z}$ given by

$$\Delta f(x) = f(x+1)-f(x).$$

There's a similar thing that's analogous to a gradient.  If we have a function $f(x,y)$ of two variables, the gradient consists of partial derivatives $\partial f / \partial x$ and $\partial f / \partial y$.  In the discrete case $g(x,y)$, we have partial differences $\Delta_x f$ and $\Delta_y f$, where

$$\Delta_x f(x,y) = f(x+1,y) - f(x)$$

and similarly for $\Delta_y f$.

Continuous functions

If you have a continuous function that is not differentiable at some points (so the gradient does not exist), sometimes you can use the subgradient in lieu of the gradient.


What does it mean when a time complexity has another time complexity within it? Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression.

For instance, "the best fixed-parameter tractable algorithm for the vertex cover problem has a time complexity of $O(1.2738^{k} \cdot n^{O(1)})$."

What does this $O(1)$ expression mean? Can I just replace it with any constant and the time complexity will still hold?

This is somewhat informal, and to figure out what it means, just parse it inside-out:

$f(n)$ is $O(1)$ means, as usual "$\exists c, n_0: f(n) \leq c$ whenever $n \geq n_0$".
$f(n)$ is $n^{O(1)}$ is meant to mean "$f(n)$ is of the form $n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c, n_0: f(n) \leq n^c$ whenever $n \geq n_0$.
$f(n)$ is $O(2^k \cdot n^{O(1)})$ means "$\exists c, n_0: f(n) \leq c\cdot 2^k\cdot n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c_1, c_2, n_0: f(n) \leq c_1 \cdot 2^k\cdot n^{c_2}$ whenever $n > n_0$.

Note that you cannot simply replace the internal $O(1)$ with any fixed constant. You know that a suitable constant does exist, but its value is left unspecified.


Is there a software algorithm that can generate a non-deterministic chaos pattern? Is there a software algorithm can generate a non-deterministic pattern or sequence? In Chaos theory, simple processes can create deterministic patterns, and psudo-random number generators can generate deterministic numbers with the same seed. Is there a software algorithm that can create completely non-deterministic patterns or sequences? Does it require hardware such as a quantum random number generator?

No deterministic algorithm can generate a non-deterministic output.

A non-deterministic algorithm (e.g., a NDFA) could, but they exist only in theory, not in practice.

An algorithm with access to a random number generator can generate a random output, and therefore its output is not deterministic.  For instance, in practice by reading from /dev/urandom or CryptGenRandom(), you can get random bits, which can be used to produce random output, or to seed a pseudorandom number generator.  (You don't need a quantum random number generator to get random numbers.)

Chaos theory is pretty much irrelevant here.


How to apply a Hadamard gate to one qubit in a 2-qubit system? Edit:

I've pinpointed that the difference between solutions occurs when I apply the $H$, up to there, the solutions match. So, perhaps it is better to phrase my question as: how to apply an $H$ gate to one qubit in a 2-qubit system?

End Edit

I have the following quantum circuit, and I need to calculate the values of the two qubits afterwards.

Now I know the values are:

$\lvert \psi_1 \rangle = \frac{1}{\sqrt{2}}(\lvert 0 \rangle+\lvert 1 \rangle)$
$\lvert \psi_2 \rangle = \lvert 0 \rangle$

It's pretty simple to see, and I checked them with a simulator just to be sure.

The trouble I'm getting into is when I try to express this as a two qubit system.

As I understand it should be as follows:

$$\lvert \psi\prime \rangle=M\lvert \psi \rangle=\frac{1}{\sqrt{2}}(\lvert 00 \rangle+\lvert 10 \rangle)$$

Where $\lvert \psi\prime \rangle$ is the state after the circuit is complete, $\lvert \psi \rangle = \lvert 00 \rangle$ is the initial state, and $M$ is the matrix representing the combined effect of all the gates of the circuit.

Now, I calculate $M$ as follows:

$$M=\frac{1}{\sqrt{2}}(I\otimes X)\begin{bmatrix}I&0\\0&X\end{bmatrix}(I\otimes X)(H\otimes I)$$

I wrote the $CNOT$ matrix in block matrix form here, and extracted the $\frac{1}{\sqrt{2}}$ from $H$ to the beginning.

$$\begin{align}M&=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}X&0\\0&I\end{bmatrix}\begin{bmatrix}X&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&0\\0&X\end{bmatrix}\begin{bmatrix}I&I\\I&-I\end{bmatrix} \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\end{align}$$

Now, plugging $M$ back into the first equation...

$$\begin{align}\lvert\psi\prime\rangle &=\frac{1}{\sqrt{2}}\begin{bmatrix}I&I\\X&-X\end{bmatrix}\lvert\psi\rangle \\ &=\frac{1}{\sqrt{2}}\begin{bmatrix}1&0&1&0\\0&1&0&1\\0&1&0&-1\\1&0&-1&0\end{bmatrix}\begin{bmatrix}1\\0\\0\\0\end{bmatrix}\\&=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\0\\0\\1\end{bmatrix}\\&=\frac{1}{\sqrt{2}}(\lvert 00\rangle + \lvert 11\rangle)\end{align}$$

Which is not the correct solution. Where am I at fault?

The problem is in the order of the transformations. The first transformation you apply in the circuit is $I\otimes X$, whereas in the computation of $M$ it is actually the last. Recall that the rightmost operator is the first to act on the state (matrix multiplication is not commutative).

Fixing that we obtain:

$$
M=(H\otimes I)(I\otimes X)CNOT(I\otimes X) =
\begin{bmatrix}
H & 0 \\
0 & H
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}=
\begin{bmatrix}
H & 0 \\
0 & H
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & I
\end{bmatrix}=
\begin{bmatrix}
I & I \\
I & -I
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
0 & X
\end{bmatrix}=
\begin{bmatrix}
I & X \\
I & -X
\end{bmatrix}
$$

Now applying $M$ on $|00\rangle$ will yield the right result.


Expressive power of lexer + parser Most modern compilers split their syntax analysis into
a lexical phase that is followed by a parsing phase.
The lexical phase is given by a regular expression, while parsing
is guided by a context-free grammar.

What class of languages can be recognised this way?
Context-free languages, or can we get into context-sensitive
languages?

As stated in the question, this recognizes only context-free languages.

Lexical analysis is actually a GSM mapping, i.e. a finite state
transduction. Since CF languages are a full Abstract Family of Languages (full AFL), they are closed under
inverse GSM mapping. Hence, if the sequences of lexemes parsed by the second phase belong to a  context-free language, the original texts as a sequence of characters also belong to a
context-free language.  This 2 levels organization does not change the CF
characters of syntax, assuming the second level is indeed context-free.

One point is worth noting, though it is a minor technical issue. To
have this CF character of the second phase, it is necessary that identifiers be replaced
by a finite set of standard categories represented each by a unique
symbol. The same is true for literals such as strings or numbers. The
point is that many languages do not in principle put any limit on the
size of identifiers, or some literals, so that there is in principle an infinite number
of them. But the context free grammar of the second phase must have a
finite alphabet, like any CF grammar.  Hence the lexical elements
returned by the first phase cannot actually distinguish all
identifiers, or all literals, for the second phase.

However the information is kept by other means for the more semantical
phases of the compiling process.

It is true that any given program does have a finite number of
identifiers and literals, but the point is that we are considering the language of all possible programs.

Another point is of course that texts of compiler accepted programs do
not form a context free language as other constraints (such as
declarations of identifiers) are imposed on programs, in parallel to
the strictly syntaxic parsing process.

But, ignoring those more "semantics" constraints, some parsers also
use a variety of parsing "tricks", such as prioritization of reduction
rules to avoid ambiguities or non-determinism. As long as this is done
with a finite memory and a pushdown stack that is used only within a
fixed finite distance from its top, this does not get the syntax out
of the context-free realm. However, what extra parsing rules may exist
for the parser also have to be known to the users of the language,
thus making the understanding of the syntax more complex to users, and
giving more ground for misunderstanding. TANSTAAFL. Supposing this is
used to reduce ambiguity, it could then happen that the user will read
his program one way, while the parser reads it another way.

My own preference is for general CF parsers, that will detect
ambiguity (which is, of course, decidable for a given string of an
ambiguous language), and reject it as a programming error. But that is
much a matter of taste in design.

Including the lexical phase into the context-free syntax may possibly
make those extra rules more complex, as reasonning can no longer
isolate lexical issues fron CF syntactic ones. It can also make the
automaton underlysing the parser more complex, or call for more extra
rules. Typically, if parsing the CF part of the syntax requires a
lookahead that may include an identifier, the look-ahead becomes
unbounded when identifiers are not reduced to one symbol by a lexical
phase. Much depends also on the chosen parser generation technology.

Though there are some scannerless parsers used, I would think this applies more to languages with specific lexical and syntactic characteristics. But I am no expert on this, and the wikipedia page seems a bit weak on the general presentation side.

Finally, another interesting point, close to the initial question is
error recovery. It is used by compilers so as to be able to catch many
errors at each run, and was important when compiling was done in batch
mode, rather than interactively. Many syntactic error recovery
techniques are based on a formal model of finite state generation of
errors, such as missing or extra symbol, or local garbling of the strings
(this is also true for natural language processing). This can also be
modeled by a GSM. Hence, ignoring again semantical aspects, the larger
language of programs with syntactic errors accepted by a parser with
error correction is also context-free.

There is more in the comments, but how long should an answer be?


Canonical form for a graph I am trying to find a description for canonical form (labelling) for a graph. Specifically, how do we arrive at canonical form for a given graph?

Graph canonization is a a procedure that takes a graph $G$ and returns an isomorphic graph $C(G)$, we the promise that $C(G) = C(H)$ iff $G$ and $H$ are isomorphic. We call $C$ a canonical form.

One possible canonical form is the lexicographically smallest adjacency matrix. Given an ordering of the vertices, we can serialize the adjacency matrix as a binary string. Given a graph $G$, we choose the ordering leading to the lexicographically smallest such string, and then order the graph accordingly to form $C(G)$. It is not hard to check that this is a canonical form.

The algorithm, as stated, has exponential complexity, so isn't practical. There might be faster ways to compute this canonical form, or they might be other canonical forms which are easier to compute. Notice, however, that canonical forms can be used to solve graph isomorphism, and so finding an efficiently computable canonical form is hard and might be impossible (depending on the meaning of efficient).

It is still possible that there is an easily computable canonical form that works for most graphs, just like graph isomorphism is easy for most graphs. For more on this topic, see this question, and particularly the survey by McKay and Piperno mentioned in my answer there.


There could not be an edge from u to v in a DAG, if w is before v in a topological order I am trying to prove that given a DAG. There exists a valid topological  ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post visit order satisfies the condition of topological order.
How do I construct a proof?

Assume that there is path $u \rightarrow v$ as well. Then we have a cycle. What does this mean in terms of topological order? Can there be such an order? Whether u comes first or v comes first depends on where you start!


Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem) When proving a language is non regular we can use Kolmogorov complexity.
As far I know to do this we just have to use this satisfy the following conditions
Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such y's brings us to an element in the set  A

Given $A \subseteq \Sigma^*$ has the following property, then it is not regular
For every $c \in \mathbb{Z^+}$ there exits $x \in \Sigma^*$, and $n \in \mathbb{Z^+}$ s.t. $Y^A_{x,n}$ exits and K-Comp $C(Y^A_{x,n}) > c + log(n)$

We are trying to show weather given a DFA will it end in a final state after certain number of steps and this process will tell us if that is not a possibility since we cannot prove regularity just non-regularity
Keeping that in mind I am trying to prove this language is not regular

Let us run through a simple example B = $\{0^n1^n | n \in \mathbb{N}\}$
Proof: Let c $\in \mathbb{N}$. Choose k $\in \mathbb{Z^+}$ such that $C(1^k) > c$, and let x = $0^k$ then we get the following$Y^A_{x,1} = 1^k$<-why? and $Y^A_{x,2} = 01^{k+1}$<- again why
therefore $C(Y^A_{x,1}) = C(1^k) > c + log(1)$ QED

You are asking many questions. Let me answer your first two, regarding $Y^A_{0^k,n}$ for $A = \{0^k1^k : k \geq 0\}$. Recall that $Y^A_{0^k,1},Y^A_{0^k,2},\ldots$ is the list of all strings $y$ such that $0^ky \in A$, arranged in some order - apparently first according to length, and then lexicographically. It is easy to see that the strings $y$ such that $0^ky \in A$ are of the form $0^m1^{k+m}$. Arranged according to length, these are $1^k,01^{k+1},0^21^{k+2},\ldots$, and more generally, $Y^A_{0^k,n} = 0^{n-1}1^{k+n-1}$.


Unbounded, 2-dimensional knapsack problem I have the following problem:

There is rectangle with fixed $W > w_i$ width and $H > h_i$ height.
Given a set of item types, where each type has some $w_i$ width, $h_i$ height and $v_i$ value.
I would like to maximize the value of the items placed in the rectangle.

An item can be placed as many times as needed. Not every type has to be present in the optimal solution. Two items can not overlap.

Is there any literature available for this (or a similar) problem? Is there a name for this problem? I didn't have luck with finding info on optimizing inside a 2-D region.

Just the special case of (in your terms) 1-dimensional knapsack is NP-complete, and that is a special case of your 2-dimensional one (just take a strip of width one to be filled with strips of width one). It is very unlikely that an efficient algorithm exists for your problem.

Similar problems are handled e.g. by newspapers (need to fill pages with rectangles for ads, for instance), when cutting up sheets into custom sizes and similar applications. Search for those, there must be publications on approximation algorithms.


How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$? How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$?

I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working..

You can use repeated substitution:
$$
\begin{align*}
T(n) &= n + \sqrt{n}T(\sqrt{n}) \\ &=
n + n + n^{3/4} T(n^{1/4}) \\ &=
n + n + n + n^{7/8} T(n^{1/8}) \\ &= \cdots
\end{align*}
$$
You reach the base case after after $\ell$ iterations when $n^{1/2^\ell} = 2$ (say), whose solution is $\ell = \log_2\log_2 n$. Assuming for simplicity that $T(2) = 0$, we get $T(n) = n\log_2 \log_2 n$.


Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic? As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous?

I mean, it would have to look something like:

S -> function_declaration | function_call | expr
function_declaration -> ... | S
function_call -> ... | S
expr -> ... | S

Maybe not all of them would have to point back to S, that depends on the specifics.
Is there any way to solve this?

There is just no need for rules (or non-terminals) that are cyclic,
which I understand means that, for some non-terminal $X$, you have
$X\stackrel*\Rightarrow X$.

What you often need is recursive rules and non-terminals, such that
$X\stackrel*\Rightarrow uXv$, where $u$ and $v$ are strings of
symbols. Without them, the language is finite.

For example, in the case of expressions you may have:

$Expr \to Term + Expr \mid Term$
$Term \to Factor * Term \mid Factor$
$Factor \to Ident \mid Literal \mid ( Expr )$

This said, you are right that cyclicity, as you define it, does make
the grammar ambiguous iff the cyclic symbol can also derive on a
terminal string.


Practical exponential time algorithms for polynomial-time solvable problems Inspired by this quote attributed to Alan Perlis:

  For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run.

How I interpret this statement is that some exponential running times should be preferred over polynomial ones for realistic problem sizes. I have never actually seen such a case though.

I wonder if there are any problems for which exponential algorithms are known that are preferable to the best polynomial ones up to a nontrivial problem sizes?

The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).


Generalisation of pancake sorting with arbitrary flipped slices? In pancake sort, the primary operation is: flip all pancakes above a given position. What about flipping all pancakes between two given positions? Anybody knows if this has been studied?

To illustrate the problem, here is a quick brute-force, greedy implementation in Python 2.7 (not quite sure it always converges though):

def sort(a):
    entropy = 0
    for i in range(len(a) - 1):
        entropy += abs(a[i] - a[i+1])
    while True:
        max_improvement = 0
        for i in range(len(a) - 1):
            for j in range(i + 1, len(a)):
                improvement = 0
                if i > 0:
                    improvement += abs(a[i] - a[i-1]) - abs(a[j] - a[i-1])
                if j < len(a) - 1:
                    improvement += abs(a[j] - a[j+1]) - abs(a[i] - a[j+1])
                if improvement > max_improvement:
                    max_improvement = improvement
                    (next_i, next_j) = (i, j)
        if max_improvement == 0:
            if a and a[0] > a[-1]:
                a[:] = a[::-1]
                print a
            return
        entropy -= max_improvement
        a[next_i:next_j+1] = a[next_i:next_j+1][::-1]
        print a

a = [7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
print a
sort(a)

Output:

[7, 1, 3, 8, 6, 0, 4, 9, 2, 5]
[7, 6, 8, 3, 1, 0, 4, 9, 2, 5]
[7, 6, 8, 9, 4, 0, 1, 3, 2, 5]
[7, 6, 8, 9, 4, 5, 2, 3, 1, 0]
[9, 8, 6, 7, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 4, 5, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 2, 3, 1, 0]
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Yes, it has been studied quite a lot. The general problem is called sorting by reversal. It is important as it is related to finding the similarity between genomes of two species that have the same genes, but in different order.

There are two variants of the problem, one where the orientation of the pancake [= gene] also matters. This is modelled using so-called signed permutations. See also the last paragraph and references in the Wikipedia page you quote.

There is a very precise characterization of the number of reversals needed for signed permutations in terms of the structure of a certain graph. For the unsigned variant, which you use in your question, the problems seems NP-hard (see the Wiki page) and even hard to appoximate.


Is finding the longest path of a graph NP-complete? The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of a graph NP-complete? Is it still NP-complete if we require the path to visit a given vertex?

First, it is easy to see that the problem is in $\text{NP}$. The longest path is a Hamiltonian one since it visits all vertices. Indeed, there is a straightforward reduction from $\text{HAM-PATH}$ to it. For details and some special cases, see for example here. Likewise, it is $\text{NP}$-complete to decide whether there is a path of length $k$ with the a similar argument: just set $k$ such that the problem is equivalent of solving $\text{HAM-PATH}$. Finally, if I understood your third point correctly, it doesn't make the problem any easier if you in addition require the path to visit a specific vertex $v$. Similar reasoning holds for this case.


How can I understand a hint for finding the lowest height of the last bulb in a Garland? Disclaimer
This is not from an ongoing contest, this is from my course on edx of ITMO.
Also this is a paid courses so the direct link to the problem is not useful unless you also register this course.

Problem description
A garland consists of light bulbs hanging from the same wire. One endpoint of this wire is fixed at a height of $A$ millimeters ($h_1 = A$. Thanks to gravity, the garland bends down: the height of every light bulb which is not at the endpoint is one millimeter smaller than the average height of its neighbors: ($\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1$ for $1 < i < n$).

Determine the smallest height of the second endpoint $B$ ($B= h_n$), given that at most one light bulb is allowed to touch the ground, and for all other light bulbs the inequality ($h_i$ > 0) should be true.

Hint: to solve this problem, you can use binary search.

Input
The first line of the input file contains two numbers $n$ and $A. 3 \le n
\le 1000$, $n$ is an integer, $10 \le A \le 10000$, $A$ is a floating-point number which has at most three digits after the decimal point.

Output
Print a single number $B$ , which is the minimal height of the second endpoint. Your answer is considered to be correct if it differs from the right one by at most $10^{-6}$.

Examples

$\displaystyle\begin{array}{|l|l|}
  \hline
  \text{input.txt} & \text{ output.txt} \\\hline
  8\ \,15 & 9.75 \\\hline
  692\ \,532.81 & 446113.34434782615 \\\hline
\end{array}$

There are problems that you either get it or don't, this is the "don't get it" for me. I cannot correlate the hint to the solution. I mean what we are supposed to search, although I can understand the problem but it's like the hint is the ambiguity for me. Without the hint, I don't know how to proceed, either.

Short answer

Let $d=h_1-h_2$. Do a binary search for the largest value of $d$ in interval $[0,A]$ so that none of $n$ bulbs in the garland will be lower than the ground. The wanted minimum value of the second endpoint $B$ corresponds to the case when $d$ is that largest value.

Explanation

The question is how to understand the hint "you can use binary search".

Before understanding the hint, we are supposed to have understood what is binary search. Binary search is a search algorithm that finds the position of a target value within a sorted array or an interval.

So, what could be that target value we are supposed to search? Within which sorted array or which interval?

The most obvious target value to search is $m$, the minimal value of $B$. We could search $m$ within the interval $[0, \text{FM}]$, where $\text{FM}$ is the maximum value of a floating-point number.
Another obvious target to search is about that lowest bulb. In case there are two lowest bulbs, the lowest bulb will mean the one to the left. The further to the right the lowest bulb is, the lower value $B$ is. We could search $\ell$, the rightmost possible position of the lowest bulb within the interval $[0,n]$.

Whenever we started to compute, we find we have to understand clearly the given equality, $\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1.$ If $h_1=A$ and $h_2$ are known, the height of every bulb is fixed, since
$$h_{3}=2\times h_{2}-h_{1}+2$$
$$h_{4}=2\times h_{3}-h_{2}+2$$
$$\cdots$$

The only requirement is that no bulb can be lower than the ground. Note that

$$\displaystyle h_{i+1}-h_i=h_{i}-h_{i-1}+2.$$

As we visit the bulb from left to right, the bulb is dropping less and less between each pair of successive bulbs initially. Once the bulb have reached the lowest level, it will climb more and more between each pair of success bulbs.   The larger the first drop $h_1-h_2$ is, the more likely one of the $n$ bulbs will hit the ground and the lower the last $B$ will be. Aha, we can also search the largest value of $h_1-h_2$ within interval $[0, A]$.

How to binary search a real number?

How can we search for the largest value of $d$, which is a real number in an interval?

Since there are infinitely many real number in an interval, checking equality is not likely to work as the stopping condition. That is why we are given the requirement for the "the minimal height of the second endpoint" that it differs from the right one by at most $10^{−6}$". The pseudocode looks like the following.

'''A=h_1, n are given.'''

'''10^(-7) instead of 10^(-6) to guard against rounding errors in computation of floating-point numbers'''
precision = 10^(-7)

function get_largest_first_drop_by_binary_search():
    L = 0
    R = A
    B_L = last_height(L)
    B_R = last_height(R)
    while ( B_L - B_R > precision):
        m = (L + R) / 2.0
        if hit_ground(m):
           R = m
           B_R = last_height(R)
        else:
           L = m
           B_L = last_height(L)
    return B_L

function last_height(d):
    ''' Given first drop h_2 - h_1 = d, return h_n, the height of last bulb'''
    return A + ((-d)+(-d+2(n-2)))(n-1) / 2

function hit_ground(d):
    ''' Given first drop h_2 - h_1 = d, return true iff the garland will hit the ground '''
    k = floor(d/2) + 2
    if k >= n return last_height(d) < 0
    if k < n return A + ((-d)+(-d+2(k-2)))(k-1) / 2 < 0
    return false

Implementation

Here is an implementation in Java. Click the run button to see the result.

Exercise

Show that the minimum value of the second endpoint $B$ is 0 if and only if $A \ge (n-1)(n-2)$.


Algorithm - How to show Big O for 2 functions I believe that Ln(n) is <= 2^(sqrt(2*lg(n))), so I am trying to prove it

I know that you can show Big O by showing Little O, so I am trying to take the limit as n approaches infinity of Ln(n)/2^(sqrt(2*lg(n)))

However I am finding it hard to prove this using the limit definition

I would appreciate any help to see how to solve this! Thanks

Interpreting lg(n) as log2(n), set n=2^x so that the inequality transforms to

ln(2)*x <= 2^sqrt(2*x)

Now apply the square root,

sqrt(2*ln(2)) * sqrt(x/2) <= 2^sqrt(x/2)

and we are left to prove that for y>0

2^y/y > sqrt(2*ln(2))

Indeed, the minimum of the left side can be found for 0=ln(2)*y-1 or y=1/ln(2) with minimum value 2^(1/ln(2))*ln(2). Numerically, the gap between 1.88416938536372 and 1.1774100225154747 is large enough to exclude any floating point errors. Thus all the equivalent inequalities including the original one are true.


When is relation in 3NF but not in BCNF? A book by Korth et al. defines BCNF as follows:

  A relation schema $R$ is in BCNF with respect to a set F of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where  $α⊆R$ and $β⊆R$, at least one of the following holds:

  $α→β$ is a trivial functional dependency (that is, $β⊆α$).
  $α$ is a superkey for schema $R$.

It then defines 3NF as follows:

  A relation schema $R$ is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $α→β$, where $α⊆R$ and $β⊆R$, at least one of the following holds:

  $α→β$ is a trivial functional dependency.
  $α$ is a superkey for $R$.
  Each attribute $A$ in $β-α$ is contained in a candidate key for $R$

So 3NF definition adds an additional 3rd condition to the BCNF definition: "Each attribute $A$ in $β-α$ is contained in a candidate key for $R$". I think we can correctly interpret this condition as $β-α$ are key attributes.

Now I was thinking about which relations are in 3NF but not in BCNF. Clearly the relation which contains the dependency that satisfies this 3rd condition can be in 3NF but not in BCNF.

The book gives following example:

  The schema dept_advisor : {s_ID, i_ID, dept_name}
  with FDs

  i_ID $→$ dept_name
  s_ID, dept_name $→$ i_ID

  Here, first FD is non trivial. Also i_ID is not a super key. Hence schema is not in BCNF. Now dept_name is a part of the candidate key (s_ID,dept_name). Hence, dept_advisor is in 3NF.

Now I came across following statement on this site, which I think I have also read in the book:

  3NF states that all data in a table must depend only on that table’s "primary key", and not on any other field in the table. At first glance it would seem that BCNF and 3NF are the same thing. However, in some rare cases it does happen that a 3NF table is not BCNF-compliant. This may happen in tables with two or more overlapping composite candidate keys.

I have two doubts:

What does it imply by using "primary key" in first sentence. Cant there be two or more candidate keys in a 3NF relation with some FDs involving one CK and remaining FDs involving other CK. This must not be the case due to the last sentence in above paragraph, which is source of 2nd doubt below. But then why use "primary key"? Should the sentence rather be "3NF states that all data in a table must depend only on that table’s candidate keys or better to say superkey"?
From definitions of 3NF and BCNF, what I felt is the relation which is in 3NF but not in BCNF should be the one having FD following 3rd condition of 3NF definition and there can be no other situation which can lead to non-BCNF but 3NF relation. If so, how is "two or more overlapping composite candidate keys" (as stated in last sentence of above paragraph) is equivalent to/lead to such FD? Or to put in different way, where are overlapping composite candidate keys in above example of dept_advisor?

Am I thinking stupidly? Am I giving unnecessary importance to these points and are in fact senseless?

"I think we can correctly interpret this condition as β−α are key attributes."

No. β−α is a set of attributes. What that statement is saying is,

Every attribute in that set is part of some (at least one) candidate key for the relation.

Also, if by 'key' attribute, you mean an attribute that is a superkey, i.e., an attribute whose value uniquely determines the tuple, then NO, every element in β−α is NOT a key attribute. It is just a prime attribute (in other words, part of some candidate key).

For example, if we write your schema as:

  Dept_advisor : {A, B, C},

then the FD's can be written as:

B → C (α = {B}, β = {C}, β−α = {C} - {B} = {C})
AC → B (α = {A, C}, β = {B}, β−α = {B} - {A, C} = {B})

Here, [1] is neither a trivial dependency nor is α (here, B) a superkey of the relation. In other words, none of the two conditions for BCNF hold for this FD.
For BCNF, you need all the FD's to satisfy at least one of the two conditions, but here you have one FD which satisfies none. So this schema is not in BCNF. You got this right.

Now, testing it for 3NF, you can confirm that both [1] and [2] satisfy at least one of the 3 conditions for 3NF. [2] satisfies the 2nd condition (α = {A,C} is a superkey), so we are good so far. [1] does not satisfy any of the first two conditions, which are also the conditions for BCNF. But, it does satisfy the third condition, i.e., each attribute in β−α (here, only one attribute, namely B) is part of some candidate key.

What candidate key is that, you ask? You can easily find one.

Take {A, B}. It is a candidate key because you have the FD B → C, which means {A, B} → {A, B, C} gives all the attributes of the relation, which means it is a superkey. But no proper subset of {A, B}, i.e., neither A nor B alone, are superkeys themselves. In other words, neither {A} → {A, B, C}, nor {B} → {A, B, C}. So yes, you got this one right too, but for the wrong reasons.

As for the other statement, about 3NF tables being dependent only on the "primary key", you are better off just ignoring it and sticking to the definition and trying to understand and use it correctly.


Proof of Trakhtenbrot's theorem In the proof of Trakhtenbrot's theorem (as given in "Elements of Finite Model Theory" by Leonid Libkin), for every Turing machine $M$, author constructs a FO sentence $\Phi_M$ of vocabulary $\sigma$ such that $\Phi_M$ is finitely satisfiable iff $M$ halts on the empty input. Then he says that as the latter is known to be undecidable so the theorem holds.

My doubt is, the vocabulary $\sigma$ that was constructed depends on the Turing Machine $M$. But the theorem holds for any relational vocabulary with at least one binary relation symbol and also it should not depend on the machine $M$. Perhaps the claim of author is enough to imply the theorem for arbitrary vocabulary, but I am unable to see how.

I'm a bit late, but the only answer does not address the question.

You state that the vocabulary $\sigma$ depends on the choice of turing machine $M$. If this were the case, then indeed the claim would only follow for arbitrary vocabularies.
But - as the index of $\Phi_M$ and the missing one of $\sigma$ hint at - only the formula depends on $M$, the vocabulary is fixed for all turing machines.

Now all this shows, is undecidability for this particular vocabulary $\sigma$. To get the desired undecidability for all vocabularies with at least one binary relation, we have to do the reduction using only a single binary relation. We do this by encoding all of $\sigma$ into a single binary relation. The specifics are a popular exercise (and indeed the first exercise in the chapter), and go back to techniques first used by Kálmar.


Karp hardness of testing for homomorphisms to a fixed non-bipartite graph Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$ such that:

  For every $u,v\in V(G)$,  $(\varphi(u)=\varphi(v))\lor(uv\in E(G)\implies\varphi(u)\varphi(v)\in E(H))$.

Note that we do not allow loops and multiple edges. This is just because $H$ is  a fixed simple undirected graph. So, mapping to the same vertices is good but remember to map to every vertex of $H$. This also does not put constraint on those vertices mapped to the same $H$-vertex. By standard definition, without a loop at that $H$-vertex, the set of $G$-vertices mapped to it needs to be an independent set.

We want to decide whether a given graph $G$ is loopless surjectively homomorphic to $H$. Note that for each fixed non-bipartite $H$, we have a decision problem, denoted by $\mathrm{HOMOMORPHIC}_H$.

Formally, for every fixed (i.e. not part of the input) non-bipartite graph $H$, $\mathrm{HOMOMORPHIC_H}$ is defined as below:

  Input: An undirected graph $G$

  Output: YES if $G$ is loopless surjectively homomorphic to $H$, otherwise NO

We want to know the computational complexity of this problem.

As others have pointed out in the comments, your definition of homomorphism is highly unusual. In particular, any function whose image is a single vertex is a homomorphism by your definition, thus trivializing the decision problem. The usual definition is as follows:

A homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $uv\in E(G)$ we have $\varphi(u)\varphi(v)\in E(H)$.

For the usual definition, the problem is known to be NP-complete for every non-bipartite $H$. The reference (according to Wikipedia) is Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110. (For bipartite $H$, on the other hand, there is a homomorphism if and only if $G$ is bipartite. Thus the decision problem is just bipartiteness of $G$, which is in PTIME.)

A few other notion are somewhat halfway between your definition and the usual one:

A strong homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $u,v\in V(G)$ we have $uv\in E(G)$ if and only if $\varphi(u)\varphi(v)\in E(H)$.
An embedding from $G$ in $H$ is an injective homomorphism, that is a homomorphism $\varphi$ such that for all $u,v\in V(G)$ with $u\not=v$ we have $\varphi(u)\not=\varphi(v)$.
An induced subgraph mapping is an injective strong homomorphism.

[EDIT]

For each of these variants, the problem is in PTIME for fixed $H$.
When injectivity is required, one can reject an instance if $|V(G)|>|V(H)|$, so only a finite set of graphs remains. For strong homomorphisms, we can have $\varphi(v)=\varphi(w)$ only if $v$ and $w$ have the same neighbours. Hence after some polynomial time preprocessing, we can again assume injectivity.


Maximizing total value given bound on total cost I have a list of pairs with values and costs:

    | value | cost |
    11, 1000
    7, 700
    7, 700
    6, 700
    2, 400
    2, 500
    1, 600

The list is ordered by value/cost decreasingly.
The task is, given a budget X find the maximum value you can get while keeping the total cost within the budget.
In the sample example, if X=1400, the maximum value would be 14.

What algorithm would be the most efficient to find this value?

Your problem is KNAPSACK, one of the classic NP-complete problems. Wikipedia contains a wealth of information about the problem, include exact and approximation algorithms.


Why vertices of directed acyclic graph are considered strongly-connected components? Well the title pretty much says it all, I've heard our professor saying that the smallest strongly-connected components in DAG (directed acyclic graph) are its vertices. Sadly I was unable to ask him for explanation and now this is stuck in my head ever since.

This has to do with the definition of Strongly Connected Component in graph theory.

  A graph to be said to be Strongly Connected if every vertex is
  reachable from every other vertex.

The smallest possible graph of any type consists of a single vertex.
Since that vertex can reach itself (since it is itself), the graph therefore meets the criteria, and can be considered Strongly Connected.

In this image, the nodes at the bottom right, and the top middle are examples of smallest possible strongly connected components:


Complete problem for $\mathrm{QP}$ (quasipolynomial-time solvable languages) Question 1: Is it known that $\mathrm{QP}=\cup_{k}\mathrm{TIME}(2^{\mathrm{log}^k(n)})$ has any complete problem?

Question 2: Can this be used to simplify the computational complexity theory at all?

Question 1: NO

Question 2: NO

Question 1: Assume to the contrary that $\mathrm{QP}$ has a complete problem $\mathrm{L}\in\mathrm{QP}$.

Then, there exists $k$ such that $\mathrm{L}\in\mathrm{TIME}(2^{\mathrm{log}^k(n)})$. Consider an arbitrary problem $\mathrm{L}'\in\mathrm{QP}$, by completeness of $\mathrm{L}$, we have that $\mathrm{L}'\leq_p\mathrm{L}$, i.e there exists a many-one polynomial-time reduction $f$ from $\mathrm{L}$ to $\mathrm{L}'$. So, given any instance $x\in\Sigma^*$ with $|x|=n$, we first reduce $x$ to $f(x)$. Since $f$ is polynomial-time computable, we have that $|f(x)|=n^{O(1)}$. Now, we run the $2^{\mathrm{log}^k(n)}$ time-bounded TM deciding $\mathrm{L}$, and accept or refute accordingly.

We now estimate the time complexity of this TM for $\mathrm{L}'$. We have:
$$2^{\mathrm{log}^k(n^{O(1)})}=2^{O(1).\mathrm{log}^k(n)}=2^{O(\mathrm{log}^k(n))}$$

So, the whole class $\mathrm{QP}$ collapse to $\mathrm{TIME}(2^{O(\mathrm{log}^k(n))})$ violating the Time Hierachy Theorem.

Thus, $\mathrm{QP}$ does not have any complete problem.

Question 2: The unconditional lack of complete problem of $\mathrm{QP}$ unconditionally separates it from $\mathrm{NP}$, $\mathrm{co}$-$\mathrm{NP}$, $\mathrm{PP}$, $\oplus P$, $\mathrm{US}$, $\mathrm{PSPACE}$. But that is of no help for computational complexity theory, since the interesting nasty, stubborn classes such as $\mathrm{ZPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{BPP}$, $\mathrm{MA}$, $\mathrm{AM}$ all remain elusive to whether any of them has a complete problem.


Detecting approximate sum collisions in two lists. Suppose two equal-length lists of double precision numbers $A=(A_1, \ldots, A_N)$ and $B=(B_1, \ldots, B_N)$. Given a constant, $\epsilon > 0$, I want an efficient algorithm for finding 4-tuples of the form $(A_a, A_b, B_c, B_d)$ for which $|A_a + A_b - (B_c + B_d)| < \epsilon$.

One thing you could do is form the sum sets $S_A:=\{A_j + A_k\}$ and similarly, $S_B$, sort them, and then iterative over these in parallel looking for elements that satisfy the requirement.

This algorithm should have complexity of the form $O(N^2)$ (with perhaps a constant multiplicative factor). Forming the sum sets has complexity $\sim O(N^2)$, the sorting has complexity $\sim N \log N$; the final step is a single pass through both sum sets; also complexity $O(N^2)$.

Is there an algorithm that does better than $O(N^2)$?

I believe there is no known algorithm with running time faster than $O(N^2)$, even if you work with integers and ask for a tuple such that $A_a + A_b - (B_c + B_d) = 0$ (i.e., is exactly zero).

There are algorithms with running time $O(N^2)$ and space $O(N)$.  Basically, they iterate through the sum sets $S_A$ and $S_B$ in order, without ever storing the entire sets in memory, by using a priority queue.

There are also algorithms that with running time $O(N^{4/3})$, if the numbers are chosen uniformly at random over some range and if you can choose $N$ appropriately (i.e., if the relationship between $N$ and the size of that range can be chosen appropriately) and if you only care about finding one such 4-tuple (even though many might exist).  I suspect this probably isn't of use to you.


How do you protect an AI from a human doing "illogical" moves? Using a monte carlo approach and evalutation function. Some moves will deemed to be more advantageous than others.

As a computer plays itself, it will generally go for the best moves possible. And hence train itself to deal with these moves.

But what if a human does a few seemingly detrimental moves to throw the AI off track. And then using the human's expertise, go on to win the game?

How can one train an AI to account for this?

Or must we assume that it can generalise board positions from "perfect" games to board positions of imperfect games?

(Presumably AlphaZero has no problem with this? Has anyone ever tried to trick AlphaZero by doing a few silly moves?)

In principle, the problem of building an AI where this can never happen seems equivalent to the problem of building an AI that plays perfectly.

More precisely: If the AI can perfectly evaluate the value of each board position, then it is also able to play perfectly even if the adversary plays imperfectly.  Conversely, if there is a situation where the AI can be tricked by playing an inferior move, then that means there is a board position that the AI evaluates incorrectly.

So avoiding this situation seems as hard as building an AI that never makes the wrong decision.  If we knew how to do that, we would have a perfect solution to the game.  There are some games (e.g., tic-tac-toe, Connect 4) where we do know how to achieve perfect play, but for more challenging games (e.g., chess), we don't know how to achieve perfect play.  As I result, it seems likely there exists a board position where playing an inferior move helps you win where you otherwise wouldn't have.

This means that we need to focus on solutions that reduce the risk/likelihood of this bad situation, as we cannot eliminate it entirely.

When the AI is trained using statistical machine learning (as AlphaGo and AlphaZero are), you can think of this as avoiding overfitting -- you don't want to overfit to any one opponent strategy.  One way that AlphaZero is trained is to play simulated games against multiple opponents -- not just against itself, but against multiple versions of itself, including older (and presumably inferior) versions of itself.  This helps avoid getting stuck in a narrow portion of the space, e.g., where white always plays the Ruy Lopez opening and black always plays the Morphy defense.  This may partly help make the AI more robust against inferior moves, but it is not a complete solution.

In Monte Carlo tree search (MCTS), the algorithm considers random moves for the opponent.  These are drawn from a random distribution that is biased towards moves the algorithm thinks is better, but there is definitely a significant chance during any playout that we'll simulate what happens if the opponent makes a move we consider detrimental/inferior.  This helps MCTS be robust against even inferior moves.  It's not perfect, but it's already baked into the MCTS algorithm.


Why does the cumulative order in which nodes are first visited with Iterative deepening is effectively breadth-first I have had comparative algorithm exercise to do about algorithm propoerties such as completeness, time complexity, memory complexity... I discovered Iterative deepening depth-first search algorithm.

On Wikipedia, it is said that it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first.

I know what breadth-first algorithm is but I don't understand that last sentence... What does it actually means?

What this statement means is that if you list the order in which vertices are "discovered" (first visited) in iterative deepening DFS, then it will be the same order in which vertices are discovered in BFS.


Questions About P, NP, languages I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too.

Given language L, which is non-recognizable, is L* context free?
Is P countably infinite, and why?
Are all recognizable languages NP-complete?

1.) Every context free language is decidable. CFL are not unrecognizable. Refer 1

2.) P is countably infinite because P is the class of decision problem that can be solved on a deterministic turing machine in polynomial time. Every turing machine can be thought of as a finite string over some finite alphabets but all possible set of turing machines are countable infinite hence P is also countably infinite.

3.) NP complete languages are recognizable. A NP Complete languages can be found by modifying the halting problem which is just another form of halting problem(NP-Complete). Halting problems are undecidable but recognizable hence all NP-Complete problems are recognizable. Refer 2 fro details.


Number and probability of random allocations of n processes to n servers I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space of allocations is n^n, and each has equal probability.

Intuitively this seems unlikely to me: if you imagine each server having a number and that number being the number of processes assigned, you wouldn't have the case of two servers being assigned n processes; yet the n^n -- as far as I can see -- assumes that such allocations are possible.

Am I missing something?

The number $n^n$ can be easily obtained if you think the problem in the other direction: each process has $n$ choices and therefore $n$ processes has $n^n$ possible choices in total. Of course it is impossible that two servers have $n$ processes. If a process can be assigned to more than one server, the number of possible assignments is far more than $n^n$.


Quantum computers, parallel computing and exponential time I've read that quantum computers can solve 'certain problems' exponentially better than classical computers.  As I think I understand it, it's NOT the same to say that quantum computers take any problems that are EXPTIME-complete, 2-EXPTIME,... and convert them to linear time or constant-time.

I would like to know something more about this matter:

Why can/can't a quantum computer solve exponential problems in sub-exponential time?
Is it at least theoretically possible to imagine a computer (quantum or otherwise) able to solve EXPTIME-complete problems in constant time? Or does this lead to a contradiction?

EDIT  a third related item:

Can quantum computers do parallel computing?

Now that the subject came up from comments, the idea about parallel computing, that's the usual/pop vision about quantum computers, like if quantum computers were able to compute "all posibilities at once" of any given problem (I think if that were the case, wouldn't be necesary to call great Peter Shor to invent a factoring algorithm!). Then "why" question about quantum computers can/cannot do parallel computing is half a computer science and a physics question.

Here a source of confusion: http://physics.about.com/od/physicsqtot/g/quantumparallel.htm

Why can't a quantum computer solve exponential problems in sub-exponential time? Factoring is believed (by some) to take classical time $2^{n^\epsilon}$ for some $\epsilon > 0$, while Shor's algorithm takes time $O(n^3)$. Does that count?

Is it at least theoretically possible to imagine a computer able to solve EXPTIME-complete problems in constant time? Sure, consider a Turing machine with oracle access to all EXPTIME problems (i.e. the oracle accepts the code of an EXPTIME machine and an input, and returns the output). This doesn't lead to any contradictions. Is this realizable in practice? Probably not.

Can quantum computers do parallel computing? It is known that BQP$\subseteq$PP$\subseteq$EXPTIME, and most people expect these inclusions to be proper. Under this conjecture, there are problems solvable in classical exponential time but not quantum polynomial time. In particular, EXPTIME-complete problems shouldn't be in BQP.


Complement of a DFA without final states Let $L_1=\{Q,\Sigma,q_0,\delta,Q\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting states with its non-accepting states, that is $\overline{L_1}=\{Q,\Sigma,q_0,\delta,Q-Q\}$. In this case we have a DFA without final states. Is this still a DFA? Is it regular?

It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (There are many other such algorithms. For example, Hopcroft's state minimization algorithm doesn't work on incomplete automata, at least without some adjustment.)

If the DFA you are referring to is complete and has no non-accepting states, then it must be the case that it recognises $\Sigma^*$ so that its complement is the empty set. But I have a hunch that's not the case.

You can always convert an incomplete DFA into a complete DFA by adding a single non-accepting state with a looping transition on every symbol. (This is usually called the "sink" state, because there is no way out.) Then for every other state which has no transition on one or more symbols, you add all the missing transitions with the sink state as a destination. Since the sink state is non-accepting and non-escapable, this operation does not in any way alter the language recognised by the DFA.

Once you've done that, it is (probably) no longer the case that every state in the DFA is accepting; there is now one non-accepting state. And the complement algorithm will make that non-accepting state accepting, and all the other states non-accepting, which will produce the complement of the language.


Minimum number of tests to identify subset of modules that trigger a bug? I have an ordered set of $M$ software modules compiled together. The interaction of some  $N$-tuple of these modules is causing a bug when the program is run.

I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests.  Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$).

$N$ is known ahead of time.

For $N=1$, I can efficiently identify the culprit in $\log_2(M)$ tests by binary search.

For other values of $N$, what approach can I take to identify the $N$ culprits?

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer.  The solution is: delta debugging.  Delta debugging solves exactly this problem.

Let me elaborate.

Problem statement

I am interpreting your question as asking about the following problem:

We have $M$ software modules, and some way to run the program in a way where only a subset of them are active (and we can choose the subset freely).
There is a subset $S$ of $N$ of the modules.  There's a fault that is triggered whenever we run the program with all of those modules active.  In other words, if the set of active modules is a superset of $S$, a fault will occur; otherwise, no fault will occur.
The fault is perfectly reproducible and detectable.
Now, we want to find the set $S$ using as few tests (invocations of the program) as possible.

Solution: delta debugging

Delta debugging will solve this problem.  If you have $M$ software modules, and some subset of $N$ of them are responsible for the fault, delta debugging can find the minimal subset that trigger the fault.

Delta debugging works by starting with all of the modules active, and gradually removing some of them.  It picks out some chunk of modules, and tries running the program with those modules inactive.  If the fault still occurs, then we know that none of them are responsible for the fault, so they can be permanently deactivated in all future tests.  Delta debugging starts with large chunks, and gradually reduces the chunk size: it first tries deactivating the first $M/2$ modules, then deactivating the second $M/2$ modules; if neither of those offers any progress, then it tries deactivating the first $M/4$ modules, then the second $M/4$ modules, then the third $M/4$ modules, and then the last $M/4$ modules; then it moves on to chunks of size $M/8$; and so on.

For more details, allow me to point you to a nice description of delta debugging.

Delta debugging is efficient

Delta debugging is expected to take about $O(N \lg M)$ tests, to find the subset.

You might notice how this is a nice generalization of binary search.  When $N=1$, binary search needs $O(\lg M)$ tests, just as delta debugging does.  The difference is that delta debugging also scales nicely when $N>1$.

You might also notice that this is close to optimum.  We can prove a $\Omega(N \lg(M/N))$ lower bound (roughly).  In particular, there are ${M \choose N}$ possibilities for the subset $S$, and each test provides one bit of information (either it triggers a fault or not), so it is easy to see that we need at least $\lg {M \choose N}$ tests.  Now

$$\lg {M \choose N} \approx \lg (M^N/N!) \approx N \lg M - N \log N \approx N \lg M - 0.7 N \lg N \ge N (\lg M - \lg N).$$

Therefore, delta debugging is approximately asymptotically optimal, in terms of the number of tests required.

For a more detailed performance analysis, see this analysis by Jesse Ruderman.

Discussion

That said, I am somewhat skeptical of whether this will be useful in practice.  A crucial assumption here is that you could run the program with a chosen subset of its modules active, and the rest artificially deactivated.  I don't see how to do that in practice.  Therefore, I do not see how this can be applied in practice.

I suspect your theoretical model of the problem probably needs to be adjusted, but since you didn't tell us anything about your particular application setting or the justification for your model, I don't have enough information to specify how to fix the model.

Typically, delta debugging is used for a different purpose.  Normally, delta debugging is used to reduce the size of the test case (not the size of the program).  Say you have a test case with $M$ lines that crashes your program, but only a subset of $N$ of the lines are actually necessary to trigger the crash (the rest are all irrelevant), and you want to find the minimal subset of lines needed. In other words, given a long complex test case that crashes your program, you want to "minimize" it: to find a smaller, shortest test case that also crashes the program -- because small test cases usually make the debugging process easier.  Then delta debugging can be used to solve that problem; in fact, that's what it was invented for, and what it's most commonly used for.


How to efficiently determine whether a relation is total? I have a set $S$ of pairs $(x_1,x_2)$ with $x_1,x_2 \in X$ for some set $X$.

I want to know whether this defines a total relation on $X$. In other words, whether:

If $(a,b)$ in $S$ and $(b,c)$ in $S$, then $(a,c)$ in $S$. (transitivity)
Exactly one of $(a,b)$ and $(b,a)$ is in $S$ unless $a=b$, in which case they are both an element of $S$. (totality and antisymmetry)

Brute-force would take $O(|X|^3|S|)$ steps (I think), because there are $|X|^3$ triples $(a,b,c)$ and looking up whether something is an element of an array costs $O(|S|)$.

A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$.

You can improve the running time of transitivity checking to $O(|X|^\omega)$, where $\omega$ is the matrix multiplication constant; I'll let you figure out how.


Is there a model of computation, that tries to be realistic? For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory.  Secondly Turing machines are not really convenient IMHO for proving things about everyday algorithms on an everyday computer.

I want a model that makes computations in a ring, namely $\Bbb{Z}_p\times \dots \times \Bbb{Z}_p = (\Bbb{Z}_p)^k$, where $p$ is prime (for a good reason... later on that).  Since that's what bytes on a computer look like they look like values in $\Bbb{Z}_8$ and even some of the instructions on those bytes on modern computers cause wrap around that looks like that of $\Bbb{Z}_8$.  It's obvious to me that any computation on my home PC can be done with computations in said ring.  But of course I'd have to prove that formally if I wrote a paper.  I can already write conditional assignments of a memory slot (element of $\Bbb{Z}_p$), as the value of a polynomial in $\Bbb{Z}_p[x_1, \dots, x_k]$.

It's hard to find literature on this, but to me it seems so obvious that this is a nice approach and I'm shocked that no one's considered this yet.  Or have they?  Links please...

As D.W. mentions in the comments, the model you are looking for is the RAM machine. In fact, there are several different models, and I recommend the following recent paper of Fürer's for a good overview.

In contrast to what you describe, the correct ring is $\mathbb{Z}_{2^n}$, where $n$ is the width of registers – up to 512 bits in future Intel processors. The exact value of $n$ doesn't matter at all as long as it's constant, since in computational complexity we are always interested in time and space complexity up to a multiplicative constant. Therefore, to make matters interesting, the RAM models described above let $n$ depend on the input size.

Regarding finitude of memory, this is captured, to some extent, by space constraints – polynomial space (or linear/quasilinear space) for algorithms working on normal data, logarithmic space (or polylogarithmic space) for algorithms working on big data; there are also streaming models for even less space. Restricting the space altogether would be destructive since then all deterministic algorithms would terminate in constant time – to make sense of asymptotics, we must allow space to grow with input size.


Longest-path in a graph, where the path should be 'straight' Is there any existing work done on finding paths that are geometrically straight?

I encountered a problem where I'd need to find the longest straight(-ish) path in a web of connected nodes, each of which has a defined position in euclidean space (they're taken from a picture). Specifically, I want to find all straightish paths longer than X, but finding the longest may be simpler and basically equivalent.

Essentially, this is a path-finding problem in a non-directed, non-planar graph, where the path's destination isn't known, and the path itself must be straight, for an arbitrary and somewhat loose definition of 'straight'.

While I've found path-finding algorithms that use graphs whose vertices have defined positions, they generally work by just using those positions to give each edge a weight, after which the positions are ignored. I'm not sure that couldn't be done here, but I think it'd require a complicated edge-weight function that somehow takes into account the weights of previous edges in the current path.

Perhaps you could consider it a directed graph, where edges go only geometrically away from the source node/existing path - edges that double-back towards the start can't be taken. Marking them as such may be linear. Finding all complete paths (that is, starting at a source and ending at a sink) in a directed acyclic graph is polynomial. So while all the implementations I've tried so far range from 'very inaccurate' to 'quite inaccurate and also slow', I wouldn't expect the problem to be harder than polynomial.

Edit:

Because the graph is derived from an image, the lines will generally never be perfectly straight, and while straightness is usually visually obvious, my current algorithms have measured straightness by minimizing the change in angle from point to point, or by minimizing the geometrical width of the convex hull of either the entire path, or of sections of the path individually in turn. Width being measured perpendicularly to the straight-line distance between the first point in a path and the last. The problem with either of those though, is that each point has to be processed many times (I think $N^3$), and it feels less than elegant, and more like brute force.

The source of the problem is measuring fibers in an image, where the image looks kinda like a large game of pick-up sticks - hundreds of straight fibers, of varying lengths, cris-crossing frequently. Vertices in the graph are at endpoints, intersections, and discontinuities (i.e. potential endpoints). I'd guess that machine learning techniques, or other methods of image-processing, may be better suited for the problem, as it boils down to recognition of simple objects in an image, but the purpose of my question is more to learn about graphs, rather than just solve that problem.

Idea 1: Short paths are straight paths

In Euclidean space, a straight path is usually a short path.

So I would compute shortest paths between every pair of points in the graph.  This can be done in $O(|V|^3)$ time with the Floyd-Warshall algorithm, which is suitable for dense graphs, or $O((|E|+|V|)|V|\log|V|)$ time by running Dijkstra's algorithm starting from each vertex in turn, which is faster for sparse graphs.

You can then evaluate each vertex pair according to whatever "straightness" criteria you like -- e.g. average/maximum angle formed or maximum perpendicular distance, balancing these against the length of the path somehow -- and choose the overall maximum.

For a quick heuristic, you could randomly subsample the points and solve the smaller subproblem.  Repeat this several times to build a list of candidate (source, sink) pairs, then run Dijkstra on each candidate in the full graph to pick the overall winner.

Idea 2: Partition edges by angle

The above should work well if it's OK for the line to be quite jagged at a small scale.  But if smoothness at a small scale is important, another approach comes to mind: Partition the edges into angle buckets (e.g. all edges making an angle of 0-5 degrees with the horizontal, all edges making an angle of 6-10 degrees, etc., for 360/5 = 72 buckets overall).  For each bucket, solve a separate subproblem that contains all vertices, but only the edges in that particular bucket.  Every path in such a graph necessarily contains only edges that have very similar directions.  (If you choose sufficiently fine buckets, you might find that the graph fragments into many small, line-like components, which will speed things up greatly as they can be solved independently.)

In fact it's not necessary to partition the edges; it's probably desirable to have some bucket overlap, so that an edge typically appears in more than one subproblem.


Turing-unrecognizable language - what TM does? I have a problem giving "intuitive" explanation to turing-unrecognizable languages.

We can prove that, say, ${\overline{A_{TM}}}$ is not turing-recognizable, because that would make ${{A_{TM}}}$ decidable, but what would the $TM$ do if it doesn't accept, reject of loop?

You might be a little confused by a definition somewhere.  A TM $M$ is a recognizer for a language $L$ if it

Accepts every string in $L$
Either rejects or loops on every string not in $L$

Now let's think about the language ${\overline{A_{TM}}}$.  An input $\langle N,x\rangle$ is in ${\overline{A_{TM}}}$ if either:

$N$ rejects on $x$.
$N$ loops on $x$

So any recognizer will need to figure out (in finite time) that $N$ is going to loop on some input, which is just the halting problem.


How to implement GREEDY-SET-COVER in a way that it runs in linear time This is an exercise in the book Introduction to Algorithm, 3rd Edition.

The original question is:

Show how to implement GREEDY-SET-COVER in such a way that it runs in time $O(\sum_{S\in\mathcal{F}}|S|)$.

The GREEDY-SET-COVER in the text book is as follows:

Definition for $(X,\mathcal{F})$ is given as:

Here is some Python code that should implement Greedy Set Cover in linear time:

(Warning, it empties the input sets during the processing!)

from collections import defaultdict

F = [set([1,2,3]),
     set([3,4,5,6]),
     set([2])]

# First prepare a list of all sets where each element appears
D = defaultdict(list)
for y,S in enumerate(F):
    for a in S:
        D[a].append(y)

L=defaultdict(set)
# Now place sets into an array that tells us which sets have each size
for x,S in enumerate(F):
    L[len(S)].add(x)

E=[] # Keep track of selected sets
# Now loop over each set size
for sz in range(max(len(S) for S in F),0,-1):
    if sz in L:
        P = L[sz] # set of all sets with size = sz
        while len(P):
            x = P.pop()
            E.append(x)
            for a in F[x]:
                for y in D[a]:
                    if y!=x:
                        S2 = F[y]
                        L[len(S2)].remove(y)
                        S2.remove(a)
                        L[len(S2)].add(y)

print E

It uses a dictionary D to store a list of all sets with a particular element.

It uses an array E to store which sets currently have each size.  In other words, E[sz] will contain information about all the sets that currently have exactly sz elements.

The key to showing that this is linear is to observe that the innermost loop removes an element from a set, so cannot be executed more times than the total number of elements in all sets.


How can I have constant time initialization for multi-dimensional arrays? For a regular array, I understand that if we have the tradeoff of space vs time, and we use more space to implement a Which, Data, and When pointers to the actual array, we can initialize the array in constant time because there are pointers to access and keep track of the elements in the array.

How can I extend the idea of using the Which, Data, and When pointers to have constant time initialization for multi-dimensional arrays? Would I have to have multiple Which, Data, and When pointers to keep track of n-th D array dimensions?

Or is the use of hierarchical tables, which stores multi-dimensional arrays as an array of pointers to tables, where each table contains a row of the array, and implementing the Which, Data, and When pointers to the hierarchical tables a correct way for having constant time initialization of multi-dimensional arrays?

Edit: Use C notation for simplicity. Let's say for a large N we have an array:

SomeType array[N];

If N is very large, and only a few of the array's elements are ever used, just initializing it can become the largest cost of an algorithm. A way around this is to have a self-checking structure that can be filled in on demand. To the above add (I'm not the original poster, so I will use my own names here):

int last_used = -1, place[N], order[N];

The idea is that last_used tells the last used entry, place[i] is the index of the i-th asigned element of array, and order[k] is the order in which the array[k] was initialized. Note that none of array, place and order are initialized, their initial values are arbitrary. place[i] and order[k] serve to check each other. To use array[i], see if order[i] < last_used (it is in the right range, might have been set already; if not, it is clearly garbage) and also place[order[i]] == i. If so, the element has been used, go ahead. If not, do:

last_used++;          /* Another one is in use */
place[last_used] = i; /* The next one in use is array[i] */
order[i] = last_used; /* Point back */
initialize(array[i]); /* Prepare for use */
/* Furiously frob array[i] */

The time of this is bounded by a constant; so the initialization time, amortized over the initialized elements, is constant. For a practical implementation, this can be packaged conveniently in a C++ class (templated on SomeType and N) overloading operator[].

Remark: This can clearly be extended to an array of such arrays.

It is amortized constant time, independent of the number of elements eventually used (initialized). But going to that complexity might just not be worth the time saved (if any).

A more practical way (due to Kernighan and Pike, IIRC) is to allocate an initial number of elements for a linear array, if you run out reallocate twice the number and initialize the new elements. The amortized cost is again constant for each initialized element, with less hassle. This obviosly works only for the case in which elements are added (mostly) sequentially; but if the elements are allocated haphazardly you'll probably be better off with another type of structure, like a hash table or some sort of tree.


What's the difference between declarative syntax and encapsulation? I had been first introduced to the idea of declarative syntax when using Angular JS. From what I understand, the idea is that you say, "do this" instead of "in order to do this, do this, this and this". You don't care how it's done, you just want it done, and you pass it off to some lower level of abstraction to do.

Now I'm going over the idea of encapsulation as I learn Java, and the idea seems very similar. From what I understand, the idea is that you break things up into modules, and you define an outwards-facing API for people to use. So people could use your in a declarative manner to say, "do this".

Is this true? If so, what is the real difference between declarative syntax and encapsulation? Just that one describes syntax and the other describes the more abstract design philosophy?

Edit: I think that my question boils down to: what's the difference between making a declarative statement and making an API call?

They're orthogonal.

In declarative programming, you describe what would count as an acceptable solution, without necessarily describing how to find it.  For instance, a declarative program might have rules like "if you want to install the package gcc, you must have first installed the binutils and cpp packages" and "if you want to install the binutils package, you must have first installed coreutils".  It's up to the platform to figure out a way to meet all of these constraints.

Encapsulation refers to protections that prevent the client of an API from tampering with the internal state of the service that implements the API.   Nothing here says the API has to be declarative in nature.  You could have a API that is more declarative in nature (e.g., the client provides some constraints, and the service figures out how to meet them), or you could have an API that is more operational in nature (e.g., the client specifies what actions should be performed, rather than listing the desired goal and leaving it to the service to figure out what actions will accomplish that goal).

So, you can have an encapsulated API that is not declarative in nature.

To elaborate: invoking an API is not necessarily declarative in nature.  You can design APIs that are declarative in feel; and you can also APIs that are operational in feel.  Not all APIs will be declarative.  For example:

A declarative API might let you give it some rules/constraints, and then specify the goal (I want gcc to be installed), and then let the service infer a sequence of actions that will achieve your goal (a sequence of packages to install, and what order to install them in).  For example, the client might call findWayToInstall("gcc"), and the service comes up with a sequence of packages to install that ends with gcc installed -- that'd be a declarative API.
An operational API might let you repeatedly give it an action to perform (e.g., you repeatedly invoke installPackage(); this succeeds if you've met all the prereqs, and it's up to you to identify a valid sequence of packages that ends with gcc installed).  For example, the client might call installPackage("coreutils") then installPackage("binutils") then installPackage("cpp") then installPackage("gcc"), and if this sequence of operations meets all of the prerequisites, it ends with gcc installed.  With this API it is the caller's responsibility to identify a sequence of actions that ends with gcc installed.  Thus, this kind of API is more operational than declarative in nature.

Of course, declarative vs operational are just concepts to help us talk about properties of programming languages and APIs.  There's no hard, bright line between them.  It's not black-and-white; there's a spectrum.  But they are useful concepts nonetheless.


Constructive proof to show the quotient of two regular languages is regular I have a question regarding the quotient of two regular languages, $R$ and $L$.

I saw the answers to this question: are regular languages closed under division
and the proof sketch is not constructive, because $L$ can be any language.
I'm thinking about a constructive proof when $L$ is regular: how can we construct that $F2$ group in the case when $L$ is regular?

We can't go over every word $x$ in $L$ and check if $\delta(q,x)\in F1$ in the case when $L$ is infinite...

The quotient of two languages $R$ and $L$ is
$$R/L = \left\{x\in \Sigma^{*} : \exists y \in L. xy \in R\right\}$$

Here is a constructive solution using a non-deterministic finite automaton (NFA) to show $R/L$ is regular when both $R$ and $L$ are regular.

Let $(Q_1,\Sigma,\delta_1,s_1,F_1)$ and $(Q_2,\Sigma,\delta_2,s_2,F_2)$ be deterministic finite automata for $R$ and $L$ respectively. Define a NFA

$$D=(Q_1 \times \{s_2\} \times \{1\} \cup Q_1 \times Q_2\times \{2\}, \Sigma, \delta, (s_1,s_2, 1), F_1 \times F_2\times \{2\})$$
where the transitions are:

$\delta((q_1,s_2,1),\sigma) = \{ (\delta_1(q_1,\sigma),s_2, 1)\}$.
$\delta((q_1,s_2,1),\epsilon) = \{ (q_1,s_2, 2)\}$.
$\delta((q_1,q_2,2),\sigma) = \{ (\delta_1(q_1,\sigma),\delta_2(q_2,\sigma), 2)\}$.

I'll leave it as an exercise for you to verify the language accepted by $D$ is $R/L$.