What is a partially computable function? In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two:

  A partial function is said to be partially computable  if it is computed by some program.

and also

  A function is said to be computable if it is both partially computable and total.

From the first definition, a partially computable function must be a partial function, but from the second definition a computable function must be partially computable and total which is a contradiction, because a function is partially computable if it is partial and a partial function can not be total at the same time!

The definition of partial function doesn't exclude the possibility that the function is total. On the contrary, every total function is a fortiori a partial function. Perhaps the terminology is unfortunate.

A function from $D$ to $R$ is a subset $f$ of $D \times R$ such that for all $d \in D$ there exists a unique $r \in R$ (denoted $f(d)$) such that $(d,r) \in f$. The domain of $f$ is $\operatorname{dom} f = D$.

A partial function from $D$ to $R$, where $\bot \notin R$, is a function $f$ from $D$ to $R \cup \{\bot\}$. When $f(d) = \bot$, we say that $f$ is undefined at $d$. The domain of $f$ is $\operatorname{dom} f = \{d \in D : f(d) \neq \bot\}$. If $\operatorname{dom} f = D$ then $f$ is total. For every partial function $f$, $f|_{\operatorname{dom} f}$ is a total function.

As you can see, a partial function is a function which can be undefined for some of the inputs; a total function is a partial function which happens to be defined everywhere.

Now regarding computability. Every program computes some partial function $f$ from $\mathbb{N}$ to $\mathbb{N}$; if the program doesn't halt on some input $x$, then $f$ is undefined on $x$, in other words, $f(x) = \bot$. A computable function is one computed by an algorithm which always halts.


Solving a system of recurrences If the time complexity $T(n)$ of two functions $x(n)$ and $y(n)$ are mutually recursive, as in Time complexity of mutually recursive functions, this gives $T(n)=O(2^n)$.  But how do you measure an algorithm with two or more (4 in the example below) recursive functions that are not necessarily mutually recursive?

Example: Recursive Step Function

$$
\begin{align*}
w(n)&=
\begin{cases}
w(n-1)+1 & \text{if } x(n-1)=y(n-1), \\
w(n-1) & \text{otherwise.}
\end{cases} \\
x(n)&=8w(n). \\
y(n)&=
\begin{cases}
1 & \text{if } w(n) > w(n-1), \\
y(n-1)+1 & \text{otherwise.}
\end{cases} \\
z(n) &=
\begin{cases}
z(n-1)+1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)=1, \\
z(n-1)-1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)\neq 1, \\
z(n-1) & \text{otherwise.}
\end{cases}
\end{align*}
$$

These functions loop until $w(n)=I$ and then output the value of $z(n)$, where $I$ is the user input value.  This input value could be rather large.  I get the worse case scenario is dependent on $w(n)$, as it increases slowly.

I have calculated that the function specifically $$w(n)=O\left(\frac{\sqrt{16n+16}}{8}+\frac12\right),$$ but I am new to time complexity.  Could anyone help me to understand?

Here is the example in pseudocode:

SET w to 0
SET x to 1
SET y to 1
SET z to 0
GET i
REPEAT
    IF z<y and z=1 THEN
        z=z+1
    ELSEIF z<y and z != 1 THEN
        z=z-1
    ELSE do nothing
    IF x=y THEN
        w=w+1 and x=8*w and y=1
    ELSE
        x=8*w and y=y+1
UNTIL w=i
PRINT z

You can prove by induction that it always holds that $z \leq 0$, and so $z \neq 1$ and $z < y$. This allows the following simplification:

Input: $i$
$x,y,z,w \gets 1,1,0,0$
Repeat:

$z \gets z-1$

If $x = y$ then $w \gets w+1$ and $y \gets 1$; Else $y \gets y+1$

$x \gets 8w$

Until $w = i$
Return $z$

The running time is proportional to the number of iterations of the loop (which also happens to be the negation of the output).

In the first iteration we have $x=y$ and so set $w\gets 1$, $x\gets 8$, $y\gets 1$. Eight iterations later, we have $x=y=8$ (at the beginning of the iteration), and so we set $w\gets 2$, $x\gets 16$, $y\gets 1$. Sixteen iterations later, we have $x=y=16$, and so we set $w\gets 3$, $x\gets 24$, $y\gets 1$.

In total, we see that the number of iterations is
$$
1 + 8(1 + \cdots + (i-1)) = 1 + 8\frac{i(i-1)}{2} = 4i(i-1)+1 = (2i-1)^2.
$$
This shows that the output is $-(2i-1)^2$, and that the running time is $\Theta(i^2)$.


Are there some good algorithm to select m by three matrices which satisfies certain conditions? I would like to find an algorithm which select matrices satisfying certain conditions.

We consider integer matrices (entries of the matrices comes from $\{1,\ldots,n\}$ for some positive integer $n$) and the numbers in each row are different from each other.

Let me first explain some definitions.

We call a matrix $M$ with m rows and k columns canonical if for all $i \in [2, m]$ and $j \in [2, k]$, $M_{i,j} > M_{i-1, j-1}$ and for all $i \in [2,m]$ and $j \in [1,k]$, $a_{ij} \ge a_{i-1,j}$. For example, $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ is canonical.

Let $M$ be a matrix with $k$ columns. Denote by $I_j$ the set of the elements in the $j$th row. We say that two rows $j_1, j_2$ of $M$ i-interlacing if $|J_{j_1} \backslash J_{j_2}|=|J_{j_2} \backslash J_{j_1}|=i$ and $J_{j_1}\backslash J_{j_2} = \{a_1,a_2,\ldots,a_i\}$, $J_{j_2} \backslash J_{j_1} = \{b_1,b_2,\ldots,b_i\}$, either $a_1 < b_1<a_2<b_2 < \cdots < b_{i-1} <a_i < b_i$ or $b_1<a_1<b_2<a_2 < \ldots < a_{i-1}<b_i<a_i$. In particular, if two rows of a matrix are identical, then we say that the two rows are $0$-interlacing.

For example, the first row and the second row of $\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$ are $2$-interlacing. The third row and the fourth row of the matrix are $1$-interlacing.

For a matrix $M$ with entries in $\{1, \ldots, n\}$, denote $x=x(M)=(x_1, \ldots, x_n)$, where $x_i$ is the number of entries in $M$ which equal to $i$. Denote $q(M)=\sum_{i=1}^n x_i^2 + \frac{2-k}{k^2} (\sum_{i=1}^n x_i)^2$, where $k$ is the number of columns of $M$. For example, let $M=\left(\begin{array}{ccc}3 & 5 & 9\\2 & 5 & 8\\1 & 4 & 7\\1 & 4 & 6\end{array}\right)$. Then $x(M) = (2,1,1,2,2,1,1,1,1)$ and $q(M)=2$.

I would like to find all $m \times 3$ matrices $M$ with entries in $\{1, \ldots, 9\}$ which satisfy the following conditions:

(1) in each row of $M$, any two entries are different from each other; the numbers in each row are increasing from left to right;

(2) any two rows of $M$ are $i$-interlacing for some $i \in \{0,1,2,3\}$;

(3) there are two rows of $M$ which are $3$-interlacing;

(4) $M$ is canonical;

(5) $q(M)=2$.

In the cases of $m=2,3,4$, I use many for loops to find out all such matrices. But when $m \ge 5$, it takes infinite time. Is there some fast algorithm to find out all the matrices which satisfy the conditions? Thank you very much.

A simple way to deal with this problem—which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements—is to treat it as a constraint satisfaction / combinatorial search problem and apply backtracking. Each matrix entry branches the search tree 9 ways, but many of these subtrees can be trivially eliminated because they immediately violate one of the conditions.

Take the $m = 5$ case that you got stuck on as an example. For condition 1, note that already there are only $\binom{9}{3}^5 = 4,182,119,424$ matrices of size 5x3 with elements in [1..9] which have elements strictly increasing from left to right in each row. It's $\binom{9}{3}^5$ because condition 1 is equivalent to, for each row, choosing 3 distinct elements from [1..9]. You can of course iterate over such rows with

for i in 1 to 7, for j in i + 1 to 8, for k in j + 1 to 9

Moreover, conditions 2 and 4 can be checked as you are generating the rows, rather than only checking these conditions once you have the entire matrix. This should drastically prune the search tree.

Tassle adds (and provides this sample code):

  You can also prune on condition (5) by first computing all possible profiles $x(M)$ which lead to $q(M)=2$, and then trying to find all satisfying matrices with a specific profile. Out of all 490314 ways to choose 15 numbers in {1...9}, only 84 lead to $q(M)=2$. In fact, using this, even python on my quite slow machine can manage m = 5 in a reasonable time.

This sort of brute forcing is also embarrassingly parallel and requires hardly any memory, so consider dividing the space of matrices among however many CPU cores you have.


λ -terms that correspond to Haskell functions Evening All
I already have a "grasp" of haskell (not terrible, about 6 month experience) and am trying to learn the fundamentals that sit behind it, thus am now turning my attention to trying to learn Lambda Calculus. I thought, perhaps mistakenly, that it might be a good idea to try to work out the λ -terms that corresponds to some functions in Haskell. I am trying the foldr and map functions.
soooo foldr should have the property
              foldr f u [N1, . . . , Nk] →f N1 (f N2 (. . . (f Nk u)))

and map would have (should imagine...)
              map f [N1, . . . , Nk] → [f N1, f N2, . . . , f Nk]

where → represents reduction by any number of β -steps....
But am struggling to flesh this out to be honest. Any help would be greatly appreciated...
Kind Regards.

You are looking for Church encodings of datastructures in $\lambda$-calculus, and in particular of lists.


To show that any language $L \in NP$ is many one reducible to HP Question : To show that any language $L \in NP$ is many one reducible to HP.

Let $L$ be a language in NP, it means there exist a non-deterministic Turing machine for $L$. Let $x$ be a input string to this non-deterministic Turing machine, now I have come up with $f(x)$ such that $x \in L \equiv f(x) \in $HP and $f$ should be computable function. $f$ will be a function which takes $x$ string as an input and gives $M.y$(. means concatenation) as output, where $M$ the encoding of an Turing machine and $y$ is just a string.

In fact we can prove something a bit stronger: any language $L$ in NP is polynomial-time reducible to the Halting Problem $HP$.

So let $L$ be a language in NP.
We have a nondeterministic TM $N$ for $L$, which runs in polynomial time.
So
$$
x \in L \iff N \text{ accepts } x
$$
Now $N$ runs in polynomial time --- let's say that on input of size $n$ it runs in time $P(n)$, where $P$ is a polynomial.
Here is an algorithm reducing $L$ to $HP$:

