Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same answer. My steps are below.

Given $T(1) = 1$, $T(2) = 1$ (Time taken is constant in these two cases)

I noticed that by unrolling a few times:
$$T(n) = 2\left[2T\left(\frac{n}{4}\right)+\frac{n}{2}\log{\frac{n}{2}}\right] + n\log n$$
$$T(n) = 2^{2}T\left(\frac{n}{2^{2}}\right)+n \log{\frac{n}{2}} + n\log n$$
$$T(n) = 2^{2}\left[2T(\frac{n}{8})+\frac{n}{2}\log{\frac{n}{4}}\right]+n \log{\frac{n}{2}} + n\log n$$
$$T(n) = 2^{3}T\left(\frac{n}{8}\right)+2n\log{\frac{n}{4}}+n \log{\frac{n}{2}} + n\log n$$

This looks like it follows
$$T(n) = \underbrace{2^{k}T\left(\frac{n}{2^k}\right) + 2^{k}n\log\left(\frac{n}{2^{k+1}}\right)}_{\log_2n \text{ times}}$$

I use the fact that $\frac{n}{2^k} = 1$, so $k = \log_2n$. Substituting this in: $2^{k}T(\frac{n}{2^k})$ = $2^{\log_2n}T(1) = n$

Doing this summation as:
$$T(n)=n + n\log_2{n}+\sum_{k=0}^{\log_2{n}-1}2^{k} n \log_2\left(\frac {n} {2^{k+1}}\right)$$
$$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2\left(\frac {n} {2^{k+1}}\right)$$
$$T(n)=n + n\log_2{n}+n\sum_{k=0}^{\log_2{n}-1}2^{k} \log_2(n-k+1)$$

This is where I get stuck, I have a feeling I messed something up somewhere and it is making this summation much harder to solve, but I am not sure where. Where did I go wrong?

First, you can get the the result from the second xase of master theorem. Second, you have a mistake in your exapnsion:

