Complexity of nested loops I'm trying to figure out the complexity of the following algorithm.

for(int i=1; i <= N; i++)
        for(int j=1; j <= i; j++)
            for(int k=1; k <= i*sqrt(j); k++)

I'm trying to figure it out using a method similar to rizwanhudda's solution in this similar question. I'm having some trouble though because the innermost loop references both i and j. Can somebody translate this problem into something similar to rizwanhudda's approach (ie count the number of triplets (i, j, k))? Thanks!

I'm not convinced the approach translates well. In particular, the last statement would become something like "the square root of the number of boxes [...]" and that doesn't work out well. A more traditional way to approach this is:

The inner loop has complexity $\Theta(i\sqrt{j}))$. This loop is executed for $1\leq j \leq i$ (middle loop) which gives a complexity of

$\Sigma_{j=1}^i i\sqrt{j}=i\Sigma_{j=1}^i \sqrt{j}$

Evaluating $\Sigma_{j=1}^i \sqrt{j}$ is tricky. There is no closed-form formula, but we can obtain an approximation by changing the sum to an integral. Note that

$\int_0^i x^{1/2}=\frac{2}{3}i^{3/2}$

is a lower bound, while

$\int_1^{i+1} x^{1/2}=\frac{2}{3}{i+1}^{3/2}-\frac{3}{2}$

is an upper bound. We may conclude that

$\Sigma_{j=1}^i \sqrt{j}=\Theta(i^{3/2})$.

Hence the middle loop has complexity $\Theta(i^{5/2})$. For the outer loop, we have to evaluate

$\Sigma_{i=1}^n i^{5/2}$

for which there is once again no closed-form formula. By applying the same integral technique, we find that the complexity is

$\Theta(n^{7/2})$.

However, finding a closed-form formula for the exact complexity (without asymptotic notation) is impossible.


Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n)) I was reading the Cormen, Leiserson, Rivest and Stein textbook, Introduction to Algorithms.

The book explained the three asymptotic notations literally very well.
However, there was this paragraph:

  Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$,
  since for a given $n$, the actual running time varies, depending on the particular
  input of size $n$.

and this one:

  It is not
  contradictory, however, to say that the worst-case running time of insertion sort
  is $Ω(n^2)$, since there exists an input that causes the algorithm to take $Ω(n^2)$ time.

I understand why did the author said that "it is an abuse to say $O(n^2)$ is the running time", as there are the inputs with best cases causing linear time and there are also inputs with worst case causing quadratic time.
I don't understand why it is not contradictory to say that the worst-case running time of insertion sort
is $Ω(n^2)$. Isn't $\Omega(g(n))$ supposed to be the best running time? So should it not be $Ω(n)$?

It confuses me. Can you please explain why $Ω(n^2)$ is possible for insertion sort when it should be $Ω(n)$?

Aren't $\Omega(g(n))$ supposed to tell best running time?

Not at all. It just means that for all large enough $n$, there exist inputs of size $n$ where the algorithm takes time at least proportional to $g(n)$.

  Can you please explain why $\Omega(n^2)$ is possible for insertion sort when it should be $\Omega(n)$?

The worst-case running time of insertion sort is $\Omega(n^2)$ because for all $n$, there exist inputs of size $n$ where it takes time proportional to $n^2$.

The running time of insertion sort in general is not always $\Omega(n^2)$, as you observed; it depends on the input. But the worst-case running time (which does not depend on the input, only on $n$) is $\Omega(n^2)$.


Reduction of the diagonalization language to the universal language I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a membership problem in $L_u$. Those are defined as follow:

$L_d = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\}$
$L_u = \{\langle M, u\rangle \mid u \in L(M)\}$

We start off with assuming $L_u$ is recursive, reduce the problem in $L_d$ to a problem in $L_u$, and solve $L_d$ using the assumption that $L_u$ is recursive, now since $L_d$ is not even recursively enumerable, our assumption that $L_u$ is recursive turns out to be wrong, and since $L_u$ has a TM which accepts it, we conclude $L_u$ is a RE but not recursive language. A few pages later, the books says:
Theorem 9.7: If there is a reduction from $P_1$ to $P_2$ then
a) If $P_1$ is undecidable then so is $P_2$
b) If $P_1$ is non  RE then so is $P_2$
I'm confused about the part b) of this theorem, it says reducing a non RE problem to another problem gives you a non RE problem, but having reduced an instance of $L_d$ to an instance of $L_u$, we have reduced a non RE problem to a RE but not recursive problem.

If you look closely at the proof to show that $L_u$ is not recursive, the autor is using a reduction to $\overline{L_u}$ (which is not RE), not to $L_u$, and explain that a reduction to $L_u$ cannot work since $L_u$ is RE.


Address bus and memory If I have an address bus of 64K, i.e. it can access 64*1024 or 65536 locations, should I also have a memory chip with 65536 locations in it?
What I'm trying to ask is that do all the 65536 locations that the address bus can address have a corresponding memory location? Or can some address bus values go unused? (Like when I have 65536 address locations but my memory chip has only 32768 locations) Is such a combination acceptable?

What you are looking for is named "address decoding".

If a processor can address 64kB, its address bus is something like A[15:0].
If you use a 1kB memory chip, its addresses will be A[9:0].

There are several options :

Either you don't connect the bits A[15:10] of the processor. The memory will be mirrored at several "places" in the CPU address map, in this example, the same memory cell is accesssed at address 0, 1024, 2048, 3072, ... etc.
Or you use additional hardware to select the memory chip only when A[15:10]=00000, for example, to map the RAM only between 0 and 1023, allowing to connect other chips and map them elsewhere in the address map : ROM, IO ports...

If a memory location is not mapped, when an read access is attempted, it will generate random noise, some default value or repeat the last access. This was true on simple CPUs (for example the old 8bits CPUs)

In more advanced architectures (typically build with 16 or 32bits CPUs), accesses to non mapped memories generates an exception usually named "Bus Error".


What is the error when using Levenshtein distance on flattened binary trees? I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive.

The trees are stored as a flattened list of indices into node and terminal lookup tables. The particular flattening structure is the pre-order encoding format (pseudo code: flat(tree) = [id(root)] + flat(left) + flat(right)).

If I calculate the Levenshtein distance between the flattened trees, rather than between trees:

How big will my error be? (Difference to tree based distance)
Would other flat structures be more accurate?

This approximation is essentially arbitrarily bad.

Suppose you have a complete binary tree $T$ containing $2^k - 1$ nodes, of which the bottom $2^{k-1}$ are leaves.  Let $u$ and $v$ be the left and right child of the root, and $U$ and $V$ be the subtrees rooted at these vertices, respectively.  Let $w$ be the rightmost leaf in $U$.  To transform $T$ into a tree in which the locations of the leaf $w$ and the entire subtree $V$ have been swapped (so that the new tree has height $2k-1$) requires $2^{k-1}-1$ deletions of all nodes in $V$, the deletion of $w$, followed by the same number of insertions -- but the Levenshtein distance between the corresponding strings is just 2: delete the single list element corresponding to $w$ (from just before the half-way point of the string) and append it to the end.

(Well, possibly up to 2 tree-edits can be saved by turning pairs of insertions and deletions into substitutions.)


what are the weakest preconditions of these following statements what is the meaning of postcondition and weakest postcondition in terms of programing and what are weakest postconditons of following statements.
1. a=2*(b-1)-1   {a>0}
2. b=(c+10)/3    {b>6}
3. a=(a+2*b-1)   {a>1}
4. a=2*b+1;b=a-3 {b<0}

Let's do the first one. You want to find what condition on $b$ will imply $2(b-1)-1>0$. All you have to do is solve this inequality.
The other ones are similar.


how to find total paths in a graph which have only one vertex common with a given path Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.

How can I find the total number of paths in the graph that do not share any edge with the (unique) path from $a$ to $b$ and have only one vertex in common with it?

For example, suppose I have following graph :

and am given $a=4$, $b=5$.  Then there are six paths satisfying the above condition:  $(1,1)$, $(1,3)$, $(2,2)$, $(2,6)$, $(4,4)$, $(5,5)$ where $(x,y)$ is the path from $x$ to $y$.

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes.

Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. You want to compute the number of different paths passing through $a$. There are two possibilities:

either $a$ has only one neighbour: then the possible paths are the $N$ paths ($a$, $i$) with $i \in N$
either $a$ has several neighbours: then count the number of vertices in the subtree of each of these neighbours. The number of possible paths is the sum of the cross-products more the $N$ paths having $a$ as start.

Note that $T$ may have between $n$ and $n^2$ paths through $a$.

To answer your question, just sum all the trees' number of paths.

EDIT: small examples

If the tree has 4 vertices called $a,b,c,d$, connected linearly like that $a-b-c-d$ with $a$ being the vertex of the given path. Then $a$ has only 1 neighboor and the possible paths are all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d)$]

If the tree has 5 vertices $a $(of the given path)$, b, c, d, e$ connected like that:

    b-a-c-d
      |
      e

Then $a$ has 3 neighboors leading to the 3 subtrees: $b, c-d$ and $e$. The possible paths are:

all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d), (a,e)$]
the cross-products between $b$ and $c-d$: [$(b, c), (b, d)$]
the cross-products between $e$ and $c-d$: [$(e, c), (e, d)$]
the cross-products between $b$ and $e$: [$(b, e)$]

total 10 paths.


Showing that the entropy of i.i.d. random variables is the sum of entropies The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by
$H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$.

For a second random variable $X=X_{1}X_{2}...X_{n}$, where all $X_{i}$'s are independent and equally distributed (each $X_{i}$ is a copy of the same random variable $Y$), the following equation is known to be true:

  $H(X)=n\cdot H(Y)$

I want to prove this simple equation, where the outcomes from $Y$ are interpreted as symbols from an alphabet $\Sigma$ and therefore $X$ is the random variable for strings of length $n$ (based on the distribution of $Y$).

It is easy to see, that
$P(X=w)=P(X=w_{1}...w_{n})=P(X_{1}=w_{1})\;\cdot\;...\;\cdot\; P(X_{n}=w_{n})=\prod\limits_{i=1}^{n}P(Y=w_{i})$
... but my approach to prove $H(X)=n\cdot H(Y)$ seems to be in a dead point
(every word $w$ has the form $w=w_{1}...w_{n}$ with $w_{i}\in\Sigma$ and  let $\large |w|_{\sigma_{i}}$ be the number of occurrences of $\sigma_{i}$ in $w$):