On input string $x$, construct a Turing Machine $M_{x}$ which does the following: "Write $x$ on the input tape, then start trying all possible runs of $N$ on input $x$, in increasing order of size (first try runs of length 0, then runs of length 1, and so on). If a run ever accepts, then halt. otherwise keep running forever.

Now if $x \in L$ then there will be a run of $N$ on input $x$ that accepts, so $M_x$ will halt. And if $x \notin L$, then no runs of $N$ on input $x$ will accept, so $M_x$ will run forever. Thus,
$$
x \mapsto M_x
$$
is a reduction from $L$ to $HP$.
And you may also want to check that the reduction runs in linear time. (That is, the amount of time required to construct $M_x$ from $x$ is linear in $x$.)


Find the smallest set of strings which "covers" a given set of strings (coverage = containing as substring) Let $S$ be a finite set of strings and $0 < k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds:

$\forall t \in T(k,l): k \leq |t| \leq l$
$\forall s \in S \ \exists t \in T(k,l): t \subset s$ (meaning: $s$ is containing $t$ as a contiguous substring).

I would appreciate any help regarding this problem. I see that I could generate the set of all strings with length between $k$ and $l$ then consider the power set but I think there must be a better way to solve this.

I'm not even sure how hard this problem is (I think there may be a reduction for the set cover problem which means it is $NP$-complete but I really don't know) or if there are any good approximation (or maybe exact) algorithms available.

I would like to solve this problem primarily in practice. Typically, $3 \leq k \leq l \leq 10$ holds, $|S| \approx 2000$ and the lengths of the elements in $S$ can vary from 10 to 50 mainly.

Without loss of generality, we can take $l=k$.  In particular, any solution to $T(k,l)$ can be converted into a solution for $T(k,k)$ by shortening each string that's longer to $k$ to a string of length $k$ (by deleting as many characters from the beginning or end as needed to get down to length $k$, chosen arbitrarily).  So, it will simplify your life to focus on solving $T(k,k)$, i.e., finding a set of strings of length $k$.

Here is one possible approach.  You don't need to exhaustively generate all strings of length $k$.  Instead, you can generate all length-$k$ substrings of words of $S$.  If each word of $S$ has length $\le n$, then there will be $\le (n-k+1) \cdot |S|$ of them.  Then, you could apply some standard set-cover algorithm to that.  So, you don't need to generate exponentially many strings; just polynomially many.

It's possible there may be better algorithms that take into account the combinatorial structure of the strings; I don't know.


Expected running time of an algorithm This demonstrates the limitations of considering expected running time of an algorithm as a useful measure. For any $n>0$, describe  a function $f:\{0,1\}^n \to \mathbb{N}$ such that

$\mathbb{E}[f] = \mathbb{E}_{x\in \{0,1\}^n}[f(x)] = n^c$ for some constant $c$
and
${\sf var}[f] = E[f^2] - (E[f])^2 = \Omega(2^n)$.

I.e., there can be performance measures $f$ which is polynomial in expectation, but variance being exponential. Give formal justification for your answer (i.e., computation of expectation and variance for the function $f$ constructed).

I'm not able to approach the problem. I guess some hint would suffice.

There is a solution with $c = 0$: what would happen if $f(x) = 1$ for every value $x$ of $\{0,1\}^n$ but one $\tilde{x}$, for which $f(\tilde{x})$ is very big?


Why are decision problems commonly used in complexity theory? From Wikipedia:

  The type of computational problem: The most commonly used problems are
  decision problems. However, complexity classes can be defined based on
  function problems, counting problems, optimization problems, promise
  problems, etc.

I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?

Is it because any other problem can be equivalently converted to a decision problem?

Oftentimes decision problems are used because they allow a precise and simple definition of the problem and, as stated, many other problems can be converted to an equivalent decision problem.

Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.


Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have found so far. They all produce the same output for the same input.
Given any specific computable-function or even a specific instance of an algorithm/implementation (for any model of computation, functional in lambda calculus, imperative in turing machines, or any other) for it, is it possible to enumerate/find all other equivalent algorithms/implementations for that same computable-function, for the same model.
ie. If I have an algorithm or even a specification for sort, it is possible to find the other algorithms for sort?

Interpreting your problem as finding a computable $f$ such that $f\big(\langle M\rangle\big)=\langle M'\rangle$ with the property that $M'$ enumerates all programs equivalent to $M$, i.e. all $M''$ with $L(M'')=L(M)$, the answer is no (such $f$ does not exist).
One way to show this is to observe that such $f$ would place the language $\left\{\big(\langle M_1\rangle, \langle M_2\rangle\big) \big| \; L(M_1)=L(M_2)\right\}$ in $RE$, while it is known that this language is $\Pi_2$ complete and thus not in $RE$. You could formulate this relative to any admissible numbering, and not necessarily in the language of Turing machines.


How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L} = \{ \overline{L} \mid L \in \mathcal{L} \}$$

and where $\overline{L}$ is the complement. From what I read in an earlier part of my textbook, the complement of $L$ is equal to $\Sigma^* - L$.

However, say that $\mathcal{L}$ is NP. An instance of a language $L$ that is in $\mathcal{L}$ is the set of graphs with Hamiltonian paths. However, in this case, its complement $\bar{L} \in$co-$\mathcal{L}$ is the set of graphs without Hamiltonian paths, i.e. $\bar{L} \in $co-NP.

But is the set of graphs without Hamiltonian paths equal to $\Sigma^* - L$ (following the definition of complement) ? In this case, we would be including some strings $\in \Sigma^* - L$ that do not represent graphs.

Another example is $A_{TM}$, which represents the language

$$\{\langle M,w\rangle \mid M \text{ accepts input }  w \}$$

In this case, does $\overline{A_{TM}}$ represent $\Sigma^* - A_{TM}$?. If this is the case, we would be including in $\overline{A_{TM}}$ several strings that do not represent TM's, or that refer to other input that is not equal to $w$. Or rather, does $\overline{A_{TM}}$ represent the language

$$\{\langle M,w \rangle \mid M \text{ diverges on input }  w \}$$

We typically think of instances to problems as being in some format. There are several ways to think of this. Consider for example $A_{TM}$, in which the input is a pair $\langle M,w \rangle$. The three most obvious are:

Every input string can be decoded into an input pair $\langle M,w \rangle$.
Inputs not of the form $\langle M,w \rangle$ don't belong to the language.
We think of $A_{TM}$ as a promise problem: inputs $\langle M,w \rangle$ where $M$ accepts $w$ are Yes instances, inputs $\langle M,w \rangle$ where $M$ doesn't accept $w$ are No instances, and we don't care about other inputs.

If you take complementation, here is what you get under each interpretation:

$\overline{A_{TM}}$ consists of all inputs strings which, when decoded to $\langle M,w \rangle$, are such that $M$ doesn't accept $w$.
$\overline{A_{TM}}$ consists of inputs not of the form $\langle M,w \rangle$, and of those of the form $\langle M,w \rangle$ such that $M$ doesn't accept $w$.
$\overline{A_{TM}}$ is the promise problem corresponding to option 1.

While these different interpretations look different, in practice the difference is very slight, given that it is easy to recognize that the input is of the correct format. For example, given interpretation 2, consider the following two languages: $\overline{A_{TM}}$, and $\widetilde{A_{TM}}$, the language of all pairs $\langle M,w \rangle$ such that $M$ doesn't accept $w$. These two languages differ in malformed inputs, that is, outputs not of the form $\langle M,w \rangle$. Since such inputs are easy to detect, we have an algorithm for $\overline{A_{TM}}$ iff we have one for $\widetilde{A_{TM}}$, and furthermore, the complexity of both algorithms is very similar.

For this reason, we typically ignore such issues, and implicitly work under the "promise problem" interpretation: the input is assumed to be of the form $\langle M,w \rangle$. Purists can think of the first interpretation instead, which from this point of view behaves identically.

More generally, whatever interpretation you choose, you still formally have to describe what encoding is used for $\langle M,w \rangle$. We typically don't bother, since all reasonable interpretations are inter-reducible, and so don't change the computability or complexity of the problem. That said, the difference between weak NP-hardness and strong NP-hardness lies exactly in which input representation is being used.


What constant in the latest fast matrix multiplication is hidden by Big-O notation? I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has evolved in the following way:

w = 3 if using a brute-force approach,
w = 2.8074 if using Volker Strassen's algorithm [1969],
... (some interesting improvements later :))
w = 2.3729 if using Virginia Vassilevska-Williams analysis of the Coppersmith–Winograd algorithm [2011]
w = 2.3728639 if using François Le Gall's adaptation of the  Coppersmith–Winograd algorithm [2014]

I often hear that the more recent algorithms presented, while theoretically interesting since w approaches 2, are not practical due to the large constant hidden by Big-O. In other words, that the size of the input matrix would need to be extremely large in order for it to be an improvement over Strassen's algorithm, for example. I would like to put a number to this.

What is the rough value of this hidden constant for any of the more recent fast matrix multiplication algorithms? Or, for roughly what input size n of a matrix would the fast matrix multiplication algorithm use less operations than Strassen's algorithm, or the brute force approach?

All improvements since Strassen's original algorithm only achieve their exponent in the limit. That is, if they are stated as $O(n^c)$ algorithms, what they really show is that for every $\epsilon>0$ you can multiply two $n\times n$ matrices using at most $C_\epsilon n^{c-\epsilon}$ multiplications, where the constant $C_\epsilon$ blows up badly (exponentially in $1/\epsilon$?) as $\epsilon\to0$. (Coppersmith and Winograd showed that this kind of behavior is actually necessary.)

The papers don't explicitly compute $C_\epsilon$. One reason is that if you are serious about the constant, then you will probably need to apply low-level optimizations that will improve $C_\epsilon$ at the expense of the simplicity of the algorithm. Another reason is that due to the exponential dependence on $1/\epsilon$, you don't expect the result to be practically meaningful, so it's not really worth it. A third reason is that fast matrix multiplication algorithms are developed in a more abstract framework, which makes it awkward to come up with an actual explicit algorithm.

Fast matrix multiplication algorithms are recursive, that is, they iterate a smart $m\times m$ multiplication algorithm. Whereas for Strassen's original algorithm $m = 2$, for the improvements $m$ depends on $\epsilon$ (exponentially?), and so you will only be able to apply the base case for very large matrices; and for such large matrices, you would actually do much worse than the high school algorithm. The benefits of these algorithms only show up once they have been iterated many times, which would correspond to astronomically high (or worse) dimensions.

If you do feel like working out a constant, there are several expositions of the theory of fast matrix multiplication. You could take the first improvement over Strassen's original algorithm, and try to work out what the parameters are like.