$$T(n) = 2T(\frac{n}{2}) + n\log(n) = 2(2T(\frac{n}{2^2} + \frac{n}{2}\log(\frac{n}{2})) + n\log(n) = n\log(n) + n\log(\frac{n}{2}) + 2^2T(\frac{n}{2^2}) =  n\log(n) + n\log(\frac{n}{2}) + 2^2(2T(\frac{n}{2^3} + \frac{n}{2^2}\log(\frac{n}{2^2})) = n\log(n) + n\log(\frac{n}{2}) + n \log(\frac{n}{2^2}) + 2^3T(\frac{n}{2^3})$$

Hence, we will have the following, if we suppose $T(1) = 0$, w.l.o.g:

$$T(n) = \sum_{i=0}^{\log(n)}n\log(\frac{n}{2^i}) = n \log(\Pi_{i=0}^{\log(n)}\frac{n}{2^i}) = n \log(\frac{n^{\log{n}}}{2^{\frac{\log(n) \times (\log(n) + 1)}{2}}}) = n \log(n) \log(\frac{n}{\sqrt{2}\sqrt{n}}) = n \log(n)\log{\frac{\sqrt{n}}{\sqrt{2}}} = \Theta(n
\log^2(n))$$

Be aware that, if we change the values of $T(1)$ and $T(2)$ to the given constant values, nothing changed in the asymptotic analysis.


Big-O in computer Science As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.

The most conspicuous use of big O notation is in the analysis of running times of algorithms. Since the exact running time depends on the cost of specific instructions, there is no point in saying that a certain algorithm takes time $14.3n$. Also, it is difficult, and pointless, to analyze everything exactly. Big O notation hides all these details while keeping the nucleus, which is the asymptotics of the running time. As an example, since quicksort is $O(n\log n)$ while insertion sort is $O(n^2)$, you should expect the former to outperform the latter for large values of $n$. (Of course, it all depends in practice on the so-called hidden constants.)


Amount of k-partitions of a number I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
For example:

The partitions of size 2 for number 5 are:

[4, 1]
[3, 2]

The partitions of size 3 for number 6 exists only of:

[3, 2, 1]

Notice that [2, 2, 2] isn't a partition because it has a repeating use of 2.

I currently have implemented a dynamic algorithm that finds the amount of partitions that allow repetition. Here $m$ is is the number and $n$ is the size of the partitions.

def count_partitions(m, n):

    def e_at(i,j):
        if i == j and j == -1:
            return 1
        if i < j:
            return 0
        else:
            return p[i][j]

    p = [[-1 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        p[i][0] = 1

    for i in range(m):
        for j in range(1, min(i + 1, n)):
            if i < 2*j:
                p[i][j] = e_at(i-1,j-1)
            else:
                p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j)

    return p[m-1][n-1]

I've also got a program to generate all the different distinct k-partitions of a number $n$

def generate_partitions(n, k):
    if n == 0:
        return []

    def rec_partition(m, b, n, a, l):
        if m == 0:
            l.append(conj_partition(a[:n]))
        else:
            c = a[n]
            for i in range(1, min(b,m) + 1):
                a[n] = i
                rec_partition(m-i, i, n+1, a, l)
            a[n] = c

    def has_double(l):
        for i in range(len(l) - 1):
            if l[i] == l[i+1]:
                return True
        return False

    l = []
    a = [0] * n

    a[0] = k
    rec_partition(n - k, k,1, a, l)

    return sorted([p for p in l if not has_double(p)], reverse=True)

So far the only way I found to get the number of distinct k-partitions is to generate them all and take the length of the returned list.

However I feel like there would be a better way to get the amount without generating them all by modifying the dynamic programming algorithm above. But I haven't had any luck with that.

Anyone has any idea that would help?

You can solve this with DP. Let $DP[n][k][m]$ denote the number of partitions of $n$ into $k$ numbers, all of which are distinct and at most $m$. Then we have the recurrence

\begin{align}
DP[n][k][m] &= \sum_{v = 1}^{m} DP[n-v][k-1][v-1]\\
&= DP[n][k][m-1] + DP[n-m][k-1][v-m]
\end{align}

Since we can take the numbers forming the partition from largest to smallest, so whenever we take some number, all numbers we take after it must be strictly smaller. The base case is $DP[0][0][m] = 1$ for any $m$ and $DP[x][y][m] = 0$ whenever $x < 0$ or $y < 0$. If you care about the order of the elements in the partition, multiply the result by $k!$.

We can calculate this recurrence in $\mathcal{O}(n^{2} k)$, but tighter analysis gives an even better bound:

For a state $(n', k', m')$ to be reachable by this recurrence from $DP[n][k][n]$, we must have $m' \leq \frac{n-n'}{k-k'} \leq \frac{n}{k-k'}$ (since our number decreased by $n - n'$, so some number in the current partition of sum $n - n'$ and size $k - k'$ must be at most $\frac{n - n'}{k - k'}$). But this means that for any fixed $k'$, there are at most $\frac{n^{2}}{k-k'}$ reachable DP states, and

\begin{equation*}
\sum_{k' = 0}^{k-1} \frac{n^2}{k-k'} = \mathcal{O}(n^2 \log k)
\end{equation*}

Thus the actual complexity is $\mathcal{O}(n^2 \log k)$.


Rule induction principles in Harper's PFPL I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19).

(1) In the rule induction principles for nat,

  To show P(a nat) whenever a nat, it is enough to show:
  (1) P(zero nat).
  (2) for every a, if (a nat and) P(a nat), then P(succ(a) nat).

why is the bracketed "(a nat and)" clause necessary (and similarly for tree)?  This seems "natural" - we shouldn't need to prove things about syntactic entities that don't define nats - but doesn't appear in the definition given of property P "respecting the rules" defining nat/tree (also on p. 19), which is how the rule induction principle is defined.  In the proof of Lemma 2.1, the extra "a nat and" part has become part of the definition of the property P - what's going on here?

(2) I don't understand the induction step of Lemma 2.1 (succ(a) nat implies a nat).  If I were doing this proof, I'd just invert the rules for nat right away, or, using Harper's property P, say: If succ(a) is of form succ(b), then by injectivity, a equals b, hence b nat as a nat, but injectivity hasn't been proven yet.  It seems instead that Harper applies the induction hypothesis about a directly to succ(a) - I must be missing something.

(3) In a more naive framework, Lemma 2.3 would just follow from sufficiency of the = nat relation rules ("inversion"), but I don't know how to write down a proof in this style.  Why is induction even needed?

I'm sorry if these questions seem like nitpicking, but Martin-Löf/LF feels very foreign to me.  If I squint and pretend I'm doing everything in a more "traditional" operational semantics, I can read other parts of the book (with slightly different proofs), but I feel I'm missing the point in doing so.

If these questions are too tedious to answer individually, are there other references on doing semantics in this style?

At the beginning of Section 2.4 the book explains that $\mathcal{P}(J)$ stands for a property of a judgment $J$. That is, the $\mathcal{P}$ in $\mathcal{P}(a\ \mathtt{nat})$ does not stand for a property of numbers, but a property of the judgment $a\ \mathtt{nat}$, which is the judgment that "$a$ is a number".

It just so happens that the inference rules for $a\ \mathtt{nat}$ precisely match those for numbers. Namely, the two rules defining the judgment $a\ \mathtt{nat}$ are
$$\frac{ }{\mathtt{zero}\ \mathtt{nat}}$$
and
$$\frac{a\ \mathtt{nat}}{\mathtt{succ}(a)\ \mathtt{nat}}.$$
Therefore, if we want to show that the judgment $a\ \mathtt{nat}$ has some property $\mathcal{P}$, then we need to show that the base case $\mathtt{zero}\ \mathtt{nat}$ has the property $\mathcal{P}$, and that whenever $\mathcal{P}(a\ \mathtt{nat})$ holds then $\mathcal{P}(\mathtt{succ}(a)\ \mathtt{nat})$ holds as well.

Or to put it the other way, the strange looking "$\mathtt{nat}$" is there because we are not talking about numbers, but about the judgments "expression $a$ satisfies the judgment $\mathtt{nat}$".


Computing the closest match of an automaton and a string I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting for the automaton). I've looked around and found Levenshtein Automaton but had trouble finding out how it would be implemented from my automaton.

Also, are there any other methods that would be suitable/worth looking at for my problem?

You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th prefix of $w$ and a word that causes the NFA to reach state $s$. This quantity is given by the following calculation, involving an auxiliary array $A'$:

$A(0,s)$ is the length of the shortest path from the initial state of the NFA to $s$ [insertion].
$A'(\ell+1,s)$ is the minimum of the following quantities:

$A(\ell,t)$ if there is a transition from $t$ to $s$ marked $w_{\ell+1}$.
$A(\ell,t)+1$ if there is some transition from $t$ to $s$ [substitution].
$A(\ell,s)+1$ [deletion].

$A(\ell+1,s)$ is the minimum of $A'(\ell+1,t)+\kappa(s,t)$ over all $t$, where $\kappa(s,t)$ is the length of the shortest path from $t$ to $s$ in the NFA [insertion].

Finally, the distance is the minimum of $A(n,s)$ taken across all accepting states $s$.

This calculation requires that you compute in preprocessing the all-pairs-shortest-path matrix for the directed graph underlying the NFA. Some of the quantities arising in the computation could be infinite.


Time complexity calculation I was calculating the time complexity of the following recurrence relation given that T(1) = 1 :

T(n) = 2T(n/2) + Logn

I was calculating the value and this is where I reached:

T(n) = logn + 2log(n/2) + 4log(n/4) + 8log(n/8) + .....+ 1

I have tried solving this by opening log but I'm unable to reach O(n). I don't want any other method like substitution or root tree to be used. I want to use simple maths and reach O(n), please let me know if you have a clue about it.


Does graph connectivity being NP-complete imply NL=P? I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly).

However, my supervisor claims that actually, connectivity being NP-complete implies that NL=P=NP. I can't see why this would be the case; the only additional information we're assuming is that there is a polynomial-time reduction from any NP problem to an NL problem, which does not imply that there exists a corresponding log-space reduction. Wikipedia also mentions

  Whether under these types of reductions the definition of NP-complete changes is still an open problem. All currently known NP-complete problems are NP-complete under log space reductions.

... which seems to support my argument.

If NP completeness of connectivity implies $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$, then $\mathsf{P}\neq\mathsf{PSPACE}$. To see why, suppose $\mathsf{P}=\mathsf{PSPACE}$, then connectivity (and any other non trivial language in P) is NP complete, thus $\mathsf{NL}=\mathsf{P}=\mathsf{PSPACE}$ (by our original assumption), which contradicts the space hierarchy theorem.

This means such implication is not yet known. For completeness, I'll add that a negative answer would imply the existence of an NP complete problem which is not complete under logspace reductions (if all NP complete problems were also complete under logspace reductions, then NP completeness of connectivity implies $\mathsf{NL}=\mathsf{NP})$.


How do I convert the following GNFA to regular expression? Here is a GNFA I made from an NFA.

I'm unsure how to treat the node of b(a∪b)* (the first node after the start node and the one below it). Since it doesn't lead to any goal state, do I disregard it in when I generate the regular expression?

Given an NFA, we can simplify it to an equivalent NFA with possibly fewer states by repeatedly applying the following two pruning steps:

Remove any states which are not reachable from the initial state.
Remove any states from which no final state can be reached.

In your case, this will result in removing the left bottom state.


Decomposing a graph into paths Given a simple graph with $n$ vertices, show that you can remove all edges in $O(n\log n)$ rounds, where in each round you are allowed to remove all edges of any (single) path.

A classical result of Lovász (On covering of graphs) states that a graph on $n$ vertices can be decomposed into at most $n/2$ paths and cycles, and so into at most $n$ paths.


Is Blum's theorem for acceptable enumerations of partially computable functions bidirectional? Theorem II.5.8 in P. Odifreddi's Classical Recursion Theory states that

  If $\{\psi_e\}_{e\in\omega}$ is an acceptable system of indices, then there is a recursive permutation $h$ such that
  $$ h(\psi_e(x)) = \varphi_{h(e)}(h(x)) . $$

where $\varphi$ is the standard enumeration of p.c. functions.

My question is whether the converse case holds: For the standard enumeration $\varphi$, some permutation $h$ and some computable enumeration of p.c. functions $\psi$, if we have $h(\psi_e(x)) = \varphi_{h(e)}(h(x))$, then $\psi$ is an acceptable enumeration.

Some possible approaches:

Prove this simpler form and then prove it is equivalent to question:

For some computable permutation $h$ and standard enumeration $\varphi$, $\theta_e(x) = h(\varphi_e(x))$ is also an acceptable enumeration.

H. Rogers' Theory of Recursive Functions p54, defines a universal partial function to be a partial computable function $\psi$ for which exists a computable function $f$ of two variables, such that $\forall x; \varphi_x = \lambda y.\psi f(x,y)$. So $f$ codes both index and argument and $\psi$ takes it as its single input. Then it proves that

  If $\psi$ is universal and $g$ and $h$ are recursive permutations, then $\eta = g^{-1}\psi h$ is universal.

Is this statement, for $g=h$, equivalent to the mentioned converse above?

It seemed very obvious to me at first, though I couldn't manage to prove it. What am I possibly missing?

Update
Removed the second question as an intermediate approach to solve the main question.

For the standard enumeration $\varphi$ and some computable permutation $h$,
$$\forall e;~ \psi_e = h^{-1} \varphi_{h(e)}h ~~~~(*)$$

We want to prove that such $\psi$ is an acceptable enumeration. It suffices to find computable functions $f$ and $g$ such that for all $e$, $\psi_e = \varphi_{f(e)}$ and $\varphi_e = \psi_{g(e)}$.

$h^{-1} \varphi_{h(e)}h$ is partial computable. So by s-m-n theorem, there is a computable function $f$ such that for all $e$, $h^{-1} \varphi_{h(e)}h = \varphi_{f(e)}$, therefor by $*$ we have, $\psi_e = \varphi_{f(e)}$

$h \varphi_e h^{-1}$ is also partial computable. So again by s-m-n theorem, there is computable $g'$ such that for all $e$, $h \varphi_e h^{-1} = \varphi_{g'(e)}$. Define computable function $g$ as $g = h^{-1} g'$. In $*$ replace $e$ with $g(e)$ to get
$$\psi_{g(e)} = h^{-1} \varphi_{hg(e)}h ~.$$
By definition of $g$, we have $h g = h h^{-1} g' = g'$, so
$$\psi_{g(e)} = h^{-1} \varphi_{g'(e)}h ~.$$
By definition of $g'$
$$\psi_{g(e)} = h^{-1} h \varphi_e h^{-1} h ~,$$
and thus
$$\psi_{g(e)} = \varphi_e ~. ~~\Box$$


Is grammar that describes an equation in prefix (Polish) notation always unambiguous? I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation:

$$Expr \rightarrow + \, Expr \, Expr \, | \, * \, Expr \, Expr \, | \, 0 \, | \, \dots \, | \, 9 \,$$

While I have no trouble taking the derivation and creating its parse tree, the question also asks whether the grammar is ambiguous. In the scope of what I've been taught, my only tool for proving ambiguity has been to find a different parse tree for whatever leftmost or rightmost derivation I have, thus proving multiple valid parses and ambiguity. However, I have not been told how to prove unambiguity. I am fairly confident that the grammar described above is unambiguous based partially on intuition, and partially because it's designed for prefix notation. I tried to generate new trees for a given string to prove ambiguity, but since the operator is always leftmost, I could not find any string in which multiple parse trees could be created. If I am mistaken, please let me know.

My question is this: Is it possible for grammar that describes strings using prefix (Polish) notation such as the one above to ever be ambiguous? My intuition tells me that it will always be unambiguous, but I was wondering why this might be the case.

Your question is easy to answer. Take your grammar, and add the following rules:
$$
\begin{align*}
&S \to T \mid \mathit{Expr} \\
&T \to \mathit{Expr}
\end{align*}
$$

Your particular grammar, however, does seem unambiguous.

Here is how I would try to prove it. First, show the expressions are self-delimiting: no expression is a prefix of another one.

Now, when trying to parse an expression, you can determine which rule should be applied first by looking at the first symbol. In the interesting cases, you then have to partition the input into two expressions. The self-delimiting property should make this possible in a unique way.


Prove that $\text{EXACT-TRIPLE}$ is not in NP I received the following assignment:

$\text{EXACT-TRIPLE} = \{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \}$.

I need to decide whether this problem belongs to NP or not. I assume it does not. How do I prove that?

The problem is coNP-hard, and so not likely to be in NP. Indeed, given a formula $\phi$, you can construct a formula $\phi'$ such that if $\phi$ has $x$ satisfying assignments then $\phi'$ has $x+3$. This gives a reduction from the coNP-complete problem UN-SAT to EXACT-TRIPLE.


Example for a non-trivial PCP verifier for an NP-complete problem During my involvement in a course on dealing with NP-hard problems I have encountered the PCP theorem, stating

$\qquad\displaystyle \mathsf{NP} = \mathsf{PCP}(\log n, 1)$.

I understand the technical definition of a PCP verifier, so I know in principle what kind of algorithm has to exist for every NP problem: a randomised algorithm that checks $O(1)$ bits of the given certificate for the given input using $O(\log n)$ random bits, so that this algorithm is essentially a one-sided error Monte-Carlo verifier.

However, I have trouble imagining how such an algorithm can deal with an NP-complete problem. Short of reading the proof of the PCP theorem, are there concrete examples for such algorithms?

I skimmed the relevant sections of Computational Complexity: A Modern Approach by Arora and Barak (2009) but did not find any.

An example using a $\mathsf{PCP}(\_,\ll n)$ algorithm would be fine.

Following up on a comment by sdcvvc I checked out example 11.7 in Computational Complexity: A Modern Approach by Arora and Barak (Draft of 2008). There, the authors describe a "PCP algorithm" for the problem Graph Non-Isomorphism (GNI):

  Input: Two graphs $G_0$ and $G_1$ with $n$ vertices each.

  Output: Accept if and only if $G_0$ and $G_1$ are not isomorph (write
  $G_0 \not\equiv G_1$).

We denote the certificate (they call it "proof") by $\pi$ and with $\pi(i)$
the $i$-th bit of $\pi$.

The algorithm $A$ proceeds as follows:

Choose a bit $b \in \{0,1\}$ uniformly at random.
Choose a permutation $\sigma \in S_n$ (of the vertices of $G_b$).
Accept if $\pi(\langle\sigma(G_b)\rangle) = b$, reject otherwise.

Here, $\langle \_ \rangle$ is some computable bijection from $\mathbb{N}^n$
to a suitable range $[0..N] \subseteq \mathbb{N}$. We assume that if the derefenced
bit in $\pi$ does not exist, i.e. the certificate is too short, we reject.

Claim: By above algorithm, GNI is in $\operatorname{PCP}(n \log n, 1)$, i.e.

the algorithm uses $O(n \log n)$ random bits and queries $O(1)$ bits of $\pi$,
$(G_0, G_1) \in \mathrm{GNI}$ implies that there is some certificate $\pi$
 so that $\Pr[A(G_0, G_1, \pi) \text{ accepts}] = 1$, and
$(G_0, G_1) \notin \mathrm{GNI}$ implies that
 $\Pr[A(G_0, G_1, \pi) \text{ rejects}] \geq \tfrac{1}{2}$ for all certificates
 $\pi \in \{0,1\}^*$.

Ad 1: Clear from the algorithm by noting that uniform permutation sampling
is possible with $\approx n \log n$ random bits¹.

Ad 2: Consider the certificate

$\qquad\displaystyle \pi(\langle H \rangle) =
  \begin{cases}
0 &, H \equiv G_0, H \not\equiv G_1 \\
1 &, H \equiv G_1, H \not\equiv G_0 \\
\text{arbitrary} &, \text{ otherwise}
  \end{cases}$

where $H$ are all graphs with $n$ nodes. Since $G_0 \not\equiv G_1$ and
$\sigma(G_b) \equiv G_b$, we have $\sigma(G_b) \not\equiv G_{1-b}$ for all $b$ and
$\sigma$. The query to $\pi$ therefore always yields $b$ and thus always accept.

Ad 3: Let $\pi \in \{0,1\}^*$ arbitrary and $H = \sigma(G_b)$ the chosen
query graph. If our query hits a non-existing bit of $\pi$ we reject by assumption,
which is correct. Otherwise, we calculate

$\qquad\begin{align}
  \Pr[\text{accept}] &= \Pr[b=0] \cdot \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                  + \Pr[b=1] \cdot \frac{\#[\pi(H) = 1 \mid H \equiv G_1]}{\#[H \equiv G_1]} \\
                 &= \frac{1}{2} \cdot \left( \frac{\#[\pi(H) = 0 \mid H \equiv G_0]}{\#[H \equiv G_0]} +
                                             \frac{\#[\pi(H) = 1 \mid H \equiv G_0]}{\#[H \equiv G_0]}
                                     \right) \\
                 &= \frac{1}{2}
\end{align}$
using that $H \equiv G_1 \iff H \equiv G_0$ in this case.

Thus, the claim is proven.

Some observations that helped me grasp these concepts better.

The certificate $\pi$ can be arbitrarily long and arbitrarily complex. Note that
"good" certificates for the above algorithm essentially solve the same problem
as the algorithm (many times).
But that does not imply that any decision problem can be solved in PCP style
by "just providing the answer in the certificate". Condition 3 prevents any
naive attempt of that kind.
It is in general not possible to derive an efficient (randomised one-sided-error)
algorithm that guesses the certificate (as is the case for NP-certificate verifiers).

Strictly speaking, this assumes that $n!=2^k$ (which of course almost never holds)
since we have infinite worst-case runtime
for other $n$. However, Arora/Barak seem to ignore this aspect.


Feasible solution existence I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty.

Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is any feasible solution to a linear program constrained with a lot of linear inequalities. Is it possible to perform the feasibility check without actually optimizing an objective function? I know that there are polynomial time optimization algorithms in O(n^3.5), but is it possible to reduce the time even more by skipping the linear optimization part?

In particular an iterative algorithm may be very beneficial for me, since I'm adding and removing inequalities to the system all the time and after each addition, I'm checking the feasibility again. Thus, the best would be a king of inductive approach which (using some previously collected information) quickly determines if the set stays feasible after addition of a new inequality.

I would prefer to write my own piece of code for this problem instead of using a 3rd party solver library.

I have seen a related post, but my question targets a general set of equations.

Theory

There's a simple argument to show you can't help to do that much better.  In particular, testing for feasibility of a set of linear inequalities can't be too much easier than optimizing a linear objective function subject to a set of linear inequalities.

Why?  If we want to optimize the objective function $\Psi$ subject to a set $\mathcal{S}$ of inequalities, one way to do that is to use binary search on the value of the objective function.  This can be done by repeated feasibility testing of a set of linear inequalities of the form $\mathcal{S} \land \Psi \ge c$, where $c$ is a constant.  In particular, you use binary search to find the largest value of $c$ such that $\mathcal{S} \land \Psi \ge c$ is feasible.

Very roughly speaking, binary search can be expected to succeed within $O(\lg n)$ iterations.  Therefore, testing for feasibility can't be more than $O(\lg n)$ times faster than maximizing an objective function.

Practice

I don't know of any more efficient way to test for feasibility of a set of linear inequalities, than simply to solve a linear program using standard linear solvers.  Basically, you pick any old objective function, and use the linear solver to maximize it subject to the set of linear inequalities.  I don't know of any procedure that is faster in practice than this straightforward approach.


Checking whether there is k circles with common area I have N circles with different radius and position in the plane. The problem is finding k circles which have a common area.Obviously this can be solved using Brute-Force in $O(N^k)$. Is there a more efficient way to do such query?

This problem and related problems have been studied in the paper "Bajaj, C., & Li, M. (1983). On the duality of intersections and closest points. Cornell University."

They call a common area for $k$ circles a '$k$-intersection'. The paper gives an $O(n^2\log n)$ algorithm for the problem of finding a $k$-intersection when the circles have different radius. (Theorem 13) It is not clear to me from the paper how that bound is achieved, but I do see how to achieve $O(n^3)$ time with their approach.

Algorithm

The main idea is to construct the following (directed) planar intersection graph $G=(V,E,F)$: The vertices $V$ of this graph are all intersection points of the circles and the edges $E$ are the circle arcs connecting those intersection points. The direction of the edges is counterclockwise on the circle, such that the interior of the circle it is part of lies to the left of the edge. We also keep track of the faces $F$ of this planar graph, which are the regions enclosed by the edges $E$.

Note that each region of circle intersections corresponds to a face of this planar graph and that the number of circles that contain the region is equal to the number of clockwise boundary edges of the corresponding face. If we have computed $G$, then we can maintain a counter for each face in $F$ and traverse the graph to visit all edges and increase the counter of face left of each edge. Then, after we have traversed the edges, each face has the number of circles that contain it stored in the counter.

Complexity

Since there can be at most $O(n^2)$ intersections of $n$ circles, $|V|=O(n^2)$. Since $G$ is a planar graph, $|E|\leq 3|V|-6 =O(n^2)$. So, traversing the graph takes $O(|V|+|E|)=O(n^2)$ time.

As for constructing the graph, the authors claim that this graph can be constructed in $O(n^2\log n)$ time by sorting the edges. I did not see any further explanation of this in the paper and do immediately see how to achieve this. (in particular, it would be helpful to know on what they sort.)

I do see how to do this in $O(n^3)$: The vertices and edges of the graph can be constructed in $O(n^2)$ time by iteratively adding new circles. When a new circle is added, we add the new intersection points and subdivide some of the existing edges.

Adding the faces is more complicated and I currently only see the naive method of for each edge $e$, traversing all edges that are on the boundary of the two faces adjacent to edge $e$. This takes $O(n)$ per edge, so $O(n^3)$ in total. It does seem like we can do better here, but I currently don't see how.

$O(n^2\log n)$ is good, but can we do better? For the case where the circles all have the same radius, this is possible: Chazelle and Lee have found an $O(n^2)$ time algorithm based on an implicit traversal through the intersection graph ("Chazelle, B. M., & Lee, D. T. (1986). On a circle placement problem. Computing, 36(1-2), 1-16."). Whether $O(n^2)$ is possible for the case with circles of different radius they leave as an open problem, which has remained open for now, as far as I'm aware.


Solve SUBSET SUM for Reciprocals of Primes Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$.

Problem

Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (not pseudo-polynomial) time for every $\alpha \in \mathbb{N}$ and $P, p_1, ... , p_n$ unknown.

First attempts

$P$ and $ p_1, ... p_n$ can be calculated with $P = \sqrt[n-1]{\prod_{i=1}^{n}{a_i}}$ and $p_i = P / a_i$.

Now we can write the problem as $\alpha/P = 1/p_{i_1} + ... + 1/p_{i_n}$

The observation is that the denominator of the reduced fraction $1/p_{i_1} + \cdots + 1/p_{i_m}$ is $p_{i_1} \cdots p_{i_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't divisible by any $p_{i_j}$. Indeed, the numerator is simply
$$
\frac{p_{i_1} \cdots p_{i_m}}{p_{i_1}} + \cdots + \frac{p_{i_1} \cdots p_{i_m}}{p_{i_m}}.
$$
All terms but the $j$th are products of $p_{i_j}$, but the $j$th term isn't, so the numerator isn't divisible by $p_{i_j}$.

As a consequence, if $\alpha/P$ is a sum of reciprocals of distinct primes, then we can read off the primes from the prime factorization of the reduced form of $\alpha/P$. We can compute this reduced form efficiently using GCD. Since we know $p_1,\ldots,p_n$, we can figure out whether the denominator is a product of a subset of $\{p_1,\ldots,p_n\}$, and if so, it only remains to check whether $\alpha/P$ is equal to the sum of reciprocals of prime in this subset.


Dynamic programming algorithms with log in the run-time Most of the classic examples of dynamic programming algorithms have run-times such as $n$ or $n^2$. Are there any natural examples with a $O(n \log n)$ run-time?

One natural example is finding the longest increasing subsequence of a sequence of $n$ numbers. Candidate subsequences can be linked in the input sequence. This is a fairly common exercise, and works for other type of subsequences, too. It is actually the exercise 15.4-6 in the 3rd edition of the Cormen et al. book too. For an algorithm, see Section 2.2 in these notes.


Is it possible to do multitasking without context switch with just one cpu? All the article I can find seems to talk about multitasking and context switch as its a two different thing. It seems that multitasking and context switch are the same thing.

Yes, it is possible (depending upon what you mean by "context switch").  See cooperative multi-tasking.  In cooperative multi-tasking, the operating system never needs to perform a context switch between tasks -- instead, tasks voluntarily take care of saving their own state and switching between themselves.


that there would be no perfect strategy for poker In my opinion, every imperfect information game where there is the possibility of bluffing lacks a perfect (or winning) strategy, for the simple reason that knowing your opponent's strategy will let you beat him easily (even if his strategy isn't 100% deterministic).

So why do the guys that developed 'Cepheus' claim that they made a program playing poker with a perfect strategy, claiming that their AI 'is guaranteed to not lose money in the long run' ?

I'm pretty sure I can create a strategy winning versus Cepheus, because I know its strategy.

Where am I wrong ?

Nash proved that every zero-sum game has a perfect strategy called a Nash equilibrium. This is a possibly randomized strategy for both players such that given that one player follows the strategy, it doesn't pay the other player to deviate from her strategy. As an example, consider the game rock, paper, scissors. One Nash equilibrium here has both players choosing their signal randomly. If one player does that, there is no point for the other player to follow any other strategy (though it doesn't hurt).

Since Poker is a symmetric zero-sum game (both players are treated the same by the game), the value of the game is zero, and any Nash equilibrium on average results in zero expected profit for both players. According to Wikipedia, Cepheus is an approximation to such a strategy. As such, Cepehus' strategy may be randomized.

What about bluffing? Let's consider a variant of rock, paper, scissors in which players can bluff. Say each player writes their choice on a piece of paper, and then there is some structured dialog in which players announce their choice and offer the other player to capitulate. The random strategy is still perfect, in that if one player follows it, it doesn't pay for the other player to deviate from it.

While Cepehus (if it were perfect) shouldn't lose on the long run, it is not guaranteed to be a good strategy in practice, since it only promises you a small negative expected profit. Perhaps when playing against good human players it will just break even on average. That doesn't mean that humans are any better than it, just that they're not any worse. Another possibility is that while in theory the only guarantee is that it breaks even, in practice it wins against sub-optimal humans. This is an empirical question that the developers are testing right now through their website.


Can there exist a recurrence relation for "sequential search"? I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.

Sure.

The cost of searching a list of length zero is zero; the worst-case cost of searching a list of length $n$ is one greater than the cost of searching a list of length $n-1$. So
$$\begin{align*}T(0)&=0 \\ T(n)&=T(n-1)+1\,,\end{align*}$$
with solution being, as you'd expect, $T(n)=n$.


Finding the time complexity of fibonacci sequence I tried it as follows and would like to know if it is correct.

The analysis is not accurate although the result is correct. You could write it more accurately by replacing $=$ with $\le$

$T(n) \le c(1+2+..+2^{n-1})$ ( $\le$ since not all level have same number of children, consider the most right-handed path, n is decreasing by $2$ every step ).

Indeed a more careful analysis can get you a tighter bound as mentioned in the comment. The idea is, the time $T(n)$ is computed with $T(n-1) + T(n-2)$ the same way as the actual fibonacci $F(n)$, and since $F(n) = O(\phi^n)$ for $\phi = (1+\sqrt{5})/2$ as the closed form.

Thus $T(n) = O(\phi^n)$ which is slightly smaller than $2^n$


On the proof techniques of Udi Manber I was familiar with the approach of first coming up with an algorithm, and then proving the loop invariant to come up with an algorithm as elucidated in CLRS (Introduction to algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein). Lately, on reading Udi Manber's introduction 'A creative approach' I have come across the idea of positing and algorithm and then proving it using induction and also getting the algorithm itself. It's like having your cake and eating it too.
There is one question which remains inexplicable to me. When I am proving an algorithm using Udi Manber's approach, am I arguing in the object language or in the meta language? In either of these cases, how am I just generating a proof? From the meta language it seems sensible to generate a proof in the object language, but arguing the soundness/completeness of these class of arguments appears difficult. But how do I guarantee that the proof is correct in the object language if it is generated by the object language itself? It is unclear to me if it is the metalanguage or the object language that is involved in here.
This question might seem poorly phrased, but I cannot find a better way to express it. Udi Manber's approach seems to generate an algorithm despite not knowing a priori what the algorithm itself is. This is something counter intuitive to me. Please kindly explain.

It is not a rigorous answer, but if we are to posit in the way of Udi Manber using induction, we are tacitly positing a recursively enumerable algorithm that can terminate. Udi Manber's algorithmic approach though does not necessarily posit a primitive recursive algorithm. If the problem in our class is not recursively enumerable, then we cannot use Udi Manber's approach, and it may as well be uncomputable. A primitive recursive algorithm is likely to be more efficient than a recursively enumerable one.


Is 3-colouring NP-hard for 5-colourable graphs? Recently it was shown that it is NP-hard to find a 5-colouring of a 3-colourable graph.
More generally, it is NP-hard to distinguish $k$-colourable graphs from those that are not $(2k-1)$-colourable, for $k\ge 3$.

J Bulín, A Krokhin, J Opršal. Algebraic Approach to Promise Constraint Satisfaction, STOC 2019. doi:10.1145/3313276.3316300 (preprint)

Turning the question around:

  Is deciding if a 5-colourable graph is 3-colourable NP-hard?

Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.


Why does lower integer represent higher priority in scheduling literature? I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu)

In the algorithms that involve priorities, it is said that smaller integer represents higher priority (e.g. a process with priority 1 has more priority than one with 3). Then, in the subsequent discussions, there are terms involved like: "Let Pi be a process with a higher priority..." On such occurrences, I get confused whether higher priority means actually higher priority or larger integer. In most of the cases it means the former, however sometimes I've to guess that from the context, which is a bit time consuming.

As far as I know, all algorithms will work well with slight modifications if larger integers represented higher priority, and that would avoid confusion. So my question is:
Is there any reason, apart from conventional / historical one, for using smaller integer for denoting higher priority? If not, why not amend it and avoid confusion?

This has always troubled me too.  The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things).

In schedulers we use the word priority in the sense of:

  the right to take precedence or to proceed before others[1]

It came into English from Norman French after the Norman conquest of England in 1066.  It came into Norman French from the Latin word prior, which (in English) means

  existing or coming before in time, order, or importance[1]

I added the emphasis on the word order to emphasize that we are using the word in the sense that requires we use ordinal numbers.  So you should think of it in terms of a medieval court hierarchy.  The king is seated at the dinner table first because he has the highest rank.  The prince (etymology: via Norman French from Latin princeps, which means "first citizen"[2]) is seated second because he has the next highest rank.  Then the dukes are seated third because they have the next highest rank.  And so on.  The knights are seated last because they have the lowest rank.  (The common folk with no title don't get seated at all because they have no rank at all.)

[1] This is from the definition from Google.  I think they may have gotten it from Oxford English Dictionary.
[2]http://en.wikipedia.org/wiki/Royal_and_noble_ranks


name matching algorithms from partial input There are a lot of algorithms out there that solve this particular problem. My main problem is in trying to understand how they work; where to start. Most of the algorithms are academic in nature.

There is a master list of product names. We feed in an input file into the program with product names, but the names of the products may be partial or incomplete. We would need to match the correct product from the master list.

There are solutions like clustering algorithms, naive-bayes, etc. But I am looking at some working examples to actually understand the concept. Would want to review the computations step-by-step for a small model.

A cheap but possibly low-precision, low-recall way is to compute something similar to Soundex or Metaphone codes for your product names and candidates. This only really accounts for misspellings, and even then not reliably or in a principled way. But it's cheap to compute.

Alternatively, for a language-independent approach, consider computing the edit distance between each candidate and all the database entries, and return the cheapest match that's under some threshold. There's worked examples of how the Levenshtein distance is computed on the Wiki page.


Are multiple interrupts generated when I hold down a key on my keyboard? When I hold down a key on my keyboard, a continuous stream of characters is generated and is displayed on the text editor, Now since pressing a key is a hardware interrupt, so does holding down a key continuously generates interrupt signals and does CPU constantly keeps acknowledging those ? or something else happens ?

TL;DR: No.

It depends on the OS and the keyboard. I'll show you how to determine this yourself on a Linux machine. I'm using Ubuntu 16.04 on an x86 processor. So if you are using a fairly modern version of Linux and an x86 processor, then the steps will be pretty much the same. I have a USB keyboard (and mouse) and almost everyone else does.

Open a new terminal and execute the following command:

watch -n0.5 "cat /proc/interrupts"

This enables you to monitor hardware interrupts in real time. Examine the last column and look for the lines that contain ehci_hcd:usbN where N is some small number. On my system, there are two such line:

            CPU0       CPU1       CPU2       CPU3
 16:         17          3          0          9  IR-IO-APIC  16-fasteoi   ehci_hcd:usb1
 23:         88      72272     101007    1327899  IR-IO-APIC  23-fasteoi   ehci_hcd:usb2

The first column shows the interrupt request signal number (IRQ). It identifies a physical bus on the motherboard that is used by the I/O device to interrupt the processor. The four columns in the middle show the number of interrupts handled by each core. There are four (logical) cores on my system. Notice how the overall number of interrupts from IRQ 23 is very large while the number of IRQ 16 interrupts is almost zero. This is a strong indication that the keyboard and mouse both use IRQ 23 to send interrupts to the processor. In general, though, the mouse and keyboard may use different IRQs depending on the USB port they are connected to. Some USB ports may share the same IRQ line1.

Now you can observe what happens to the interrupt counts when using the keyboard. Hold the mouse still (so that the mouse does not generate any interrupts) and press some keys on your keyboard. When a keyboard key is pressed, the interrupt count on one of the CPUs will increase by exactly one. When a key is released, the interrupt count will also increase by one. In addition, you can see that, while the key is held down, the interrupt count does not change. Therefore, the keyboard does not send interrupts for the key held down. Instead, Linux uses a software keyboard repeat mechanism, by default, for USB keyboards. As long as the keyboard has not yet sent an interrupt indicating that the key has been released, Linux knows that it is held down.

Software keyboard repeat is implemented by using a timer interrupt. There are two parameters involved, both are configurable. The first is called the typematic repeat rate (also called autorepeat rate), which specifies the rate at which the keydown event should be repeated in terms of the number of characters per second. The second is called the typematic delay, which specifies how long a key must be held, in milliseconds, before it begins to repeat. You can print the current values of these parameters using sudo kbdrate. On modern versions of Linux, it prints:

Typematic Rate set to 10.9 cps (delay = 250 ms)

You can also modify these parameters using the same tool, and then observe the effects using /proc/interrupts as discussed above.

Since software keyboard repeat relies on the timer interrupt, it can support a wider range of typematic repeat rates and shorter typematic delays. This is in contrast to hardware keyboard repeat, which is the default mode for AT and PS/2 keyboards in old versions of Linux. People who used to suffer issues from hardware keyboard repeat were advised to use atkbd.softrepeat=1. Most keyboards are configurable regarding keydown repeat behavior.

For more information, you can refer to /include/linux/input.h and /include/linux/input.c of the Linux source code as a starting point.

Footnote 1:

You can determine with certainty which IRQ line the USB keyboard and mouse are connected to by executing the following command:

lsusb -v

This will print a list of all USB ports and controllers on the PCIe interconnect. On my system, all USB ports are either on Bus 001 or Bus 002. In /proc/interrupts, these are named ehci_hcd:usb1 and ehci_hcd:usb2, respectively. So, for example, if lsusb tells you that the keyboard is on Bus 001, then the keyboard uses IRQ 16. When a key is pressed or released, the scan code of the key is simply stored in the keyboard buffer and the keyboard controller then raises an interrupt to one of the CPUs (as specified by I/O APIC interrupt affinity). Then the target CPU gets interrupted, calls the interrupt handler mapped to the IRQ, which in turn reads the scan code from the keyboard controller buffer and stores it into the kernel's keyboard buffer for further processing.


Essential difference between Assembly languages to all other programming languages I understand that any assembly programming language has so little abstraction, so that one who programms with it (OS creator, hardware driver creator, "hacker" and so on), would have to know the relevant CPU's architecture pattern very well.

For me, this requirement to know the relevant CPU's architecture pattern very well is the essential difference between assembly programming languages to the rest of ("higher") programming languages that don't require that, so we get:

nonassembly/high programming languages
assembly/low programming languages
machine code languages which usually won't be used as programming languages but theoretically can be used as such (and as any other type of computer language for that matter)

Is this the only essential difference, if not, what else there is?

The two most obvious characteristics of an assembly language are:

It is specific to a particular CPU architecture.
There is a one-to-one correspondence between assembly language commands and machine code instructions (once you strip out labels, assembler directives and code comments).

By contrast, a high-level language will have the following characteristics:

It is portable to some degree i.e. it can be compiled to run on several different target platforms.
It provides a layer of abstraction (control structures and data structures) which allows the programmer to ignore the low-level details of the target platform. As a result, there is no longer a simple one-to-one correspondence between language commands and machine code instructions.

However, this is not a black-or-white distinction; there is a grey area where low-level and high-level languages overlap. For example, cross assemblers take assembly language written for one platform and translate it into machine code that can run on a different platform (usually with some restrictions). And there are assemblers (sometimes called "high level" assemblers) that support simple control structures such as IF structures and FOR loops.


How to implement the details of shotgun hill climbing to make it effective? I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems to be the best fit, as I have no clue how the best start value can be found.

But there is not a lot of information about this type of algorithm except the rudimentary idea behind it:

  [Shotgun] hill climbing is a meta-algorithm built on top of the hill climbing algorithm. It iteratively does hill-climbing, each time with a random initial condition $x_0$. The best $x_m$ is kept: if a new run of hill climbing produces a better $x_m$ than the stored state, it replaces the stored state.

If I understand this correctly, this means something like this (assuming maximisation):

x = -infinity;
for ( i = 1 .. N ) {
  x = max(x, hill_climbing(random_solution()));
}
return x;

But how can you make this really effective, that is better than normal hill climbing? It is hard to believe that using random start values helps a lot, especially for huge search spaces. More precisely, I wonder:

Is there a good strategy for choosing the $x_0$ (that is implementing random_solution), in particular knowing (intermediate) results of former iterations?
How to choose $N$, that is how many iterations are needed to be quite certain that the perfect solution is not missed (by much)?

The general idea behind doing multiple climbs is to try to avoid local optima. This is the reason shotgun climbing might work better than just a plain hill climbing method.

Usually one starts with a random value. On the other hand if one can guess something better, that can be used as a initial value as well. If there is no knowledge of what a good start value should be, it makes sense to use a random one.

The suitable value for $N$ varies. Usually one has to define a stopping criterion. A suitable criterion might depend on your specific domain. For example, if for some small number of moves you don't improve your solution at all, you stop. In general, you don't know -- you are using heuristics and they give you no guarantees. You might want to even determine a suitable $N$ experimentally.


How difficult is this matching-like problem? Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand  "$i$ is matched to $j$" if $f(i)=j$. I am looking to solve
$$ \min_{f: A \rightarrow B} \sum_{j \in B} (\mbox{ number of nodes matched to } j)^2, $$
$$ \mbox{ subject to } |i-f(i)| \leq 2 \mbox{ for all } i \in A. $$
In other words, the function $f$ should not "move" any $i \in A$ too far and should come as close to a matching as possible.
Has something like this been studied before? If so, is it known to be NP-hard, or is there an obvious reduction? Are there any known variations on this (e.g., by changing the cost) that are polynomial-time solvable?

Observing that there exists an optimal solution such that for any $i_1<i_2$ , $f(i_1)\le f(i_2)$ (otherwise, we can swap $f(i_1)$ and $f(i_2)$), there is a dynamic programming algorithm solving your problem.
We sort $A$ and $B$ firstly. Suppose $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, where $a_1<\cdots<a_n$ and $b_1<\cdots <b_m$. Let $D(i,j)=\min_{f:\{a_1,\ldots,a_i\}\to\{b_1,\ldots,b_j\}}\sum_{j'\le j}(\text{number of nodes matched to }j')^2$, then $$D(i,j)=\min_k D(i-k,j-1)+k^2,$$
where the minimum is taken over all $k$ such that $a_{i-k}$ is able to be matched to $b_j$. The original objective is to compute $D(n,m)$. It can be done by this recurrence in $O(n^2m)$ time.


Why doesn't this put $BPP$ in $NP$? From Sipser Gacs we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists t_1,\dots,t_{|r|}\forall r\in\{0,1\}^{|r|}\vee_{i\in\{1,\dots,|r|\}}M(x,r\oplus t_i)=1.$$
From Adleman we know $x\in L(M)$ for a machine $M\in BPP$ $\iff$ $$\exists  r\in\{0,1\}^{|r|}M(x,r)=1.$$

Why is this just $BPP\subseteq P/Poly$ (looks like a derandomization to $BPP\subseteq NP$)? If Adleman's theorem just puts $BPP\subseteq P/Poly$ (because we need to find $r$) then why cannot I argue for similar reasons Sipser Gacs only puts $BPP\subseteq coNP/Poly$ (because we need to find $t_1,\dots,t_{|r|}$)?

What should Adleman's theorem have looked like if it indeed showed $BPP\subseteq NP$ and what should Sipser Gacs' theorem have looked like if it indeed showed $BPP\subseteq coNP/poly$?

Adleman's theorem states that you can amplify the success probability of $M$ so that there will be a single choice for the random string $r$ that works for all $x$:
$$ \exists r \forall x : x \in L(M) \Leftrightarrow M(x,r) = 1. $$
(Here $x$ goes over all inputs of length $n$, and $r$ goes over all possible random strings that $M$ requires for inputs of length $n$.)

Unfortunately, it's not clear how to find $r$, and even worse, if I give you $r$, it's not clear how to verify that it satisfies the property stated above. This is why we have to supply it as advice.

The Sipser–Gács theorem similarly states a different property from what you list. It states that if $M$ is a BPP machine then
$$
\forall x \bigl(x \in L(M) \Longleftrightarrow \exists t_1,\ldots,t_{|r|} \forall r : M(x,r \oplus t_1) = 1 \lor \cdots \lor M(x,r \oplus t_{|r|}) = 1 \bigr).
$$
Here the strings $t_i$ could depend on the input $x$. This is why you get $\Sigma_2^P$ or $\Pi_2^P$ rather than $\mathsf{NP}/\mathsf{poly}$ or $\mathsf{coNP}/\mathsf{poly}$.

Summarizing, you have to be careful with quantifiers when stating a theorem. Changing the order of the quantifiers could drastically change the meaning.


About the 'trick' for finding the diameter of an graph in $O(n^2)$ The diameter of an undirected, unweighted graph can be found in $O(n^3)$ with e.g. the Floyd–Warshall algorithm. However, there is an idea how to improve the runtime:

Pick a vertex $v$
Find $u$ such that $d(v,u)$ is maximum
Find $w$ such that $d(u,w)$ is maximum
Return $d(u,w)$

This idea fails; for instance, when starting at $v$ here:

However, it is not immediately clear to me if we can not amend the above algorithm with another indirection, and also consider all nodes with maximum distance instead of only one. That is:

Pick a vertex $v$
Find the set $U$ such that $u \in U \implies d(v,u)$ is maximum
For each node $u$ in $U$, find the set $W_u$ such that $w \in W \implies d(u,w)$ is maximum
Merge these sets $W_u$ into a new set $W$
Calculate the eccentricity of all nodes in $W$
Return the maximum eccentricity found this way

The improved algorithm works for the above counterexample as well as others (e.g. this one).

I assume it is still wrong. If it were not, it would offer a significant improvement for at least some kinds of graphs. Is there a counterexample? And how could a counterexample for further additional indirections be constructed?

The diameter of the following graph is $2a+4$. If you start from $v$, you will need $i=2a+1$ iterations to have $s,t\in W_{i}$. It provides a family of counter-examples for an arbitrary large number of indirections (as $a \to \infty$).


Low-degree nodes in sparse graphs Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one.

I have tried to solve this problem by using the property $\sum_{v \in V} \operatorname{deg}(v) = 2|E|$.  Can this problem be solved by using pigeon hole principle?

Yes, it can.

You have $n-1$ edges, which means $2n-2$ holes for node-pigeons. If every node is supposed to have degree two (or more), we have to place (at least) two pigeons for each node, that makes a total of $2n$ pigeons.

By said principle, (at least) two pigeons do not find a solitary hole, which means (at least) one node is isolated or (at least) two nodes have only one edge. As no node is isolated by assumption, you have (at least) two nodes with degree one.


Time complexity of writing a number as power of 2's I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$.
It seems to me that we do $\lceil \log_2n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot \log_2n)$. However, this seems like a very loose upper bound to me as the number we start with gets smaller with each division. So, what would be a better upper bound on the time complexity of writing an integer $n$ as power of 2's ?

Division by 2 is linear in the number of digits (lets call that $s$) $O(s)$ aka. $O(\log n)$.

output = [];
bool carry;
for(digit in digits){ // most significant digit first
    if(carry) digit+=10;

    carry = isOdd(digit);
    push_front(output, floor(digit/2));

}
if(output.front == 0) pop_front(output);
//carry is the new bit to push to the front of the result
// and output is the new digit array

Because the number of digits decreases with a constant rate (1 digit every 3 to 4 divisions). This algorithm results in a $O(s^2)$ time complexity aka. $O(\log^2 n)$.


Why have a numeric type hierarchy? The more I think about it, the stranger the concept of having a number type, which is a super-type of integers, rationals and reals seems to be. One thing that comes to mind is the Wittgenstein's concept of class families (where objects are grouped into families, even though neither one is a sub-type of the other, but have some "common property", not necessarily common to all objects in the family). Certainly, not a hierarchy.

And yet, in languages like Java, Common Lisp, Haskell and possibly lots of others there is a concept of a numerical super-type for types like integers, reals, complex etc.

Is there any computer-science-related explanation of existence of such super-type, or is this simply a convenience, which has no deeper meaning?

To some extent it's a convenience. Not all languages have the hierachy you speak of. For instance Ocaml has no such hierarchy and you need to explicitly cast integers to floats. (This is the price you pay for having type inference with principal types in Ocaml.)

But there are other reasons as well. Numeric types are there because we want to do math with computers. In mathematics there are many kinds of numbers, and they are naturally organized according to what structure they carry: the integers form a ring, the rationals form a field, the reals form a complete field, and the complex numbers a complete algebraically closed field. So the mathematical hierarchy gets reflected in the organization of numeric types.

In Haskell there are a number of numeric type classes (Num, Float, Rational, ...) which give the programmer flexibility and modularity. In Haskell it is very easy to switch from one kind of Num to another – as opposed to other software systems where it takes years to switch the numeric data types (consider how big a project it was from 32-bit to 64-bit Windows).


To what extent is my interpretation of computable numbers correct? Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to calculate all of the digits of $\pi$ and begins dismembering the person. This is possible because $\pi$ is a computable number.

In contrast, if the person had asked the robot to calculate Chaitin's constant (assuming the robot didn't say something like "which Chaitin's constant?" or "insufficient parameters") or some other non-computable number, would the people have been able to escape the robot's dismembering?