$H(X)=-\sum\limits_{w\in\Sigma^{n}}P(X=w)\;\log(P(X=w))$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)\;\log\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{n}P(Y=w_{i})\right)\left(\sum\limits_{i=1}^{n}\log\left(P(Y=w_{i})\right)\right)$
$=-\sum\limits_{w\in\Sigma^{n}}\left(\prod\limits_{i=1}^{k}P(Y=\sigma_{i})^{\large |w|_{\sigma_{i}}}\right)\left(\sum\limits_{i=1}^{k}\large |w|_{\sigma_{i}}\normalsize \;\log\left(P(Y=\sigma_{i})\right)\right)$

So, I am able to change some indices from word length to the length of the alphabet, which is used in $H(Y)$. But what now? Any help?

Your attempt at the proof does not take into account any natural order on $\Sigma^n$. While it may still work, it seems difficult.

A much easier proof can be given by induction over $n$. The base case is trivial ($H(X)=H(Y)$) for $X=Y$.
Then, denote $X=X_1\cdots X_n$ and $X'=X_1\cdots X_{n-1}$, so you have

$$H(X=w)=-\sum_{w\in\Sigma^{n-1}}\sum_{\sigma\in \Sigma}Pr(X=w\sigma)\log Pr(X=w\sigma)$$
$$=-\sum_{w\in\Sigma^{n-1}}\sum_{\sigma\in \Sigma}Pr(X'=w)Pr(Y=\sigma)\log Pr(X'=w)Pr(Y=\sigma)=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)(\log Pr(X'=w)+\log Pr(Y=\sigma))=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\left(\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(X'=w)+\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)\right)=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\log Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)+\sum_{w\in \Sigma^{n-1}}Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)=$$
$$=H(X')+H(Y)=(n-1)H(Y)+H(Y)=nH(Y)$$


Which of the following regular expressions generate(s) no string with two consecutive 1’s? This is a GRE practice question.

Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)

I. (1 + ε)(01 + 0)*

II. (01+10)*

III. (0+1)*(0+ε)

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) II and III only

My understanding is that neither I nor III generates strings with 11. In I, a string containing 1 is either 1 or 1 surrounded by 0's. In III, all 1's are preceded by 0's. But the correct answer is A, so III must generate a string with 11 somehow. Please explain. Thanks!

III is $(0+1)^* (0+ \epsilon)$ which means pick a word from $\Sigma^*$ where $\Sigma = \{0, 1 \}$ and then concatenate it with either $0$ or $\epsilon$.

so III Does generate a string with two consecutive $1$'s. In fact it generates every string which contains $1$'s, $0$'s or is empty.


Distributed parallel computing algorithms for content dependent data I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel and send data to master node. Here linear improvement in encoding is seen as number of nodes are increased. But now I want to further optimize this algorithm to get better results. Chunks I send to different machines might take different amount of time for encoding depending on content in that video chunk. So which algorithms in distributed parallel processing can be used here to optimize this process? To implement his system I am using OpenMPI framework.

You have a static number of tasks to be executed, and each task is independent (i.e., no communication among tasks is required). However, the chunks assigned to different machines might take a different amount of time for encoding.

In this situation, the simplest and probably the best possible approach, consists in cyclically mapping tasks to processors, in order to balance the computational load. This is a form of probabilistic mapping (see sub-section on Probabilistic Methods and Cyclic Mappings, just before Section 2.5.2 on the linked web page). As an example, if you have $p$ processors and $n$ tasks (with $n > p$), you can simply assign task $i$ to processor $i \mod p$.


Concurrency and fairness I'm studying the concurrency in programming and the atomic instructions.
What i have not understood is the concept of "fairness" applied to this matter.
Can you give me an hint ?

Suppose you are running two concurrent processes (or threads), which both perform intensive disk I/O. Both repeatedly attempt to read/write on some file.

Now, the scheduler must decide which requests to handle. The scheduler could serve the first process, then the second on, then the first, etc. in a round-robin fashion. This would guarantee fairness: any process request is eventually served.

Suppose instead that the scheduler wants to maximize disk throughput. One way to do that is to move the disk head as little as possible. This can be done by serving the I/O request which operates on the closest file (roughly speaking) to where the head is found at the moment. Assume the first process only accesses file A, while the second process accesses only file B. If both continuously perform requests on their files, the only one of them will be served: e.g. if A is the first accessed file, B will never get accessed since keeping the disk head on A optimizes performance with respect to moving the head to file B. Hence, the second process will never get served, and will "starve". This scheduler is not fair.


Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n For analyzing the running time of an algorithm , I'm stuck with this recursive equation :
$$
T(n) = \log(n) \cdot T(\log n) + n
$$
Obviously this can't be handled with the use of the Master Theorem, so I was wondering if anybody has any ideas for solving this recursive equation.

I'm pretty sure that it should be solved with a change in the parameters, like considering $n$ to be $2^m$, but I couldn't manage to find any good fix.

I suppose you are looking for an asymptotic bound. Notice that the recursion depth is $\log^* n$, that is how often do I have to apply the logarithm recursively to get below 2. Also, the function is increasing. Using these two facts, you can plug in the recursion once and then you  see that you have at most $\log^*$ summands, each of them at most $\log^2 n$ and then the additional $n$. This sum is dominated by $n$.

$$
\begin{align}
T(n)&=\log(n) T(\log n)+n=\log n \log\log n \;T(\log\log n)+\log^2(n)+n \\
&\le \log^*n\log^2n+n=O(n)
\end{align}
$$

Clearly $T(n)\ge n$ and thus $T(n)=\Theta(n)$.


A query regarding P vs NP Problem Statement: Given a Problem $(A)$ such that: Any proposed solution $(S_0)$ is guaranteed to be polynomial size w.r.t. $A$. Now, consider a fixed set of $K$ properties $\{k_0, k_1,...k_c\}$, where each property is $coNP-Complete$.

For any solution $S_0$ is considered a valid solution iff: "None of the property in $K$ has a $NO$ instance for $S_0$".

Example: For some hypothetical problem $(A')$ let the solution $S_0'$ be a simple graph with $n$ nodes. Let $k_i$ be the property: "$S_0'$ does not contain  a clique with $n/4$ nodes".

Query: Assuming the highly improbable scenario that $P=NP$, it implies $P=NP=co-NP)$. Thus, all the properties in $K$ are $P-Complete$. Does that imply that finding the solution $(S_0)$ for $(A)$ is in $P$ ?
It seems so but still need confirmation.

Your problem is essentially a $NP^{coNP}$ problem. If $P=NP$ then the polynomial hierarchy collapses and your problem is in $P$.

If $P=NP=coNP$ then we can check in polynomial time whether a solution $S_0$ is valid (using a polynomial-time algorithm to check each property, which exists because $coNP=P$). Thus, the problem is in $NP$, and thus, in $P$.


Why $R\circ\emptyset$ is not always equal to $\emptyset$ I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is any regular expression.

Couldnt find any example that contradicts that

Assuming by "$.$" you mean concatention ($\circ$ when made explicit by Sipser) and by $\phi$ you mean $\emptyset$, I'm not sure what the confusion is. Sipser is claiming that sometimes (in almost every case actually), $R\circ\emptyset \neq R$. You are correct in saying that $R\circ\emptyset = \emptyset$, so the only case where $R\circ\emptyset = R$ is when $L(R)=\emptyset$. For any regular expression that generates at least one string (including $\varepsilon$), $L(R) \neq \emptyset$ but $L(R\circ\emptyset) = \emptyset$, so $R\circ\emptyset \neq R$.


Divide and Conquer Algorithm to calculate $a^n$ I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$.

So for example, using the Java language pattern, the algorithm will be defined as follows:

public double exp(float a, int n) {
    ...
}

But I am unable to determine what would be possible sub-problems of this problem as there is not set from which I can create subsets.

How can I achieve this using a divide and conquer method?

I think you are looking for something along these lines.

public double exp(float a, int n) {
    if(n<=0) return 1; // just for safety saying <= instead of == to allow
    if(n==1) return a;
    float floor_exp = exp(a,floor(n/2))
    if(floor(n/2) < ceil(n/2)){
        return floor_exp * floor_exp * a;
    }
    else{
        return floor_exp * floor_exp;
    }
}

Note that floor and ceil are not functions in Java but in Python. Use these for Java. Also this will only work for n >= 0. The result is incorrect for the other case.


How to show that problems are in NP? I want to show that the following problems are in NP (NP-completeness is irrelevant) by textually describing a non-deterministic Turing machine which runs in polynomial time. The assumptions are that addition, multiplication, tests for divisibility can be done in polynomial time and natural numbers are represented in binary.

a) $\{n \in \mathrm{N} \ | \ n \ $is not a prime number$\}$

b) $\{x_1, ..., x_n, y \in \mathrm{N} \ | \exists M \subseteq \{1, ..., n\} : \sum_{m \in M}x_m = y \ \}$

For a) it's clear that there must be a non-trivial divisor if $n$ isn't a prime, but how does it exactly work? How can I reject invalid and verify valid inputs?

The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. Intuitively, a problem is in $\mathsf{NP}$ iff we have an efficient (polynomial time) verification algorithm with polynomial size certificates/proofs.

For example, if you want to check if a given number $m$ is composite,
the following works:

Format of certificates: certificates are a pair numbers $(a, b)$,
Verification algorithm: a certificate $(a,b)$ is accepted iff $1<a,b<m$ and $ab=m$.

If a number is composite then there is a pair of number $(a,b)$ which satisfies the condition and has size $O(\lg m)$. It is important that the certificate has polynomial size in the size of input (here the size of input is $\lg m$).

If a number is not composite there are no such pairs.

Note that we fix a particular certificate verifier for all inputs. You cannot change the verification algorithm from one input to another one.

A more challenging question is to show that primeness is also in $\mathsf{NP}$, i.e. there are polynomial size primality certificates.


Meaning of $\stackrel{*}{\rightarrow}$ production rule? I've seen the production rule $\stackrel{*}{\rightarrow}$ in some papers concerning regular languages.

What's the meaning of $\stackrel{*}{\rightarrow}$ production rule?

It's either the transitive closure or reflexive-transitive closure of $\rightarrow$. That is, $A\rightarrow B$ means that you get from $A$ to $B$ in exactly one step; $A\rightarrow^*B$ means either you get to $B$ in one or more steps (transitive closure) or in zero or more steps (reflexive-transitive closure).


If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges? My problem is mainly from this lecture notes on convex optimization here page4

Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer programming problem

\begin{equation*}
\begin{aligned}
& \underset{}{\text{minimine}}
& & \sum_{u,v\in E}|x_u-x_v| \\
& \text{subject to}
& & x_s =1 ,x_t=0 &x_v\in \left\{ 0，1\right\}  \forall v \in V
\end{aligned}
\end{equation*}

then we can relax to:

\begin{aligned}
& \underset{}{\text{minimine}}
& & \sum_{u,v\in E}|x_u-x_v| \\
& \text{subject to}
& & x_s -x_t =1
\end{aligned}