How to detect facial landmarks - using haar and other way? I have done some projects using haar cascade(Ex.- Face-detection,Eye inside face detection,shoe detection etc), I also have some knowledge about it. I have trained my own models learning from youtube, this site etc.

Now I want to take it to the next level.

I want to detect facial landmarks, I have used different modules to do this, I have used dLib. But I want to learn more about it and as far as I know using multiple haar will be very much inefficient.

So how can I do this?

What I want to detect from the image :

There is a recent survey paper on exactly this topic: Wu & Ji, Facial Landmark Detection: A Literature Survey, International Journal of Computer Vision 127:2, February 2019, pp 115-142. That should give you pointers to everything you might want to know.

If you don't have access to Springer, here's the copy on arXiv.


Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$ The master theorem can be used in case of a recurrence relation of the form $T(n) = aT(\frac{n}{b}) + g(n)$

But is it possible to use the master theorem for recurrence relations of the form $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$?

Yes, you can.

We use the master theorem in the context of giving upper bounds to increasing functions $T$. In this context, we know that $T(n)=aT(\lfloor n/b\rfloor) + g(n) \leq aT(n/b)+g(n)$ so any upper bound on the recurrence without $\lfloor\cdots\rfloor$ is also an upper bound on the recurrence with $\lfloor\cdots\rfloor$.


Is mapping reduction from $\overline{A_{TM}}$ possible? I know $\overline{A_{TM}}$ is not Turing Recognizable (to prove it, infact, I proved its complement to be both Turing-recognizable and not decidable).

My question is, if $\overline{A_{TM}}$ is not Turing Recognizable, can I reduce $\overline{A_{TM}}$ to some language A (say $E_{TM}$) to show it is not Turing Recognizable, too? Or this does not makes sense, because it's not Turing Recognizable and so cannot exists such a reduction function/TM?

The notion of mapping reducibility is completely general:

Let $A, B \subseteq \Sigma^*$ be languages. $A \leq_{\mathrm{m}} B$ if there exists a computable function $f: \Sigma^* \rightarrow \Sigma^*$ such that

$$w \in A \iff f(w) \in B$$

No properties are required of $A$ or $B$.

We can use a mapping reduction from $\overline{A_{\mathsf{TM}}}$ to show that $EQ_{\mathsf{TM}}$ is not recognizable. Let $f$ be given by

$$f(\langle M,w \rangle) = \langle M', M'' \rangle$$

where $M'$ is the TM

"On input $x$ simulate $M$ on input $w$ and answer what $M$ answered"

and $M''$ is the TM that rejects every input.

Clearly, $M$ does not accept $w$ if and only if $L(M') = L(M'')$.


Estimating probability from generative model Assume that we have access to a generative model $G$, that takes as input a state-action pair $(s,a)$ and outputs a sample consisting of a successor state-observation pair $(s',o)$, that is, $(s',o)\sim G(s,a)$.

It can be assumed that the states, actions, and observations all take on a finite number of values (can be positive integers).

Is it possible to use the generative model to estimate the probability $P(o|s,s',a)$?

My thoughts:

Fix $s_0,a_0,s_0'$.

  Generate $(s',o)\sim G(s_0,a_0)$
  If $s'=s_0'$, add a particle to bin $b(o)$
  Return to step 1

Continue the above three steps for $M$ runs so that we have $M$ particles in different bins (each bin corresponding to an observation we have seen so far). Now how do we convert the set of particles to probabilities?

Think of this as estimating a probability of some outcome, based on observations of many trials.  Suppose we flip a coin 1000 times, and it comes up heads 327 times.  What is your best estimate for the probability that the next flip will come up heads?  $0.327$, right?  You get that by dividing the number of heads by the number of trials.

What if you rolled a six-sized die 1000 times, and it came up a "one" 327 times?  What is your best estimate for the probability that it comes up "one"?  The same thing -- $0.327$, right?

It's the same here.  Each time that you generate $(s',o)$ and find that $s'=s'_0$, think of that as a trial -- the outcome of the trial is the observed value of $o$.  (Ignore all iterations where $s' \ne s'_0$; they're not even a trial.)  So, if you have a particular bin, say the bin corresponding to $o=1$, then you count the number of trials where you observed that $o$ was $1$, and divide by the total number of trials.  That's your estimate for the desired probability.


8-bit floating-point representation I'm studying about representing fractional numbers as floating-point values. It is going to be an 8-bit representation. Somewhere in the text, it is said that:

  "We use the first bit to represent the sign (1 for negative, 0 for
  positive), the next four bits for the sum of 7 and the actual exponent
  (we add 7 to allow for negative exponents), and the last three bits
  for the mantissa's fractional part"

Now the question is:
Why "7" -and not another value- must be added to the actual exponent ?

With 4 bits you can represent 16 different values: 0,1,...,15. If you want to allow negative exponents it makes sense to take (approximately) half of the possible values to mean a negative exponent. By adding 7 to the exponent you map the values -7,-6,...,0,1,...,8 to the representable range. You might also want to look up two's complement.


Minimal spanning tree with degree constraint I have to solve this problem: We have weighted $n$-node undirected graph $G = (V,E)$ and a positive integer $k$. We can reach all vertices from vertex 1 (the root). We need to find the weight of minimal spanning tree in which the degree of vertex 1 is at most $k$ (we don't care about other vertices' degrees). We can assume that such a tree exists.

Can someone give an idea how to approach the solution?

What I've already tried:

1) I know how to find essential edges from vertex 1. We can use dfs and start from a random edge of vertex 1. When we return to vertex 1 we can check if this edge (another vertex 1 edge) has lower weight than the previous one. If yes, than the previous one is not essential.

2) After that I wanted to use Kruskal's algorithm (adding in the beginning of the algorithm all essential edges). But the problem is that sometimes we should not take an edge with minimal weight to construct the required tree.

For example: 9-node undirected graph, $k = 3$

(vertex1 vertex2 weight)
1 2 1
2 3 5
3 4 6
4 5 7
5 1 1
1 6 1
6 7 8
7 8 9
8 9 10
9 1 2

So essentials will be (1,2) and (1, 6) (or (1, 5) and (1,6)). Kruskal will take (1,5) (or (1,2)) anyway. And the weight will be 41, but the correct answer is 39.
So I don't know how to use Kruskal's algorithm here.

(The same example visualized, vertex 1 = vertex A)

I thought that we may construct a minimal spanning tree without constraints and after that try to transform it to the required one, but I don't know how to do this (how to transform without brute force).

As D.W. suggested, you can start as follows:

Temporarily delete vertex $1$.
For each of the resulting connected components $C_1, \dotsc, C_m$ find a MST, using e.g. Kruskal's or Prim's algorithm.
Re-add vertex $1$ and for each $C_i$ add the cheapest edge between $1$ and $C_i$.
If $m=k$, you are done.

If $m<k$, you can now do the following:

For each edge $\{1,v_j\}$ not yet added, determine the most expensive edge on the path from $1$ to $v_j$ in the current tree. Call this edge $e_j$ and compute $d_j = \operatorname{cost}(e_j) - \operatorname{cost}(\{1,v_j\})$, the cost savings of replacing $e_j$ by $\{1,v_j\}$ in the spanning tree.
Create a priority queue of the tuples $(v_j, e_j, d_j)$, ordered by decreasing value of $d_j$.
As long as $\operatorname{deg}(1) < k$ and the first value $d_j > 0$, consider the first tuple from the proority queue:

If $e_j$ has already been removed, find the edge $e_j$ and the value $d_j$ corresponding to the current tree. Update the tuple and its position in the priority queue.
Otherwise replace $e_j$ by $\{1,v_j\}$ in the spanning tree and remove the tuple from the queue.

Finding $e_j$ can be done in ${\cal O}(n)$, using e.g. a modified DFS. This makes the second phase ${\cal O}(n^2)$. Since Prim's algorithm is ${\cal O}(n^2)$ as well, this is also the running time for the complete algorithm.


Why is the assignment rule the way it is in Hoare Logic? Why is the assignment rule the way it is in Hoare Logic/Axiomatic Semantics?
I can't wrap my head around why the assignment rule is backwards from what I expected.

I understand Hoare logic is use to prove formal propositions of the state of a program as commands are executed. Thus, if we execute the command $$x:=e$$ I would have expected that the next state has such substitution...but it seems the substitution happens before we execute the assignment which I find bizzare. I would have expected:

$$ \{ P \} x:= e \{P[e/x]\}$$

Given that $P$ are statements about the program state.

I'm sure there is a good explanation for this and sorry if this is a basic question, I know it must be. But can someone explain it to me?

Bonus Question:

Why don't we write the assignment rule as:

$$ \{ Q \} x:= e \{Q[x/e]\}$$

note its NOT the same as my original suggestion because we have the $x$ and $e$ swapped around. i.e. in the post condition wherever we have an $e$ we place an $x$ (which is fine because the statement we just execute is that $x$ holds the value of $e$, so we should be able to replace $e$ for $x$ in the post condition if the pre condition help.

Related posts that I've read that have not helped:

Hoare triple for assignment P{x/E} x:=E {P}
Wikipedia Hoare logic
https://www.quora.com/unanswered/Why-is-the-assignment-rule-the-way-it-is-in-Hoare-Logic
https://www.reddit.com/r/ProgrammingLanguages/comments/e8suhh/why_is_the_assignment_rule_the_way_it_is_in_hoare/

Appendix:

For us dyslexics, in this question this is what the substitution notation means:

$$ P[e/x] = P[e \to x] $$

i.e. replace every free occurrence of $x$ with expression/term/thingie $e$.

So after reading and thinking about it more this is my explanation (thanks software foundations):

The key confusion for me seems to be the meaning of $P[e/x]$ (replaces every free instance of x with e). What this does is wherever you see the symbol $x$ literally remove it and place $e$. e.g. $ P[e/x] = (x+y+1)[e/x] \to P[e/x] = (e+y+1)$ so notice how $x$ literally disappeared from $P$. So what we want is once we do the assignment:

$$ x:= e$$

that the statement is true if we had $x$ instead of $e$. So if the rule is:

$$ \{ P[e/x] \} x:= e \{ P \}$$

then what we want is, when we plug $x$ for $e$ we want the statement in consideration to be true. So before we started the code we have $P[e/x]$. Then we run the assignment and all instances of $e$ disappear and we get $x$'s to replace them. That must be true if the code that ran was assignment (since $x$ now hold the value $e$, so you can remove $e$'s and place $x$).

Thats the explanation of the abstract concept. Lets (shamelessly) use the software foundations (SF) example:

  {{ Y = 1 }}  X ::= Y  {{ X = 1 }} In English: if we start out in a state where the value of Y is 1 and we assign Y to X, then we'll finish in a state where X is 1. That is, the property of being equal to 1 gets transferred from Y to X.