As far as I understand (1)(2), the robot could make an algorithm to calculate the first $n$ digits for any $n$, but to attempt to compute "all" of Chaitin's constant would take an infinite amount of time, because each new digit would require a new program, or something like this.

Question: Is this interpretation at all correct or am I completely off the mark here? To what extent could one describe computable numbers as numbers which "prevent a robot in this specific situation from dismembering people"?

I.e., do all non-computable numbers have algorithmically random (decimal, binary, etc.) expansions?

Source.

This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition.

$\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as output, and we actually need a "better" definition.

To fix this issue, we say a number $p$ is computable, if we can approximate $p$ up to any given precision. One way of formalizing this is requiring the existence of a program $M_p(n)$, which upon receiving a number $n$ outputs (in finite time) a number $\hat{p}$ such that $|\hat{p}-p|\le\frac{1}{n}$. The comic actually refers to this definition, as $\pi$ having an infinite expansion does not prevent the robot from dismembering the guy.

If your goal is to avoid dismembering, then it is not clear how to use uncomputable numbers. What exactly is the meaning of calculate $x$? If i ask for some fixed approximation of an uncomputable number, then the robot can give me one (sure, it has no way of algorithmically producing the approximation, but perhaps this is some weird robot with a table of all approximations to any natural constant up to $10^{-100}$). You would probably stand more chance with incompleteness issues, rather than with computability issues. I would ask the robot for a proof in $ZFC$ of its consistency. If it is consistent, he wont find any, and if it isn't, who wants to live anyway.