for  $0 \leq l \leq 1$ we define $S_l:= \left\{v|x_v \geq l\right\} $ then we have $$\sum_{u,v\in E}|x_u-x_v| \geq\int^{1}_{0}|\delta_l(S_l)|dl$$
where $\delta_l(S_l) $ denotes the crossing edge in $S_l$

how to see this inequality ?

It's important to first understand how $\delta(S_l)$ changes. When $l = 0$, $S_l$ contains all vertices, and when $l = 1$, $S_l$ contains no vertices. In either case, there is no edge going between $S_l$ and $\overline{S_l}$, so $\delta(S_l) = 0$.

For values of $l$ between $0$ and $1$, $\delta(S_l)$ contains exactly the edges with one endpoint in $S_l$ and one endpoint in $\overline{S_l}$. In particular, if we define

$$f_{ij}(l) =\left\{
 \begin{array}{ll}
  1  & \mbox{if } l \mbox{ is between } x_i \mbox{ and } x_j \\
  0 & \mbox{otherwise.}
 \end{array}
\right.$$

then we have $$|\delta(S_l)| = \sum_{(i, j) \in \delta(S_l)} 1 = \sum_{\substack{(i,j) \in E \\ i \in S_l \\ j \not\in S_l}} 1 = \sum_{(i, j) \in E} f_{ij}(l).$$

Now let's consider one particular edge, from $u$ to $v$. Because $f_{uv}(\cdot)$ is just $0$ everywhere except for on one interval where it takes on the value $1$, the value of $\int_0^1 f_{uv}(l)\,\mathrm{d}l$ is just the length of the interval on which $f_{uv}(l) = 1$, that is, $|x_u - x_v|$. So

$$\sum_{(u, v) \in E} |x_u - x_v| = \sum_{(u, v) \in E} \int_0^1 f_{uv}(l)\,\mathrm{d}l = \int_0^1 \sum_{(u, v) \in E} f_{uv}(l)\,\mathrm{d}l = \int_0^1 |\delta(S_l)|\,\mathrm{d}l.$$


substitution method on T(n) = T(floor(n/2)) + n recurrence While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.

Why we assumed that this inequality holds for all positive $m<n$, in particular for $m=\lfloor n/2\rfloor$? on what basis do we choose this $m$ and why do we need it. Appreciate your answers.
EDIT: Excerpt is from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

As Yuval has mentioned in the comment that the proof is based on the complete induction.
However, an important thing is missing in the screenshot that you have shared. The "base case" is missing. Without the base case, the induction hypothesis and proof make no sense.
Here, the base case is when $n = 1$. You might want to verify that $T[1] = O(1)$. And, if that is the case, then $T[1]$ satisfies the induction hypothesis, i.e., $T[n] \leq c \cdot n \log n$ for $n = 1$ and sufficiently large $c$. Now, you would like to prove that the hypothesis also holds for other values of $n$.
For this, you assume that $T[m] \leq c \cdot m \log m$ for any $m<n$. And, suppose using this you could prove that $T[n] \leq c \cdot n \log n$. Then, it will imply that the hypothesis is indeed the correct hypothesis for every $n$. This is because you can apply this proof step to the base case. And, it will give you the correctness of the hypothesis on $T[2]$. Then, you apply the proof step on $T[2]$ and it will give you the correctness on $T[3]$, and so on... Therefore, it proves that the hypothesis is indeed the correct hypothesis for all value of $n$, for sufficiently large $c$.


does cpu time reflect BigO time complexity QUESTION
does CPU time reflect Big O time complexity?
WHAT I MADE
I implemented two Fibonacci functions in C programming language. The former has recursive behaviour while the latter has iterative behaviour.
I found out that the worst case scenario for the recursive version is exponential time (i.e. $2^n$) and linear time for the iterative one - since I have a simple loop within.
I then computed the CPU time for both the version using the time.h C library.
WHAT I EXPECT
I expect those CPU values to be somehow related with that time complexity. Generally speaking, I expect way larger CPU times for the recursive version.
WHAT I GOT
I got the foregoing plot using MATLAB (that is a loglog plot of cpu times as function of $n$).

Seems like the CPU time for the recursive function has an exponential behaviour - that is what I was expecting. Though, I'm not completely sure about CPU time for the iterative version since that function does not look like this one (section log-log graphs).
I'd like to answer myself without doubts but I'm quite newbie.

There are really two questions here:

How does CPU time relate to time complexity?
Can you use a plot of CPU time to understand time complexity?

Let me answer each in turn.

Time complexity

Time complexity refers to the total time it takes for the algorithm to finish.

If by "CPU time" you just mean the time it took for this particular program to run, excluding the time for other programs or the operating system, then yes, these are the same.

If by "CPU time" you meant the time spent on computation but not time spent on I/O, then it might or might not match what is meant by time complexity.  In practice, I/O is often slower than computation -- maybe by a significant factor.  Normally, in theoretical work where we measure time complexity, we don't try to account for that distinction, as it's "only a constant factor".

The plot heuristic

Plotting the running time as a function of the size of the input can definitely be a useful heuristic to form an informed guess about what the asymptotic time complexity of the an algorithm is.  It's often a good guide.  However, be warned that it is not 100% reliable: there are some cases where it can be misleading.

I'd like to refer you to the following three questions for more on this topic:

how to understand time complexity from a plot?
How to fool the plot inspection heuristic?
How does the automatic complexity analysis of Codility work?

Bottom line

In summary: yes, basically, plotting CPU time  as a function of input size can be a helpful way to assess asymptotic time complexity, as long as you keep in mind the caveats.


CNF form of variable assignment problem There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying all assignments and then checking if they are distinct, but I think it could be done better)

If you only have to encode this (and don't have any other constraints on $x_i$), you can then use the following constraints:
$x_1 < x_2 < \dots < x_{n-1} < x_n \leq k$
which is $n$ constraints.

Let $m=\lceil \log_2 k\rceil$ and $x_i = b_{im}, b_{i(m-1)}, \dots, b_{i1}$, where $m$ is the high bit and $1$ is the low bit.
Define $d_{ij} = b_{ij}\textrm{ XOR }b_{(i+1)j}$.
Then, the constraint $x_1 < x_2$ is representable as:
$$
\bigvee_{i=1}^{m} \left[\left(\bigwedge_{j=i+1}^m d_{1j}'\right)\left(b_{2i}b_{1i}'\right)\right] = 1
$$
basically the i-th clause encodes that the top $m-i$ bits are identical and the $i$-th bit is $1$ in $x_2$ and $0$ in $x_1$.

Abusing notation slightly (taking the constants in the representation of $k$ for $x_{n+1}$), a similar technique can be used for $x_n \leq k$, where one would add an extra clause $\bigwedge_i d_{ni}'$ for handling the equality.

The above formula is a DNF. To get to CNF, one would simple encode $\textrm{NOT}(x_2 \leq x_1)$.

Finally, if it's needed to represent $x_1 \geq 1$ one can do this by adding a CNF clause $\bigvee_i b_{1i}$.

Note that the complexity here is really good. $O(nm)$ clauses, and $O(nm^2)$ literals. In particular if $n$ and $k$ are large this is much better than for other techniques (but it isn't applicable in other settings where other constraints could change the ordering).


Deciding if a Turing machine has made a left move In writing a decider for a machine to see if it has made a left move or not on an input of w, it is said that if we continue the computation for $|w|+N+1$ ($N$ : number of states) number of steps, we can make a decision for this decide.

I didn't get why $|w|+N+1$ number of steps. Could someone explain this in more detail?

$|w|$ steps are needed to scan the input, if a left move is made during this scan accept.

Otherwise, at the end of the input, the head of the Turing machine is on the blank part of the tape (over the first blank symbol after the input). Suppose the state is $q_{i_1}$. If the Turing machine doesn't make a left step and stays on state $q_{i_1}$, then it will do it forever (it will continue moving right on the infinite blank tape on state $q_{i_1}$). But it can move right and switch to state $q_{i_2}, i_1 \neq i_2$.

If you continue with this reasoning you see that there are only two possibilities:

it moves left or
it enters a state $q_{i_{k+j}}$ for the second time and thus it will loop forever: $q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...\rightarrow q_{i_{k+j}}=q_{i_k} \rightarrow q_{i_{k+1}}\rightarrow ...$

But there are only $N$ different states so at most $N+1$ more steps are needed to detect such loop.


Sorting a set of $n$ elements containing only $\log n$ unique elements We have a set of $n$ elements which contains at most $\log n$ different numbers. I want to sort this set faster than $O(n \log n)$. Is it possible?

I tried using a hash table to find the set of $\log n$ unique elements, then sort them in $O(\log n \log \log  n)$, after that creating a new array of $n$ element with this array of $\log n$ elements in $O(n)$, but it is not the right answer since using hash table may fail, and the worst case still needs more than $O(n \log n)$.

Is there any algorithm faster than $O(n \log n)$?

Your solution is almost complete. Try replacing the hash table with a comparable data structure, such as a balanced binary search tree. Since the tree will only contain at most $\log n$ elements, all the operations on the tree will take time $O(\log\log n)$, and the resulting algorithm will take time $O(n\log\log n)$.

Any comparison-based algorithm for your problem takes time $\Omega(n\log\log n)$. To see that, notice that there are roughly $(\log n)^n$ different possible relative orderings for your set (the actual number is a bit smaller, but not by much). Any comparison-based decision tree must therefore have depth $\Omega(\log [(\log n)^n]) = \Omega(n\log\log n)$.

If you allow more general algorithms, then you can improve the complexity to randomized $O(n)$ using a hash table, along the lines that you mentioned. Since you can afford a hash table of size $O(n)$ although the occupancy is only $\log n$, the probability that your algorithm exceeds its expected running time significantly will be very, very small.

It is also possible that under a suitable computation model, you can sort you list in deterministic $O(n)$ time. Some people consider this kind of algorithm cheating, though.


Halting problem without self-reference In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a $T$ exists. Then, we consider a case where we restrict $i$ to $M$ itself, and then derive a contradiction by using an instance of a diagonal argument. I am interested how would the proof go if we are given a promise that $i \not = M$? What about promise $i \not = M^\prime$, where $M^\prime$ is functionally equivalent to $M$?

Suppose HALTS is a TM that reads its input as a pair $M$ and $x$, where $M$ is a TM encoding and $x$ is any input to that TM.

Your question is if what would happen if we assumed HALTS solved the halting problem for all inputs $\langle M,x \rangle$ such that $x$ is not an encoding of a TM that is functionally equivalent to $M$.

I claim this implies a contradiction. I came up with this on the spot, so I welcome any and all criticism of my proof. The idea of the proof is that rather than diagonalizing something on itself, we make two mutually recursive TMs that behave differently on some input (thus are not functionally equivalent), but otherwise cause contradictions.

Let $D_1$ and $D_2$ be two mutually recursive TMs (which is to say we can simulate, print, etc, the description of $D_2$ inside the program of $D_1$ and vice versa). Note that we can make mutually recursive TMs from the recursion theorem.

Define $D_1$ and $D_2$ as follows: on input $x$, if $|x| < 10$ (10 chosen arbitrarily), then $D_1$ accepts and $D_2$ loops. (Thus, they are not functionally equivalent).

Given input $x$ with $|x| \ge 10$, define $D_1$ to simulate HALTS on $\langle D_2, x \rangle$ and halt if $D_2$ halts or loop if $D_2$ loops.

Given input $x$ with $|x| \ge 10$, define $D_2$ to simulate HALTS on $\langle D_1, x \rangle$ and loop if $D_1$ halts or halt if $D_1$ loops.

Then note that for any $x$ with $|x| \ge 10$, $D_1$(x) either halts or loops. If $D_1$ halts on input x, then we know HALTS($D_2$, x) determined that $D_2$ halts on input x. However, $D_2$ halting on input x implies that HALTS($D_1$, x) loops.

If $D_1$ on input $x$ loops, the contradiction follows similarly.

This is a contradiction unless $x$ is an encoding for a turing machine functionally equivalent to $D_1$ or $D_2$, in which case HALTS has undefined behavior. However, $x$ was chosen at arbitrary from all strings of size greater than $10$. Thus, it remains to show there exists a turing machine with an encoding of size greater than 10 that behaves differently than $D_1$ and $D_2$. We can construct such a machine trivially. QED.

Thoughts?


Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$ I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment.

I need to prove a language $L$ is not Turing-recognizable by giving a reduction from the following language:

$$D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}\,,$$

where $M$ is a Turing machine, and $\langle M\rangle$ is a binary encoding of $M$, and it is already assumed $M$ is neither decidable nor recognizable.

Most of the things I've read show how to prove a language is undecidable, but not unrecognizable. How would it be different?

I've encountered the following that I feel I can modify for my problem:

$$\mathrm{A_{TM}} = \{\langle M,w\rangle \mid M \text{ accepts }w\}\,.$$

$D$ reduces to $\mathrm{A_{TM}}$. Consider the computable function that maps $\langle M\rangle$ to $\langle M',w\rangle$, where $w=\langle M\rangle$ and $M'$ is a machine that accepts if and only if $M$ rejects. Therefore, $\mathrm{A_{TM}}$ is undecidable.

But I'm not really sure how to understand it, in plain English. Could someone explain it? Plus, how could I change this to show $\mathrm{A_{TM}}$ is unrecognizable (even if it is recognizable)?

Like any claim, you have more than one way to prove a language $L$ is unrecognisable.

In case your language is in $Co-RE$ you can do one of the following:

Show $\overline{L}$ is in $RE$ by describing a TM that accepts $\overline{L}$.
Show $\overline{L}$ is in $RE$ by reduction $\overline{L}\le_m Some-Language-In-RE$.
Show $\overline{H_{TM}} \le_m L$ or $\overline{A_{TM}} \le_m L$ or some other language you know is in $Co-RE$

Note that you must show that $L\notin R$ in order to deduce $L\notin RE$.

If $A\notin Co-RE$, you can show a reduction to your language

$A\le_m L$ where $A\notin RE$ so if $L\in RE$ you have a contradiction.

There is more than one way.
I'm not sure I understand your question, but if your task is to show $D\notin RE$.
I would show $\overline{D}\in RE$, and than show $D\notin R$.


How to prove (un)decidability Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time limit when a program is given no input.
In other words - is this problem decidable or undecidable?
I was thinking of reducing the Halt problem when it is given no input, but I'm a bit unsure of whether I should concider the byte size and time limit as input as well, or how I should conquer this problem.
Thank you.

The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes.
For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and reject).


