Fastest way to compute a path from a known cycle with unordered edges and vertices I have an (undirected) graph isomorphic to $C_n$ with unordered edges/vertices in some data structure (in particular, a list of tuples representing the edges), etc. I was wondering what is the fastest algorithm to compute a path which begins and ends at some given node in the cycle, given this set of nodes? The simplest thing seems to be to just use DFS, but that seems like overkill for what I'm sure is a relatively simple algorithm.

I understand your question this way:

There is given a graph with nodes and edges. There might or might not be one or more circles in that graph. And there is given a certain start-node within the set of nodes.

You ask, if this start-node is part of at least one circle, and you ask, which nodes (of which one is the given start-node) and edges form the smallest circle.

If this was your question, then I have an answer:

DFS is not the best choice. BFS is. BFS = Breadth-first-search. There is an wikipedia-article that describes this algorithm.

The idea of this algorithm is to begin to test all nodes at the end of the edges that are directly connected with the given node. This gives you a list of all direct neighboring nodes of the start-node. I call them the level-1-neighbors.

In the next step you repeat this search for each level-1-neighbors, but now you ignore all edges that directly lead back to where you did come from. The result are the level-2-neighbors. And then you repeat this for the level-n-neighbors to get the level-(n+1)-neighbors.

This transforms your graph into a new graph, which is a tree. The start-node is the root of this tree, the level-1-neighbors are the roots children, level2-neighbors are children of those children.

If your original graph contains a circle, then nodes will appear twice (or more often) in the resulting tree, because there are (at least) two different ways, that you can move through the circle to reach nodes in the circle (clockwise and counter-clockwise).

So, if a certain node appears a second time in the graph, then you have found a circle. The circle is the path starting at one representation of that node, going up till you reach the first common ancestor of both representations and then go down to the second representation.

If the common ancestor is the root node, you found the circle with the least number of nodes that goes through the given node. If the common ancestor is not the root, then you just have found a circle, that is connected with the given node by a side-arm. In this case you must go on searching.

There is an easier (but longer) algorithm for the case that there are directed edges: Use BFS until you hit the start-node for a second time. Then the path from the root to the second representation of the start-node is the shortest circle. This is simpler (you need not compare every new node with any node you already passed, but only with the root), but probably needs more resources because the tree you have to build will be deeper.

In both versions of the algorithm you must pay attention not to get lost in loops (again and again walking through circles that are not the needed circle)


How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display? I did some quick math on how much data is contained on a screen at any given instant and I ended up with a number well beyond what I thought was possible. 256 colors for Red, Green, and Blue each define a pixel and there are currently 1920x1080 pixels on my screen so..

256 x 256 x 256 x 1920 x 1080 bits = 4.35 Terabytes of data

Obviously that would require more space than is on my desktop, let alone some Raspberry pi. So how do they do it? Any other resources anyone has for learning how displays work in general I'd love to have a look.

You're confusing the number of possible values that a pixel can display with the amount of data being shown at any given instance. The number you give is the number of possible pixel states that your display can be in, multiplied by the number of pixels, which isn't really a meaningful number.

(EDIT: As Mehrdad and phihag point out, I'd incorrectly assumed you'd given the number of possible images. That number is actually $(256 \times 256 \times 256) ^ {1920 \times 1080}$, which is much larger than your number.)

The important detail is, at any time, a pixel is only in one state.

There are 256 possible values for each pixel, but we only are in one of them at any given time.

Any number between 0 and 255 can be encoded using 8-bits, just the same way you can write any number between 0 and 999999 using only 6 decimal digits. So there are 24 bits per pixel, or 3 bytes per pixel.

So 3*1920*1080=6220800 bytes, or just over 6MB.

Think of it like this, you as a person can verbally list all the digits in some 20-digit number, but you can't possibly list every 20-digit number. Your monitor could never in its lifetime display all possible images, but it certainly display one of those images.


Using Yao's principle to find a lower bound This is a HW question, so I'm not expecting any answers, just a general guidance/help.

Definition. Given $\underset{\neq0}{\underbrace{s}}\in\left\{ 0,1\right\} ^{n}$, a function $f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{n}$ will be called s-difference-preserving if for all $x,y\in\left\{ 0,1\right\} ^{n}$ s.t. $x\neq y$: $x\oplus y=s\iff f\left(x\right)=f\left(y\right)$ (where $\oplus$ is the bitwise xor operation).

Given a difference-preserving (that is, there exists such s so it is s-difference-preserving) function $f$, we talk about algorithms that find such $s$.

We need to prove that every such random (las-vegas) algorithm worst case (w.c. input) average (on the randomness of the algorithm) complexity is $\Omega\left(\sqrt{2^{n}}\right)$.
Where by complexity, we talk about query-complexity. That is, how many times we need to query f, to find a value for an input $x$ - that is, find $f\left(x\right)$.

What I know and tried so far:

I assume this is a classic problem for Yao's principle.
So I want to find a distribution, and an optimal deterministic algorithm for it (optimal on average, on that distribution), such that its query-complexity is \Omega\left(\sqrt{2^{n}}\right) on average on that distribution.

Given an $s$, it's easy to create an s-difference-preserving function, since any $s$ defines a partition of pairs on $\left\{ 0,1\right\} ^{n}$. So we just need to choose a different value for every pair $x,y$ s.t. $x\oplus y=s$.

I also know $f\left(0\right)=f\left(s\right)$, and that to find $s$ for a fuction, it's enough to find a pair $x,y$ s.t. $f\left(x\right)=f\left(y\right)$, and then calculate $x\oplus y$.

I thought of defining $\forall i\in\left[\sqrt{2^{n}}\right]:\ s_{i}=i\cdot\sqrt{2^{n}}-1$. And create $s_{i}$-difference-preserving function $\forall i\in\left[\sqrt{2^{n}}\right]$.

Define a uniform distribution on them and have the deterministic algorithm check the values of every $s_{i}$. This is done in $\sqrt{2^{n}}$ queries on average. But I don't know how to prove this algorithm is optimal for that distribution. Furthermore, I suspect it isn't, since then I would be able to do the same with $s_{i},\ \forall i\in\left[2^{n}\right]$ and “prove” a lower bound of $2^{n}$ which is probably not true.

I would love any help with this.Also, not as part of the HW, but because I'm interested (these are questions we don't need to submit a solution to), can you think of any deterministic algorithm for the general problem? can you think of any monte carlo random algorithm (with 0.5 chance of success)?

I hope this is not too long, and written clearly enough. Would appreciate any help. Thanks!

Suppose that there exists a Las Vegas algorithm $A^f$ asking $q(n)=o\big(2^{n/2}\big)$ queries. Let $Q_f\subseteq\{0,1\}^n$ be the random variable which denotes the set of queries raised by the algorithm with oracle $f$.

Sample $f$ from the uniform distribution over the collection of all difference preserving functions, and choose $s\in\{0,1\}^n$ uniformly at random, both independently from your algorithm's coins. Let us now ask what is the probability that there exists $g,g':\{0,1\}^n\rightarrow\{0,1\}^n$ such that $g,g'$ agrees with $f$ on $Q_f$, $g$ is $s$-difference preserving, and $g'$ is not. We denote this probability by $p_A$. Note that if $p_A>0$ then your algorithm cannot respond correctly on all inputs, since there exists $f,s$ such that $f|_{Q_f}$ has both $s$-preserving and non $s$-preserving extensions.

If $f|_{Q_f}$ does not have an $s$-preserving extension, then either there exists $x\in Q_f$ such that $x\oplus s\in Q_f$, or we have $x,y\in Q_f$ with $f(x)=f(y)$. For the first case, Note that $x\oplus s$ is uniformly distributed over $\{0,1\}^n$ and independent of $Q_f$, thus the probability that there exists such $x$ is bounded by $\sum\limits_{x\in Q_f}\frac{|Q_f|}{2^n}\le\frac{q^2(n)}{2^n}=o(1)$. A similar bound is obtained for finding a collision for a random $f$ (the preimage of any element in the range of $f$ is of size 2). Additionally, $f$ is not $s$ preserving with probability $\ge\frac{1}{2^n}$, so we can also (with high probability) find a non $s$ difference preserving extension for $f$.


Algorithm to determine if an interval is covered by a list of intervals? Given a list of intervals $[s_1, e_1], [s_2, e_2], \ldots$, what's the most efficient way to determine if an interval $[a, b]$ can be covered by the intervals in the list?

I don't know if it's the most efficient algorithm, but here's my suggestion:

Your problem is somewhat similar to balancing parenthesis: you can put all $s_i$ and $e_i$ values on a list and sort it (Lets call this list $V$), but keep the type of each element ($s$ or $e$ element) attached to the value. Then use this list to integrate all the intervals with the following algorithm (uniting overlapping intervals to one interval):