Given an array arr[] of N integers. Do the following operation n-1 times For every Kth operation:
Right rotate the array clockwise by 1.
Delete the (n-k+1)th last element.

eg:

A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, 3, 4, 5} and delete the last element that is {5} so A = {6, 1, 2, 3, 4}. Again rotate the array for the second time and deletes the second last element that is {2} so A = {4, 6, 1, 3}, doing these steps when he reaches 4th time, 4th last element does not exists so he deletes 1st element ie {1} so A={3, 6}. So continuing this procedure the last element in A is {3}, so outputp will be 3

How to solve this?

It seems some kind of problem with mathematical solution (try to find the position with a closed math formula). However, here is an algorithmic approach that runs in $O(n \log^2 n)$.

Using segment tree / Fenwick tree, you can find the number of removed elements in a range (using prefix sums). Keep track of the offset (imagine having a pointer on the first element (imagine a cyclic arry and in each step we push it one element to the left instead of rotating right). Using binary search on the Fenwick tree, you can find the index of element having the distance you are looking for the offset element. Nite that after deleting half of the elements $k$ will be greater than the size and hence you can directly output the first unremoved element before the offset.


What is meant by a preemptive algorithm? The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.'
So, how does this relate to an algorithm, especially the Nearest Neighbour Algorithm?

An arbitrary algorithm can't be preemptive or non-preemptive. Preemption is a mode of multitasking, used by an operating system to control user processes. From the Preemption Wiki page:

  In computing, preemption is the act of temporarily interrupting a task being carried out by a computer system, without requiring its cooperation, and with the intention of resuming the task at a later time.

The opposite of Preemption is Cooperative Multitasking.


Correct cost function of multi classification problem using neural network? I am going through machine learning course on coursera. While going through the section on neural networks I came across the cost function for multi - classification problem using neural networks ( ignoring the regularization term ):
$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] \end{gather*}$$