Closure operator and set of fixpoint In chapter 2.2 of

Giacobazzi, Roberto; Ranzato, Francesco, Uniform closures: Order-theoretically reconstructing logic program semantics and abstract domain refinements, Inf. Comput. 145, No.2, 153-190 (1998). ZBL0921.68057.

it's said:

  An  (upper) closure  operator (or simply closure) on a poset $C$ is  an  operator $\rho:C \to C$ monotone, idempotent and extensive (i.e.,
  $\forall x \in C . x \le \rho(x)$). We denote by $uco(C)$ the set of all closure operators on the poset $C$. If $C$ is a complete lattice then each closure operator $uco(C)$ is uniquely  determined  by the set  of its  fixpoints, which is its image $\rho(C)$

Where can I find a proof of the phrase in bold?

There is an intimate connection between closure operators and complete lattices.

Given a closure operator $C$ on a set $X$, we can construct a complete lattice $L(C)$ as follows:

The points of the lattice are the fixpoints of $C$.
The meet of the lattice is $A \wedge B = A \cap B$.
The join of the lattice is $A \vee B = C(A \cup B)$.

Conversely, given a complete lattice $L$ of subsets of $X$, we can construct a closure operator $C:=C(L)$ on $X$ using the formula
$$ C(A) = \bigcap \{ B \in L : B \supseteq A \}. $$

It turns out that these two operators are inverses:
$C(L(C)) = C$ and $L(C(L)) = L$.

In particular, this shows that $C$ is determined by the set $L(C)$ of fixpoints, since
$$
C(A) = \bigcap \{B \in L(C) : B \supseteq A\}.
$$

(This information is taken from the sample chapter of M-solid varieties of algebras by Koppitz and Denecke.)


Relationship between #of cores and Dynamic Power The book I'm currently reading specifies that Dynamic Power = (1/2) * Capacitive Load * (V^2) * frequency However, that is assuming it's a single-core system. I wonder if we're calculating the Dynamic Power of a dual-core system, would that be twice the formula of Dynamic Power above ?

The capacitive load of a dual-core system would be (roughly, ignoring, e.g., sharing parts of the memory hierarchy) twice that of a single core system (with the same core implementation), so the formula would be unchanged.

(Of course, the frequency and even the voltage for different cores might be independently adjustable.)


Choose N pairs of (job, time slot) with a constraint on the number of different jobs I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of other predefined constraints. We refer to a particular pair of (job, time slot) as a "shift".

I'm not optimizing the entire workforce at once but instead I assign one person at a time.* Here's an overview of how I modeled the sub-problem:

Enumerate the set $S$ of all possible shifts ($|S| = |J|\times|T| = 90$ in my case)
Use an objective function related to the number of people already assigned to each shift (and the need for that shift)
Find solution $x \in \{0,1\}^{|S|}$ that associates to each element of $S$ a value in $\{0, 1\}$

The constraints are the following:

Each person can be assigned up to N shifts (depending on their preference)
Up to 2 shifts during the same day
No consecutive shifts except when the job remains the same
Each person can do only up to two different jobs during the entire event

I managed to encode all the constraints as a linear program except the last one. Any idea on how that could be done ? If that is not possible at all (which I suspect), what tool can I use to solve this problem ?

* I know that is sub-optimal, but finding a better algorithm will probably be the subject of another question ;)

The last constraint is also no problem. You already have variables $x_{j,t}$, that say if the person works the $j$th job on the time slot $t$. Now you can introduce new binary variables $y_j$, that represent, if the person works at the job $j$ or not. Then you can model the constraint by:

$$\sum_{j \in J} y_j \le 2$$

The only part left is how you connect the information from the $x_{j,t}$ with $y_j$. But that is also not hard. If any of the $x_{j,t}$ is $1$, then you can force $y_j$ to also be $1$ with the constraints

$$y_j \ge x_{j,t}\qquad\forall t \in T, \forall j \in J$$

and force $y_j$ to $0$ if all $x_{j,t}$ are $0$. This can be done with:

$$y_j \le \sum_{t \in T} x_{j,t}\qquad\forall j \in J$$


Why is Uniform cost search called "uniform" cost search? By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function.

Is this explanation correct ? If yes, then don't all un-informed cost searches (like BFS, DFS, etc) have no heurstic and thus, be called as "uniform cost searches" ?

Truth to be told, I am not completely sure about my answer, so take it with a grain of salt:

Uniform Cost Search is just a variant of Best-First Search. Among other variants, take Breadth-First Search where $f(n)$ equals $d(n)$, its depth. This actually means that nodes are not treated uniformly since different paths to the same node might result very easily in different depths ---with different costs if the costs of the operators are different among them. Much the same happens with Depth-First Search where nodes are distinguished by the path that led to them.

What makes Uniform-Cost Search a uniform search is that nodes are distinguished just by $g(n)$ so that all paths that lead to a particular node n are considered to be equivalent (and they are indeed when seeking the optimal solution), with the first one (the one with the optimal value) being expanded, and all the others being discarded. In this regard, I would consider a number of Best-First Search variants, uniform such as $A^*$ where nodes are uniformly treated according to $f(n)=g(n)+h(n)$ with $h(n)$ being an admissible estimate.


Reductions where the number of certificates from one problem can be computed for another to varying degrees Let $A$ and $B$ be two decision problems in $NP$. Consider three cases:

(1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same number of solutions as $A$.

(2) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a fixed number of solutions for every solution of problem $A$. We can, in polynomial time, calculate the number of solutions for $A$ provided an oracle that gives the number of solutions to $B$, and vice versa. What if we can guarantee that the number of solutions for an instance of $A$ will be greater than the number of solutions for the corresponding instance of $B$ or vice versa?

(3) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having a solution if and only if $A$ has a solution. However, we do not have a polynomial time algorithm to compute the number of solutions for $A$ provided some number of solutions for $B$.  We also cannot guarantee that such a polynomial time algorithm does not exist.

What formal names and notation for the above sort of reductions? When is a Levin reduction called parsimonious? Instances one and two only? Is the third example necessarily worth anything?

Parsimonious reduction.
Polynomial-time Turing reduction (a.k.a. Cook reduction).
Polynomial-time many-one reduction (a.k.a. Karp reduction).

I've not come across cardinality restrictions of the form you mention in (2) so I don't know any name for them. If you find there isn't a name already, "monotone" would be a good one to choose.  In the case where the number of solutions to $B$ is less than $A$, you need "less than or equal to" since, if $A$ has exactly one solution, you still need to reduct it to a "yes" instance of $B$.


Category Set language using simply typed lambda calculus I am currently self learning Category Theory and Simply typed lambda calculus (STLC).  For learning purposes, I have implemented an STLC interpreter as given in  Types and Programming Languages book of Benjamin Pierce. Now i am wondering if I can extend this interpreter with category of sets (category Set ). i.e. interpret expressions to construct sets, pushouts, pullbacks etc.
Unable to find any directions on how to do this. Can someone please provide any helpful suggestions on this?

There are at least two directions in which you can proceed.
First, Church's simple type theory (see also this explanation) extends the simply typed $\lambda$-calculus with the types of natural numbers and booleans, and other constructs that make it sufficiently expressive to encode a certain kind of classical set theory. These ideas were pursued in the HOL theorem provers. For instance, HOL light for a small implementation. This approach has the flavor of doing logic, i.e., there is no general notion of computation - as opposed to the simply typed $\lambda$-calculus, which is a programming language.
Second, dependent type theory, of which there are many variants, is also an extension of the simply typed $\lambda$-calculus. It can be used as a foundation of mathematics. They are used in proof assistants, such as Coq, Agda, and Lean. Some variants, notably Martin-Löf type theory, do retain the character of a programming language. In fact, Idris is a programming language based on dependent type theory.
None of the above is "set theory", but these formalisms are quite suitable for expressing mathematics, including category theory.


How do computers really communicate with hard-drives on x86_64? All of us have saved a file on our computers using a programming language. If I look down through the layers of abstraction, I usually get stuck at a kernel-level call or a C-call like fwrite(); But even at this already deep level things like filesystems and location of storage are hidden from us. For example, one cannot tell on which drive a file is stored when the partition uses more than one drive, nor do you need to care which file-system is used.

This leads me to an extensive set of questions:

Imagine you are a creator of an OS running on x86_64.
You have not yet created an abstraction for working with external devices. Somebody now plugs in a device using a USB - Port.

Does this interrupt the processor or does this change a flag the OS can read?
How would you make sure a routine is set up which will start communicating with the device once plugged in?
After this routine is set up, which protocols are you using to communicate with the device?
Does it matter that the device is plugged in via USB, or would other ports work the same? If it does matter, how does the program know? (x86: Which assembly instructions are achieving communication with any device?)
You have now figured out that the device is indeed a hard-drive. Is communicating with every hard-drive the same? You would now like to - only for the matter of further questions -  do the following: If this device contains another OS (OS-signature in boot section), start the other OS (reading), if however, the disk does not contain another OS you would like to inject your data to the disk at byte disk_size/2. (Writing) How would you accomplish that? (Protocol?, Assembly - Instruction?)
EDIT: In my mind, a UEFI is also a tiny little OS. The boot section -  in my mind - correct me if I am wrong - is a part of a hard drive where Bios or UEFI is searching the actual OS. So any OS could start another OS...

Kind regards!

Disclaimer: I am not asking for assembly code, I am asking for the mechanism in general. However, examples given in x86_64 are welcomed.

The processor has a control bus which allows it to tell the motherboard it wants to write somewhere else than RAM. When the processor sets a certain line on the control bus, it can write data to a port instead of RAM.
The processor can send data to certain ports which, by convention, are used to talk to hardware. The Hard-Drives have controllers which will answer to certain values on their respective conventional ports. These will be called commands. SATA drives which are the most common types today use certain ports for bilateral communication between processor and hard-drive.
An example is PIO mode that all SATA compliant drives must respect. In PIO mode (https://wiki.osdev.org/ATA_PIO_Mode), the port 0x1f7 is used to send commands to the drive. It will then output its data onto a certain port that the processor will read to fetch the data.
As to USB, it is similar. The USB controller (xhci today see https://wiki.osdev.org/XHCI and https://wiki.osdev.org/Universal_Serial_Bus#USB_2.0_Host_Controllers) is actually polling its own USB port to determine if a device is plugged in at some point. This provides the plug and play functionalities.
When you do a read/write operation you use IO ports again just like before but these ports are mapped to RAM addresses creating RAM holes known as the PCI hole. To determine the memory mapped ports locations you need to parse the ACPI tables which are built by the BIOS during initialisation of the system. The ACPI tables have conventional locations in RAM that the OS can look for. Once the OS finds these tables it needs to interpret language known as AML to determine what devices are connected on the computer and where (at what RAM address) to find the ports/registers to communicate with these devices.
Other hardware then hard-drives (keyboard/mouse) work with interrupts and ports which is another complex subject.
PS: Developping your own x86-64 operating system is not that unrealistic. Osdev.org can help on that path. If you have some time and go step by step you will learn a lot.


Why doesn't this quine-less language contradict Kleene's recursion theorem? Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing complete without a quine.

I give a slightly simplified version of what they gave. Start with a Turing complete programming language $P$. Create a programming language $P'$ that is interpreted according to the following rules:

Try running the program according to the rules for $P$
If the input was empty, and if it outputs it own source code and then would terminate according to the rules of $P$, throw an error instead. We'll call this error a "quine error".

For example, $Python'$ is like $Python$, except that when given no input, if the program outputs its own source, it will throw a quine error instead of terminating normally.

What is the resolution to this apparent paradox?

The recursion theorem only applies to admissible programming languages. A programming language $P$ is admissible if it satisfies the following three properties, with respect to some reference programming language $U$:

The problem of simulating a $P$-program on an input $x$ is r.e.
There is a computable transformation $f$ which, given a $P$-program, outputs an equivalent $U$-program.
There is a computable transformation $g$ which, given a $U$-program, outputs an equivalent $P$-program.

In your case the first two properties hold, so the third must fail. You can try to implement $g$ by "compiling" a $U$-program to a $P$-program, but this compilation would fail if the resulting program attempts to print its own source code. The recursion theorem shows that there is no way around this problem.


Test if there exists an integer k to add to one sequence to make it a subsequence of another sequence Suppose that sequence $A$ contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ and sequence $B$ contains $m$ integers $b_1,b_2,b_3,\ldots,b_m$. We know that $m \geq n$. We assume without loss of generality that both sequences $A$ and $B$ are sorted in ascending order.

What's the fastest algorithm to determine if there exists an integer $k$ such that the sequence $a_1+k,a_2+k,a_3+k,\ldots,a_n+k$ is a subsequence of the sequence $B$?

Here is a naive algorithm, which would take $O(n(m-n))$ time. Store the sequence $B$ as a hashtable. For each element $b_j$ of the $B$ (except the largest $n$ elements), use $b_j-a_1$ as your guess at $k$; you can verify this guess by checking whether each of $a_1+k,\dots,a_n+k$ are in the hashtable $B$. This takes $O(n)$ expected time per guess at $k$, and you make $m-n$ guesses, so in total the expected running time is $O(n(m-n))$. Can we do better?

I came across this problem while trying to match two binary images (testing whether one image contains the other).

Here is a heuristic that won't always work, but should work with high probability if the integers in the arrays are chosen randomly from a large enough space.

Initialize a hashtable of counts $C$ to all zeros.  Then, repeat $t$ times: randomly pick $i,j$, compute $b_j-a_i$, and increment $C[b_j-a_i]$.  Finally, sort $C$ by counts, from largest count to smallest; then for each of the largest few values of $C[k']$, try $k'$ as your guess at $k$, and verify each guess.

Notice that in each iteration, the probability of incrementing $C[k]$ is at least $1/m$; whereas if $l\ne k$, we expect $C[l]$ to be incremented much more rarely (assuming the integers in the arrays are random and large enough).  Thus, after $t$ iterations, we expect $\mathbb{E}[C[k]] \ge t/m$ but $\mathbb{E}[C[l]] \ll t/m$.  So, once $t$ is large enough, $C[k]$ should be larger than every other entry in $C$.

How large does $t$ need to be?  I expect that $t = O(m \log m)$ should suffice, based on a central limit theorem approximation for the counts $C[l]$, assuming we are willing to accept a small probability of error (which can be driven exponentially small).  The constant factor hidden by the big-O notation might be non-trivial.

This is only a heuristic, and there will certainly be inputs where it fails.


Which NPC problems are NP Hard I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete

And Wikipedia defines this as

  A problem $H$ is NP-hard if and only if there is an NP-complete problem
  $L$ that is polynomial time Turing-reducible to $H$.

Like NP Complete problem is there any problem considered to be the first NP Hard problem?

To show one problem to be NP Hard we need just to reduce one NPC problem to it?

Whether all NPC problems are NP Hard?

If no, why not?

A problem is NP-hard if every problem in NP can be reduced to it by some appropriate kind of reductions (typically, polynomial-time many-one reductions). A problem is NP-complete if it is in NP and is NP-hard.

Therefore, by definition, every NP-complete problem is NP-hard.


Why is this greedy algorithm claim true? I'm taking a course about submodular functions and their applications towards influence maximization in a network. We've been discussing a greedy algorithm for selecting $k$ initial nodes to maximize influence and I'm confused about a statement made in class.

Let $O = \{o_1, . . . , o_l\}$, and $o_{\max}$ be the element with the highest marginal contribution in $O$ at stage $i + 1$. That is: $o_{\max} = \arg\max_{o\in O} f_{S_i}(o)$. At stage $i + 1$ the algorithm selects element $a_i+1$ and we are guaranteed that its marginal contribution is the highest. In particular, its marginal contribution is also higher than the marginal contribution of the element in $O$ that has the highest marginal contribution:
$$f_{S_i}(a_i+1) \geq  f_{S_i}(o_{\max})$$

$f$ gives the expected number of nodes influenced and $f_S$ is the marginal contribution of adding set $a$ to set $S$ ie: $f_S(a) = f(S\cup a) - f(S)$
$$f_{S}(a) \geq f_S(o^*)\,.$$

This doesn't make sense to me. Consider the circle cover problem:

At timestep $t = 1$, the greedy algorithm selects $A$ and optimal selects $B$. (Greedy is on the left and optimal is on the right).

$$f_S(A) \geq f_S(B)\,,$$
but at $t=2$
the greedy selects $B$ and optimal selects $C$.
$$f_S(B) \ngeqslant f_S(C)\,,$$
because the marginal contribution of the greedy algorithm is only 4 when the optimal is 5.

Why did we say that selecting elements greedily has better marginal contributions than optimal? I'd appreciate a theoretical and possible concrete example if possible!

The claim is not that

$$f_S(B) \ge f_S(C).$$

Rather, the claim is that

$$f_{S_1}(B) \ge f_{S_1}(C).$$

Do you see the difference?  Here $S_i$ is the set of elements chosen (by the greedy algorithm) in the first $i$ iterations, so $S_i=\{A\}$.  Thus, the claim is that

$$f_{\{A\}}(B) \ge f_{\{A\}}(C),$$

i.e.,

$$f(\{A\} \cup \{B\}) \ge f(\{A\} \cup \{C\}).$$

The latter claim is indeed true, as both the left-hand side and the right-hand side are 9 (i.e., $f(\{A,B\})=f(\{A,C\})=9$), since they cover 9 of the "blue dots".


Finding the lowest-weight negative cycle in a weighted digraph Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

Finding the least weight simple negative cycle is NP-hard even in the undirected case, as shown in this answer by reduction from Hamiltonicity. The reduction is very simple: make each edge have weight $-1$. There is a cycle of least weight at most $-n$ iff the graph is Hamiltonian.


Why is addition in GF(2^8) the same as XOR? I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure why it's described as 'addition' in the literature I read but the code I see implements it with XOR.

Finite fields are usually described as polynomials over the base field (in this case $GF(2)$) modulo some irreducible polynomial. If you represent each polynomial as a vector of coefficients, then addition of polynomials corresponds to elementwise addition of the coefficients, which in the case of $GF(2)$, translates to XOR.

For example, suppose that your field elements are $1+x^2$ and $x+x^2 + x^5$. Their binary representations are $101$ and $100110$ (LSB is the coefficient of $1$). Their sum is $1+x+2x^2+x^5 = 1+x+x^5$ (since $2=0$ over $GF(2)$), whose binary representation is $100011$. This is the XOR of $101$ and $100110$.


Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem This is a question from an exam I did today:

  Given $M$, a turing machine, we need to decide the following:

  1) $M$ halts on every input

  2) The language of $M$ is CFL

My question is, can I prove that this problem is not in $RE$ (recursively enumerable) using Rice's theorem? I understand that Rice's theorem works for languages and not machines, and when first looking at it, number 1 is a property of a machine not the language. But what I said, is that actually it is a property of a language: $M$ halts on every input iff $L(M)$ is decidable! (in $R$), so we can use Rice.

What do you think?

First of all, it is not true that $M$ halts on every input iff $L(M)$ is decidable. Indeed, $L(M)$ can be decidable even if $M$ doesn't halt on every input. Consider for example the machine which never halts on any input—the empty language is certainly decidable.

Rice's theorem considers properties of partial functions. The partial function is the one computed by the Turing machine, with $\bot$ representing the case that the Turing machine doesn't halt on a specific input. If a machine $M$ always halts then the corresponding function is total—never attains the value $\bot$. This is a property of partial functions, and fits within the framework of Rice's theorem.

If you're not sure about this, have a look at the proof that the language of total Turing machines (ones that halt on all inputs) is not decidable.


Show that language is context-free Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such words over alphabet $\Sigma$, for which there exists some run of automata $A$, such as in every step symbols on the stack belongs to the regular language $R$.

Show that language $L_R(A)$ is context-free.

Let $Q$ be the set of states in a DFA $D$ for $R$. We replace $\Gamma$ with $\Gamma \times Q$, and update the PDA so that the stack contains, apart from the original stack symbols, also the state that $D$ is in after reading the current word on the stack. The PDA only allows transitions if the element at the top of the stack corresponds to an accepting state of $D$, and also checks this condition at the very end.


Different application of Arden's theorem leads to different answers So, I have to solve for the following set of equations

$q_1$ = $q_1$a + $q_2$b + $\epsilon$
$q_2$ = $q_1$a + $q_2$b + $q_3$a
$q_3$ = $q_2$a

There are two ways to do this.
I did this

$q_1$ = $q_2$b + $\epsilon$ + $q_1$a
$q_1$ = ($q_2$b + $\epsilon$)a* Applying Arden's theorem

Now substituting in $q_2$ the values of $q_1$ and $q_3$

$q_2$ = $q_2$ba*a + a*a + $q_2$b + $q_2$aa
$q_2$ = a*a + $q_2$(ba*a+b+aa)
$q_2$ = a*a(ba*a+b+aa)* Applying Arden's theorem
$q_2$ = a*a(ba*+aa)*

Now substituting in $q_3$, the answer should be

$q_3$ = a*a(ba*+aa)*a

However, the correct answer is

(a + a(b+aa)*b)*a(b+aa)*a

which can be obtained by first substituting $q_3$ in $q_2$, and then substituting $q_2$ in $q_1$, and finally solving $q_2$, $q_3$ from the obtained regular expression for $q_1$.
Can someone tell where I have gone wrong in the above method, or am I applying ardens theorem in the wrong way ?

The two regular expressions describe the same language.


Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$? It is known that $\mathrm{SPACE}(o(\log \log n)) = \mathrm{SPACE}(O(1))$ (see e.g. these lecture notes by Christian Scheideler).

One inclusion is trivial, so I'm trying to show that $\mathrm{SPACE}(o(\log \log n)) \subseteq \mathrm{SPACE}(O(1))$ as follows.

Let $L$ be a language and $A$ is a Turing machine with alphabet size plus tape symbol is equal to $c$, to solve the problem $L$. We know that number of configurations is going to be at most $c^ {o(\log \log n)}\times\mathrm{poly} (o(\log \log n))$ (roughly), but even $c^ {o(\log \log n)}  \notin O(1)$.

For example, $ s(n) = \log \log \log n \in o(\log \log n)$ but $c^{s(n)} \notin O(1) $. I don't know, how to proceed further.

My question: How to prove that $\mathrm{SPACE}(o(\log \log n))\subseteq \mathrm{SPACE}(O(1))$?

You're basically there. If the machine uses at most $s(n)$ tape cells for inputs of length $n$, then it can't visit more than $C(n)=|Q||\Sigma|^{s(n)}s(n)$ different configurations (possible states times possible tape contents times possible head positions).  Since the machine decides a language, it must halt for all inputs, which means that it can't repeat a configuration, since a deterministic machine that repeats a configuration must loop forever. Therefore, by the pigeonhole principle, it can't run for more than $C(n)$ steps on any input of length $n$.

If $s\in o(\log\log n)$ then $C(n) = o(n)$ so the machine terminates after fewer than $n$ steps for all sufficiently large $n$. Intuitively, the machine can't stop in, say, $\sqrt{n}$ steps because, in that many steps, it hasn't seen the whole input, so it doesn't even know what $n$ is.

More formally, let $t(n)$ be the greatest number of steps taken by the machine on inputs of length $n$. Let $w$ be an input long enough that $t(n)<n$ for all $n\geq |w|$, and choose $w$ so that the machine runs for $t(|w|)$ steps on this input.  We know that $t(|w|)\leq C(|w|)<|w|$, so the machine must terminate before it has time to read the whole input. Because it doesn't read the whole input, its execution on input $wz$ must be the same as its execution on $w$, for any string $z$. Therefore $t(|wz|)=t(|w|)$ for all strings $z$, so the function $t$ is constant for all inputs greater than length $|w|$.

Because it halts in a constant number of steps, it only uses a constant number of tape cells, so the language it decides is in $\mathrm{SPACE}(O(1))$.


How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution.
By substitution I got the following (not sure if it is correct):
$$T(n) = 5^kT(1) + \sum_{i = 0}^{k}{5^{i}\left(\frac{n}{2^{i}}\right)^{2}\lg^{2}\left(\frac{n}{2^{i}}\right)}$$
I am not sure how to proceed from this. I don't even know if this approach is correct so far. How do I solve this recurrence?

You can use the master theorem.
This theorem allows you to solve some recurrences of the form $T(n) = aT(n/b) + f(n)$.

You need to compare $n^{\log_b a}$ with $f(n)$.
In you case $n^{\log_b a} = n^{\log_2 5}$ and $f(n)=n^2 \log^2 n$.

There are different cases depending on how the above functions compare, but I am only going to discuss the one that is relevant to you (you can find more on Wikipedia).

In your case $f(n) = O(n^{\log_b a - c})$ for some constant $c>0$.
To see this pick, e.g., $c=0.1$ and substitute to obtain:
$n^2 \log^2 n = O(n^{\log_2 5 -0.1})$, which is true since $\log_2 5 - 0.1 > 2$.

The master theorem then tells you that $T(n) = \Theta(n^{\log_b a})$, which in your case is $T(n) = \Theta(n^{\log_2 5})$.


Converting Regular expression to DFA by building syntax tree There is a way to convert regular expression to DFA (deterministic finite automata)
which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition technique to build DFA for that particular regular expression. But this case only works when operators in the regular expression are only . (Dot), * (star), | (or). I just want to know if the operators in the regular expression are like ?, [], - and etc. Then can i convert regular expression to DFA just like above way?

Thanks in advance.

No, using complementation yields an exponential blow-up in the size of the DFA.


Maximum number of vertices in undirected graph I'm studying about time complexity of Kruskal's algorithm.

But there are two opinions to express time complexity as $O(|E|\lg|E|), O(|E|\lg|V|)$.

I know $O(|E|\lg|E|)$ is occurred from sorting by non-decreasing order of vertices.

But I don't understand of $O(|E|\lg|V|)$. This answer explains by $|E|\le|V|^2$, however from my knowledge, maximum number of vertices in undirected graph is $|E|\le\frac{|V|(|V|-1)}{2}$.

What is right time complexity for Kruskal's algorithm?

Kruskal's algorithm is only applied to connected graphs. These have at least $|V|-1$ edges. On the other hand, the complete graph has $\binom{|V|}{2}$ edges, and so
$$
|V|-1 \leq |E| \leq \binom{|V|}{2}.
$$
The left-hand side is $\Omega(|V|)$ and the right-hand side is $O(|V|^2)$. Therefore $\log |E| = \Theta(\log |V|)$. For this reason, the two quoted running times $O(|E| \log |E|)$ and $O(|E| \log |V|)$ are completely identical — on connected graphs, an algorithm has running time $O(|E| \log |E|)$ iff it has running time $O(|E| \log |V|)$.


Are recursively enumerable languages closed under shuffle? For languages $L_1, L_2$ over some alphabet $\Sigma$, we define

$$ \textit{Shuffle}(L_1, L_2) =  \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \wedge b_1, \ldots , b_n \in L2 \setminus \{ \varepsilon\}\}$$

I think that RE are closed under shuffle, I tried to use the multitape TM model with 3 tapes, one for the input, one for the $a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \}$, and the last one for $b_1, \ldots , b_n \in L_2 \setminus \{ \varepsilon \}$, but the problem is that $a_1, \ldots , a_n, b_1, . . . , b_n$ are words from the languages,not symbols, so we do not know when $a_1$ ends and $b_1$ begins,
any suggestions for proving closure under shuffle ?