Another useful paragraph from SF:

  Similarly, in
         {{ Y + Z = 1 }}  X ::= Y + Z  {{ X = 1 }}
  the same property (being equal to one) gets transferred to X from the expression Y + Z on the right-hand side of the assignment.
  More generally, if a is any arithmetic expression, then
         {{ a = 1 }}  X ::= a  {{ X = 1 }}
  is a valid Hoare triple.

Addendum from comment's great observation:

  it is important to recognize that the rule
  {
  P
  [
  e
  /
  x
  ]
  }
  x
  :=
  e
  {
  P
  }
   allows both the expression
  e
   and the variable
  x
   to occur in the postcondition. In other words, the inference rule allows you to deduce a postcondition in which any subset of the occurrences of
  e
   in the precondition have been replaced with
  x
  , including none of them. Moreover, it allows you to deduce all of these different postconditions simultaneously.

Reply to bonus why is

1) $ \{P[e/x]\} x:=e \{P\} $

better than

2) $ \{ Q \} x:=e \{Q[x/e]\} $:

Besides the subtle point of replacing x with expressions that might be invisible (e.g. e=0, should we replace $0$ with an infinite number of $x$'s? What if the zeros are not there...the rules should be syntactic but I think it's better to avoid such confusions), I think this is the reason:

  What the rule of assignment should capture is that we are assigning the expression e to the variable x. Thus, only x should be "replaced" by e. Intuitively, in the code (or more precisely the state of the program $\sigma$) when x starts holding the value e, it doesn't randomly mean that everywhere where there might be an e it becomes x after executing the assignment $x:=e$. In fact what it does mean is that now in the post condition we have x's. Now those x's if we did not have the assignment should have the value of $e$ i.e. we only "undo" the replacement/assignment the assignment command did. Not every other random expression e. In short, the only way to know where to place the correct e's is by starting in the post condition after the assignment has been done, then starting from there place e's. If we do it backwards we might be replacing e's we didn't want to replace (even if they were probably true, which I guess they should since we are saying x holds the value e after assigning e to x).


Complexity of a particular algorithm I am a bit confused about calculating complexities.

Above is a C++ program converting a char array into an int, incrementing the value, parsing it back to char array.

#include <iostream>

int main() {
    char number[] = {'4', '3', '1'};
    int num = 0;
    //char to int conversion
    for (int i = 0; i < (int)sizeof(number); i++) {
        num += number[i] - '0';
        num*=10;
    }
    num/=10;

    //incrementation
    num++;

    //int to char conversion
    for (int i = (int)sizeof(number) -1; i >= 0; i--) {
        number[i] = '0' + num % 10;
        num/=10;
    }

    //printing the result
    std::cout << number << endl;
    return 0;
}

Now let's say array size(3) is n. In that case I would say that the complexity is O(n+n) which is O(2n). However I've heard that O(2n) is actually O(n) for some reason but I could not find any actual source about it. What is the time complexity of this program?

The way $O(f(n))$ is defined, $O(k \times f(n))$ = $O(f(n))$ for positive constants $k$. Therefore, $O(2n)$ = $O(n)$. The reason this works is that $f(n) = O(g(n))$ if and only if there exists some constant $c$ such that for all $n \geq n_0$ it holds that $f(n) \leq c \times g(n)$. We can therefore demonstrate that $k \times f(n) = O(f(n))$ since $k \times f(n) \leq c \times f(n)$ precisely for $c \geq k$.


What changes do I need to make to my algorithm to make this scene from a different angle? The code below is in F#. It creates a scene which looks like a perspective coming from the top left. I thought if I would change i % j = w then it would come from the top right instead, but that doesn't work. So what change do I need to make for it to be able to come from the top right, bottom left, bottom right and even the top centre?

open System

let w = Console.WindowWidth
let h = Console.WindowHeight

for i in 1 .. w - 1 do
    for j in 1 .. h - 1 do
        Console.SetCursorPosition(i, j)
        if i % j = 0 then printf "."

Console.Read() |> ignore

Here is what the program looks like.

 .......................................................................................................................  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
     .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .
      .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .
       .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .        .       .       .       .       .       .       .       .       .       .       .       .       .       .
         .        .        .        .        .        .        .        .        .        .        .        .        .
          .         .         .         .         .         .         .         .         .         .         .
           .          .          .          .          .          .          .          .          .          .
            .           .           .           .           .           .           .           .           .
             .            .            .            .            .            .            .            .            .
              .             .             .             .             .             .             .             .
               .              .              .              .              .              .              .
                .               .               .               .               .               .               .
                 .                .                .                .                .                .                .                  .                 .                 .                 .                 .                 .
                   .                  .                  .                  .                  .                  .
                    .                   .                   .                   .                   .
                     .                    .                    .                    .                    .
                      .                     .                     .                     .                     .
                       .                      .                      .                      .                      .
                        .                       .                       .                       .
                         .                        .                        .                        .
                          .                         .                         .                         .
                           .                          .                          .                          .
                            .                           .                           .                           .
                             .                            .                            .                            .

Can you try replacing the original condition i % j == 0 with the following conditions? They work for me.

For a perspective coming from the top right, (w-i) %j == 0
For a perspective coming from the bottom left, i %(h-j) == 0
For a perspective coming from the bottom right, (w-i) % (h-j) == 0
For a perspective coming from the the top centre, (w/2-i) % j == 0


Why is binary search using this weird thing to calculate middle? I noticed that in many books calculation of midpoint for binary search uses this:

int mid = left + (right - left) / 2;

Why not use

int mid = (left + right) / 2;

instead?

Because left + right may overflow. Which then means you get a result that is less than left. Or far into the negative if you are using signed integers.

So instead they take the distance between left and right and add half of that to left. This is only a single extra operation to make the algorithm more robust.


Deterministic query complexity and polynomial degree What is the current best upper bound known on deterministic decision tree complexity of a Boolean function in terms of its polynomial degree? Also, what is the current widest separation known between these two measures?

According to Table 2 in Aaronson, Ben-David and Kothari, the best separation between degree $\deg f$ and decision tree complexity $D(f)$ is $D(f) = \Omega(\deg f)^2)$, achieved by Göös, Pitassi and Watson, and the best upper bound is $D(f) = O((\deg f)^3)$ (perhaps already from the classic work of Nisan and Szegedy).


Shortest paths candidate Let $G = (V,E)$ be a directed graph  with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. Let $f : V \to \mathbb R$ be a given function. Describe an algorithm that runs in $O(|V| + |E|)$ time that answers yes/no to the question: is it true that for all $u \in V, f(u) = \delta(v,u)$, where $\delta(v,u)$ is the weight of the shortest path from $v$ to $u$?

Obviously what comes to mind is Bellman-Ford algorithm, but it doesn't satisfy the time requirement. I don't really see how having the candidate $f$ function helps us in this regard.

The idea is to build a graph with only the edges that are candidates for the shortest path from $v$ to $u$ assuming that $f$ is the required solution.

If during the process we find an edge that lead to a shorter path then we return false.

Otherwise, at the end, we check that all the nodes are still connected (with a DFS) hence that there exists a path with the required weight.

  if $f(v)\neq 0$ then return false

  $\forall e=(v_1,v_2)\in E $ do

  if $f(v_2) > f(v_1)+w(e)$ then return false

  if $f(v_2) < f(v_1)+w(e)$ then remove $e$ from $E$

  done

  build $cV$ the set of reachable vertices in the new graph (with a DFS)

  return $V=cV$

Correction:
- if there exists $u\in V$ such that $f(u)>\delta(v,u)$ then there exists $e=(v_1,v_2)\in E$ such that $f(v_2) > f(v_1)+w(e)$. Let $e_1,...,e_n$ be the shortest path from $v$ to $u$ if $f(v_{i+1}) \leq f(v_i)+w(e_i)$ then $f(u)\leq \delta(v,u)$ contradiction.

Hence the algorithm return false.

otherwise if there exists $u\in V$ such that $f(u)<\delta(v,u)$ then $u$ is disconnected from $v$ in the resulting graph.
Hence the algorithm return false. $u$ is connected, hence there exist a path $e_1,...,e_n$ from $v$ to $u$ such that $f(v_{i+1}) = f(v_i)+w(e_i)$ hence $f(u)\geq \delta(v,u)$ contradiction.
otherwise if for all $u\in V$ $f(u)=\delta(v,u)$ then all the edges belonging to the shortest path verify $f(v_{i+1}) = f(v_i)+w(e_i)$ hence are still in the graph at the end hence all the vertices are still connected. Also there are no edges such that $f(v_2) > f(v_1)+w(e)$ otherwise $f(v_2)>\delta(v,v_2)$.

Complexity:

$O(|E|)$ to build the new graph plus $O(|E|)$ for the DFS plus $O(|V|)$ for set equality hence $O(|V|+|E|)$.


Name of double sided search algorithms I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an effort to improve efficiency. I have not seen this applied to bfs before. Does anyone know the name of this algorithm? Does it have a name? I saw the technique for doing a double sided Dijkstra algorithm, doing the iteration on the smaller vertex with smaller degree described online but can't find the page now. Does anyone know of a references for the Dijkstra style algorithm I just described?

More detailed description of algorithm I am trying to research:
  Do a two sided breadth first search starting at both vertices. At each iteration expand the boundary of the smaller boundary.

The pseudo code is as follows

double_sided_breadth_first_search( ug, vertex0, vertex1 )
  #ug undirected graph as an adjacency list, ie hash map from vertex to set of neighbor vertices
  # vertex0, vertex1 - the two vertices that we wan't to connect
  boundary0 = { vertex0 }
  boundary1 = { vertex1 }
  visited = hashmap from vertex => vertex0 or vertex1
  common_vertex = null
  distance = 0
  while |boundary0| > 0 and |boundary1| > 0 and common_vertex is null {
    distance = distance + 1
    if |boundary0| <= |boundary1| then
       expand boundary0, mark vertices in new boundary with vertex0
        set common_vertex if one is marked as vertex1
    else
       expand boundary1, mark vertices in new boundary with vertex1
        set common_vertex if one is marked as vertex0
  }
  if common_vertex not null {
    return distance
  } else {
    error
  }

Here is python code that implements the algorithm

What you have implemented is a variation of bidirectional Dijksktra's algorithm.

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed or undirected graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet. When each search is Dijkstra's algorithm, we end up with bidirectional Dijkstra's algorithm.

In which order the algorithm should expand the search in each direction and in which efficient condition the algorithm can stop the search are two obvious and critical factors for a bidirectional search. They are studied in quite a few papers.