where $m$ is the number of training data points $\{(x_1,y_1),...(x_m,y_m)\}$. Each data point is classified into one of the $K$ categories ie. $1\;\le{\;y_i}\;\le{K}$ ( so $y_k^{(i)}$ means if $\;y_k^{(i)} == k\;$ ). And $h_\Theta$ is the hypothesis function.

My doubt is why does the cost function has a summation over $K$. Why aren't there $K$ separate cost functions ( $ 1 \; \le{k} \le K$ ), and we have different $\Theta$ when we minimize each of the $K$ cost functions separately:

$$\begin{gather*} J(\Theta)_k = - \frac{1}{m} \sum_{i=1}^m  \left[y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k) + (1 - y^{(i)}_k)\log (1 - (h_\Theta(x^{(i)}))_k)\right] \end{gather*}$$

In the second approach we are trying one-vs-all classification. How is it different from first approach. First approach is taking sum over all cost functions of second approach. So minimization problem being solved in both cases are different. But I am unable to pin point what the difference between the two approaches is ? Both seem intuitively correct to me. Am I doing some stupid mistake ?

The loss function you have shown is not correct.  The correct one is

$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k)  \end{gather*}$$

The loss function has a summation over $K$ because we must take into account all possible classes.  The neural network outputs $K$ values, $h_{\Theta}(x^{(i)})$, and the loss function should depend on all $K$ of those.  There is a single loss function because we are training a single neural network, and we need exactly one loss function per neural network; if you wanted to train $K$ neural networks, then you would use $K$ loss functions.