Hint: A language is recursively enumerable if and only if it can be recognised by a nondeterministic Turing machine. Use this fact to build a nondeterministic recogniser for $\textsf{shuffle}(L_1,L_2)$ from the deterministic recognisers for $L_1$ and $L_2$. What is it, that one most use nondeterminism to guess?


What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone I encountered a question to give an example of a set $A$ that is not decidable as $A$, but which becomes decidable if it is concatenated with itself, i.e. $AA$.

In case a set $A$ is decidable, then it is easy to see that $AA$ is also decidable, since a $TM$ that decides $A$ can be modified to also recognize $AA$... But I am having a hard time to look for examples given its converse.

You can pick your favourite undecidable language $L$ and build $A$ in this way:

$A = \{ 1 \} \cup \{ 2n \} \cup \{ 2n + 1 \mid n \in L \}$

$A$ contains $1$ and all even numbers, but it also contains ... (I let you try to complete the proof)

Note that I assume that $AA = \{ xy \mid x, y \in A\}$; because if you define $AA=\{ xx\mid x \in A\}$ then it doesn't exist an undecidable language $A$ such that $AA$ is decidable (again I let you try to prove it :-).


Finding sequence of pairs with second element of previous pair matching first element of next pair I am interested in efficient ways of doing certain problem.