create a list of intervals L, Create a stack St
for every element n in the sorted list V (from the smallest to the largest)
{
    if n is an s element and St is empty
    {
         create a new interval I (a pair of numbers)
         assign I.s = n
         push some value to St
    }

    else if n is an s element and St isn't empty
    {
         push some value to St
    }

    else if n is an e element (stack can't be empty here)
    {
         pop a value from St
         if St is empty
         {
               assign I.e = n
               add interval I to the interval list L
         }
   }
}

return L

Now you have a list of integrated intervals, and checking if $[a,b]$ si covered by one of them is easy: for every interval $I$ in $L$, check if $a \geq I.s$ and $b \leq I.e$ (there are no overlapping intervals in $L$ now, they were integrated in the previous step).

Integrating the intervals to create $L$ takes $O(n)$ computation time and so is checking if $[a,b]$ is covered by one of the intervals in $L$, which makes the sorting $V$ the most expensive task here, $O(n\log{n})$.

Hope this helps, though there might be a linear time algorithm for performing this task...


Is it valid to make an admission of a topological space by a "partial quotient map"? It is well-known that the Sierpiński space, $\{F,T\}$ endowed with topology $\{\emptyset, \{F\},\{F,T\}\}$, is admissible. I tried to implement it in Haskell.
First I implement $\mathbb{N}$ (including zero; some topologists might prefer denoting it by $S_\omega$) by Peano definition:
data Peano = Zero | Succ Peano deriving (Eq, Ord)

This encodes $\mathbb{N}$, but there is one additional value lurking behind: fix Succ. I denote it by $\omega$, and I denote $\mathbb{N} \cup \{\omega\}$ by $\overline{S_\omega}$. We observe that $\overline{S_\omega}$ is in order topology.
I abuse this fact and implement the Sierpiński space by taking a quotient space. The quotient map $q$ is:
$$
q(o) =
\begin{cases}
F & \text{if } o < \omega \\
T & \text{o.w.}
\end{cases}
$$
In Haskell, This can be realized by:
newtype Sierpinski = Sierpinski Peano

instance Eq Sierpinski where
    Sierpinski m == Sierpinski n = let
        q m = case m of
            Zero   -> False
            Succ n -> q n
        in q m == q n

But to think about it, q doesn't halt on $\omega$. In other words, q is partial, and doesn't match $q$. Is this really a valid implementation of the Sierpiński space?

When we implement a space we do not actually implement the space itself, but rather a representation of it. That is, an implementation of $X$ consists of a datatype $T$ and a partial surjection $\delta : T \to X$, as in Type Two Effectivity. When $\delta(p) = x$ we say that the datatype value $p \in T$ represents or realizes the point $x \in X$. Cruicially, there may be many values that represent the same point. Only $T$ exists in the computer, $X$ and $\delta$ are mathematical objects. A particularly well-behaved kind of representation is an admissible one, as you mention.
In your case, you correctly implemented an admissible representation of the Sierpinski space: $X$ is the Sierpinski space, $T$ is Sierpinski, and the surjection $\delta$ maps $\omega$ to $\bot$ and $\mathtt{Succ}^n \,\mathtt{Zero}$ to $\top$. There is no need for further quotienting.
The attempt to define == on Sierpinski is not about quotienting, but rather trying to define the characteristic map $\mathrm{eq} : X \to \{0,1\}$ of equality as a map into Booleans, which is only possible when the space is discrete. You discovered that the Sierpinski space is not discrete.
If we have a representation $\delta : T \to X$ then we can form the representation of a quotient $Y = X/{\sim}$ as $\delta' : T \to Y$ where $\delta'(p) = [\delta(p)]_{\sim}$. That is, quotienting affects the map but not the datatype.


Detection of redundant boolean constraints I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin transformation. From the nature of my problem I know that there are redundant constraints. For example, I have a rule:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4)) \,\,\,\,\,\,(1)$$

and another:
$$AND\:(OR\: (x1,x2),\: OR\: (x3,x4), \:OR\:(x5,x6))\,\,\,\,\,\, (2)$$
where $x_i$ are inputs. Both constraints have in common subnodes, for example $OR (x1,x2)$. Due to this I know that there is no point in having both constraints - if the first one becomes FALSE, then the second equals FALSE too. So the second one is redundant. This example is the easiest. One more, closer to what might be found in my formula:
$$AND\:(x1,\:x2,\: OR \:(AND \:(x3,x4), \:AND\:(x5,x6)))\,\,\,\,\,\,(3)$$
and the second one:
$$AND\:(x3,x4)\,\,\,\,\,\,(4)$$
In this case, I can simplify the first one to the form of:
$$AND\:(x1,\:x2,\:AND\:(x5,x6))\,\,\,\,\,\,(5)$$
due to (4).

I prefer to have a lot of small rules (by a lot I mean $10^3$ or $10^4$, which in CNF become $10^5-10^6$ of clauses).  The rules are not complicated - 10 ANDs and ORs and 20-30 inputs per rule at most, but they are usually much simpler.

Is there an efficient way to remove such redundancy from a formula? Is it possible with CNF formulation or I should use some other representation of the formula (BDD, for example)?  Any help and directions will be useful.

The simplification you're describing is called subsumption.  It's a standard technique and some SAT solvers (e.g. minisat) will apply it along with other simplification techniques as a preprocessing step before attacking the SAT problem itself.  In particular, subsumption and equivalent variable substitution together, applied to the generated CNF formula, are enough to do the common subformula elimination you described in the question.  That's because each circuit transformation yields an output variable, and output variables derived from the same circuit can be efficiently identified and reduced to references to a single variable.  After that normal subsumption rules applied to clauses will eliminate the common subformulas.

If you're using a solver that doesn't do this preprocessing, then you can do thr rough equivalent of it during conversion to CNF.  First you'll need to apply duplicate circuit suppression while you're doing the Tseitin tranformation.  As you're doing the transformation to CNF, memoize each circuit you've converted. If you encounter the circuit again, skip the circuit conversion and use the same output variable that you used for the memoized circuit.  Once you've converted everything to clauses, do normal clause subsumption, i.e. check each clause A against every other longer B clause to see if A's literals are a subset of B's.  If so, then A subsumes B and clause B can be discarded from the formula.


Equivalence relation Mathematical base In Computer science I have this equivalence relation problem:

Let $R$ and $S$ be two equivalence relations on the same set $A$. Define a new relation $U$ such that $U(x,y) \leftrightarrow [R(x,y) \text{ or } S(x,y)]$. Is $U$ necessarily an equivalence relation?

I said that is was an equivalence relation because $U$ is only true if $R$ or $S$ is true, and only depends on one. I do not know know exactly how to explain it, or prove this. Should I use proof by contradiction to prove this and make the negated statement $!U(x,y) \leftrightarrow {![R(x,y) \text{ or } S(x,y)]}$ and from this we can see that $U$ is an equivalence relation because the negation is saying that $R(x,y)$ or $S(x,y)$ isn't an equivalence when it actually is?

I am kind of stuck so any help is appreciated.