Define $z^{(i)}$ to be the class of $x^{(i)}$ according to the training set, i.e., we take $z^{(i)}$ to be the value of $k$ such that $y^{(i)}_k=1$.  Then
the loss function above is equivalent to

$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \log ((h_\Theta (x^{(i)}))_{z^{(i)}})  \end{gather*}$$

which does not have a summation over $K$.

I suggest reading more about the cross-entropy loss.  See, e.g., https://rdipietro.github.io/friendly-intro-to-cross-entropy-loss/

There are some errors in your notation.  The training set has points $(x^{(i)},y^{(i)})$, not $x_i,y_i$.  Here $y^{(i)}_k$ means that $y^{(i)}=k$, not that $y^{(i)}_k=k$ (the latter would be circular, defining $y^{(i)}_k$ in terms of itself).


Find the fastest duration for a certain distance in a walk I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic problems.

I'm looking for an algorithm that is able to find a answer to the following question:

If I ran 10 km this morning, how can I find out how fast my fastest kilometer was? (=searching for duration of fastest km)

My "run" datastructure consists of a list of data records, where each entry contains the following information:

timestamp in milliseconds
distance since start in meter

The data structure is arranged chronologically.

I already got a pretty straight forward solution to the problem, but I guess I would end up with a poor performance on this one:

start with the last entry of the list (i=size) and stop if available / remaining distance data[i] is smaller than 1km
search backwards in the list and calculate the distance delta for each entry until the delta for the distance is >= 1km OR (if we got a duration candidate from a previous iteration) the current calculated duration is already exceeding out current best.
if duration is too high start all over with i=i-1 until end condition is met
if a duration candidate is found remember this candidate decrease "i" and proceed with 1)

I really believe there must be an algorithm or better approach out there that can be applied to this question. Does anyone have an idea or can steer me in the right direction?

I suggest you use exactly your algorithm, except use binary search during your binary search.  You will want to store the events in an array rather than a linked list, to allow efficient random access into it.  The total running time will be $O(n \log n)$, where $n$ is the number of events in your data structure.  That seems quite reasonable, and this should be quite efficient in practice.


What is the meaning of 'moderately exponential' running time? I was reading some research paper where for hypergraph of bounded rank $k$ they have given moderately exponential algorithm. The runtime of the algorithm is $e^{  \mathcal {O}(k^2\sqrt n) \cdot poly(n)}$. Here $k$ is the rank of the hypergraph, and $poly(n)$ means polynomial in variable $n$.

  What is the meaning of moderately exponential running time ?

I have seen this  link, but did not understand much.

Moderately exponential is not a widely accepted term in general theoretical computer science, though it might have a widely accepted meaning in the area to which the paper you are citing belongs.

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha < 1$; an exponential running time would be $\exp O(n)$ or worse.


Algorithm for using power series to numerically solve a partial differential equation given a boundary condition? Motivation:
Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any implementation of the method. So I'm thinking of implementing a SymPy function similar to Mathematica's AsymptoticDSolveValue (here)  but for PDEs (here or here). So far I'm able to generate a symbolic multivariate polynomial given a list of non-negative integers D=[d1,...,dm] (here, here and here).
Example:
Now I'm able to use the symbolic multivariate polynomial to numerically solve a PDE. For example (from here) given the PDE:
$$\frac{\partial^2 u}{\partial x_1^2} - \frac{\partial^2 u}{\partial x_2^2}=0 \, ,\tag{1}$$
and the boundary conditions:

$u(x_1,0)=x_1^2+x_1\, , \tag{2}$
$u_{x_2}(x_1,0)=2x_1+1 \, , \tag{3}$

I can generate a 2D symbolic polynomial in Sympy:
from itertools import product
from sympy import IndexedBase, symbols, Poly
D = (5, 5) # 5 and 5 are just some random integers, any non-negative integer should do
d = len(D)
indices=list(product(*map(range, D)))
a = IndexedBase('a')
coeffs = {i: a[i] for i in indices}
vars = symbols(f'x1:{d+1}')
u = Poly(coeffs, *vars)

Equation 1 can be implemented as:
pde=u.diff(0,0).add(-u.diff(1,1))

Implying
$$j(j+1)a_{i,j+1}=(i+1)(i+2)a_{i+2,j} \tag{4}$$
The first boundary condition:
u.eval(1,0)

Implying
$$a_{0,0}=0 \, , \, a_{1,0}=1 \, , \, a_{2,0}=1 \, , \,a_{i,0}=0 \, \forall \,(2<i) \tag{5}$$
and the second boundary condition
u.diff(1).eval(1,0)

giving
$$a_{0,1}=1 \, , \, a_{1,1}=2 \, , \, a_{i,1}=0 \, \forall \, (2<i) \tag{6}$$
Now from this point it is just a system of nonlinear algebraic equation of $a$s (in this specific case linear). Which should be solvable with other analytical/numerical methods.
Question:
I want to automate the process above. I want to have a function:
AsymptoticPdeSolve(eqns,fs,vars,D)

Where eqns is the set of symbolic partial differential expressions, fs are the set of functions we want to solve, vars are the variables and D is the dimension of our multivariate polynomials.
I would appreciate if you could help me know what is the best algorithm for this process. I will use an existing symbolic library/software like SymPy, so anything already existing doesn't need to be reimplemented.
P.S. Axiom-FriCAS has a seriesSolve function which source code can be found here. Also since I posted this question, Nicolas CELLIER was so kind to implement an early version in sympy which can be seen in this Jupyter notebook.

Instead of building a polynomial and trying to deduce the equation on the coefficients, you can just derive it directly from a general term coefficient

>>> i, j, x1, x2 = symbols('i j x1 x2')
>>> a = IndexedBase('a')
>>> u = Function('u')
>>> pde = u(x1, x2).diff(x1, 2) - u(x1, x2).diff(x2, 2)
>>> term = a[i, j]*x1**i*x2**j
>>> pdeterm = powsimp(pde.replace(u, Lambda((x1, x2), term)).doit())
>>> pdeterm
i*x1**(i - 2)*x2**j*(i - 1)*a[i, j] - j*x1**i*x2**(j - 2)*(j - 1)*a[i, j]

The PDE being identically zero means each coefficient of each x1, x2 term is 0.