I have list of $n$ pairs, where $n$ is usually a few houndred thousands and each pair's element is an integer (let's assume it is integer from $0$ to $10000$) and I am trying to find a sequence such that it start and ends at chosen integer (we can assume it is eg. $0$) and second element of previous pair matches first element of next pair. So as an example, if we have set of pairs $\{(0,1), (1,3), (3, 2) (3,0)\}$ the valid sequence would be eg. $(0,1), (1,3), (3, 0)$. If there is a few answers then I can find arbitrary one. Moreover it is no certain  that my list of pairs actually has a solution. If it does not have solution, then the method should return no valid solutions.

I think that maybe some kind of dynamic programming could be useful here, but I don't really have an idea for something better than just checking all the options, which I am almost certain is quite bad. Do you have any interesting insight about this problem?

The integers of your problem form nodes, the pairs form directed edges. Then you can use Tarjan's strongly connected components algorithm to find the groups of nodes that form a cycle.


Identifying system events affecting timing behavior of an application Q: What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job?

My question is purely in the context of Worst Case Execution Time (WCET) analysis.

I have gathered a short list of events, which I think are the contributors to WCET of an application, by utilizing some knowledge about computer-architecture:

A wrong branch prediction
Cache misses
Pipleline stalls
Fetch related delays
. . .

I would like to enrich this list both in breadth and length. So any addition to the list of such events or the details of how any particular event causes a delay is most welcomed.

P.S. If my question if not well formulated, please do help me to improve.

You forgot the most obvious factor: the input of the program. The time taken by a program heavily depends on the input unless it does not have any input or  the input comes from a small fixed set.

Other factors can be classified into two classes: 1) Internal factors and 2) External factors.

Internal factors:
1) Input
2) Waiting for I/O
3) Waiting for System resources like memory/semaphores etc.
4) How effectively memory is cached in CPU (may be different for different runs, what you have termed as cache misses.)
5) Disruptions in instruction pipeline
6) Interactive events
7) If the process needs to swap in/out some pages to swap area
8) If the process uses other hardware such as graphics card/audio/network
9) Hardware interrupts from graphics card/audio/network
10) Clock interrupts
11) Scheduler running
12) If the process is multi-threaded, then delays because of thread switching
13) If the process is multi-core and you need to share data between core, delay depends on the architecture of the CPU

External factors:
1) Multiprocessing (the biggest culprit)
2) Priority of the process
3) Context switching
4) Operating System preemptions
5) Hardware errors and service interruptions (of course)
6) Communication with other processes
7) Communication with other processes in other machies
8) Input that is not readily available, (it is available as a stream)

We need to have a good guess of running time of a process for majority of scheduling algorithms and for real-time systems. But a perfect calculation is simply impossible in real cases. The usual practice is to run the process for typical  (or typically worse) case input many times, make a guess and then over estimate it. This is done even in real-time system, if I understand correctly. In quite a few real-time systems the running process quite arbitrarily demands a guarantee of what it thinks is the over-estimated time it will take to finish the computation.


How do you marginalize in graphical model elimination? I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In equation (3.10), we see that
$$m_5(x_2,x_3) = \sum_{x_5}p(x_5|x_3)p(\bar{x}_6|x_2,x_5)$$

where the $x_i$ are random variables and $\bar{x}_i$ indicates a fixed/realized value of $x_i$.

Given that all $x_i$ are discrete random variables (as is the case in chapter 3), both $p(x_5|x_3)$ and $p(\bar{x}_6|x_2,x_5)$ are represented by two-dimensional matrices. And since $m_5$ is a function of as-yet unrealized variables $x_2$ and $x_3$, it is also a two-dimensional matrix.

How then do we perform the multiplication and the summation above?

I'm realizing now that it's just regular matrix multiplication.

For the case above, let $p(x_5|x_3)$ and $p(\bar{x_6}|x_2,x_5)$ be represented by $r\!\times\!s$ and $s\!\times\! t$ matrices, respectively, where $x_5$ can take on $s$ different values. Then, for each element $m_{ij}$ of $m_5$, we have that

$$m_{ij}=\sum_{k=1}^s p_{ik}(x_5|x_3)p_{kj}(\bar{x_6}|x_2,x_5)$$

where $1\leq i \leq r$ and $1 \leq j \leq t$.

This is matrix multiplication. Also, intuitively, the dimensions will always work out, since each factor in the product will always be a function of the variable we're summing over.

I think the notation is what was tripping me up. I usually don't see matrix multiplication written explicitly as a sum of products.


Asymptotic runtime for querying an interval tree Suppose that we have an array of size n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges [0], [1], [2], [3], ... , [n], and merging two of them together we end up having the root node holding the range [0, n]. For example we have the following interval tree for an array of size 6.

The total amount of nodes is O(n).

I'm trying to understand what's the maximum posible  root - internal node paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of log n but I can't see why, which is the reason why I'm asking this question.

For example in the picture above, for the query [1, 4] we will do the following visits:

[0,5] => [0,2] => [0,1] => [1] => [0,1] => [0,2] => [2] => [0,2] => [0,5] => [3,5] => [3,4] => [3,5] = > [0,5] => end

We have to travel from the root to some other internal node 3 times in total.

Now let's see a different example:

If our query is [1, 8] we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.

So I can't understand why querying in an interval tree is O(log n).

How can you formally prove that querying is indeed O(log n), ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of log n?

Querying an interval tree is $O(\log n + m)$, where $n$ is the size of the tree and $m$ is the size of the output. This explains your confusion. Note that there is a trivial $\Omega(m)$ lower bound.

Unfortunately I couldn't find an online proof of this bound, and since there are many variants of interval trees and many different queries, it's best if you tried to prove it yourself for your type of interval tree and query.


Consequence of NP=coNP to some hierarchy problems If $NP=coNP$ does it hold that $P/Poly=PH/Poly$ and/or $NP\subseteq P/Poly$ and/or $VNP=VP$?

What can we legitimately say if $NP=coNP$?

To the best of my knowledge, no such implications are known.


There is equivalence in an NP-hardness proof or not? I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$.

My question is: Should I verify both direction ($\Leftrightarrow$) or only one direction ($\Rightarrow$)? More precisely, which one to show from these two:

Solve $P_1\;\Leftrightarrow$ solve  $P_2$
Solve $P_1\;\Rightarrow$ solve  $P_2$

You only need to show that solving $P_1$ allows you to solve $P_2$ (and, hence, every other problem in NP).

$P_1$ might not be in NP so it's not necessarily the case that solving $P_2$ allows you to solve $P_1$.  On the other hand, if $P_1$ is in NP, then you already know that solving $P_2$ allows you to solve $P_1$, by definition of NP-completeness.


Comparison between Aho-Corasick algorithm and Rabin-Karp algorithm I am working on string searching algorithms that support multiple pattern search.  I found two algorithms that seem like the strongest candidates  in terms of running time, namely Aho-Corasick and Rabin-Karp. However, I could not find any comprehensive comparison between the two algorithms. Which algorithm is more efficient? Also, which one is more suitable for parallel computing and multiple patterns search? Finally, which one requires less hardware resources?

For AC algorithm, the searching phase takes $O(n+m)$ time, while it is $O(nm)$ for RK. However, the running time for RK is $O(n+m)$ which makes it similar to AC. My tentative conclusion is that RK seems practically better as it does not need as much memory as AC. Is that correct?

Asymptotic running time analysis is not likely to be the best tool to pick between these two algorithms: asymptotic analysis ignores constant factors, and the constant factors will be critical here.  The two algorithms have basically the same asymptotic running time, so asymptotic analysis probably isn't very helpful to choose between them.

Instead, the right way pick between the two algorithms is through experimental analysis.  Identify a representative workload, and then benchmark the performance of both algorithms on your workload, on the kinds of machines you intend to use in practice.

Incidentally, it sounds like you might have a slight confusion about the asymptotic running time of Rabin-Karp.  On the one hand you say that Rabin-Karp has $O(nm)$ running time, but then in the next sentence you say Rabin-Karp has $O(n+m)$ running time.  Perhaps you are confused by the difference between expected (average-case) vs worst-case running time.

Since Rabin-Karp is randomized, expected (average-case) running time is the appropriate metric to use to predict real-world performance in practice.  In particular, here the average is taken over the random choice of hash function.  It's specifically not an average taken over the choice of strings.  Even for the worst possible string and pattern, the average running time will still be $O(n+m)$.  With a suitable hash function, the probability that the running time is longer than $c\cdot(n+m)$ is exponentially small in $c$.  To put it another way (and being slightly informal), there's only an exponentially small chance that Rabin-Karp takes longer than $O(n+m)$ time.  We already have to accept exponentially small chances of bad things happen -- for instance, there's a tiny but non-zero chance of a cosmic ray causing a bit-flip in your memory that causes the program to loop forever.  So, worrying about this exponentially small chance makes no sense.

From an engineering point of view, Rabin-Karp's running time is $O(n+m)$ [or it might as well be].  Ignore the $O(nm)$ stuff; that's not really relevant to practice.


Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$? I am trying to find the worst-case complexity of the following algorithm. The input to the algorithm is a list of positive integers $a_1,\ldots,a_n$ and a bound $C$.

$S\gets$ empty set
$k\gets0$
for $i\gets1$ to $n$ do

add $i$ to $S$
$k\gets k+a_i$
if $k>C$

$j\gets\arg\max_{i\in S}a_i$
$k\gets k - a_j$
remove $j$ from $S$

In the worst-case, at each iteration $i$, we go to the if condition and calculate the max. So, if the max operation requires $\Theta(n)$, then the worst-case complexity is $\Theta(n^2)$. As suggested in the comments, $\Theta(n)$ is not the best possible.

Here, I use an array to represent $S$. I can use a heap instead as a data structure to find the max in $\Theta(\lg n)$. So, the worst-case complexity is $\Theta(n\lg n)$. Am I right?

EDIT: I found this article https://cstheory.stackexchange.com/questions/18119/finding-smallest-k-elements-in-array-in-ok which finds the $k$ smallest elements in $O(k)$ time. My algorithm computes the $|S|$ smallest elements. Hence, it can be done in $O(|S|)$ time. But the $|S|$ is not given apriori. This is another issue now. Any help?