In order to prove that $U$ is an equivalence relation, you need to use the definition: prove that $U$ is reflexive, symmetric and transitive. If you try to do that but it doesn't work, you can try to disprove the claim that $U$ is always an equivalence relation by giving a counterexample: equivalence relations $R$ and $S$ such that the corresponding $U$ isn't an equivalence relation (that is, it either isn't reflexive, isn't symmetric or isn't transitive); you can use your failed proof attempts to guide you in the construction.


Number of independent parity checks satisfied by a code I have been studying quantum error correction codes and as background, I am currently studying the theory of classical linear codes. Despite many efforts, I am unable to understand the following excerpt:

Any given parity check u divides Hamming space exactly in half,into those vectors which satisfy u and those that do not.Therefore,the 2^k vectors of a linear subspace in 2^n Hamming space can satisfy at most n−k linearly independent parity
checks.These parity checks together form the parity check matrix H, which is another way to define the
linear subspace.

Any given parity check $u$ divides Hamming space exactly in half, into those vectors which satisfy $u$ and those that do not.

Suppose your Hamming space is $X = \{0,1\}^n$. A non-zero parity check $u$ divides $X$ into two sets: $X_0 = \{ x \in X \mid \langle x,u \rangle = 0 \}$ and $X_1 = \{ x \in X \mid \langle x,u \rangle = 1 \}$. The two sets have equal size $2^{n-1}$.

Indeed, let $v$ be some non-zero vector such that $\langle u,v \rangle = 1$ (for example, $v$ could contain a single 1 entry, at some index in which $u$ also has a 1 entry). If $x \in X_0$ then $x + v \in X_1$, and conversely, if $x \in X_1$ then $x + v \in X_0$. Hence we can partition $X$ into pairs $(x,x+v)$ in which the first member is in $X_0$ and the second in $X_1$.

Here are two illustrating examples. If $u = (1,\underbrace{0,\ldots,0}_{n-1\text{ copies}})$ then $X_0$ consists of all vectors with 0 in the first coordinate, and $X_1$ consists of all vectors with 1 in the first coordinate. If $u = (\underbrace{1,\ldots,1}_{n \text{ copies}})$ then $X_0$ consists of all vectors with even parity, and $X_1$ consists of all vectors with odd parity.

Therefore, the $2^k$ vectors of a linear subspace in $2^n$ Hamming space can satisfy at most $n−k$ linearly independent parity checks. The statement here actually doesn't follow from the preceding statement. However, it is similar in spirit (and a generalization of the preceding statement). Earlier we have considered a single parity check $u$. We showed that if $u$ is non-zero, then the set $\{x \in X \mid \langle x,u \rangle = 0\}$ contains exactly half the space. If $u = 0$ then it consists of the entire space.

Now we are considering the common solutions of $m$ different vectors $u_1,\ldots,u_m$. The set $C = \{x \in X \mid \langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0\}$ contains at least $2^{n-m}$ vectors. If the vectors are linearly independent (this generalizes the condition $u \neq 0$), then $C$ contains exactly $2^{n-m}$ vectors. More generally, $C$ contains $2^{n-d}$ vectors, where $d$ is the dimension of the linear span of the vectors $u_1,\ldots,u_m$. I won't prove all these statements, but this is basic linear algebra.

If $C$ is a linear subspace containing $2^k$ vectors, and every element $x \in C$ satisfies $\langle x,u_1 \rangle = \cdots = \langle x,u_m \rangle = 0$, then the dimension of the span of $u_1,\ldots,u_m$ is at most $n-k$, per the discussion above. If we know that $u_1,\ldots,u_m$ are linearly independent, then the dimension of their span is $m$, and so $m \leq n-k$.

These parity checks together form the parity check matrix $H$, which is another way to define the linear subspace.

We can describe a linear code in two ways. One is using a generator matrix $G$: the linear code consists of all linear combinations of the rows. The other is using a parity check matrix $H$: the code consists of all vectors whose inner product with each row is 0. (Some books use rows, other columns.) Using our earlier notation, the rows of $H$ are just the vectors $u_1,\ldots,u_m$, where we insist that the vectors be linearly independent (the same holds for generator matrices).

Here is an example. Let $n = 3$, and consider the code whose generator matrix is
$$
\begin{bmatrix}
1 & 1 & 0 \\
1 & 0 & 1
\end{bmatrix}
$$
(We note that the same code has many generator matrices, and many parity check matrices.)

The code consists of all linear combinations of the rows:
$$
\begin{matrix}
0 & 0 & 0 \\
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1
\end{matrix}
$$
You can check that these are exactly the vectors with even parity. Hence a parity check matrix for this code (in this degenerate case, the unique parity check matrix) is
$$
\begin{bmatrix}
1 & 1 & 1
\end{bmatrix}
$$
We can also treat this as a generator matrix of a code. The resulting code is known as the dual code (dual to the code for which this matrix functions as a parity check matrix).


What happens if you run Kosaraju’s algorithm on a DAG? What happens if you run Kosaraju’s algorithm for finding strongly connected components of directed graphs on a DAG?

We should think about the property of SCC(strongly connected component)

A directed graph $G(V, E)$ is acyclic if and only if $G$ has no SCCs with more that one vertex. Because a directed cycle is SCC by definition of the cycle.

Hence, the result of the Kosaraju’s algorithm on a DAG will return $|V|$ trivial SCCs. In other words, it returns $\{\{v\}\mid v\in V\}$.


Does the undecidability of the halting problem require Turing Machines to be enumerable? I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the enumeration. Did I miss anything?

(define (run-forever) (run-forever))

(define (try p)
  (if (halts? p p)
      (run-forever)
      'halted))

I suspect this has to do with how a TM is encoded, i.e. the parameter for try. Being able to encode a TM might require enumeration? But I'm still very confused.

No, being able to enumerate Turing machines is not directly relevant.

Let us consider some abstract notion of algorithm. The ingredients for the undecidability are as follows:

The Halting problem makes sense. This means that

a) Algorithms can "halt" on some inputs, and fail to "halt" on others. Halting allows the algorithm to output something, eg "Yes" and "No".

b) Algorithms can take algorithms as input.
Algorithms allow if-then-else branching
There is an algorithm that takes an algorithm as input, and simulates how the input-algorithm would act.

The code snippet in the question is essentially how you do it, and the criteria above are essentially saying "this code snippet is valid pseudoc-code for our abstract notion of algorithm".

To see that the fact that TMs can be enumerated really does not factor in, one can look at models of computation such as the BSS-machines. These can have arbitary real numbers as parameters in the code, so there are uncountably many machines. However, they still meet all criteria above, and thus the standard argument shows that BSS-machines cannot decide the BSS-Halting problem.


Why the 127 encodings of ASCII needed to be extended to 256? As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still Can't understand what that has to do with the ASCII Chart.

Can anyone explain the full story?

ASCII has 128 characters. Many countries had similar encodings for 128 characters. That is all history. Nobody uses ASCII anymore. There was a phase with lots of different encodings for more than 128 characters, some with 256 (Mac Roman and Windows 1152 were quite popular) and some like the Chinese GB with thousands of characters.

Nowadays people mostly use Unicode, with a bit over a million code points, which can be further combined to produce more characters. There are plenty of unused code points which can be assigned values in the future, and that happens all the time.

Please note that for most people English is a foreign language. And it would be “naïve” to think that ASCII let’s you write all English text.


Equivalence of regular grammars I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving that two regular grammars recognize the same language decidable?

Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert each DFA to a canonical minimum DFA, then decide whether the two DFAs are equivalent. Each transformation preserves the language represented, so this ultimately decides whether the two grammars have the same language.


can it be said that NL^NL = NL? I was wondering if it can be said that $\mbox{NL}^\mbox{NL}=\mbox{NL}$. That is, a decision problem  $S$ can be decided using a nondeterministic TM using logarithmic space with oracle calls to $S'\in \mbox{NL}$ iff $S\in \mbox{NL}$.
My intuition is yes, because if $S'\in \mbox{NL}$ then there is a NDTM $M$ that decides it in logarithmic space. And so one can use the NDTM $M'$ for $S$ but every oracle call will be simulated on $M$, preserving the logarithmic space constraint.
I am not sure if this approach is correct, and if it is, how to formally explain such an algorithm for the simulation.

It's not quite as simple. Calls to oracle have a "magic" quality of taking only one unit of time. Even if NL can simulate the oracle calls, these simulated invocations of the oracle can take more resources than is needed by the oracle machine. To prove these classes equal you need to prove that calls to the oracle do not improve performance in the computational complexity sense because producing the input to the oracle already requires sufficient resources that the oracle machine cannot use this "magic" to get improved performance.


Is the language of binary representation of perfect squares regular? Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$.  Let $L = \{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \}$.

  Is $L$ a regular language?

I think one can prove that $L$ is not regular by using the pumping lemma, but I don't know how to use it here.

We start with a lemma.

Lemma. Let $a>b \geq 4$. If $2^a+2^b+1$ is a square then $a \geq 2b-3$.

Proof. Let $2^a+2^b+1 = x^2$. Clearly $x$ must be odd, say $x = 2y+1$. Then $x^2 = 4y^2 + 4y + 1$, and so $(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$. If $y$ is even then $y+1$ is odd and so $y = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$ and so $a \geq 2b-2$. If $y$ is odd then necessarily $y+1 = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Since $b \geq 4$, we can conclude that $a \geq 2b-3$. $\square$

Let $L' = L \cap 10^*10^*0001$. According to the lemma, all words in $L'$ are of the form $10^{a-b-1}10^{b-1}1$ with $a-b-1 \geq (b-1)-3$. Moreover, since $2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$, for all $c \geq 3$, $10^{c-2}10^c1 \in L'$.

If $L$ is regular then so is $L'$, say its minimal DFA has $p$ states. Consider the word $10^{p-2}10^p1 \in L'$, and mark the substring $0^p$. The extended pumping lemma shows that for some $0 < q \leq p$, $10^{p-2}10^{p+q(t-1)}1 \in L'$ for all $t \geq 0$. However, according to our lemma, for all $t$ we must have $p-2 \geq p+q(t-1)-3$ and so $1 \geq q(t-1)$, which is false for $t \geq 3$.


Is the 0-1 Knapsack problem where value equals weight NP-complete? I have a problem which I suspect is NP-complete. It is easy to prove that it is NP. My current train of thought revolves around using a reduction from knapsack but it would result in instances of 0-1-Knapsack with the value of every item being equal to its weight.

Is this still NP-complete? Or am I missing something?

Yes, this is called the subset-sum problem and is NP-Hard.


Difficult Question to Understand (Computer Artitechture) You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is the minimum number of bits of state in the controller?

Answer: The system has at least five bits of state to represent the 24 floors that the elevator might be on.

Can someone explain how this comes to be?

Well, as binary typically goes, one bit represents two possible values: 0 and 1. With two bits there are a possible combination of four values: 0, 1, 2, 3 in hex/decimal/octal or 00, 01, 10, 11 in binary. Expand out to three bits you have eight values. 0 to 7 or 000, 001, 010, 011, 100, 101, 110, and 111.

Expand upon this and you'll have your understanding.

For reference (with a nice animation for counting on any base): https://www.mathsisfun.com/binary-number-system.html


How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights? Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see [1] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle.

The proof in [1] makes use of binary search with a search space from weight $0$ to the sum of all weights. But I am struggling with the fact that the weights could very large. For example: Let $\{c_1, ..., c_m\}$ be a set of clauses where some clause $c_i$ has weight $w_i = 2^{2^{m}}$. Then binary search will take $log_2(2^{2^{m}}) = 2^m$ steps in the worst case, which is exponential in the input length $m$.

What am I missing?

Reference:
 [1] Papadimitriou - Computational Complexity (1994)

The input length is not $m$. To represent an integer of $2^{2^m}$, one needs $\log_2{2^{2^m}}=2^m$ bits. Hence an algorithm taking $2^m$ steps is considered linear in the input length, which is $2^m$.

A number like $2^{2^m}$ can be represented by just giving $m$, but it is usually assumed that numbers are given in binary. And the result that MAX-SAT is in $FP^{NP}$ only holds when that encoding is used.


Regular expression for words containing single 1 and even number of 0s What would be a regular expression for the language of words containing a single 1 and an even number of 0s?

If a word contains exactly one 1 and an even number of zeroes, then we can decompose it in one of two different ways:

An even number of 0s, followed by 1, followed by an even number of 0s.
An odd number of 0s, followed by 1, followed by an odd number of 0s.

You take it from here.


Proof of QuickSort algorithm correctness Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

Pick an element from the array (no matter which one and how in this context)
Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: why does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear proof that algorithm does really work in a way they describe. So I’m looking for such a proof.

I realize that:

Array of one element (i.e with length 1) is already sorted.
After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

https://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Lectures/comp250-lecture17.pdf
Trying to understand this Quicksort Correctness proof
https://course.ccs.neu.edu/cs5010sp17/Efficiency/quicksort5.html

First, you need to write down your algorithm that you call "Quicksort" precisely. The devil is in the detail, and if your code doesn't get the details right, then it won't sort correctly (or you won't be able to prove that it sorts).

And then you need to use complete induction: Take the induction statement S(N) "My algorithm will sort any subarray with n ≤ N items correctly". The more obvious statement S'(N) "My algorithm will sort any subarray with N items correctly" isn't strong enough.

Next you prove S(1): If the array has 0 or 1 elements, does your algorithm sort it correctly? Most implementations will check that there are two or more elements as their very first step, and subarrays with 0 or 1 elements are sorted, so this should be no problem.

Then you need to prove that S(N) implies S(N+1). If S(N) is true, then any subarray of size n ≤ N will be sorted correctly, so only the case of an array with N+1 elements needs to be handled. Here you have to prove that one Quicksort step will divide an array of N+1 into two subarrays of size ≤ N, with each element of the left subarray <= each element of the right subarray, and no overlap.

PS You will always end up with an induction proof, more or less disguised. For example: Assume there is an array that doesn’t get sorted correctly by Quicksort. If there is any array, then there must be a smallest array that doesn’t get sorted. Take that array, pick the pivot and create two sub arrays, a left one and a right one. Sort both sub arrays with Quicksort. Since they are both smaller than the smallest array that isn’t sorted correctly, they will be sorted correctly. So Quicksort works.

That’s a property of the integers: if a set of positive integers is not empty, then it has a smallest element. Take the set of all sizes of arrays that are not correctly sorted by Quicksort. If that set is not empty, then it has a smallest element, and therefore there is a smallest array that cannot be sorted. And then you prove that the smallest array that cannot be sorted can indeed be sorted, so your assumption that some array cannot be sorted was wrong.


Proving that finding wheel subgraphs is NP-complete Can you help me with this problem ?

  Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.

Hint: Hamiltonian Cycle is $NP$-Complete.


Optimal quantization of histogram I have a histogram of occurrences, as a list of counts (non-negative integers). For the purposes of a compression algorithm (specifically arithmetic coding) I must quantize these occurrences into a histogram whose entries sum to $2^n-1$.

To maintain sanity, I require some properties of the quantization algorithm:

Any element with 0 occurrences must have 0 occurrences after quantization.
Any element with > 0 occurrences must have > 0 occurrences after quantization.
The sum of the quantized histogram must add up to $2^n-1$.

To guarantee that there is a satisfiable solution there will be no more than $2^n-1$ elements.

Given those constraints the values of the quantized histogram $Q$ must proportionally be as close as possible as the values of the original histogram $H$.

Or more formally:
$$\forall i: H_i > 0 \rightarrow Q_i > 0$$
$$\forall i: H_i = 0 \rightarrow Q_i = 0$$
$$\Sigma Q = 2^n-1$$
$$\min \sum_i (H_i/\Sigma H - Q_i/\Sigma Q)^2$$

Is there a direct algorithm that gives an optimal result? Or perhaps a fast near-optimal approximation?

Without requirement #2 there is a solution by choosing $Q_i = \lfloor H_i/\Sigma H \cdot (2^n-1) \rfloor + a_i$. Where $a_i$ is initially 0 for all $i$. It's easy to see that $\Sigma Q \leq 2^n-1$, and setting $a_i$ = 1 for the $2^n-1 - \Sigma Q$ elements that have the biggest undershoot error solves the problem optimally.

The difficulty lies in the requirement that no element with nonzero occurrences may be floored to zero occurrences in the quantized histogram. Consider [1, 1, 1, 1000]. Without this requirement the most accurate quantization to $n = 3$ is [0, 0, 0, 7]. However the requirement gives us [1, 1, 1, 4].

This can be reduced to the following problem.

APPROXIMATE ROUNDING:
Input: real numbers $c_1,\dots,c_m \in \mathbb{R}$, an integer $d \in \mathbb{N}$
Goal: find non-negative integers $x_1,\dots,x_m \in \mathbb{N}$ that minimize
$\sum_i (x_i - c_i)^2$, subject to the requirement $\sum_i x_i = d$.

The reduction: define $S = \{i : H_i > 0\}$, $x_i = Q_i - 1$ for $i \in S$, $d=2^n-1-|S|$, and

$$c_i = -1 + (2^n-1) H_i / \sum_j H_j.$$

Now the optimal solution to APPROXIMATE ROUNDING immediately yields the optimal solution to your problem, by setting $Q_i = x_i + 1$ for each $i \in S$ and $Q_i=0$ for each $i \notin S$.

Can we solve APPROXIMATE ROUNDING efficiently?  I don't know.  I conjecture there exists $t \in \mathbb{R}$ such that the optimal solution is $x_i = \lfloor t c_i \rceil$ for all $i$ (i.e., $x_i$ is $tc_i$ rounded to the nearest integer).  If this is true, we can use binary search to find $t$ such that $\sum_{i \in S} \lfloor t c_i \rceil = d$, and thereby solve APPROXIMATE ROUNDING efficiently.  However, I have no proof that this works.

Erwin Kalvelagen over on Math.SE has suggested that APPROXIMATE ROUNDING can be solved using a MIQP solver.


How fast can we identifiy almost-duplicates in a list of strings? I'm having trouble figuring out the upper bound running time for this scenario:

Input:

$N$ number of strings
$M$ upper bound of string length
$T$ threshold for edit distance (2 strings with a Damerau-Levenshtein edit distance lower than $T$ are considered "duplicate")

Expected values

$N \approx 1,000,000$

$M \approx 200$

$T \leq 2$

The algorithm should do the following:

For each string in the list, find any other items in that list that have an edit distance smaller than some threshold, and mark them as "duplicate" (e.g. add them to some other list that tracks duplicates)

I'm having trouble calculating the upper bound for the optimal solution

What is the most optimal upper bound for such an algorithm?

I guess first I need to understand what is the best algorithm for the edit distance itself (is it $O(M \cdot N)$?) then it's simply $N^2$ times that, right? so it is surely "slower" than $N^2$ but my question is how slower?

Comparing two strings

Algorithms for computing the Levenshtein edit distance between a pair of strings can be found in the Wikipedia page on the edit distance.  As that page explains, the running time for computing the edit distance between two strings of length $M$ is $O(M^2)$ time and $O(M)$ space.  If you only care about whether the edit distance is $\le T$ or $>T$, then the running time can be reduced to $O(MT)$ time and $O(M)$ space.

Algorithms for computing the (full) Damerau-Levenshtein distance are linked to on the corresponding Wikipedia page.  As Wikipedia explains, the (full) Damerau-Levenshtein distance can be computed in $O(M^2)$ time and $O(M^2)$ space; the algorithm is found in the Lowrance and Wagner paper cited there, or in Appendix A of the Bard paper cited there.

Wikipedia also shows how to compute what is known as restricted Damerau-Levenshtein edit distance; that is considerably easier than computing the full Damerau-Levenshtein distance, and the restricted Damerau-Levenshtein edit distance can be computed using a simple modification to the standard dynamic programming algorithm for the Levenshtein edit distance.  The running time is $O(M^2)$, and it can be reduced to $O(MT)$ time if you only care about whether the distance is $\le T$ or $>T$.

Wikipedia also claims that for spelling correction and typo detection in natural language, the restricted Damerau-Levenshtein edit distance rarely differs from the full Damerau-Levenshtein distance, so you might as well use the restricted distance as it is easier to understand and implement.  I have no personal knowledge of this; just passing along what is claimed in Wikipedia.

I recommend reading Appendix A of the Bard paper cited at Wikipedia for further implementation details.

Comparing all pairs: naive computation of pairwise distances

Therefore, the naive algorithm of computing the edit distance between each pair of strings will take $O(N^2 MT)$ time and $O(M)$ space.

However, for real-world problems of the sort you mentioned, this naive algorithm is typically not optimal.  If $T$ is fairly small, there are much better algorithms; the best algorithm depends heavily on $T$.  But since you haven't specified $T$ in your question, you haven't provided us enough information to suggest a specific algorithm.

Comparing all pairs: better data structures

A related problem is: given the set of $N$ strings, compute a data structure that allows us to quickly find the closest one in the set to any given string (under edit distance as our measure of "closeness").  There is lots of theoretical work on this problem, e.g., using BK-trees, Levenshtein automata, and many other techniques.  See especially Efficient map data structure supporting approximate lookup and  https://cstheory.stackexchange.com/q/4165/5038 for an entry into the literature.

In your case, this might be overkill, though.

The case where $T=1$: sorting

In the special case where $T=1$, there is a clean algorithm.  In other words, we want to consider two strings $X,Y$ if their edit distance is $1$ (i.e., $X$ can be transformed into $Y$ with a single insertion, deletion, or substitution, transposition).

Notice that if $d(X,Y)=1$, then the single difference must appear in either the first half of the string or in the last half of the string.  In other words, either the first half of $X$ matches the first half of $Y$ (they have a long matching prefix), or the second half of $X$ matches the second half of $Y$ (they have a long matching suffix).

This immediately suggests a nice two-stage algorithm:

Sort the entire list of strings.  For each string $X$, enumerate all other strings $Y$ that agree with $Y$ in its first half and check whether any of them are at edit distance $1$ from $X$.  This can be done through a linear scan of a short contiguous stretch of the sorted list, and the start and end of that stretch can be found quickly with binary search.
Next, reverse all the strings and do the same thing again.

(Note that you need to be a little bit careful about the definition of "half" above, to take into account that $X,Y$ might differ in their length.  However these pesky details can be easily worked out with a little bit of care.)

The space requirement is $O(N)$.  Sorting takes $O(N \lg N)$ time.  If you're lucky and the strings are fairly random, then hopefully each string will have only a small number of other candidates that match in the first half or last half.  If this is the case, the running time might be in the vicinity $O(N \lg N)$.

Does this generalize to $T>1$?  Maybe, but it gets messier.

One way to try to generalize is to split the string into $T+1$ equal-length segments, and note that if $d(X,Y)\le T$, then there must be some segment where they match.  However, this runs into messy details because the length of $X$ might differ from the length of $Y$. Therefore, if $T>1$, I don't recommend this approach.

Another way to try to generalize is to break each string down into different fields: say the street address, the city, the country, the postal code.  Now if two addresses $X,Y$ have edit distance $\le 2$, then either (a) some field of $X$ is at edit distance $2$ from $Y$, and all other fields match exactly, or (b) there are two fields where they have edit distance $1$, and all other fields match exactly.  You can find all matches of type (a) by, for each field, building a hashtable keyed on everything but that field; now any two strings that match will be mapped to the same hash bucket, so you just need to solve the problem separately for each bucket.  You can also find all matches of type (b) similarly.  This might be more promising, depending upon the structure of your problem.

Pragmatics

In practice, there are some techniques that I suspect will probably be helpful.  One is to try to use spell-correction on each field of the address first, and then use the spell-corrected addresses to look for duplicates (confirming them by reference to the original value).

Another possible heuristic might be to map each address to geographical coordinates on the sphere, and look for pairs of addresses that are locally very near each other.  This won't detect typos in (say) the country or state, but it might be helpful in detecting typos in (say) street address, by reducing the set of pairwise comparisons you need to make.

Other resources

You might also like to look into the literature on how to build fast spell checkers, as that is a closely related problem.  Take a look at Peter Norvig's article on that problem: http://norvig.com/spell-correct.html


Can the complement of a non-recursive language be RE I've got a problem where I need to check the validity (i.e to say whether it's true or false) of the following statement:

  Complement of a non-recursive language can NEVER be recognized by any turing machine.

How I've thought of this is that, if a language $\mathcal{L}$ is non-recursive, there is no turing machine that accepts the language. That is, there's no TM that halts for every string in $\mathcal{L}$. But there could be a TM $M_1$ that halts for some of the strings in $\mathcal{L}$.

Now suppose, the proposition is $\ false$. So there could be a TM ${M_2}$ that recognizes the complement of $\mathcal{L}$. So ${M_2}$ halts and accepts every string that is NOT in $\mathcal{L}$ and may or may not halt for strings in $\mathcal{L}$.

Intuitively, It appears that ${M_1}$ and ${M_2}$ could be same, which makes my assumption $\ true$. That is the the proposition is $\ false$.

But I'm not certain about the arguments I've made (as the equivalence of $M_1$ and $M_2$ is based on intuition). Can someone verify whether I'm correct or correct me otherwise.

From your question I believe there is some confusion of the terms being used here. A recognizable language L is one such that a turing machine exists accepting it,  halting on every yes instance. There are also co-recognizable languages, those are languages whose complements are recognizable. Now, if a language happens to be both recognizable and co-recognizable, it is recursive, or decidable (why?). So a language can be non-recursive, but it may still be recognizable or co-recognizable. What can you say about the emptiness problem for turing machines $E_{TM} = \{\left < M \right >\ :\ \mathcal L(M) = \varnothing\}$ ?


$T(n)=2T(n/2)+n\log n$ and the Master theorem According to  Introduction to algorithms by Cormen et al,
$$T(n)=2T(n/2)+n\log n$$ is not case 3 of Master Theorem. Can someone explain me why?

And which case of master theorem is it?

$\log n$ grows slower than $n^\epsilon$ for any $\epsilon>0$. Thus $n\log n$ grows slower than $n^c$ for any $c>1$. However, the third case of the Master theorem requires the existance of a $c>1$ so that $n\log n$ grows at least as fast as $n^c$ (up to a constant factor).

The function is covered by the second case of the Master theorem as given in Wikipedia.


Is this probability distribution data structure already discovered? Problem formulation

I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, w_2, \dots, w_n > 0$, upon request each $a_i$ may be returned with probability
$$\frac{w_i}{\sum_{j = 1}^n w_j}.$$

A Java implementation of my data structure can be obtained here, yet I will specify the algorithm here textually:

There are two types of nodes, relay nodes and leaf nodes. The actual elements with their actual weights are stored in leaf nodes. What comes to relay nodes, we allow only those that have both children (the tree is binary). However, each relay node know how many leaves is there in the subtree starting from that very relay node; also each relay node knows the sum of weights of all its leaves.

Whenever adding a new element, we start traversing the tree from its root, and until we reach a leaf node, we choose that relay node, whose node count is smallest; this way it maintains a logarithmic height.

What comes to the removal of an element, the data structure maintains a hashtable mapping each element to its leaf node. So, first we get the leaf node, remove it, after which, we replace the parent relay node with the sibling leaf.

Whenever sampling an element, we start from root, and choose an appropriate relay node until we reach the appropriate leaf node, whose element we return.

All three basic operations seem to run in worst-case $\mathcal{O}(\log n)$, and my benchmarking supports the observation.

A simple visualization:

Question

Is this data structure already discovered? If yes, could you tell me the name of the paper that discusses it?

This is a straightforward use of augmented data structures.  I wouldn't expect it to be publishable on its own; it's more of an undergraduate exercise.  So, I would expect that it's probably been thought of many times before by many people independently, but not necessarily written down in any particular research paper.

The idea of storing in the node of a tree the number of leaves under it is a completely standard idea in augmented data structures.  So too is the idea of storing each node the sum of the values in the leaves under it.  If you read some algorithms and data structures textbooks that describe augmented data structures, I'm sure you'll find examples of both of those motifs.


compressed information = randomness? Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom.

So, if the randomness means not comprehensible and not compressible, I don't understand why ths file is, at the same time, information that my computer and I can understand.

This file could be a book that my computer can show to me and read, and I can read and sum it ...so, it is really randomness?

Note: I understand that if I can make a summary of a text or define it with less words, that not means that it could be possible to get all the information of this book again, of course but this book is not random for me.

Note II: I undesrtand ramdoness as something that is not possible to reproduce with an smaller algorithm. I mean a string is random when I can't find an other smaller string that is an algorithm that can reproduce the first one.

Note III: I want to thank you all for your help.

okay, what you are talking about can be explained using the concept of Kolmogorov Complexity.

Let's understand the Kolomogorov complexity and randomness.

Suppose you have a string $A = HHHHH$ and $B = TTHTH$, now intuitively it seems $B$ has more randomness than $A$, however, statistically, both strings have an equal probability of being chosen. This troubled researchers for sometime untill Kolmogorov and Chaitin (independently) came up with a notion of randomness.

A string is said to be random if it cannot be compressed, that is it has no 'structure' in it.
Formally, for any word $x \in (\Sigma_{bool})^*$, the Kolmogorov Complexity $K(x)$ of the word is the binary length of the shortest program generating it.

A word is said to be random if it is not compressible. i.e. $K(w_n) \geq |w_n| + c$

If you want to look up more on this, you can start with this wonderful survey note by Lance Fortnow

Now, as I understand your question, you are asking how is an a word that is incompressible be 'information' while we use the same notion for randomness.

So, this is a bit philosophical... well, randomness is always philosophical! anyway, What we call/define to random is actually information without a structure. The outcome of an unbiased coin toss is also random, i.e. it should not have any structure to it, and one should never be able to find any patterns or periodic repetitions in the string.

Information is basically a numerical measure of the uncertainty of an experimental outcome.

Now, let's use the K-Complexity... suppose we start writing down the outcomes of a coin toss. Now without the information you basically do not have an metric to evaluate randomness of the string. The randomness is more of a property associated with information.
You can probably associate a certain degree of randomness to anything that's based on experiments.

The K-complexity is just a measure of randomness in information.
For an completely 'random' string, the $K(w_n) = |w_n| + c$ and for a completely 'non-random' string, the $K(w_n) = \delta + c$ where $\delta$ is some small quantity.


Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary
notation on its tape. Explain how it can count down from n to 0 in O(n) steps.

Here's my logic to approach this problem, but I am not sure if the time complexity of part b is O(n log n).
For unary notation on the given tape, the tape has 1's of length n >= 1. The machine on each configuration prints out the contents written in unary notation in the tape and then moves its head one step to the right by replacing 1 to x. Thus, we can intuitively see that the machine that counts down from n to 0 passes through all configurations in O(n) steps during its computation, printing out the number of 1's in the tape on each configuration (i.e. n, n-1, n-2,..., 0).
For binary notation, if we have a binary counter representing the number n, then there will be a total of O(log n) different bits (since each bit represents exponentially smaller and smaller values). And we should pass all elements in the tape to update the value between 0 and 1, which takes O(n). Thus, the time complexity, in this case, ends up being O(n log n).

Here is a rough sketch of how you can solve the second part.
Suppose that the number $n$ is of the form $2^k - 1$ for some non-negative integer $k$ and that the head of the Turing Machine is initially located at the end of the binary representation of $n$ (i.e., at the position of the rightmost, least significant, bit).
Proceed as follows:

While the current tape symbol is a $0$, replace it with $1$ and move the head to the left.
If the current symbol is $1$:

Replace the current symbol with a $0$
Move right until you reach the last non-blank symbol of the tape
Repeat from the beginning

Halt

In analyzing the time complexity, I will ignore the transitions that move right. This is because each of these transitions can be "charged" to a distinct transition that moved the head to the left, and we can safely ignore multiplicative constants in our asymptotic upper bound on the running time.
Notice how, once we ignore these transitions, at most a constant number of steps pass from the instant in which a TM flips a bit of the input tape, to the instant when the next bit flip happens. Then, to estimate the running time we can just count the overall number of bit flips.
Consider all values of $n$ from $2^k-1$ down to $0$, in this order.
The rightmost bit changes every time we move from one value to the next.
The 2nd to last bit changes every other time, the 3rd to last bit changes once every $4$ values, and so on.
In general, the $i$-th least significant bit changes once every $2^{i-1}$ values.
The total number of bit flips is then:
$$
n + \frac{n}{2} + \frac{n}{4} + \dots  = O\left(\sum_{i=0}^\infty \frac{2^k}{2^i}\right) = O(2^k) = O(n)
$$


Is there a query language variant of Turing Completeness? By this I mean a theory where you can say Language X is Query Complete so that you know that language is able to do any sort of query? I'm guessing not because some queries would run into things that a language would have to be Turing complete to work?
Why do I wonder - well you might have a relational database and a graph database and someone might say anything that can be done in the relational database can be done in the graph database (albeit at different speeds) so I would like if there were some terms DB A and DB B are both Query Complete - or if not that if there was a way to categorize levels of "query completeness" (I'm just going to assume my ill defined concept is totally understandable to everyone) so one can say stuff like "DB A is query level 4 but DB B is at query level 3, but of course much faster because of those limitations."
I sure hope (so as to not feel like a bigger idiot than normal) that the answer to this question isn't just a flat No.

The most you could expect out of a query language would be Turing completeness. In other words, the most powerful you could make a (physically realizable) query language would be to allow operations equivalent to treating the entire database as a single string and running an arbitrary program with that string as input.
Any real-world database query language that includes WHILE loops in the query language (e.g. PL/SQL) is probably Turing-complete in this sense. With such a language, you can go all the way down to reading and writing single rows at a time as necessary to read arbitrary data out of the database and interpret a Turing machine with the data as input. Of course, this is horrifically inefficient, but that's beside the point!


How to solve $T(n)= T(n - 1) + \frac{1}{n\log n}$? I am interested in the asymptotic bounds of the following recurrence:
$$T(n)= T(n - 1) + \frac{1}{n\log n}$$
with base case $T(1) = 1$. I'm having trouble while solving this recurrence. It seems much more tricky than I initially thought.
I've tried out by iterative method and since $\log(n!) = n\log n$,
I've got $\frac{1}{n\log n}$.
At this point, I've got that the summation of $\frac{1}{i}$ is equal to $\Theta(\log n + O(1))$.
So at the end, I've come up with this bound (by simplifying the two terms):
$\Theta(\frac{1}{n})$.
I'm not so sure about this bound. What is a good way to approach this problem?

We have
$$
T(n) = \sum_{m=3}^n \frac{1}{m\log m} + T(2).
$$
We can bound
$$
\int_3^{n+1} \frac{dx}{x\log x} \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \int_2^n \frac{dx}{x\log x}.
$$
Since $(\log\log x)' = \frac{1}{x\log x}$, this shows that
$$
\log\log(n+1) - \log\log 3 \leq \sum_{m=3}^n \frac{1}{m\log m} \leq \log\log n - \log\log 2,
$$
and so $T(n) = \log\log n + \Theta(1)$.


Derivation of product type eliminator in type theory In HoTT book, section 1.5 (Product Types) in order to define the eliminators for the product type it assumes a function of type $g:A \rightarrow B \rightarrow C$ and then goes on to define the eliminator rule ,saying that we can define a function $f:A \times B \rightarrow C $ for any such g by:

$f((a, b)) :\equiv g (a) (b)$.

Then it states that

  Note that in set theory, we would justify the above definition of $f$ by the fact that every element of $A \times B$ is an ordered pair, so that it suffices to define $f$ on such pairs. By contrast, type theory reverses the situation: we assume that a function on $A \times B$ is well-defined as soon as we specify its values on pairs, and from this we will be able to prove that every element of $A \times B$ is a pair.

Would you please explain in further detail what the above paragraph is trying to state?

What is meant here, is that you can construct an identification $x=(\mathsf{pr}_1(x),\mathsf{pr}_2(x))$ for any $x:A\times B$. In other words, you can show $$\Pi_{(x:A\times B)}x=(\mathsf{pr}_1(x),\mathsf{pr}_2(x)).$$
In order to do this, we use the induction principle of $A\times B$. By the induction principle it suffices to show that $$\Pi_{(a:A)}\Pi_{(b:B)}(a,b)=(\mathsf{pr}_1(a,b),\mathsf{pr}_2(a,b)).$$
Now you simply observe that by the definition of the projection maps, there are judgmental equalities $\mathsf{pr}_1(a,b)\equiv a$ and $\mathsf{pr}_2(a,b)\equiv b$. Therefore, the above type reduces to $$\Pi_{(a:A)}\Pi_{(b:B)}(a,b)=(a,b),$$
which can be proved by reflexivity.

We conclude that every element of $A\times B$ can be identified with a pair, namely the pair of its own projections. The same is true for $\Sigma_{(x:A)}B(x)$.


How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis? I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the helper methods in my calculations.

If I have an array with a fixed size of 32 indices, and I have a function that sums up the elements in that array, will that function be $O(n)$, or $O(1)$?  I think that a function that sums up the elements of an array is $O(n)$ because each element of an $n$-length array must be visited, but if the function only sums up arrays of length 32, is it still $O(n)$?

There are some things to consider here.

Conceptually, an algorithm that iterates once over the input array has runtime $\Omega(n)$ (and $O(n)$ if it does constant-time work per element), $n$ being the size of the array.

In application, if the algorithm is only ever called with arrays of length $n \leq n_0$ for some constant $n_0$, you may treat the used time as $O(n) \subseteq O(n_0) = O(1)$. Note that the $n$ here is probably not the one you use for your whole algorithm!

In practice, every algorithm runs constant time as real computers have finite memory. This is not an interesting model in the sense that it does not help to differentiate between algorithms that do behave very differently in practice, so we don't use it.

You may be interested in some of our reference questions on asymptotics, runtime analysis and the time used by arithmetic operations.


why is this computational method by Knuth "effective" and "powerful"? This is a follow-up question regarding Knuth's one formulation of the concept of an algorithm here. I am asking it here because I do not have enough reputation to post a comment to that question. To make my question self-contained, here it goes.

Knuth introduces the following formulation which "restrict the notion of algorithm so that only elementary operations are involved", (copied from the above mentioned question):

  Let $A$ be a finite set of letters. Let $A^*$ be the set of all strings in $A$ (the set of all ordered sequences $x_1$ $x_2$ ... $x_n$ where $n \ge 0$ and $x_j$ is in $A$ for $1 \le j \le n$). The idea is to encode the states of the computation so that they are represented by strings of $A^*$ . Now let $N$ be a non-negative integer and Q (the state) be the set of all $(\sigma, j)$, where $\sigma$ is in $A^*$ and j is an integer $0 \le j \le N$; let $I$ (the input) be the subset of Q with $j=0$ and let $\Omega$ (the output) be the subset with $j = N$. If $\theta$ and $\sigma$ are strings in $A^*$, we say that $\theta$ occurs in $\sigma$ if $\sigma$ has the form $\alpha \theta \omega$ for strings $\alpha$ and $\omega$. To complete our definition, let $f$ be a function of the following type, defined by the strings $\theta_j$, $\phi_j$ and the integers $a_j$, $b_j$ for $0 \le j \le N$:

  $f((\sigma, j)) = (\sigma, a_j)$ if $\theta_j$ does not occur in $\sigma$
  $f((\sigma, j)) = (\alpha \phi_j \omega, b_j)$ if $\alpha$ is the shortest possible string for which $\sigma = \alpha \theta_j \omega$
  $f((\sigma,N)) = (\sigma, N)$

He describes this formulation as effective and powerful.

My questions are:

What is the purpose of $\alpha$ being the "shortest possible string for which $\sigma = \alpha \theta_j \omega$?
Why is it so powerful? For example, if we are doing repeated multiplication (say compute $x^{10}$ given some $x \in I$), the string replacement values $\phi_j$ have to be predefined without knowing the value of $x$; but it seems that $\phi_j$ would have to depend on the specific value of $x$. So how does it really work?

Clearly I am missing something. Any help would be appreciated!

It's necessary to have some restriction such as "$\alpha$ is shortest possible string for which $\sigma = \alpha \theta_j \omega$" so the algorithm is unambiguous, because it's possible for $\theta_j$ to appear at multiple locations in $\sigma$.
After seeing Knuth's answer to exercise 1.1.8, I see how something like $x^k$ can be computed this way. Below is my rather cumbersome approach.

Let $A = \{a,b,c,d,e,t\}$ and $N=10$.

Given $x,k$ where $x>0$ and $k \ge 0$, the input will be $a^xb^k$ ($2^3$ would have input $aabbb$), and output will be the string $c^{x^k}$ ($x^k$ number of $c$'s. empty string denotes 1).

\begin{array}{cccccc}
j & \theta_j & \phi_j & b_j & a_j & \text{comments}\\
0 & b & (\text{empty}) & 1 & 9 & \text{remove one $b$. if no $b$, done.} \\
1 & c & c & 3 & 2 & \text{if first time (no $c$'s), add $c$. else expand} \\
2 & a & tc & 2 & 8 & \text{add a $c$ for each $a$} \\
3 & a & t & 4 & 6 & \text{for each $a$, add in $c$ amount of $d$'s} \\
4 & c & ed & 4 & 5 & \text{for each c, add in a $d$} \\
5 & e & c & 5 & 3 & \text{change $e$ back to $c$} \\
6 & c & (\text{empty}) & 6 & 7 & \text{clean up. remove all $c$'s} \\
7 & d & c & 7 & 8 & \text{clean up. change all $d$'s back to $c$'s}\\
8 & t & a & 8 & 0 & \text{clean up. change $t$'s to $a$'s}\\
9 & a & (\text{empty}) & 9 & 10 & \text{remove all $a$'s. return}
\end{array}


A query regarding the hierarchy of monotone Complexity Classes I have recently started studying the monotone complexity classes. There doesn't seem to be a single/clear containment hierarchy or single source regarding the same. Can we create one?

The classes are namely: $mTC^0, mNC^0, mNC, mAL, mcoNL, mL, mNL, mP, mNP, mP/Poly$. (I think that covers most)

The relationships I am aware of:

$mTC^0 \subset mNC^0 \subset mL$
$mL \subset mNL$
$(mP = mAL) \subset mNP$
$mNC \neq mP$

My queries about containment relationship b/w:

$mNC$ vs. $mP$
$mP/Poly$ vs. $mP$

Please feel free to add Open Questions and other known relationships b/w these classes as you see fit.

Raz and McKenzie, Separation of the monotone NC hierarchy, showed that the monotone NC hierarchy is strict, and separated it from monotone P. In all of these separations, the upper bound holds for the uniform class while the lower bound holds even for the non-uniform class (so by monotone P, they really mean monotone P/poly).

Monotone P is easy to separate from monotone P/poly since the latter contains uncomputable functions. For example, the language $\{w : |w| \in K\}$ is in monotone P/poly for any $K \subseteq \mathbb N$, but isn't in monotone P if $K$ is uncomputable.

(By the way, there are several reasonable ways to define monotone P, and I'm not sure they are all equivalent. However, all of them should satisfy what I wrote in the preceding paragraph.)


Prove Undecidability Without Using Rice's Theorem Show that checking if a TM accepts some input string of length greater than some constant $k$ is undecidable. Here the constant $k$ is publicly known.

I tried solving this problem by trying to reduce the "Acceptance Problem" i.e. the problem where we have to check whether a TM $M$ accepts a string $w$ or not.

One idea I had was that we can modify the input $M$ to $M'$ such that $M'$ simply increases the length of the string to become greater than $k$ but that is wrong since by input we strictly mean what was provided and any thing that the TM does cannot be considered as part of the input.

How can I solve this?

So the question is, for a particular constant $k$, is there a TM which decides on input $\langle M_i \rangle$ whether there exists a string $w$ with $|w|\geq k$ such that $M_i$ halts on input $w$? Your reduction is almost correct, let me show you: Suppose that this problem is decidable, then the acceptance problem is decidable.

If the problem is decidable, then if you wanted to know whether TM $A$ accepts $w$, you could build a machine that accepts $1^kw$ only if $A$ accepts $w$, and accepts no other string, and then you would ask your question about that Turing Machine. Let me say this with more detail.

Let $BT$ (for Banach Tarski) be the Turing Machine that decides the problem you describe, and suppose we want to know whether some TM $A$ halts on input $w$ with $|w|<k$. Then we construct a TM $H_{A,w}$ as follows: $H_{A,w}$ checks whether the input is $1^kw$, i.e. $w$ padded at the beginning with $k$ ones (so $w$ is "hard-coded" into this machine). If not, it stops. If the input is $1^kw$, then it moves to the first symbol of $w$ and simulates $A$. Does $H_{A,w}$ accept any input longer than $k$? If so, then it accepts $1^kw$, because that is the only string it could possibly accept. If it accepts $1^kw$, then $A$ accepts $w$, because we were simulating $A$ on $w$. If it accepts $1^kw$, then you could ask $BT$ the question you describe about $H_{a,w}$, i.e. run $BT$ with input $H_{A,w}$. If it returns yes, then $A$ accepts $w$. If not, not.

We have now provided a reduction from the Acceptance Problem to your problem. But we know that the Acceptance Problem is undecidable! So it cannot be that your problem is decidable, because then the Acceptance Problem would be decidable. $\square$


Single-source shortest path algorithm for graphs representing stacked behavior I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG).

That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent interprocedural call and return. The impact of these is that they determine which edge must be traversed on a call return.

Is there a shortest path algorithm adapted to this kind of graph?

Edit
Clarification: suppose that I am able to identify a pair of nodes of interest (n1, n2) in the graph using a plain boring graph traversal, I want to obtain the shortest path between n1 and n2 that respects the constraints of the graph.

Yes.  You want CFL-reachability.

You put a left-parenthesis on each call edge and a right-parenthesis on each return edge (with a different kind of parenthesis for each function).  Then, you look for a path where the sequence of symbols along the edges in the path form matched parentheses.

This is basically the intersection of a context-free language (CFL) with a graph reachability problem (finite state automaton), and as you know, the intersection of a CFL and a regular language is itself a CFL.  As a result, there are efficient algorithms for CFL-reachability.

There's also lots of theory and work on algorithms to make this as efficient as possible.  You can even find existing tools for this sort of thing.

I'd suggest you start by looking at the following papers:

Thomas Reps.  Program Analysis via Graph Reachability.  Information and Software Technology, vol 40 no 11-12, Nov/Dec 1998, pp.701--726.

Thomas Reps, Susan Horwitz, Mooly Sagiv.  Precise interprocedural dataflow analysis via graph reachability.  POPL '95.

Thomas Reps, Stefan Schwoon, Somesh Jha, David Melski.  Weighted Pushdown Systems and their Application to Interprocedural Dataflow Analysis.  Science of Computing Programming, vol 58 no 1-2, Oct 2005, pp.206--263.

The first two consider only the reachability problem (is there a path from $s$ to $t$?). The third can be used for the shortest paths from (find the shortest path from $s$ to $t$).


Variation on Insertion Sort I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the "find lowest" or inner loop.

I'll reproduce the algorithm here in Python (aka the universal psuedocode) to explain. I'll also use iteration so it's easier to understand.

def insertion_sort(list):
  for i in range(len(list)):
    for j in range(i + 1, len(list)):
      if list[j] < list[j]:
        list[i], list[j] = list[j], list[i]

The difference is that I repeatedly swap the old lowest with new lowest numbers as they're found, and reinsert the old lowest back into the list where the new lowest was.

Can I still (correctly) refer to this as insertion sort and is there a significant effect on efficiency?

Also, just in case there's anyone here who loves scheme:

(define lowest-to-front-helper
  (lambda (list lowest)
    (if (eq? (cdr list) '())
        (if (>= (car list) lowest)
            (cons lowest list)
            (cons (car list)
                  (cons lowest '())))
        (if (< (car list) lowest)
            (let ((temp (lowest-to-front-helper (cons lowest (cdr list)) (car list))))
              (cons (car temp)
                    (cdr temp)))
            (let ((temp (lowest-to-front-helper (cdr list) lowest)))
              (cons (car temp)
                    (cons (car list) (cdr temp))))))))

; Permutes list such that the lowest element is moved to the front. (Non-stable.)
(define lowest-to-front
  (lambda (list)
    (lowest-to-front-helper (cdr list) (car list))))

(define insertion-sort
  (lambda (list)
    (if (eq? (cdr list) '())
        list
        (let ((temp (lowest-to-front list)))
          (cons (car temp) (insertion-sort (cdr temp)))))))

Insertion sort maintains the following loop invariant:

After iteration $i$, the first $i$ positions in the array are the first $i$ positions of the input, in sorted order

Note that this doesn't mean that they need to be in their final positions for the sort to work at the end.  I'd say that this is the defining thing for "insertion sort", but that's not really a formal statement.

Insertion sort is not hard to turn into a recursive procedure.  The main routine you want is a helper called  insert-sorted such that consumes a sorted list and a number, and outputs a new sorted list (one longer) that includes the number.  You can write it in a way that is pretty much paradigmatic for Scheme (note, code just typed in, not tried):

(define (insert-sorted n l le)
    (if (null? l)
        (list n)
        (if (le n (car l))
            (cons n l)
            (cons (car l) (insert-sorted n (cdr l) le)))))

In words, if n comes before the first element of l or l is empty, then n goes in first position.  Otherwise, the list we want starts with the first element of l and ends with n in the right place in the tail of l.

With the helper, involves repeatedly calling insert-sorted to build up the sorted list.  If you want to follow the invariant exactly, then an approach like this will work:

(define (insertion-sort l le)
    (define (rec s l)
        (if (null? l) s (rec (insert-sorted (car l) s le) (cdr l))))
    (rec '() l))

However, this solution explicitly maintains s, the partially sorted list.  More idiomatic scheme would be to just use the call stack for this:

(define (insertion-sort l le)
    (if (null? l)
        '()
         (insert-sorted (car l) (insertion-sort (cdr l) le) le)))

I'll leave it to you to work out what the invariant for each implementation is.


What does it mean that a let-binding can be treated polymorphically, only if its right-hand side is a syntactic value? Types and Programming Languages by Pierce says:

  22.7 Let polymorphism

  A ﬁnal point worth mentioning is that, in designing full-blown
  programming languages with let-polymorphism, we need to be a bit
  careful of the interaction of polymorphism and side-eﬀecting
  features such as mutable storage cells. A simple example illustrates
  the danger:

let r = ref (λx. x) in
(r:=(λx:Nat. succ x); (!r)true);

  ...

  It is better to change the typing rule to match the evaluation rule.
  Fortunately, this is easy: we just impose the restriction (often
  called the value re striction) that a let-binding can be treated
  polymorphically—i.e., its free type  variables can be
  generalized—only if its right-hand side is a syntactic value. This
  means that, in the dangerous example, the type assigned to r when we
  add it to the context will be X→X, not ∀X.X→X. The constraints imposed
  by the second line will force X to be Nat, and this will cause the
  typechecking of the third line to fail, since Nat cannot be uniﬁed
  with Bool.

I am trying to understand the above sentence in bold.

In the example, is the let binding not treated polymorphically, because  ref (λx. x) is not  a syntactic value?
Could you give an example, where the let binding can be treated polymorphically?

Is the above  sentence related to  the following three sentences in bold? Or are they talking about several different things?

  23.8 Fragments of System F

  The most popular of these is the let-polymorphism of ML (§22.7), which
  is sometimes called prenex polymorphism because it can be viewed as a fragment of System F in which type variables range only over quantiﬁer-free types
  (monotypes) and in which quantiﬁed types (polytypes, or type schemes) are not
  allowed to appear on the left-hand sides of arrows. The special role of let in
  ML makes the correspondence slightly tricky to state precisely; see Jim (1995)
  for details.

  23.2 Varieties of Polymorphism

  More common
  in practice is the form known as ML-style or let-polymorphism, which restricts polymorphism to top-level let-bindings, disallowing functions that
  take polymorphic values as arguments, and obtains in return a convenient
  and natural form of automatic type reconstruction (Chapter 22).

Thanks.

You seem to have been confounded by many related and similar but crucially different concepts! Let me attempt to explain them one at a time.

Parametric polymorphism is the ability to write types that quantify universally over type variables using the $\forall$ quantifier. It is similar to template polymorphism in C++, or generics in Java. For example, the type $\forall \alpha . \alpha  \rightarrow \alpha$ means "for each and every type $\alpha$, given an expression of type $\alpha$, this function returns an expression of type $\alpha$. This is (almost) equivalent to writing the Java method signature public <T> T foo(T bar).

Parametric polymorphism is parametric in that for each and every possible type $\alpha$, the function behaves in the same way. This gives us powerful free theorems about the behavior of a function, e.g., a function with type $\forall \alpha . \alpha  \rightarrow \alpha$ could only be the identity function, as you were given something of an unknown type, the only thing that you could do with it is to return it unchanged (unless you cheat by non-termination).

Hindley-Milner is a special and restricted form of parametric polymorphism, in that it only allows $\forall$ to appear at the beginning of a type. That is, you cannot have types like $\forall \alpha . (\forall \beta . \beta \rightarrow \beta) \rightarrow \alpha$. The reason why people love Hindley-Milner is that type reconstruction (or type inference), or reconstructing the type of an expression without type annotations, is always deciable and principal (meaning that the type reconstructed is always the most general type possible).

The value restriction is a restriction in programming languges with both Hindley-Milner type systems and mutable storage. With the value restriction, a polymorphic type would only be inferred for a definition if the right-hand side of the definition is a syntactic value. The idea is to prevent problems with mutable store:

Consider the following ML program:

let r = ref []
r := [3]; r
let l = List.map (function true -> 1 | false -> 2) !r

Without the value restriction, the type 'a list ref would be inferred for r. However, the second line makes the contents of r have the type int list, nevertheless r still keeps the (incorrectly) polymorphic type 'a list ref and the third line would result in an uncaught type error!

The value restriction prohibits definitions whose right-hand side is not a syntactic value from being inferred a polymorphic type. In the program above, r would no longer have a polymorphic type since ref [] is not a syntactic value. The second line will fix the type to r to int list ref, causing the third line to correctly report a type error.

For more about value restriction, the first and second part of Jacques Garrigue's paper Relaxing the Value Restriction explains it rather concisely. There is also Andrew Wright and Matthias Felleisen's paper A Syntactic Approach to Type Soundness in which the value restriction was first invented.


Tournament Scheduling Problem I am trying to design an algorithm to compute the solution to this problem.

Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in chronological order with the least total travel distance when a person has to travel from one tournament to the next to the next.

A valid list of tournaments (called a tour) is where there are no overlaps in dates. The sports person travels from one tournament to the next along the straight line between the 2 coordinates.

I have a working solution but it uses too much memory.

I start by building a graph where nodes are tournaments and edges are the straight line distances between the coordinates of a node and a child_node. Each node has child nodes representing only tournaments which occur after it.

I then define a tour as a list of these nodes.

I start with a previous_tours list (containing tours of length i) and a current_tours list (containing tours of length i + 1). The previous_tours list is initialised with tours of length 1, which is just n tours each with one of the nodes.

Then to calculate the current_tours list, I loop through the previous_tours list and for each tour (current_tour) I get the last_node in the tour. Then for each child_node in last_node, I copy the current_tour and append the child_node to the end of the tour and add each copy to the current_tours list. This calculates all possible tours of length 2 as nodes only have child nodes occuring after it. The distance between the last_node coordinates and the child_node coordinates is added to the tours total travel distance. I then set previous_tours to current_tours.

I repeat this until I have all possible tours of length p. Then I loop through this list to find the one with the least total travel distance.

This is giving me the correct answer, but I am giving it a list of 120 tournaments and trying to calculate the best tour of length 4 and it uses around 5GB of memory when I implemented it in C++

I was thinking of just adding in a heuristic at each iteration to cut down the number of possible tours.

Does anyone know a more efficient way of getting this result without using a heuristic in that way?

The chronological order constraint actually makes this problem much easier to solve than D.W. thought. It means that we can orient edges in the graph from earlier to later tournaments (reflecting the fact that we cannot travel back in time), and wind up with a DAG (cycle-free directed graph). The problem can be solved optimally in $O(pn^2)$ time and $O(pn)$ space (so, at most a few milliseconds and KB for your problem size) using dynamic programming.
Let $f(v, i)$ be the length of the shortest $i$-vertex path that ends at vertex $v$. The goal is to compute $f(v, p)$ across all vertices, and pick the $v$ that minimises the function among all of them.
The shortest $i$-vertex path ending at vertex $v$ must be the result of extending (by one edge, to $v$) the shortest length-$(i-1)$ path to one of $v$'s predecessors:
$f(v, i) = \min_{u:uv\in E} f(u,i-1)+d_{uv}$
where $E$ is the set of all edges in the graph and $d_{uv}$ is the distance between $u$ and $v$.
Naturally we also have $f(v, 1) = 0$ for all $v$. So, we can compute all these function values and store them in a 2D array as follows:

Initialise $f[1][v] = 0$ for all $v$.
For $i$ from 2 to $p$:

For each $v$ in $V$:

Set $x = \infty$.
For each predecessor (in-neighbour) $u$ of $v$:

Set $x = \min(x, f[i-1][u] + d_{uv})$.

Set $f[i][v] = x$.

Set $z=v_1$.
For each $v$ in $V\setminus \{v_1\}$:

If $f[p][v] < f[p][z]$ then set $z=v$.

After running this, we know the lengths of all shortest paths of $i$ vertices or less ending at each vertex, and that the shortest overall path of $p$ vertices ends at vertex $z$. To find an actual shortest path ending at vertex $z$, we can trace backwards through the matrix looking for predecessor entries that satisfied the $\min$ condition:

Set $i=p$.
While $i>0$:

Output the current vertex, $z$.
Set $x = \infty$.
For each predecessor (in-neighbour) $u$ of $z$:

If $f[i-1][u] + d_{uz} = f[i][z]$:

$u$ is the previous tournament on some optimal path ending at $z$, so set $z=u$, decrease $i$ by 1 and jump to the top of the while loop.

This will output the tournaments in reverse order, but that can be easily fixed.


Algorithm : Median of a dynamic array This question is inspired by this SPOJ problem. That problem asks median of the final array, that can be done in $O(k+n)$, where k is the number of update queries and n is the size of the array.

The variant : Given an array of length N (of the order $10^5$), initially all elements are 0. There are K (of the order $10^5$) queries of type A B, meaning array elements in range $[A,B]$ must be increased by 1. After every query operation, find the median of the array.
Can this be solved efficiently (subquadratic time, ie, better than $\Omega(N^2$)?

UPD: O$(N \sqrt N)$ solution
Bucketing
Let's split the array into blocks of $\sqrt N$ size.
For each block let's keep all values in it in an array.
Let's also keep pairs $(Number, Count)$, counting the occurrences of each number, present in the block. We will also keep these pairs in an array, sorted by the $Number$. We also keep partial sums for this array, for each $Number$ indicating number of numbers less than this, in this block. (In the beginning this can be precalculated in $O(N log N)$ ).
Let's also keep a value $Mod$, that indicates that in reality all numbers in these block are not as they are saved, but actually bigger by $Mod$.
Last, for each block let's keep a pointer in the array of pairs, pointing to the first $Number$, such that $Number+Mod$ is more than or equal to the current value of the median.
Answering query
Let's count total number of values in all blocks less than the median - simply sum all partial sums for pointers.
Let's also count number of values equal to the median - by summing second components of pairs, at which our pointers point.
This takes $O(1)$ for each block and therefore $O(\sqrt N)$ for each query.
If we found out that total number of values less than or equal to the median is less than ${N \over 2} + 1$, we may need to shift some of the pointers forward, since the value of median then increases by 1.
In total each query we will at most need to shift  $\sqrt N$ pointers by 1, making in total $O(N \sqrt N)$ shift forward.
Updating query $(A,B)$
For blocks fully covered by the interval we can simply increase the $Mod$ values. After that some of the pointers may need to be shifted backward by at most 1, to keep their invariant (pointing at first number more than or equal to the current median). Total number of shifts backwards won't exceed $O(N \sqrt N)$ for one query.
For two blocks half covered by the query let's update values in the array in the naive way:
First, increase each of them by $Mod$ and also increase each value in our sorted array of pairs by $Mod$. Clear $Mod$.
Then let's create a hash map of all values increased by 1 in the query.
Then let's loop through array of pairs and for each $Number$ we decrease it's $Count$ by an appropriate number in the hash map, and create an entry in the second array of pairs, indicating $(Number + 1, Count)$. Once we finish, we will have all numbers in our block presented by 2 array of pairs, both sorted by the first components. Then we can merge these to in the $O(\sqrt N)$.
Finally, recalculate partial sums for this new merged array and naively find the position of the pointer by looping through it.
Seems to be it, $O(\sqrt N)$ per query but I wouldn't want to code it;)
================================================================================
Here is an idea for $O(N \sqrt{N} log N)$ solution.
Observation: (Intuitive, Beautiful, Tested but Unproven):
By increasing the subarray by 1 we can only increase the median

By 0 or 1, if array has odd length
By 0 or 0.5 or 1, if array has even length

I tested this hypothesis extensively locally.
Let's assume $N \approx K$.
Bucketing
Then let's split our queries into $\sqrt N$ groups $\sqrt N$ each. At the beginning of each block we do the following:

Calculate the median. Let it be $M$.
Let's introduce $L=M-\sqrt N$, $R=M+\sqrt N$, $LC$ - number of elements less than $L$ in the array.
For each value $X$ between $L$ and $R$ create a sorted list of all positions, in which value $X$ currently resides. We will keep each list as an implicit cartesian tree (data structure that allows cutting and merging subarray in $O(log Length)$. Example - STL Rope). This is the most computationally expensive step of the above and it takes $O(N log N)$ in the worst case, making overall complexity of these steps for all query groups $O(N \sqrt{N} log N)$.

Answering
When we will want to find the median, we will go through all values of $X$ between $L$ and $R$ and calculate sum $LC + CN(L) + CN(L+1) + CN(L+2)+ \cdots$ until it exceeds ${N \over 2} + 1$ for some value $L+t$ which will be new median. (Or average of two consecutive values). Here $CN(L)$ denotes number of items in the sorted list that corresponds to value $L$.
Updating
When we will want to update our structure after the next query ($A$, $B$), we will do the following:

For each $X$ between $R$ and $L$ find subarray that contains all values between $A$ and $B$ (if we, for example, keep in the node of implicit cartesian tree minimum and maximum values in the corresponding subtree, we can find the appropriate indexes of subarray in $O(log N)$).
Erase the corresponing subarray and insert a subarray, obtained the same way from the previous list.
For list with numbers equal to $L$ we don't insert anything since we know that all values less than $L$ will stay less than $L$ in the scope of next $\sqrt N$ queries so we simply add them during summation as variable $LC$
Splitting and merging implicit cartesian tree requires $O(log N)$ operations, we have $O(\sqrt N)$ cartesian trees, and our actions happen for each of $O(N)$ queries, leaving total complexity at $O(N \sqrt N log N)$.

Finally, we can save all queries in current block and then update our array, for example in $O(N + \sqrt N log \sqrt N)$ time by sorting queries and using scanline.
Afterthoughs:
I wonder if, since median can only increase by 1 or 0.5, we can solve this problem in $O(N log N)$ time somehow.
Also, same as in the answer above, it may be possible that $O(N \sqrt N log N)$ can be optimized to $O(N log^2 N)$, although it is not obvious to me, how.


Specify an upper bound of the size m of R with the big O notation I am trying to learn the Big O notation through the example below, can you help?

Let S be a set of n vertexes of a graph G and R be a set that the set of edges of G. Specify an upper bound of the size m of R with the big O notation. The bound shall be as tight as possible.

Are upper bound of the size m and runtime two different concept?

How to proof that the m is O(n^2) if that is the case or else?

Thank you for your attention!

Are upper bound of the size m and runtime two different concept?

The concept is just upper bounding. It doesn't matter whether you're bounding the number of vertices in a graph, the number of steps a program takes to execute, or the number of elephants in India – it's just an upper bound.

Probably the first time most CS students see big-O notation is in the context of runtimes and it's a common mistake to assume that big-O somehow means runtime. But it doesn't. This is the same mistake as, "The first time I saw numbers, they referred to somebody's height. Therefore, numbers mean height."


Finding the Candidate Keys of a Relation Using the FD's I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below specifically.

  Given the following relation $R$ and the set of functional dependencies $S$ that hold on $R$, find all candidate keys for $R$. Show your work.

  $R(A, B, C, D, E, F)$

  $S:$

  $AB \rightarrow C$

  $AC \rightarrow B$

  $AD \rightarrow E$

  $BC \rightarrow A$

  $E \rightarrow F$

Initially, I broke the attributes into groups: attributes found only on the left, only on the right, and on both sides (they are $D$, $ABCE$, and $F$ respectively). I also know that I should try to compute the closure of $D$. This is where I get stuck. At first glance, this seems like I am unable to solve this problem, which isn't true. I also tried computing the closures of $(AD)$, $(BD)$, $(CD)$, and $(ED)$ because I thought that the closure of $D = D$. Any thoughts?

You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys.

There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures of the individual attributes-- they will just be themselves. I.e. given R(A,B,C) and FDs A,B->C and B,C->A, the closures of each individual attribute {A}+, {B}+, and {C}+, will be, respectively, {A}, {B}, {C}.

Here, though, you have one FD that has a single-attribute on its left-hand side: E->F. The closure of {E}+ is E itself plus whatever E can determine, which is F, thus {E}+ = {E,F}.

Now, you have figured out the closures of the individual attributes. But that doesn't go far since the rest of the FDs have two attributes on their left-hand sides. You can then calculate the closure of, say, {A,B}+. Automatically you can add A and B into that closure since each attribute determines itself. Now look to the set of given FDs and you see that there is one that goes A,B->C. Since you already have A and B inside the closure (you have all of the attributes on the FD's left-hand side in your closure) then you can add whatever attributes are on the right-hand side into your closure. So now the closure of {A,B}+ = {A,B,C}.

Essentially you keep building larger closures with the ultimate goal of finding closures that encompass the entire set of attributes.

In this case, the candidate keys (there are three) all have three-attributes each. Try calculating the closure of {A,B,D}+. You know automatically that A,B,D should go inside it. You can also add whatever attributes are in closures that are subsets of {A,B,D}+, such as {A,B}+ from before. Thus, you can add C to the closure which now looks like {A,B,C,D}. Now check the list of given FDs again and you will see that A,D->E can now be added, since A and D are inside the closure. Thus, the closure is now {A,B,C,D,E}. Finally, you can add in the FD of E->F. And that completes the set of attributes of the relation.

Here is a useful tool for checking your work:
http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools.html

You can use it to check your work on calculating closures and candidate keys.


FA for w when length of w is even or divisible by 3 I want to construct a FA for the language

$\{w \in \{a,b\} | $length of w is either even or divisible by 3$\}$.

I've been playing around with some FAs, but I can't seem to create one that does the job. I can easily create one that accepts words with even length, and also one that accepts words with lengths divisible by 3, but I am unable to combine these.

This is my attempt:

A simpler solution is to use a DFA with 6 states which count the number of letters seen so far, modulo 6. This is a DFA with 6 states $q_0,\ldots,q_5$, and transition function $\delta(q_i,\sigma) = q_{i+1 \bmod{6}}$. The accepting states are $\{q_0,q_2,q_3,q_4\}$, since a number is even or divisible by 3 iff its residue modulo 6 is one of 0,2,3,4.

Using Myhill–Nerode theory, you can easily show that this is the minimal DFA for the language. Using an NFA with multiple initial states, you can improve this to 5 states: have two starting states $q_0^{(2)},q_0^{(3)}$ which also double as accepting states, states $q_1^{(2)},q_1^{(3)},q_2^{(3)}$, and transitions $\delta(q_i^{(m)},\sigma) = \{q^{(m)}_{i+1 \bmod{m}}\}$. This is likely the minimal number of states for this type of NFA.