It looks like there is not a special or specific name for the variation of bidirectional Dijkstra's algorithm that expands the search from the side whose front is nearer to its starting points. One reason to explain away the lack of a name is that it is not easy to argue that strategy should offer a nicer heuristic when compared to other strategies.

You may want to read the Wikipedia article on bidirectional search.


VC dimension of the class of polynomial classifiers of degree $n$ I came across this statement on page 85 of the book "understanding machine learning: from theory to algorithms"

The general idea is as follows:

Consider a binary classiﬁcation problem with the instance domain being $X = \mathbb R$.

For every $n \in \mathbb N$ let $H_n$ be the class of polynomial classiﬁers of degree $n$; namely, $H_n$ is the set of all classiﬁers of the form $h(x) = \operatorname{sign}(p(x))$, where $p\colon  \mathbb R \to \mathbb R$ is a polynomial of degree $n$.

Prove that the VC dimension of $H_n$ is $n+1$.

The idea is that a polynomial of degree $n$ has at most $n$ roots, and so can change signs at most $n$ times. Therefore no polynomial of degree $n$ can form an alternating pattern +-+-... or -+-+... of length $n+2$. This shows that the VC dimension is at most $n+1$.

On the other hand, for any set of $n+1$ pairs $(x_1,y_1),\ldots,(x_{n+1},y_{n+1})$, there is a polynomial of degree $n$ which interpolates them, given by the Lagrange interpolation formula. Using $y_i = \pm 1$, you can easily show that any set of $n+1$ points is shattered. Therefore the VC dimension is exactly $n+1$.


Number of states in DFA equivalent to given NFA Let's say there is a NFA with $n$ states with an alphabet consisting of $x$ symbols. I convert it to an equivalent DFA. Can I say that the number of states in the equivalent DFA is $x^n$?

The standard powerset construction takes an NFA with $n$ states over an arbitrary alphabet and produces a DFA with $2^n$ states; this is tight for alphabets containing at least two symbols (see Chrobak's paper below for several references for this).

As for unary alphabets, Chrobak showed in his paper Finite automata and unary languages that a unary NFA with $n$ states can be converted to a unary DFA with $O(e^{\sqrt{n\log n}})$ states, and showed that this is tight (up to the hidden constant factor).


Pumping lemma of regular language I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider

$$D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, \text{ and } x_i \neq x_j \text{ for } i \neq j\}.$$

I want to know how to prove this is not regular using pumping lemma.

This is another classical example in which the pumping lemma is the wrong way to go. Here are two cheap alternatives.

Use the Myhill–Nerode theorem. For any $i \neq j$, the words $1^i$ and $1^j$ are inequivalent, since $1^i\#1^i \notin D$ while $1^i\#1^j \in D$. Since there is an infinite pairwise inequivalent collection of words, the language is not regular.
Use closure operators. If $D$ were regular, then so would $\overline{D} \cap 1^*\#1^* = \{1^i \# 1^i\}$ be. Now it's easy to use the pumping lemma.

It's also possible to use the pumping lemma directly. Suppose that the pumping length is $p$. Take $w = 1^p\#1^{p!+p} \in D$. According to the pumping lemma, we can write $w = xyz$ so that $0 < |xy| \leq p$ and $xy^iz \in D$ for all $i$. Let $y = 1^q$, so that $1 \leq q \leq p$. Choose $i = p!/q + 1$. Then $xy^iz = 1^{p!+p} \# 1^{p!+p} \notin D$, contradiction.

The trick of using factorials here is standard. Now that you've seen it, you can use it whenever it's needed.


Find an optimal ordering I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated!

  Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example,

  $$\begin{bmatrix}
    1 & 0 & 1 & 0  & -1 \\
    -1 & 0 & 0 & 0  & 1 \\
    0 & 1 & 1 & 0 & -1 \\
    -1 & -1 & 0 & 1  & 1 \\
    1 & 0 & 0 & 0  & -1
    \end{bmatrix}$$

  Without trying every single permutation, find an ordering of columns $c_i$ that maximises the number of rows for which the first non-zero element is $1$.

For the example above, one such ordering (it's not unique!) is $(c_3, c_4, c_1, c_2, c_5)$, i.e.,

$$\begin{bmatrix}
    1 & 0 & 1 & 0  & -1 \\
    0 & 0 & -1 & 0  & 1 \\
    1 & 0 & 0 & 1 & -1 \\
    0 & 1 & 1 & -1  & 1 \\
    0 & 0 & 1 & 0  & -1
  \end{bmatrix}$$

Here, for $4$ out of $5$ rows the first non-zero element is $1$.

This problem, which I'll call CO for Column Ordering, is NP-hard.  Here's a reduction from the NP-hard problem Vertex Cover (VC) to it:

Decision problem forms of VC and CO

Let the input VC instance be $(V, E, k)$.  It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $E$ is incident on at least one chosen vertex?"  We will construct an instance $(A, k')$ of CO that represents the question: "Given the matrix $A$ with elements in $\{-1, 0, 1\}$, is it possible to permute the columns of $A$ such that a 1 appears before a -1 on at least $k'$ rows?"  These two problems are stated in decision problem form, whereby the answer to each is either YES or NO: formally speaking, it is this form of a problem that is NP-complete (or not).  It is not too difficult to see that the more natural optimisation problem form stated in the OP's question is roughly equivalent in terms of complexity: binary search on the threshold parameter can be used to solve the optimisation problem using a decision problem solver, while a single invocation of an optimisation problem solver, followed by a single comparison, is enough to solve the decision problem.

Constructing an instance of CO from an instance of VC

Let $n=|V|$ and $m=|E|$.  We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns.  The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered.  The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

For each vertex $v_i$, create a column in which:

among the top $(n+1)m$ rows, the $j$-th block of $n+1$ rows all contain a +1 when edge $e_j$ is incident on $v_i$, and 0 otherwise, and
the bottom $n$ rows are all 0 except for the $i$-th, which is -1.

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Finally, set the threshold $k'$ for the constructed CO instance: $(n+1)m + n - k$.  In other words, we allow at most $k$ rows in which a -1 appears before a +1.  Let's call this number of violating rows the "cost" of a CO solution.

Proof

The correspondence between a solution to the CO instance and a set of vertices in the original VC instance is: Every column to the left of the fence corresponds to a vertex that is in the set, and every column to the right of the fence corresponds to a vertex that is not.

Intuitively, the -1s in the top of the "fence" column force the selection of a subset of columns to be placed to its left that together contain +1s in all these positions -- corresponding to a subset of vertices that are incident on every edge.  Each of these columns that appears to the left of the "fence" has a -1 on a distinct row somewhere in the bottom $n$ rows, incurring a cost of 1; the +1s in the bottom of the "fence" ensure that all columns placed to its right incur no such cost.

Clearly a VC solution using at most $k$ vertices yields a solution to the constructed CO instance with cost at most $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to the CO instance with cost at most $k$ corresponds to a vertex cover with at most $k$ vertices.

Suppose to the contrary that there exists a solution to the CO instance with cost at most $k$ that leaves some row in the top $(n+1)m$ rows with a -1 before a +1.  This row belongs to a block of $(n+1)$ rows corresponding to a particular edge $uv$.  Every row in this block in the original instance $A$ is identical by construction; permuting columns may change these rows, but does not affect the fact that they are identical.  Thus each of these $n+1$ identical rows has a -1 before a +1 in the solution, implying a cost of at least $n+1$.  But $k \le n < n+1$: contradiction.

Since each of the $m$ blocks of rows in the top $(n+1)m$ rows have a +1 before a -1, each of the corresponding edges is covered by a vertex corresponding to a column to the left of the fence: that is, this subset of vertices constitutes a vertex cover.  Since none of the top $(n+1)m$ rows have a -1 before a +1, the only place where cost can accrue in the solution is in the bottom $n$ rows, from columns placed to the left of the fence.  Each such column has cost exactly 1, so given that the cost is at most $k$, there must be at most $k$ such columns, and hence at most $k$ vertices in the cover.

Finally, it's clear that the CO instance can be constructed in polynomial time from the VC instance, meaning that if a polynomial-time algorithm existed for solving CO, any VC instance could also be solved in polynomial time by first constructing a CO instance as described above and then solving it.  Since VC is NP-hard, CO is too.


Existence of interval arrangement satisfying constraints Problem statement:

Input:
(a) A natural number $n$.
(b) $m$ requirements on $I_1,\ldots,I_n$ of the form:

Segment $I_i$ is entirely to the right of segment $I_j$.
Segments $I_i$ and $I_j$ intersect.

Output:
Is it possible to find $n$ non-empty segments (on the real number line) which fulfill the $m$ requirements?

Here is my solution attempt.
I started by considering what happens when I have only requirements of type 1 (no particular reason, just easier to visualize).
I created a directed graph with $V=\{v_1,v_2,\ldots,v_n\}$ nodes, where each node represents a segment. I added an edge $e=(u,v)$ iff the segment $u$ is to the right of segment $v$ ($e$ represents a requirement of type 1). A solution exists if the graph is a DAG, which can be checked in linear time using DFS.
My problem is with edges of type 2. I understand that a solution exists iff there is no edge of type 2 between two nodes which have a path with edges of type 1 between them.
I believe I found an $O((m+n)m)=O(mn+m^2)$ algorithm using BFS from every node $u$ for which an $e=(u,v)$ of type 2 exists. I run the BFS from the node $u$ and check if $v$ is discovered. If it is, no solution exists.
Is there a linear time algorithm for this?

Construct a graph in which each vertex corresponds to an endpoint of an interval. Then add the following edges:

If $\ell_i,r_i$ are the endpoints of $I_i$, then add the edge $\ell_i \to r_i$.
For a constraint $I_i < I_j$, add the edge $r_i \to \ell_j$.
For a constraint $I_i \cap I_j \neq \emptyset$, add the edges $\ell_i \to r_j$ and $\ell_j \to r_i$.

Now check that there are no directed cycles. (This answer is inspired by an answer on stackexchange.)


Arden's rule expressed as matrix algebra The following theorem is (in the context of languages) known as
  Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is
  quasiregular, then we have a solution which is unique and which
  preserves rationality. In the next lemma we show the converse: For
  every rational series we can find a linear system such that the first
  component of its solution vector is exactly the given series. With
  these two results we have already done most of the work for proving
  the Theorem of Schutzenberger, which teaches us that the families of
  rational and recognizable series coincide.

  Theorem 2.2.1

  Let $B \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,1}$ and $A \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,n}$ a quasiregular matrix. The linear
  system

  $$