>>> pdeterm.coeff(x1**i*x2**(j - 2))
-j*(j - 1)*a[i, j]
>>> pdeterm.coeff(x1**(i - 2)*x2**j)
i*(i - 1)*a[i, j]

This is the same as what you had above if you shift i and j

>>> pdeterm.coeff(x1**i*x2**(j - 2)).subs({j: j + 1})
-j*(j + 1)*a[i, j + 1]
>>> pdeterm.coeff(x1**(i - 2)*x2**j).subs({i: i + 2})
(i + 1)*(i + 2)*a[i + 2, j]

I'm not sure if there's an advantage to having them one way or another.  For a general PDE, you'd want to write a function that does this automatically.

The boundary conditions can be managed in a similar way using subs.

You can then solve the system analytically with solve or numerically with nsolve.


Using inductive hypothesis on recurrence relation? I have a recurrence relation as follows
$$T(n) = 2T(\lfloor n/2\rfloor) + n\log(n)$$
Using the induction hypothesis how do I obtain a relation $T(n)\leq E$ such that $E$ contains neither $T$ nor floor operator ($\lfloor\cdot\rfloor$).

We can open up the recursion to obtain
\begin{align}
T(n) &\leq n \log n + 2\lfloor n/2\rfloor \log \lfloor n/2 \rfloor + 4\lfloor \lfloor n/2 \rfloor/2\rfloor \log \lfloor \lfloor n/2 \rfloor/2\rfloor \\ &\leq
n\log n + n \log (n/2) + n\log (n/4) + \cdots \\ &\leq
n\log n + n\log n + \cdots \\ &= O(n\log^2 n),
\end{align}
since it takes $\Theta(\log n)$ steps to get to the base case.
If you're more careful, you can show that in fact $T(n) = \Theta(n\log^2 n)$.


Classification of job shop scheduling problems I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory.

The factory has several types of machines (say, locksmith, miller, welding)
There are few machines of each type. (say, 3 locksmiths, 2 millers, 3 welders)
There are several types of operations (some machines do more than one operation on the job, say, locksmith does soldering and assembling).
The jobs on the machines have different times, all known beforehand.
The jobs have dependencies on jobs done before (say, a product's made of 10 screws and 4 subparts, each of which needs 4 screws).

From what I searched, this looks sort of like a Flow Shop problem. The difference is in the dependencies and in the same machine doing different operations with different times on a job.

My main question is:

Is there some kind of a classification of these problems? A summary telling the differences?

For example, I don't understand much of how do these differ: Open Shop, Job Shop, Flow Shop, Permutation Flow Shop. And whether or not I missed something similar that could fit better to my problem.

As a side question, what approach do you think could help me best with the unusual requirements I've posted above? I'm writing my current approach below.

So far I've been able to work with the tree of dependencies without regard to the makespan times: just making a plan - a list of IDs, really - of what comes after what, from looking at the tree of what's been done so far and what are the leaves (nodes having done all their dependencies).

This allows for fast creation of meaningful individuals in the Genetic Algorithm population, but there seems to be no computationally cheap way to learn the individual's makespan time (which I have as the fitness function).

For that I have to create a calendar, or Gantt chart, if you will, to which I put the operations on the jobs in the earliest place possible, in the machine queue that's free at that moment, etc. The whole plan has to materialize and that seems the most costly computation of the whole problem.

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008.  The author's homepage also has pages devoted to each of his books.  It has chapters for multiprocessor scheduling, open shop scheduling, flow shop scheduling and job shop scheduling.

The flow shop problem has $n$ jobs with $m$ machines.  Each job needs to visit machines in the exact order $1,2,\ldots,m$.  There are $nm$ parameters $d_{ij}$, which is the amount of time job $i$ demands on machine $j$.  There is no constraint on the order in which machines service jobs.  (The constraint is on the order in which jobs need machines.)

The permutation flow shop problem seems to add the constraint that every machine must service the jobs in the same order.  So the goal is to permute the jobs to minimize the makespan of pipelining each job through the machines in order.

The open shop problem completely relaxes the ordering constraints.  Each job demands time on each machine, but in no particular order.  (And, of course, the amount of time demanded by job $i$ on machine $j$ can be 0.)

The flow-shop problem and open-shop problems are special cases of the more general job shop problem with precedence constraints:  We are given a set of jobs $J=\{J_1,\ldots,J_n\}$ and a set of resources $R=\{R_1,\ldots,R_m\}$.  Each job $J_i$ consists of a set of operations $O^i=\{O_1^i,\ldots,O_p^i\}$.  Each operation $O_k^i$ requires a set of resources $R_k^i \subseteq R$ for a time $t_k^i$, and for each job, $J_i$ there is a set of precedence constraints (i.e., a partial order or directed graph) on the operations, $O_k^i \xrightarrow[\mathrm{before}]{} O_l^i$, stating that operation $O_k^i$ needs to finish before $O_l^i$ starts.

Your problem is a job-shop problem with an additional generalization that there are classes of identical resources ("3 locksmiths") and the operations can use any resource in the class.  This brings in an aspect of the multiprocessor scheduling problem.

N.B., I believe that I've used the terminology that is used in the books by Coffman and Denning, and by Pinedo.  The wikipedia pages are an utter disaster.  The wikipedia page on job shop scheduling gives a definition of the open-shop problem that contradicts the wikipedia page on open shop scheduling.  The wikipedia page on the flow shop problem is incomprehensible.  And wikipedia is confused about the difference between multiprocessor scheduling, which involves $m$ interchangeable resources, and job-shop scheduling.  For example, the wikipedia page on the Coffman-Graham list scheduling algorithm calls it a solution to the job-shop scheduling problem, although Coffman and Graham use the term "multiprocessor", not job-shop in the titles of their papers.  (And note that the author of the wikipedia page on multiprocessor scheduling seems unaware of the original variant with precedence constraints.)


Someone explain the venn diagram for the logic equation A*(B+C) So, I am studying logic circuits and how to prove them with Venn diagrams. When drawing a Venn diagram for the equation A*(B+C) I figured it would look something like this:

But according to the answer key, and wolfram alpha, it looks something like this:

Can someone explain why this is? Because doesn't A*(B+C) simplify to AB + AC, which would only be the two shaded regions?

$(B+C) = B\overline{C}+\overline{B}C + BC$

and A with that and you get:

$A*(B+C) = A*(B\overline{C}+\overline{B}C + BC) = AB\overline{C}+A\overline{B}C + ABC$

Remember that OR is the union and AND is the intersection.


Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $ I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:
$$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$
I quickly made a CFG that represents that language (or so I believe):
$$ S \to 0S1 \hspace{0.2cm} | \hspace{0.2cm} A  \\
   A \to 1A0 \hspace{0.2cm} | \hspace{0.2cm} \epsilon
$$
The problem is that I began to think if the Pumping Lemma would hold (it should since I have a CFG for the Language, so it must be a CFL).
(Having the Pumping Lemma in mind) I chose a word, w = $ 0^{n}1^{n}0^{n}1^{n} $. I immediately stopped because this word will not pass the Pumping Lemma (it can be used to demonstrate that $  \{ ww \hspace{0.2cm}| \hspace{0.2cm} w \in \{0,1\}^{*}\}$, the language of duplicated words, is not a CFL, I have done it before)
Now I'm stuck with a Pumping Lemma that fails, and a CFG that produces the language and don't now what to do.
I tried to come up with a word that the grammar couldn't produce and failed, I tried to invalidate the PL but failed (there are no restrictions that tells that the word cannot have all segments of the same size, so $w$ is in the language).
As far as I know If the PL holds, the language doesn't have to be a CFL, but if it fails is absolutely unquestionable that the Language is not a CFL.
What I'm I missing?

$\{ww\mid w\in\{0,1\}^*\}$ not being context-free does not imply every subset is also not context-free. In this case, $0^n1^n0^n1^n$ passes the pumping lemma, since it can be written as follows $0^p1^p0^p1^p=0^p1^{p-1}1^n0^n0^{p-1}1^p$.


Converting between (standard) primal to dual forms (LP) I'm working on a HW assignment as follows:

Given the primal canonical problem: $$min \langle c,x \rangle \text{ s.t. } Ax \geq b, x \geq 0$$
and the canonical dual problem: $$ max \langle b,y \rangle \text{ s.t. } A^Ty \leq c, y \geq 0$$

Show that converting PC (primal canonical) to DC (dual canonical) is similar when done directly or when done via canonical to standard conversion (i.e. primal canonical -> dual canonical == primal canonical -> primal standard -> dual standard -> dual canonical).

I converted the CP to SP (standard primal) by adding slack variables $s_1,\ldots,s_n\geq 0$ and adding them to each inequality.

My problem is showing the similarity between the SP and SD (standard dual).

What I've done so far is this: SD (standard dual) wants to maximize $b^Ty$ so:

$b = Ax$
$b^ty = (Ax)^Ty = (x^TA^T)y = x^T(A^Ty) \leq x^Tc$

Now, I don't know how to proceed. How can I show that minimizing $c^Tx$ is maximizing $b^Ty$? Am I on the correct path?

PS: I am pretty sure dual and primal problems can be shown where the primal is max and the dual is min, but I think it doesn't matter at all, right?

In class you have been shown several algorithms:

Algorithm A: Convert a primal canonical to a dual canonical.
Algorithm B: Convert a primal canonical to a primal standard.
Algorithm C: Convert a primal standard to a dual standard.
Algorithm D: Convert a dual standard to a dual canonical.

Notice that if you run Algorithms B,C,D in sequence, then you get another algorithm for converting a primal canonical to a dual canonical. The question is to compare the dual canonical program constructed this way to the one constructed by applying Algorithm A.


Is lambda calculus suitable for expressing semantics of non-functional languages? Would it be convenient to express semantics of imperative languages (e.g. C) and object-oriented languages (e.g. Java) with $\lambda$-calculus?

Or in the other words: is $\lambda$-calculus a suitable candidate for expressing semantics of all context-sensitive languages?

There are two main approaches to giving the semantics of a language that I'm aware of.  $\lambda$-calculus is a suitable candidate for expressing semantics in either approach.  (Note that my knowledge of programming language semantics is restricted to a single course that I took in the mid-1990s, so I may be missing significant developments from the past 20 years.)

The first approach is operational semantics.  According to David Schmidt's Denotational Semantics, Allyn&Bacon, 1986, page 2, operational semantics "uses an interpreter to define a language."  In this sense writing a syntax-directed translator or attribute grammar as an extension of your parser gives an operational semantics to the language.  Somewhat more abstractly, you might define a small-step operational semantics (like those on the Wikipedia page) where you define the meaning of each syntactic expression with respect to the actions it takes to transform a formally defined state or environment.  The imperative programming language Scheme (which is notable for having "first-class" functions and continuations and as being the progenitor of JavaScript) has switched to an operational semantics in their most recent standard.

The other approach is denotational semantics.  In denotational semantics you define a domain of program outcomes, and then for every syntactic structure in the program its meaning is a function that maps from an environment (a map from variable names to values) to the outcome domain.  Scheme Revision5 and earlier have denotational semantics.  The semantics of set! (Scheme's imperative construct) are given towards the end of Page 41.

I would guess that language semantics are largely used to prove the correctness of implementations, and in particular to clarify what optimizations are legal and under what circumstances those optimizations are legal.  But my only experience in this domain is with respect to compiler optimizations and the memory semantics of C++11, which does not have a formal semantics.


How is this definition of the quantum Fourier transform to be understood? In regards to the quantum Fourier transform Page 845 of The Nature of Computation states

  The amplitudes $\tilde{a}_\mathbf{k}$ are the Fourier coefficients of $a_\mathbf{x}$,
  $$\tilde{a}_\mathbf{k} = \langle \mathbf{k}|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x}\,.$$

Here $x$'s are the standard basis vectors and the $k$'s are (presumably) the Fourier basis. And $\psi = \sum_\mathbf{x} a_\mathbf{x}|\mathbf{x}\rangle$.
To pick a concrete example let the number of qubits, $n$, be 2. The book isn't clear on this but my first guess is that the $\mathbf{k}$'s should be these:

$$
\begin{bmatrix}1/2\\1/2\\1/2\\1/2\end{bmatrix}, \begin{bmatrix}1/2\\-i/2\\-1/2\\i/2\end{bmatrix},\begin{bmatrix}1\\-1\\1\\-1\end{bmatrix},\begin{bmatrix}1/2\\i/2\\-1/2\\-i/2\end{bmatrix}.
$$

Though, I've also heard the argument that they should be the columns of

$$H \otimes H = \begin{bmatrix}1/2 & 1/2 & 1/2 & 1/2\\1/2 & -1/2 & 1/2 & -1/2\\1/2 & 1/2 & -1/2 & -1/2\\1/2 & -1/2 & -1/2 & 1/2 \end{bmatrix},$$

where $H$ is the $2\times 2$ Hadamard matrix. However, the book also states that

  each "frequency" is, like $\mathbf{x}$, an $n$-dimensional vector mod 2.

And I don't see how to convert the entries of either of these bases into elements of $\mathbb{Z}_2$.
Ignoring that issue I immediately run in to the following. Take the first vector of either basis as $\mathbf{k}$ and compute the Fourier coefficient $\tilde{a}_\mathbf{k}$ according to the definition above while also using $|\psi\rangle = \begin{bmatrix} 1/2 & 1/2 & 1/2 & 1/2\end{bmatrix}^T$ as an example. On the one hand

$$
\langle\mathbf{k}|\psi\rangle = 1\,.
$$

But on the other hand

$$
\frac{1}{\sqrt{2^n}}\sum_\mathbf{x}(-1)^{\mathbf{k\cdot x}}a_\mathbf{x} = \frac{1}{2} \left((-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2} + (-1)^{1/2}\frac{1}{2}\right) = i\,.
$$

What am I not getting here?

The index $\mathbf{k}$ goes over all vectors in $\{0,1\}^n$ (which can be identified with $\mathbb{Z}_2^n$). The index $\mathbf{x}$ also has the same range, and $\mathbf{k} \cdot \mathbf{x} = \sum_{i=1}^n k_i x_i$. You can think of this sum as being computed modulo 2 (or in $\mathbb{Z}_2$) if you wish, since $(-1)^2 = 1$.

As an example, when $n = 2$ we get
$$
\begin{align*}
\tilde{a}_{00} &= \frac{a_{00} + a_{01} + a_{10} + a_{11}}{2}, \\
\tilde{a}_{01} &= \frac{a_{00} - a_{01} + a_{10} - a_{11}}{2}, \\
\tilde{a}_{10} &= \frac{a_{00} + a_{01} - a_{10} - a_{11}}{2}, \\
\tilde{a}_{11} &= \frac{a_{00} - a_{01} - a_{10} + a_{11}}{2}.
\end{align*}
$$

This is exactly the tensor square of the $2\times 2$ Hadamard matrix.


Relation of deterministic push down automata and lower elementary recursion Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata.

Deterministic context free languages can be recognized by a deterministic Turing machine in polynomial time.

The lower elementary functions are a subset of the elementary recursive
functions.

Lower elementary recursive functions are limited to polynomial time growth.

From this is it correct to derive that deterministic push down automata are of
equal power to the lower elementary recursive functions?

Edit:
My reasoning is that because the deterministic context free languages can be recognized in polynomial time that a deterministic push down automata is implementing a boolean function of up to that complexity. The lower elementary functions are also up to polynomial time. As such are they not equal in power?

No, that doesn't follow at all.  There are problems that can be solved in polynomial time, but that don't correspond to any deterministic context-free language.


Satisfiability of first-order logic is undecidable? I struggle with understanding why the satisfiability in the first-order logic is undecidable. Could you explain it with some examples? I've also seen that satisfiability in some first-order formulas are decidable.

Please explain it with as much as many examples.

The fact that first-order logic (with some non-triviality constraints) is undecidable means that no algorithm can decide correctly whether a given first-order formula is true or not. However, for any single statement $\varphi$ it is easy to come up with an algorithm that decides $\varphi$ correctly (just hard-code the answer). So it is impossible to give examples of "undecidable statements", since there is no such thing.

What is possible is to give a restricted set of sentences whose truth value is already undecidable. In effect, this is what the proof of undecidability does. The proof shows that you can encode the statement "the Turing machine $T$ halts on empty input" in first-order logic (again, given some mild non-triviality constraints), so this infinite sequence of statement is already undecidable, that is, no algorithm can correctly decide whether such a formula is true or not.


Are these special (one production) Context-Free Grammars always unambiguous? Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):