You need a data structure that supports the following three operations efficiently:

insert an element into the set
delete an element from the set
find the largest element in the set

There are multiple such data structures.  One reasonable choice is a balanced binary search tree, where all three operations can be implemented in $O(\log n)$ time.


Is O((n^2)*log(n)) greater than O(n^(2.5))? I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?

In order to compare 2 complexities just calculate a limit of their ratios as below:

$\displaystyle\begin{align*}
 \lim_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}}
   &= \lim_{n\to\infty}\frac{log(n)}{\sqrt{n}}
    = \lim_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}}
    = \lim_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\
    &\underset{\left| k = \sqrt{n} \right|}{=}
      \ \ \lim_{k\to\infty}\frac{2log{(k)}}{k}
    = 2\lim_{k\to\infty}\frac{log{(k)}}{k} \\
    &\leq 2\lim_{k\to\infty}\frac{ln{(k)}}{k} \\
    &\overset{\ast}{=} 2\lim_{k\to\infty}\frac{(ln{(k))'}}{k'}
    = 2\lim_{k\to\infty}\frac{\frac{1}{k}}{1}
    = 2\lim_{k\to\infty}\frac{1}{k} \\
   &= 0
\end{align*}$

We use L'Hôpital's rule to simplify calculating a limit for $\frac{\ln(k)}{k}$ at *.

As you can see, $O(n^2\times\log(n))$ is lower than the other.


Why is backpatching needed during intermediate code generation? In compiler design, control-flow statements are translated to sequences of three-address-code (3AC) instructions a lot of which are jump statements. A 3AC instruction of the jumping type  could be an unconditional jump in the form of a goto statement with a target label as its argument, such as

  goto L1

or it may be a conditional jump in the form of an if statement, as in

  if a < b goto L1

Now when the compiler generates a 3AC jump instruction, the target label is available to it in the form of an inherited attribute ( which I assume is a pointer to an object/structure and so we could think of it as a pointer to a variable ).

Now, the labels passed to say, an if-else statement as inherited attributes would also be then attached to certain target instructions after the if-else construct that used those labels has been translated.

Suppose, a label L1 has been used a lot of times before in constructs that have now been  translated. Now suppose that label has to be attached to say a target assignment statement (the next instruction to be emitted) whose index is in the array of instructions is 137 (because there are 137 3AC instructions already stored in the quadruples array). Then at this point of time the variable L1 would get the value 137 and so all the earlier uses of L1 would also now get the value of L1 (because the variable pointed to by them now gets a value).

And so in this way we have translated control-flow statements in one pass and there is no need for backpatching to reduce the number of passes further.

I don’t understand why what I just wrote wouldn’t work and without backpatching two passes would be required to attach labels to their correct instructions.

Suppose you encounter a jump instruction "goto L1" before encountering the label L1 itself. The solution you propose (as far as I understand) is to reserve a location M1 in memory at which L1 will be stored, and to translate "goto L1" into an instruction of the form "jump to the address stored at address M1". Later on, upon reaching L1, you update location M1 with the address of L1.

This is a form of "runtime backpatching", in which the processor itself is doing the backpatching when running the code. Accessing memory tends to be slow, and so it is much better to hardcode addresses, shifting the effort from runtime to compile time. This is where backpatching comes in. When encountering "goto L1", the compiler will note that the address is missing, and will fill it in later, when the address of L1 is known.


Merge Sort Confusion - Initial Phase Missing? Below is the solution to a merge sort exercise - "Use a merge sort to sort the list". I'm confused because I thought that there needed to be an initial phase of breaking the list in to sub-lists, yet here only the "reconstruction" phase is shown.

Am I missing something, or is there a problem with the given solution please?

What is pictured is often called "bottom up mergesort", which is contrast to the "normal" mergesort, which you could call "top down merge sort".

You can find them contrasted in this article from Algorithms:

  Bottom-up mergesort. Even though we are thinking in terms of merging together two large subarrays, the fact is that most merges are merging together tiny subarrays. Another way to implement mergesort is to organize the merges so that we do all the merges of tiny arrays on one pass, then do a second pass to merge those arrays in pairs, and so forth, continuing until we do a merge that encompasses the whole array. This method requires even less code than the standard recursive implementation. We start by doing a pass of 1-by-1 merges (considering individual items as subarrays of size 1), then a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth.

We don't need to use recursive calls to decide how to break down the array. Rather, it's implicit which elements can be grouped with which elements by simply grouping them into powers of two.
This version of merge sort can be more easily written without recursion, which removes some overhead. It's also seems more amenable to various optimizations, such as SIMD or other vectorized operations, loop unrolling, etc.


Maximal majoritarian program under incomplete voting I have conducted two surveys on French political preferences. As half of each sample (of ~1000 persons) gave a satisfactory margin error, I have randomly displayed (or not) several questions. Now, I have an incomplete dataset of the preferences of the sample over many political propositions (I can provide it if needed). For the sake of simplicity, let us assume that for each proposition of reform, either the respondent agrees for a change (True), or not (False), either the question was not asked to him-her (NA).

I am looking for a political program (i.e. a set of propositions) which gathers a majority of adhesion: I call this a majoritarian program. For a program to be majoritarian, we need that a majority of the respondents agree jointly with all the propositions of the set. As the dataset is incomplete, we need to check that any subset of propositions in the program gathers a majority (i.e. gathers more True than False). Indeed, it could be that only 5 respondents have voted to all the propositions in the program, by chance all favorably; then, we could still not deduce that this program is majoritarian because one of its proposition could have failed to obtain a majority itself.
Finally, I am looking for the maximal majoritarian program, i.e. the largest one (in terms of number of propositions).

Does anyone have an idea on how to solve exactly this computational problem? Any insight on the question is welcome, including broader reflection on optimizing over the subsets of a big set.

So far, three methods have come to my mind to solve this problem:

Brute force
I have optimized an exact algorithm (which I can provide). With my (rather small) dataset (a hundred propositions), it works if I restrict the number of propositions I analyze to 47, but it is way too computationally demanding if I try to analyze all propositions. Indeed, the number of potential programs of size k grows exponentially: it is $2^k$.
Completion of data I haven't try this because I don't know the theory of imputing missing data. If such an imputation proves always reliable, then the problem may be solved. Indeed, a friend have shown me a way to reduce my problem to linear optimization as long as the dataset is complete.
Machine learning By defining appropriate an weight on each answer, that depends on the examined program, we can train a neural network to find the best ordering of propositions so as to form our program with the adequate number of highest-ranked propositions. (The gain function values individual adhesion to the program as well as its size.) However, this method is just an heuristic for the problem, and its solution is simply a proxy for the real answer. Indeed, the necessary check of the potentially maximal program may take too long a time (as we need to examine each subset of propositions in the program). Nonetheless, I will implement this method soon.

We can formalize this problem as follows.  Let the propositions be numbered $1,2,\dots,n$.  We have a function $f$ that, given a subset $S \subseteq \{1,2,\dots,n\}$ of propositions, returns true or false according to whether every proposition in $S$ has majority support among the survey respondents who saw every proposition in $S$.  Define $S \subseteq \{1,2,\dots,n\}$ to be a majoritarian program if $f(T)$ is true for all $T \subseteq S$.  Now we want an algorithm that, given ability to invoke $f$, finds the largest majoritarian program $S \subseteq \{1,2,\dots,n\}$.

We will of course interpret $S$ as follows: for each $i \in S$, we take whichever side of proposition $i$ has majority support (when considered in isolation; among all survey respondents who saw $i$), and take the conjunction of all of those.  Given $S$ you can easily compute $f(S)$ from the survey responses.

Here is one natural but not necessarily optimal algorithm for this.  Basically, you grow subsets from the "bottom up".  In particular, the algorithm looks like this:

Try(S):
1. If S is not a majoritarian program, return
2. If S is larger than the largest so far, remember S as the largest so far.
3. For each i in 1+max(S) .. n:
4.     Try(S ∪ {i})

You start by invoking Try({}), and when it returns, the best subset so far is the largest majoritarian program possible.  This effectively takes small subsets and tries to grow them to become bigger, but if they don't get majority support, the search is pruned and it stops trying to grow that set.

The running time could be exponential.  If you get lucky, you could hope that it runs more efficiently than that, though I don't know if you'll be lucky.

As a heuristic, you could sort the propositions by order of polarization, from most unanimous to most controversial.  That might speed up the search, or allow you to cut off the search after a certain time limit and take the best you've seen so far (with no guarantee that it is optimal, but the hope that it might be close).


Understanding Hamiltonian Path, NP vs Co-NP I am having difficulty understanding the distinction between NP and Co-NP.

According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a directed graph with a Hamiltonian path from s to t}, there exists a nondeterministic Turing Machine M that can decide this problem in polynomial time. I understood this to mean that for some input (G,s,t), M accepts if G has a Hamiltonian Path from s to t, and M rejects if G does not have a Hamiltonian Path from s to t, both in polynomial time.

However, the book also says that !HAMPATH =  { (G,s,t) | G is a directed graph with no Hamiltonian path from s to t} is in Co-NP, so it is not known to be in NP.

Why couldn't the same NTM for HAMPATH be used to decide !HAMPATH, except that it returns the opposite state?

A nondeterministic Turing machine is perhaps more clearly viewed as a Turing machine with two inputs: one is the actual input, in your case $\langle G,s,t \rangle$, and the other a polynomial size "witness", in your case a purported Hamiltonian path $p$. The machine checks, in polynomial time, that $p$ is indeed a Hamiltonian path from $s$ to $t$ in $G$, and if so, accepts; otherwise it rejects.

In what sense does this machine $M$ nondeterministically accept $\mathsf{HAMPATH}$?

If $\langle G,s,t \rangle \in \mathsf{HAMPATH}$ then there exists a witness $p$ such that $M(\langle G,s,t \rangle,p)$ accepts.
If $\langle G,s,t \rangle \notin \mathsf{HAMPATH}$ then $M(\langle G,s,t \rangle,p)$ rejects for all values of $p$.

Now consider the machine $!M$ which accepts when $M$ rejects and rejects when $M$ accepts.

If $\langle G,s,t \rangle \in \mathsf{!HAMPATH}$ then $!M(\langle G,s,t \rangle,p)$ accepts for all values of $p$.
If $\langle G,s,t \rangle \notin \mathsf{!HAMPATH}$ then there exists a witness $p$ such that $!M(\langle G,s,t \rangle,p)$ rejects.

As you can see, $!M$ doesn't have the same promises regarding $\mathsf{!HAMPATH}$ that $M$ has regarding $\mathsf{HAMPATH}$.