X = B + AX
$$

  has the unique solution $X = A^∗B$. Moreover, if $A$
  and $B$ are $\mathbb{K}-rational$ then the solution $X$ is $\mathbb{K}-rational$.

  Proof:

  First we show that $X = A^∗B$ is a solution:

  $$
B + AX = B + AA^∗ B = (I + AA^∗)B = A^∗B = X.
$$

My question is as follows: what does asterisk mean in this context (when it is used with matrices)? I know what Arden's Lemma is, but I don't understand the proof given here.

To credit the author of this paper: Regular Languages And Their Generating Functions: The Inverse Problem by Christoph Koutschan.

The notation is probably defined in the paper or in some standard reference, but one can guess that
$$
A^* = (I - A)^{-1}.
$$
This definition satisfies the identity $A^* = I+AA^*$, since
$$
I+AA^* = I-((I-A)-I)A^* = I-(I-A)A^*+A^* = I-I+A^* = A^*.
$$
Presumably a quasiregular matrix $A$ is one for which $I-A$ is invertible, perhaps with some additional assumptions.


Given a set of sets, find the smallest set(s) containing at least one element from each set Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible while still meeting this criterion, although there may exist more than one smallest $M$ with this property (the solution is not necessarily unique).

As a concrete example, suppose that the set $\mathbf{S}$ is the set of national flags, and for each flag $S$ in $\mathbf{S}$, the elements are the colors used in that nation’s flag. The United States would have $S = \{red, white, blue\}$ and Morocco would have $S = \{red, green\}$. Then $M$ would be a set of colors with the property that every national flag uses at least one of the colors in $M$. (The Olympic colors blue, black, red, green, yellow, and white are an example of such an $M$, or at least were in 1920.)

Is there a general name for this problem? Is there an accepted “best” algorithm for finding the set $M$? (I’m more interested in the solution itself than in optimizing the process for computational complexity.)

The problem is the well-known NP-complete problem Hitting Set. It is closely related to Set-Cover. The NP-completeness proof can found in the classic book of Garey and Johnson.

If you want to approximate it, you might want to translate your instance first to Set-Cover, and then apply an approximation algorithm for Set-Cover. However, Set-Cover cannot be be approximated by a constant factor in polynomial time, unless P=NP as shown by Lund and Yannakakis.

If you are interested in exact solutions and your inputs behave nicely, I would recommend using a fixed-parameter tractable. The running time is here not only expressed in terms of the input length $n$ but also in terms of an additional parameter $k$. If the running time is $O(f(k)\cdot n^{O(1)})$, we call the algorithm a FPT-algorithm. Here, $f(k)$ is an increasing function. So if $k$ is constant we have a polytime algorithm. The first chapter of the book by Flum and Grohe, explains an FPT-algorithm for hitting set (more precisely for $p$-card-hitting set). The algorithm is easy to implement and uses the method of bounded search trees. Still it needs to much space to explain here, basically you break down the necessary(?) brute-force search, into small pieces (when $k$ is small).


Does my solution converge to O(N) for worst-case time complexity? Forgive me if this should be in StackOverflow or Mathematics instead!

I was given the following question at an interview:

Given an array of unique integers, find the first missing non-negative integer that is missing to form a consequence sequence of non-negative integers.

For example, the input [3, 4, -1, 0, 1] should give 2.
The input [1, -3, 2, 0] should give -1 (i.e no missing numbers).
The input of [-2, -3, -5] should give 0

I came up with a solution that is something akin to here: https://play.golang.org/p/b2pXr9kZYxM:

func findMissingNumber(nums []int) int{
    j := 0
    for i, num := range nums {
        if num < 0 {
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
    if j >= len(nums) {
        return 0
    }
    count := 0
    for i:=j ;i < len(nums);{
        count++
        if nums[i] == i-j {
            i++
            continue
        }
        if nums[i]+j >= len(nums) || nums[nums[i]+j]+j >= len(nums) {
            nums[i] = -1
            i++
            continue
        }
        temp := nums[nums[i]+j]
        nums[nums[i]+j]= nums[i]
        nums[i] = temp
    }
    fmt.Println(count)
    for i := j; i < len(nums); i++ {
        if nums[i] == -1 {
            return i - j
        }
    }
    return -1
}

Both the interviewer and I agreed that my solution could've been slightly more optimized (GeekForGeek seems to agree) but we were unsure if the worst-case for my solution was $O(N)$ or $O(N^2)$.

It seems like my solution has $$ O(N) + O(N/2) + O(N/4) + O(N/6) +\cdots+ O(1) $$ which becomes essentially:
$$\frac{N}{2}\sum_{n=1}^{N} n^{-1}$$

My calculus is a bit rusty (as are my algorithm skills) but I know this is a series diverges for $N \to \infty$. But can I say that for N sufficiently smaller than infinite (i.e Integer.Max), my worst-case becomes simply $$O(kN) = O(N)?$$

$ \sum_{i=1}^n \frac{i}{n} $ is the harmonic sequence, which goes to $\log(n)$

since in your question you claim the $T =\frac{n}{2} \sum_{i=1}^n \frac{i}{n}$

$T = \frac{n}{2} \log(n) = O(n\log(n))$


Distributive property with sum types and product types In Philip Wadler's presentation, "Category Theory for the Working Hacker", something confused me. At about 30:52, he says:

  We need this additional construct which is called distributivity. Here it is, right? It just says "given a choice of an A or a C and a choice of a B or a C, we can get a choice of an A or a B and a C."

This is shown on the slide as:

  $$ (A + C)\times(B + C) \cong (A + B) \times C $$

Is this correct? I have the following doubts about it:

I think that, in Boolean algebra, the distributive property would give $ (A + C)\times(B + C) = (A \times B) + C $.
Given a choice of an A or a C and a choice of a B or a C, we might choose C both times, giving us only a C and a C. For example, in Haskell:

    data AorC = ACA A | ACC C       -- sum type
    data BorC = BCB B | BCC C       -- sum type
    data Prod = Prod AorC BorC      -- product type
    cAndC = Prod (ACC c1) (BCC c2)  -- choose type C both times

Polynomial types (those obtained through $+,\times,0,1$ and type variables) form a commutative semiring.

Basically, all the elementary arithmetic laws for $+$ and $\times$ hold as expected, up to (natural) isomorphism. These include commutativity, associativity, and distributivity of $\times$ over $+$.

More concretely, the distributive law is
$$ (A\times C)+(B\times C) \simeq (A+B)\times C$$
and I think this was the law that Philip Wadler meant to show.


Is there an algorithm for converting a CFG in Greibach Normal Form into a CFG in strong GNF? A CFG is in strong GNF when all rewrite rules are in the following form:

$A \rightarrow aA_1...A_n$

where $n \leq 2$.

Such an algorithm is described in Koch and Blum, Greibach Normal Form Transformation, Revisited.


Is a Knapsack Problem with only Color Constraints NP-Complete? I have a knapsack problem that has been frustrating me for weeks, in which we consider a set of n items, described by their integer value, and being of one of C colors.

There exists a constraint on the number of different colors of objects in the knapsack (but no "weight" constraint), and the goal is to maximize the value of the knapsack.

It's basically the same setting as in this model http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22.9533&rep=rep1&type=pdf except that there is only one knapsack and the items are "weightless".

Is this problem hard, easy, yet to be classified? I would really appreciate any pointers. Please and thank you in advance.

So, items have only 2 parameters:

Color. I assume that each item has one color ("one of C colors"). If not, this problem is probably $\mathsf{NP}$-hard.
Price.

Now we need to pack a knapsack to maximize the price. Knapsack can have at most $k$ colors.

Algorithm:

For each color count the total price of items that are colored by color $C_i$. Call these values $P_i$. Takes linear time.
Find $k$ maximal values of $P$. Takes polynomial (linear?) time. Can be done using sorting.

This is the answer.


How can I determine the input size of an algorithm? Could you explain to me the input size of the algorithm with these cases? I can't understand the cases with multiple input parameters. Thanks.

algorithm_1( a[1,...,n], b[1,...,n] )
    for i ← 1 to legth[a] step 1 do
        for j ← 1 to legth[b] step 1 do
            x++
    return 0

-

algorithm_2( a[1,...,n], b[1,...,n] )
    return 1

-

algorithm_3( a[1,...,n], n )
    for i ← 0 to n step 1 do
        sum += a[i]
    return sum

-

algorithm_4( m, n )
    for i ← 0 to n step 1 do
        sum += m*2
    return sum

for the first code segment, input size is 2n. a has n elements, so does b.
for the second code segment, input size is 2n. a has n elements, so does b.
for the third segment, input size is n+1. a has n elements, and there is another value n.
for the fourth code segment, input size is 2.


Interview Question with Arrays and Consecutive Subintervals I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..

The question is:

  "An array of $n$ integers is correctly positioned with respect to an
  integer $k$ if for any $k$ consecutive indices in the array, there
  does not exist values at two indices, $x$ and $y$ such that $x \geq 2$
  * $y$ (where $x$ and $y$ are values at 2 indices of the array in a subarray of size $k$). What is an $O(n \log k)$ algorithm to determine
  if an array is correctly positioned?"

For example: $[5, 6, 7, 4, 5, 9]$ is not correctly positioned if $k = 4$ since in in the interval $[7, 4, 5, 9]$ we have that $9 \geq 4 * 2$.

My thought is to check all potential subintervals like $[0..k]$, $[1..k+1]$, $[2,..k+2]$ using a min-heap but I really can't think that would satisfy the time constraint since it's resulting in building far too many heaps.

Does anyone know how to approach this problem, or have a solution for it?

Having trouble figuring out how to keep track of this sliding window using heaps, and thinking maybe I have to use a min-heap and max-heap? And compare the max to the min for every subinterval using insertions and deletions?

Despite common belief, maintaining the maximum (or minimum) element out of the last $k$ elements does not involve a $O(\log k)$ factor, and can be done in amortized $O(1)$. Using this twice (once for max and once for min) you can solve your problem in $O(n)$.

The trick is done using a monotonic double-ended queue, one where all the elements are either in descending or ascending order. Furthermore, for each element we keep track of the index we encountered it, so we can invalidate it from the queue.

Suppose that we iterate over elements in a stream, and wish to maintain the minimum value (the maximum is analogous). Let's call the current value $x$ and the current index $i$. We first initialize an empty double-ended queue $Q$ and start iterating:

Remove all elements from the queue that would be made irrelevant by $x$. Since we know our queue is in ascending order, this is very simple, we keep
removing elements from the back that are bigger than $x$. They are now irrelevant for the window, as $x$ is newer and smaller.

while not empty(Q) and peek_back(Q).value > x:
    pop_back(Q)

Add $x$ to the back of the queue, but keep track of its index as well.

push_back(Q, value=x, index=i)

Invalidate old items in the queue. We only have to do this if the item is in the front of the queue, otherwise its harmless (this lazy removal is what allows us to keep $O(1)$ time).

while peek_front(Q).index <= i - window_size:
    pop_front(Q)

Now peek_front(Q) contains the smallest element in our window, so we can use it and then keep iterating.

Note that steps #2 and #4 are $O(1)$ time, and steps #1 and #3 are $O(r)$ time where $r$ is the number of removed elements from the queue. However since each element is only added once to the queue, the $O(r)$ steps must be amortized $O(1)$.


Adjacent house , dynamic programming problem I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be either positive or negative value. But the aim is to maximize the profit by buying a subset of these houses. So infact, you should buy houses which are >0 value. However, you cannot buy houses that adjacent to the house you are buying, e.g i-1 and i+1 should not be bought. I am not quite sure where to start to look at this problem, I mean what exactly will be the difference of looking it from the greedy or dynamic programing way. Thanks for any suggestion.

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list,  or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.

Can you now write down a recurrence? And solve the recurrence efficiently? What happens when we have one or two houses in all?

Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for  $1\leq i < j\leq n$,


In what case would bi-directional BFS have a worse asymptotic run time than regular BFS? I am trying to prove that bidirectional BFS could have a worse run time than regular BFS. I am confused on how this would be possible, considered bidirectional BFS always divides the run time in two, since it is executing two searches. Would a specific order of nodes and vertices have to take place in order to give bidirectional a worse running time? Or is it a quantity issue?

Edit:
Here is a graph I made. I'm assuming bi-directional BFS would infinitely search in this instance because if search one went right, and search two went left, they wouldn't find a path. Then, search one would go left, and search two would go right. Doesn't this mean that the search would run infinitely, because it doesn't stop until both have found the same path?

When attempting to find a path from a source vertex $s$ to a target vertex $t$, with both BFS and bi-directional BFS, if you assume a fairly steady branching factor $b$, the number of possibilities checked (and hence the running time) is dependent on the depth. For BFS the depth is the distance from the source to the target, giving $b^{k}$ vertices visited, for bi-directional BFS the two searches meet in the middle, so it's two lots of half-distance searches - $2\cdot b^{k/2} = 2\cdot\sqrt{b^{k}}$, which is clearly better.

So to get a worse time, you need a route from $s$ to $t$ that traverses very few vertices, but the route from $t$ to $s$ would visit many vertices. Essentially you want an asymmetric branching factor.

The family of star graphs would be sufficient for this. A star graph has a single central vertex, and all other vertices are connected directly to it, and no other vertices. So if you have $s$ as one of the pendent vertices, and $t$ as the central vertex, normal BFS would take constant time, and bi-directional BFS would take linear time. You can also invent more complicated examples that share this property of a low branching factor going one way, but a high one coming the other (up to a point).


Finding the cheapest buy order with fixed inflation for each product Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.

Each product $p\in M$ has a base price $b_p$, as well as an inflation rate $r_p$. At time unit $t$, product $p$ therefore has the price $b_p \cdot {r_p}^t $.
 We can assume $b_p\in \mathbb{R}$, $r_p>1$.

I'm looking for an efficient (i.e. polytime) algorithm that returns the optimal buying order which minimizes the total price.

There's an easier variant of the problem (all $b_p=1$) which can be solved using the greedy algorithm
"Always buy the one product with the highest inflation".

Given that the base prices can be vastly different, this algorithm can't be directly transferred, but knowing that an easier version of the problem had a linear-time solution, this one probably still isn't $\mathsf{NP}$-complete.

If we view every product as a function of time $p_i(t) = b_p \cdot {r_p}^t$, the greedy algorithm above tells us, that if for $t_0$ holds $p_i(t_0) = p_j(t_0)$,  then from the point once $t_0$ has passed we should always pick of $p_i, p_j$ the one with the higher inflation.

I'd be open for both hints and solutions.

The problem in the question
The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nb_pr_p^{f(p)}$ is minimum.
A more general problem and polynomial-time algorithms
The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nc(p,f(p))$ is minimum.
The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.
For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.


Finding negative cycles for cycle-canceling algorithm I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is lowered in each round. To find a negative cycle I am using the bellman-ford algorithm.

My Problem is:
Bellman-ford only finds cycles that are reachable from the source, but I also need to find cycles that are not reachable.

Example: In the following network, we already applied a maximum flow. The edge $(A, B)$ makes it very expensive. In the residual network, we have a negative cost cycle with capacity $1$. Removing it, would give us a cheaper solution using edges $(A, C)$ and $(C, T)$, but we cannot reach it from the source $S$.

Labels: Flow/Capacity, Cost

Of course, I could run Bellman-ford repeatedly with each node as source, but that does not sound like a good solution. I'm a little confused because all the papers I read seem to skip this step.

Can you tell me, how to use bellman-ford to find every negative cycle (reachable or not)?
And if not possible, which other algorithm do you propose?

To expand upon my comment, remember, this algorithm for finding Min-Cost-Flow relies on the fact that $f$ is maximal. By first running Ford-Fulkerson to find $f$ and the resulting residual network $G_f$, the cost $f$ is then reduced by finding negative cycles in $G_f$. That is, by finding negative cycles in $G_f$ we do not change the amount of flow, $f$, but merely the cost.

Now by running Bellman-Ford from $t$ in $G_f$ we can trace backwards on edges that have non-negative flow (by definition of $G_f$). If cycles are adjacent to any edges in these paths, then we can "transfer" some amount of flow to other edges in the cycle. In other words, we keep the net-flow for some cycle the same, but are able to change the cost.

Notice an unreachable cycle from $t$ must have zero-flow. Otherwise we would have a contradiction in $f$ being maximal.

I apologize for the "hand-wavy-ness" of this explanation. I will try to be more formal when I have time tonight.


proving " if $k\log(k) = \theta (n)$ then $k = \theta (\frac{n}{\log(n)})$" First i began with the definition of $\theta$ as below:
$c_1n \leq k \log(k) \leq c_2n  \implies c_1\frac{n}{logk} \leq k \leq c_2\frac{n}{logk}$
and we also know if $k\log(k) = \theta (n)$ then $k = O(n)$ then $k \leq cn$ thus $c\frac{n}{logn} \leq c_1\frac{n}{logk}\leq k $ and thus $k = \omega(\frac{n}{\log(n)})$.
In in this manner, i have to prove that $ c_2\frac{n}{logk} \leq  c\frac{n}{logn}$ too to show that $k = O(\frac{n}{\log(n)})$ . But it ($ c_2\frac{n}{logk} \leq  c\frac{n}{logn}$) seems false! Is this really false and there is a better solution, or is there any proving tricks for $ c\frac{n}{logn} \leq c_1\frac{n}{logk}$?

First, let me explain why your claim holds. Then we'll see how to prove it.

If $k \log k = \Theta(n)$ then $k$ has the same order of magnitude as $n$, and so we expect $\log k \approx \log n$ (or, more formally, $\log k = \Theta(\log n)$). Diving by $\log n$, we deduce $k = \Theta(n/\log n)$.

This was just intuition, so now let us see a rigorous proof. A rigorous proof rests on a rigorous definition of big $\Theta$, and this is a surprisingly delicate matter. In this case it suffices to assume that $n \geq 1$.

Upper bound

Suppose that $k \log k \leq Cn$ for $C>0$.

If $k \leq \sqrt{n}$ then
$$
\frac{k}{\frac{n}{\log n}} \leq \frac{\log n}{\sqrt{n}}.
$$
Now $\frac{\log n}{\sqrt{n}}$ is continuous and tends to zero at infinity, so it is upper-bounded by some constant $M$. Therefore in this case
$$
k \leq M \frac{n}{\log n}.
$$

If $k > \sqrt{n}$ then
$$
Cn \geq k \log k > k \log \sqrt{n} = \frac{1}{2} k \log n,
$$
and so
$$
k \leq 2C \frac{n}{\log n}.
$$

We conclude that for all $k$,
$$
k \leq \max(2C,M) \frac{n}{\log n}.
$$

Lower bound

Left to you as an exercise.


How do we translate first order logic's universal quantifier (the $\forall$) and the existential quantifier (the $\exists$) to Prolog? I'm trying to convert some English statements to first order logic statements and I'm trying to use Prolog to verify the translations. My question is: how do I convert a first order logic statement (having $\forall$ and $\exists$ quantifiers) into Prolog rules?

For example, there's this English statement:

  Every voter votes for a candidate which some voter doesn't vote for.

and here's my translation of the English statement into first order logic:

$$\forall x, y[Voter(x) \land Candidate(y) \land Votes(x, y) \rightarrow \exists z[ Voter(z) \land \lnot Votes(z, y) ] ]$$

Now I'm not sure if this translation is correct. That's what I want to find out. My question is: how do I convert this first order logic statement to a Prolog rule?

So first I'm trying to fill a Prolog database with some facts.

human(p1).
human(p2).
human(p3).
human(p4).
human(p5).
human(p6).
human(p7).
human(p8).
human(p9).
%humans who are neither voters nor candidates
human(p10).
human(p11).

%humans who are only voters
voter(p1).
voter(p2).
voter(p3).

%humans who are candidates and voters
voter(p4).
voter(p5).
voter(p6).
candidate(p4).
candidate(p5).
candidate(p6).

%humans who are only candidates
candidate(p7).
candidate(p8).
candidate(p9).

%some random votes
votes(p1, p6).
votes(p2, p6).
votes(p3, p6).
votes(p4, p7).
votes(p5, p8).
votes(p6, p5).

I'm using human, voter, candidate, and votes. Here are some attempts to model the statement into a Prolog rule:

rule1 :-
  foreach((voter(X), candidate(Y), votes(X, Y)),(voter(Z), \+votes(Z, Y))).

rule2 :-
  foreach((human(X), voter(X), candidate(Y), votes(X, Y)),(human(Z), voter(Z), \+votes(Z, Y))).

Prolog does not support arbitrary first-order logic but only a fragment of it known as Horn clauses. These are statements of the form
$$\forall x_1, \ldots, x_n \,.\, P(x_1, \ldots, x_n) \Rightarrow q(x_1, \ldots, x_n)$$
where $P$ is built from atomic predicates and conjunctions, and $q$ is an atomic predicate. Not every statement in logic can be converted to this form.

You are suggesting use of foreach. Note that this is not properly a logic quantifier in Prolog, but rather a special-purpose routine which operates on lists. Pure prolog does not have any of this. If you are willing to use lists and to limit attention to only quantification over finite lists of elements, then you can just implement everything easily enough in Prolog using lists and functions on them. But that misses the point of logic programming, does it not?


What if the travelling salesman travelled by plane? It seems intuitive to solve a 2D dot-to-dot travelling salesman problem by eye using a greedy strategy. However we can only solve the TSP by eye if the graph is topographically accurate e.g. if A to B is 10 and A to C is 10 then B to C can't be 1000.

Is the greedy strategy still sub-optimal when we obey 2D scaling, ie travelling by plane? Below I managed to create a topographically accurate example where the greedy strategy is indeed sub optimal:

Starting at S:

Greedy: S B C A S => 2.83 + 4 + 5 + 2.2 => 14.03
Optimal: S A B C S => 2.2 + 3 + 4 + 3.16 => 12.36

Is there something special about the example above that will be common to all suboptimal greedy routes? Can geometry be used to minimize error?

I suggest you read more about the Traveling Salesman Problem.  All of your questions are answered in other standard references (such as the Wikipedia link I gave).  No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard.  The greedy algorithm is not optimal for that case, either.  No efficient algorithm is known that can always find the optimal solution, though there are algorithms that may be useful in practice.


How to get expected running time of hash table? If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much for an expected running time. Am I making a mistake here?

If you think of $1000$ as a constant, then yes, the running time is terrible. The idea of hash tables is that if the hash table is moderately bigger than the amount of data stored in it, then operations are very fast. Suppose for example that the hash table has size $m = 2n$. Then each operation takes constant time in expectation.

In implementations of hash tables, the hash table expands as more entries are inserted, to ensure that the ratio $\alpha$ is reasonable. Amortized analysis shows that this does not cause a performance hit in terms of the total running time, though individual operations might be slower (this is only a problem if you're writing a real-time application).


How to find $c$ and $n_0$ for Big-Oh questions I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n_0$ values.

For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I go about finding the $c$ and $n_0$ values for $g(n) = O(f(n))$?

In general, you should first set up the inequality and then try to solve for $n$ in terms of $c$. Often, this won't be feasible - there may not be a way to analytically obtain a closed-form solution involving only $c$ and $n$. In such cases, you can usually massage the inequality down to something where solutions can be determined by inspection.

In this case, we can start with the inequality $2^n \leq cn!$. You should be able to convince yourself that this isn't going to be a super-clean solution for $n$ here. Instead, we can try to massage this into a form that can be reasoned about.

Both of these terms involve repeated multiplication; we can write them out like that and see whether we notice a trick: $2 \times 2 \times ... \times 2 \leq c \times 1 \times 2 \times ... \times n$. We notice that the LHS is a product of $n$ terms, and the RHS consists of $c$ multiplied by $n$ other terms. Of the $n$ terms on the RHS besides $c$, all but $1$ are greater than or equal to the corresponding term on the LHS. If we rewrite the RHS as $(c \times 1) \times 2 \times ... \times n$ and choose $c = 2$, we get $2 \times 2 \times 3 \times ... \times n$. All $n$ of these terms are greater than or equal to the corresponding terms on the LHS, meaning the product is bigger, as we wanted. Thus, the choice $c = 2$ works for all choices of $n_0$.

Just to give you an idea of what a boring resolution would look like: let's show that $f(n) = 2n + 3$ is $O(g(n))$ if $g(n) = n + 1$.

We get $2n + 3 \leq c(n+1)$. Solving for $n$, we get $2n + 3 \leq c(n+1) = cn + c$, so $2n - cn \leq c - 3$ and $n(2 - c) \leq c - 3$. Note that if we choose $c \leq 2$, there are no valid solutions for $n$. We now have two cases: either $c \geq 2$ or $c < 2$. In the latter case, we can write $n \leq \frac{c-3}{2-c}$ which, along with the constraint that $n > 0$, yields no solutions. In the former case, we write $n \geq \frac{c-3}{2-c}$. You may now plug in any value of $c$ you like and find an $n_0$ to suit. We can see that the choice $c = 3$ allows us to choose $n_0 \geq 0$; the choice $c = 2.5$ requires that we choose $n_0 \geq 1$; etc.

If you're dealing with more complicated functions - specifically, ones that aren't monotonically increasing - you'll want to choose $n_0$ from the rightmost interval. Otherwise, the functions cross over each other again for a period, making your choice wrong. Usually, you don't have to worry about runtimes being other things than monotonically increasing, but it is a mathematical possibility of which you should be aware.


Reducing closed TSP to open with fixed starting vertex I have implemented a branch and bound algoritm for finding a Hamiltonian cycle in my software, but I actually need to find a shortest route from fixed vertex through all verticies ending at any of them.

As far as I understood, I can reduce closed-cycle TSP to open-cycle with fixed starting point by adding dummy vertex. But I can't find or figure out the weights of the edges of this vertex.

How can I do this?

Add two dummy vertices, $d_1,d_2$.  Add edges of weight 0 from all other vertices to $d_1$.  Add an edge of weight 0 from $d_1$ to $d_2$.  Add an edge of weight 0 from $d_2$ to your fixed starting vertex.  (If you need a complete graph, each missing edge can be replaced by an edge with weight $+\infty$ or some very large positive weight.)  Then any Hamiltonian cycle in the resulting graph will correspond to a Hamiltonian path in the graph that starts at your fixed vertex.


How many recursively enumerable sets are there? I'm trying to get some notion of how "many" recursively enumerable sets there are.

Here's one way of formalizing the question: consider $S =\{q: q\in Q\cap [0,1]\}$ and $R\subset S$ the set of recursively innumerable subsets of $S$.

What is the measure of $R$? My intuition is that it is 0 (i.e. a given set is almost surely not RE), but I am having difficulty proving it.

Countably infinite. Each RE set corresponds to a TM $M$ recognizing that RE set, where the set of all TMs is countably infinite.


Given an oriented graph, return true if paths have a specified length I'm having trouble solving this exercise about graphs, I hope you can help me:

Given a graph $G = (V,E)$, two sets of vertices $A \subseteq V$ and $B \subseteq V$ (represented as arrays), and an integer $k$, verify in $O(|V|+|E|)$ if each path that starts from a vertex $v \in A$ and connect a vertex $u \in B$ have a length that is greater or equal than $k$.

So if each vertex in $A$ that connect a vertex in $B$ have a length that is greater or equat to $k$, you should return $true$; otherwise, if exists at least one vertex of $A$ that connect a vertex in $B$ on a path that have a length that is less than $k$, you should return $false$.

My problem is to guarantee the linearity on the graph's dimension. My idea was to execute $|A|$ BFSs, one for each node that is contained in $A$. But, if $|A|=|V|$ i have a complexity that's squared on the graph's dimension.

Thank you very much.

New Update : I've tried to think about the Dijkstra algorithm; in that algorithm i have one source and i have to calculate the shortest path from the source and other nodes. Still it's easy if i have one source, but if i have a set of nodes, still cannot guarantee the linearity. Please, do you have more specific hint?

Let's say a vertex $v$ is at distance $t$ from the set $A$ if there exists a path of length $t$ from some element of $A$ to $v$; and there is no shorter path.

Can you think of an efficient way to compute the distance from $A$ to each individual vertex in the graph?

Perhaps you might like to modify BFS.  Hint:

   Maybe you can think of some way to change the initialization, to make BFS do what you want.


Interpolation: How to generate 3D objects from 2D cross-sections? Consider a sphere sitting on an $xy$-plane, and take 2D slices parallel to the $xy$-plane at various heights of z. Suppose we take 10 slices, evenly spaced along the $z$-axis, and now have 10 images of circles each with a corresponding $z$.

My goal would be a function that could learn from these 10 slices, such that if I were to input a new value of z, it would draw a circle (that is ideally close to the correct circle at that height).

Would there be a way to train something like a neural network to take the height z as the input, and output circles corresponding to the slice of a sphere at a particular height?

Such a method should scale to multiple dimensions. For example, if I had some multidimensional object I wished to reconstruct using slices of that object. Note that the parameter corresponding to slices may now be a vector.

EDIT:
The goal is to interpolate between 2D shapes that do not have simple analytic solutions. For example, one image is a circle and another is a rectangle.

The problems I am facing are where there are no simple analytic solutions for new shapes as a function of z. Imagine that there exists a very rugged non-linear 3D object (like the cross section of a person) - but we can only determine a few slices of this object as it is computationally expensive for some reason. We wish to interpolate between these few slices and generate a 3D object. Such a solution should also work for strange multidimensional shapes beyond 3D.

A neural network is not a good choice for this.  For this task, you can get a much better solution by analytically solving for the unknown radius of the sphere.  In particular, if the radius of the sphere is $s$, then a slice at height $z$ will have radius $r$, where these three variables satisfy the equation

$$(s-z)^2 + r^2 = s^2.$$

Re-arranging, we find

$$s = {z^2 + r^2 \over 2z}.$$

So, you can solve immediately for the radius of the sphere.  Once you know the radius of the sphere, you can predict the radius of other slices at any height of your choice, using the above equations a second time.

You could certainly train a neural network to interpolate, given enough training data.  For instance, the input to the neural network might be 6 images: the three slices "above" z, and the three "below", and the output is a bunch of slices interpolated between the one above z and the one below; where each image is a picture of the slice.  However I'm not sure how well this will work, and it will likely require a lot of training data to have any chance whatsoever of being useful, so you might do better to look for some other solution.


Count all paths between two vertices The problem is we have to count number of paths between a source and a destination in a graph. The brute force approach is using backtracking which is $O(n!)$.

Is there any better solution to this problem?

Note that we have to count paths so we can't visit the same node again in a path.

I think this problem is np-hard and is similar to finding hamiltonian path in a graph. So, I can use Held-Karp algorithm to solve it in $O(n^2*2^n)$ using dynamic programming. Am I right?

Let $A$ denote the adjacency matrix, $A^k$ its $k$th power, and $(A^k)_{ij}$ the entry of $A^k$ at row $i$, column $j$.  Then $(A^k)_{ij}$ is a count of the number of paths of length $k$ from node $i$ to node $j$.

Let $M = \text{Id} + A + A^2 + A^3 + \cdots$.  Then $M_{st}$ is a count of the number of paths (of any length) from source $s$ to destination $t$.  So, we just need to compute the matrix $M$.  The matrix $M$ can be computed using the matrix identity

$$M = (\text{Id} - A)^{-1}.$$

Thus, with a matrix subtraction and inversion, then looking at the $u,j$ entry of the resulting inverse, you can obtain a count of the number of such paths.

This includes paths where a node can be repeated.  If you want to count the number of simple paths, then the problem is #P-complete for general graphs (and thus likely has no efficient algorithm), or can be done in linear time for directed acyclic graphs by topological sorting and then using dynamic programming.