$S \rightarrow aSb\;|\;\epsilon$
$S \rightarrow aSbS\;|\;\epsilon$
$S \rightarrow aSaSb\;|\;\epsilon$
$S \rightarrow aaSaaSbb\;|\;\epsilon$
$S \rightarrow aSbScSdSeSf\;|\;\epsilon$
etc...

Grammars like these uphold 4 basic rules:

The non-terminal symbol $S$ can never appear next to itself.

e.g. $[\;S \rightarrow aSSb\;|\;\epsilon\;]$ would not be allowed.

The non-terminal symbol $S$ can appear at the beginning or end of a production but not on both sides at the same time.

e.g. $[\;S \rightarrow SabaS\;|\;\epsilon\;]$ would not be allowed.
e.g. $[\;S \rightarrow Saba\;|\;\epsilon\;]$ or $[\;S \rightarrow abaS\;|\;\epsilon\;]$ would be allowed.

The sequence of terminal symbols that exist between each non-terminal $S$ cannot all match. (EDIT: This rule is redundant, Rule 4 already ensures that at least two sequences of terminals are non-matching)

e.g. $[\;S \rightarrow aSaSa\;|\;\epsilon\;]$, $[\;S \rightarrow abSabSab\;|\;\epsilon\;]$, etc. would not be allowed.
e.g. $[\;S \rightarrow aSaSb\;|\;\epsilon\;]$, $[\;S \rightarrow abSabSaf\;|\;\epsilon\;]$, etc. would be allowed.

The sequence of terminal symbols at the beginning and end cannot match.  (i.e. $[\;S \rightarrow ☐_1SaS☐_2\;|\;\epsilon\;]$ s.t. $☐_1 \neq ☐_2$ where $☐_1$ and $☐_2$ are a sequence of terminal symbols)

e.g. $[\;S \rightarrow aSbSa\;|\;\epsilon\;]$, $[\;S \rightarrow aaSbSaaS\;|\;\epsilon\;]$, etc. would not be allowed.
e.g. $[\;S \rightarrow aSbSb\;|\;\epsilon\;]$, $[\;S \rightarrow aaSbSaxS\;|\;\epsilon\;]$, etc. would be allowed.

  The grammar cannot be made to break any of the above rules via a $S \rightarrow \epsilon$ production. (Vimal Patel)

  e.g. $[\;S \rightarrow aSbSaSbS\;|\;\epsilon\;]$ could become $[\;S \rightarrow abSabS\;|\;\epsilon\;]$ if the first and third $S \rightarrow \epsilon$, thus violating Rule 4.

Are (Context-Free) Grammars, that follow these 4 rules, always unambiguous? It would seem so. I really don't see any conceivable way that such Grammars could be ambiguous.

(Note: To show why Rule 4 is necessary consider the grammar $S \rightarrow aSbSa\;|\;\epsilon$ with the string $aababaababaa$. A visual derivation can be found here.)

I've spent a lot of time thinking about this question and have had a hard time finding any way of either proving or disproving it. I've tried showing that Grammars like these are $LL(1)$. However, it seems only Grammars of the form $S \rightarrow aSb\;|\;\epsilon$ are $LL(1)$. Grammars like $S \rightarrow aSaSb\;|\;\epsilon$ are not $LL(1)$. Maybe I need to use a higher $k$ for $LL(k)$?

(This question is a follow-up/reformulation of a previous question.)

I would really appreciate any help I could get here.

Here is a simple counter example:
$S \rightarrow aSbSaSbS \space |\space  \epsilon$

and string $w: abababab.$
In one case we use last $S$ and in other case we use second $S$. All other $S$ goes to $\epsilon$.

Why I was able to get this grammar?

Let's rewrite above grammar with numbers assigned to each $S$'s.

$S \rightarrow aS_1bS_2aS_3bS_4 | \epsilon$

Now We can virtually eliminate $S_1$ and $S_3$. (For this whenever we have to derive something from $S_1$ or $S_3$ we will only derive $\epsilon$ from both of this type of $S$'s.)

So we get $S \rightarrow abS_2abS_4|\epsilon$.  (At this time we already have got rid of rule 3.)

Which we were looking for.


Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the length (in bits) of the input that matters, not its value/magnitude. The solution has the following structure:

# some preprocessing
for i in range(n):
    for w in range(W):
        # compute stuff

They repeat the same example: $W=10_2=2$, but $W=100_2=4$, i.e. every extra bit doubles the length of $W$. Here's my confusion

Why can't I apply the same logic for $n$?

As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$.

An input to the knapsack problem consists of a list of $n$ weights, a list of $n$ values and a maximum weight $W$.  Since each weight and each value must take at least one bit to write down, we know that $n<|X|$. But $W$ is written in binary and you can easily produce an instance where, say, $W$ has bit-length $|X|/2$. In such an instance, the running time of $nW$ is about $|X|2^{|X/2|}$, which isn't polynomial.

The key point that you've missed is that $n<|X|$ because, effectively, the input specifies $n$ in unary.  (That is, if the weights are $1,3,2,5,2,2$, then $n$ is basically the number of commas, modulo the usual off-by-one error.)