Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial? I was working through a textbook (Probability & Computing by Michael Mitzenmacher & Eli Upfal) and am not able to understand the following:

  Let $F(x)$ be given as a product
  $F(x) = \prod_{i=0}^{n} (x - a_i)$. Transforming $F(x)$ to
  its canonical form by consecutively multiplying the $i$th monomial with the product of
  the first $i-1$ monomials requires $\Theta(n^2)$ multiplications of coefficients.

A canonical form of a polynomial is $\sum_{i=0}^{n} c_i x_i$.

Why does this take $\Theta(n^2)$ time?

Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula:
$$
(x-c) \sum_{i=0}^d b_i x^i = (-cb_0) x^0 + \sum_{i=1}^d (b_{i-1}-cb_i)x^i + b_dx^d.
$$
If you compute $(x-a_1)\cdots(x-a_n)$ by successively multiplying the terms, i.e. by computing $P_1 = x-a_1$ and $P_{d+1} = P_d(x-a_{d+1})$ for $1 \leq d \leq n-1$, then you need this many multiplications:
$$
1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = \Theta(n^2).
$$


What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a I'm given the following python function:
def recurser(i, j):
    x = 0
    if j == 0:
        return 1
    if i == 0:
        return 1
    x += recurser(i, j - 1)
    x += recurser(i - 1, j)
    x += 1
    return x

And I'm Asked to find x for any i = j = n where n can be any positive integer. however the recursion can do the job but the question says no recursion is allowed so that I have to solve the following recursive function:

F(n,n) = F(n-1,n) + F(n, n-1) + 1
F(0,a) = 1 for every positive a
F(a, 0) = 1 for every positive a

Is there any solution for it?

Your function produces the sequence A109128, that is
$$
\mathit{recurser}(i,j) = 2\binom{i+j}{i} - 1.
$$
You can prove this by induction.
How I found out: I computed the first few values, and searched the OEIS.


Relative vertex capacity in max flow algorithm I am designing a network for a max flow and would appreciate the following feature:

Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let through the rest. Unlike vertex capacity, which says "let though at most N units of flow", I need to "let through everything but N units of flow".

An example:

Vertex of relative capacity 10
Incoming flow = 15. Outgoing flow will be 15 - 10 = 5.
Incoming flow = 10. Outgoing flow will be 10 - 10 = 0.
Incoming flow = 5. Outgoing flow will be 5 - 10, which is less than 0, so 0.

Does such a feature exist? And if yes, which edges/vertices/edge capacities do I need to add/remove/modify and how?

Thanks a lot!

For edge "consumptions" I believe the following approach should work: [I misread your question at first, but am leaving this part for the benefit of future people reading this]

Suppose you have some edge $u\rightarrow v$ with "consumption" $c$. Then you can model this by inserting a vertex $w$ in the middle to get $u\rightarrow w \rightarrow v$ and then add an edge $w\rightarrow t$ with capacity $c$, where $t$ is your sink. Then you have to ensure that your max-flow algorithm prioritizes pushing flow through $w\rightarrow t$ over $w\rightarrow v$. Thus this flow will be "consumed" as much as possible before going through the edge. I see two ways in which this can be done:

If your algorithm works by finding an augmenting path, make sure that this augmenting path goes through $w\rightarrow t$ rather than $w\rightarrow v$ if possible (i.e. if $w\rightarrow t$ is not saturated). Also make sure that this holds for the "reverse edges" (i.e prioritize taking flow away from $w\rightarrow v$ rather than $w\rightarrow t$). This should not be difficult to do, but depends on the exact implementation, and on your access to it.
Or you can use a max-flow min-cost algorithm and give a positive cost (say 1) to every edge except those of the $w\rightarrow t$ type (who receive a cost of 0).

Then to get the answer to your original problem just ignore all the $w\rightarrow t$ edges.

Now, for vertex $v$ with "consumptions" $c$ you can simply add an edge $v\rightarrow t$ with capacity $c$ and modify your algorithm in the same way.

If you don't care about the exact value of the flow through each edge but only the total max-flow, then you don't even need to change anything to the algorithm and can just use the returned value for the new graph as is.


Splitting a node in B+ tree with odd number of keys This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key".

To illustrate with an example.

For 5-way B+-tree,

(24, 25, 44, 79) is one of the leaf nodes with its root being (..,24,80,...)

(..,24,80,...)
      \
       \
        \
       (24, 25, 44, 79)

After Inserting 40.

The node (24, 25, 40, 44, 79) gets overloaded and is forced to split(considering the siblings are full as well).

In such a case, is there any advantage of splitting it as

(24, 25)   (40, 44, 79)
over (24, 25, 40)   (44, 79)

Is this split A

(..,24, 40, 80,...)
         | \
         |  \
         |   \
    (24, 25)  (40,44, 79)

better than this split B?

 (..,24, 44, 80,...)
          | \
          |  \
          |   \
 (24, 25, 40)  (44, 79)

If so, what makes A correct and B wrong, considering that both are satisfying the rules of the B+ tree.

I couldn't find any resource to back my argument that B is equally correct as A.

There is no advantage to choosing one over the other.

"Real" B+-tree implementations will often rebalance if they can, rather than splitting. When a node becomes overfull, if there is a sibling (whether to the left or the right) which isn't yet full, it's often better to balance the entries evenly between this node and its sibling. This saves an allocation.


O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force? I came up with this O(V+E) algorithm for calculating the chromatic number X(g) of a graph g represented by an adjacency list:

Initialize an array of integers "colors" with V elements being 1
Using two for loops go through each vertex and their adjacent nodes and for each of the adjacent node g[i][j] where j is adjacent to i, if j is not visited yet increment colors[g[i][j]] by 1.
After doing this the maximum integer in the array "colors" is the chromatic number of the graph g(if the algorithm works).

Here is my C++ code:

#include <bits/stdc++.h>
using namespace std;

struct graph {
    vector<vector<int>> adjL;
    vector<int> colours;
    vector<bool> vis;
};

int chrNUM(graph& G) {
    int num = 1;
    for(int i = 1; i < G.adjL.size(); i ++) {
        for(int j = 0; j < G.adjL[i].size(); j ++) {
            if(!G.vis[G.adjL[i][j]]) {
                G.colours[G.adjL[i][j]] ++;
                num = max(num, G.colours[G.adjL[i][j]]);
            }
        }
        G.vis[i] = true;
    }
    return num;
}

void initGET(graph& G, int N, int M) {
    cin >> N >> M;
    G.adjL.assign(N + 1, vector<int>(0));
    G.colours.assign(N + 1, 1);
    G.vis.assign(N + 1, false);
    for(int i = 0; i < M; i ++) {
        int u,v;
        cin >> u >> v;
        G.adjL[u].push_back(v);
        G.adjL[v].push_back(u);
    }
}

int main() {
    graph g;
    int n;  //number of vertices
    int m;  //number of edges
    initGET(g, n, m);
    cout << chrNUM(g);
}

I am wondering if there is a flaw? Maybe it works for certain graphs only? Maybe it gives X(g) for smaller graphs but a value higher than X(g) for larger graphs? I found it worked correctly for all the graphs I have tried (up to 20 vertices). I know this is an NP complete problem but I want some counterexamples for my algorithm if possible or an explanation as to why the method won't work. I have also got a recursive (DFS) solution which is a bit different but mostly similar to this. Any ideas?

Thanks in advance!

Your algorithm is known as greedy coloring. Wikipedia gives an example of a bipartite graph, the crown graph, where the greedy coloring can produce a coloring using $n/2$ colors (for the worst ordering). For random $G(n,1/2)$ graphs, the greedy coloring typically produces a coloring using double the optimal number of colors.


Existence of path under weight and value budgets Consider the following problem:

Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$ and end point $t$. We are also given two values $W,V$.
Decide whether there is a simple path from $s$ to $t$ with total weight at most $W$ and total value at most $V$.

How do I show that the problem is NP-hard by reduction from PARTITION?

Here is the idea of the reduction; I'll let you fill in the details.

We are given an instance of the partition problem, consisting of numbers $x_1,\ldots,x_n$ summing to $S$. We construct a (non-simple) graph on the vertex set $s = v_0,\ldots,v_n = t$. For $i=1,\ldots,n$, there are two edges from $v_{i-1}$ to $v_i$: one with weight $x_i$ and value $0$, and one with weight $0$ and value $x_i$. Our target weight and value are both $S/2$.

I'll let you figure out why this works, and convert it to a simple graph.


Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive? Say language $L$ is recursively enumerable, but not recursive.
Say $a$ and $b$ are symbols of the alphabet and $w$ a word.
Say we have the following language:

$L' = \{ aw | w \in L \} \cup \{ bw | w \notin L \}$

That is, $L'$ consists of the words that are in $L$ with an $a$ added at the beginning and the words that are not in $L$ with a $b$ at the beginning.

Is $L'$ not recursive? If we had a Turing Machine $TM$ for $L'$, $TM$ would halt for some positive cases ($w \in L$) but for other positive cases ($w \notin L$) it wouldn't halt. Is it therefore not recursive and recursively enumerable?

From what I understand:

Recursively enumerable: the Turing Machine will always halt if $w \in L$, otherwise it may or not halt.
Recursive: it always halts.
Recursively enumerable, but not recursive: it only halts if $w \in L$; otherwise it loops.
Not recursively enumerable: no Turing Machine exists.

So I don't know how to classify a language whose Turing Machine halts for some of its words.

EDIT: of course, now that I think about it, if the $TM$ doesn't halt and accept for some words then they didn't belong to the language in the first place.

There are two important misunderstandings in your question.

You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it.
If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ and rejects every input not in $L$ and, therefore, it halts on every input. It doesn't make sense to talk about a Turing machine deciding a language but not halting on some input, or not accepting some string that's in the language.

With that in mind, a language $L$ is:

Recursively enumerable if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$. It may loop or reject strings not in $L$.
Recursive if there is a Turing machine that accepts every string in $L$ and rejects every string not in $L$.
Recursively enumerable but not recursive if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$, but no TM that accepts everything in $L$ and rejects everything not in.  The "but..." part can be rephrased as "every Turing machine that accepts every string in $L$ must either also accept some string not in $L$ or must loop on some string not in $L$."
Not recursively enumerable if every Turing machine either accepts at least one string not in $L$, or loops or rejects at least one string in $L$.

For your specific language, I'm going to assume that $\Sigma=\{a,b\}$. If not, then the notation gets a little uglier but nothing fundamental changes.

If $L$ is RE but not recursive, then
$$L' =\{aw\mid w\in L\} \cup \{bw\mid w\notin L\}$$
is not RE. suppose it is RE and is accepted by some Turing machine $M$. Then we can decide if $w\in L$ by simulating $M(aw)$ and $M(bw)$ in parallel until one of them accepts.  If $M$ accepts $aw$, then $w\in L$; if it accepts $bw$, then $w\notin L$, and one of these two things must happen. This contradicts the assumption that $L$ is not recursive.


Preventing multiple threads from racing on a queue while not wastefully polling its size I have a queue with 50 ints in it, and I have 3 threads that want to race at the queue to print the values in it, with a 2 second delay before trying to get the next int.

The queue is not thread safe, and the semaphore protecting is is decoupled from the number of items inside the queue(the number of items in the queue are checked by calling .size() for the queue, but the lock is obtained by blocking on the semaphore until its owner unlocks it.

I am trying to understand how to prevent the three threads from accessing the queue at the same time, but at the same time not trying to access the queue if the queue is empty.

If the queue is empty, but unlocked, i will have a bunch of threads locking the queue, checking its size, and unlocking it, until something is added to the queue. This seems silly and wasteful; Is there a solution to this?

You wouldn't have just your queue and your semaphore. You would also have a global atomic variable where "false" means "I can guarantee one hundred percent that there is no data in the queue", and "true" means "There is probably some data in the queue, but maybe not".

Any code that modifies the queue would very carefully update the global variable. You need an operating system that makes it possible that code using locking can change such a variable as you need it.

For some interesting reading, google for "dispatch_once implementation".


How to prove that one problem belongs to class P? Is there any typical proving method when proving that one problem belongs to class P?
For example, when proving that
The problem of finding n to the kth power is the P problem. (Each multiplication can be done in unit time)
If you present an algorithm that can solve this problem with $O (\log n)$, can it be a proof?

Yes. In fact, any algorithm that runs in polynomial time counts. For examle, even an $O(n^8)$ would suffice! Therefore, there is no real need to optimize your algorithms to such extremes.


When is the big-O relation preserved under exponentiation? Suppose that $f, g$ are functions from the positive integers to the positive reals. Under what circumstances will $\log f(n)=O(\log g(n))$ imply $f(n)=O(g(n))$?

It's easy to see that this isn't always true: If $f(n)=3^n$ and $g(n)=2^n$ then we know that $3^n\notin O(2^n)$, but taking logs gives $\log3^n = n\log 3$ and $\log 2^n=n\log 2$ and it's obvious that $n\log 3=O(n\log 2)$.

The reason is also clear: If there exists a $c>0$ such that $\log f(n)\le c\,\log g(n)$ then all we can say is that $f(n)\le (g(n))^c$, which won't necessarily allow one to conclude $f(n)=O(g(n))$. When, though, can we correctly make the inference?

It is at least sufficient to have $\log f(n) \in o(\log g(n))$. This gives us that for sufficiently large $N$, we have $\log f(n) \leq \log g(n)$ for all $n > N$.

Hence immediately we have that for $c=1, n > N$, $f(n) \leq c\cdot g(n)$ and ergo $f(n) \in O(g(n))$.

This also suggests the condition that if we have that $\log f(n) \leq c\cdot \log (g(n))$ where $c \leq 1$ for sufficiently large $n$, then we also get $f(n) \in O(g(n))$.


CFG to Chomsky normal form I've read this part like 3-4 times and I'm not understanding what is going on.

Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The series of grammars presented illustrates the steps in the conversion. Rules show in bold have just been added. Rules shown in gray have just been removed.

Specific steps/instructions from the book

1.The original CFG G6 is shown on the left. The result of applying the first step to make a new start variable appears on the right.

S→ASA|aB         S0→S
A→B|S             S→ASA|aB
B→b|ε             A→B|S
                  B→b|ε

2.  Remove ε rules B→ε, shown on the left, and A→ε, shown on the right.

S0→S              S0→S
 S→ASA|aB|**a**        S→ASA|aB|a|**SA|AS|S** from?
 A→B|S|**ε**           A→B|S|ε
 B→b|**ε**             B→b

3a. Remove unit rules S→S, shown on the left, and S0→S, shown on the right.

S0→S                  S0→S|**ASA|aB|a|SA|AS**
 S→ASA|aB|a|SA|AS|S    S→ASA|aB|a|SA|AS
 A→B|S                 A→B|S
 B→b                   B→b

3b. Remove unit rules A→B and A→S

S0→ASA|aB|a|SA|AS     S0→ASA|aB|a|SA|AS
 S→ASA|aB|a|SA|AS      S→ASA|aB|a|SA|AS
 A→B|S|**b**           A→S|b|**ASA|aB|a|SA|AS**
 B→b                   B→b

4. Convert the remaining rules into the proper form by adding additional variables and rules. The final grammar in Chomsky normal form is equivalent to G6, which follows. (Actually the procedure given in Theorem 2.9 produces several variables Ui, along with several rules Ui→a. We simplified the resulting grammar by using a single variable U and U→a.)

S0→AA1|UB|a|SA|AS
 S→AA1|UB|a|SA|AS
 A→b|AA1|UB|a|SA|AS
A1→SA
 U→a
 B→b

I don't understand why they added the "bold" (** **) items. I also don't understand 4. Can someone please explain this to me. Thank you!

Removing $\epsilon$ transitions:

Consider the rule $B\to \epsilon$. We want to remove it. To do so, we look for occurrences of $B$ in the grammar, and whenever we see on (e.g. in $S\to aB$), we add the option of choosing $B\to \epsilon$. So the rule $S\to aB$ becomes $S\to a$. Similarly, $A\to B$ becomes $A\to \epsilon$ (which we will have to remove in the next step).

Since $A\to \epsilon$ was introduced when removing $B\to \epsilon$, we now add rules where $A$ appears. For example, the rule $S\to ASA$ becomes $S\to ASA|SA|AS|S$, according to the different options of using $A\to \epsilon$ after $S\to ASA$.

In step 4 - for every rule that yields more than a pair of variables (e.g. in this case $S\to ASA$) we split this into pairs as follows. Introduce a new variable $T$, we add the rules $S\to TA$ and $T\to AS$. Then, applying these forces us to actually have $S\to ASA$.


Decidability of "Is this regular expression prefix-free?" Say that string $x$ is a prefix of a string $y$ if there exists a string $z$ such that $xz = y$, and say that $x$ is a
proper prefix of $y$ if in addition $x \not= y$. A language is prefix-free if it doesn’t contain a proper
prefix of any of its members.
$$
\text{Prefix-FreeREX} = \{(R) \mid R \text{ is a regular expression and $L(R)$ is prefix-free}\}
$$
I was wondering about how to prove that Prefix-FreeREX is decidable. Also why does a similar approach fail to show that Prefix-FreeCFG is decidable?

Let $L$ be a language on the alphabet $A$. Then $L$ is prefix-free if $L \cap LA^+$ is empty. If $L$ is regular and given by a regular expression, then $L \cap LA^+$ is also regular (and one can effectively compute a regular expression for it). Now testing whether a given regular language is empty is decidable.
For context-free languages, the situation is different. Above proof does not work because the context-free languages are not closed against intersection. In fact, there is no algorithm to decide whether a given context-free grammar generates a prefix-free language.
Here is a proof of this claim [Luc Boasson, personal communication].
Let $(u_1, v_1), \dotsm, (u_n,v_n)$ be two finite lists of words of $A^*$ defining an instance of the Post Correspondence Problem (PCP) and let $X = \{x_1, \ldots, x_n\}$ be an alphabet of $n$ letters. Assume that $A$ and $X$ are disjoint and consider the homomorphims $u, v: X^* \to A^*$ defined by $u(x_i) = u_i$ and $v(x_i) = v_i$. Consider the languages
\begin{align}
 U &= \{x^Ru(x) \mid x \in X^+ \} \\
 V &= \{x^Rv(x) \mid x \in X^+ \}
\end{align}
Let $\sharp$ be a new letter. Then $U \cup V\sharp$ is a context-free language. It is prefix-free if and only if $U$ and $V$ are disjoint if and only if the Post Correspondence Problem has no solution. Thus deciding whether a given context-free language is prefix-free is undecidable.


Simplifying SOP: implementing OR with NAND I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such:

$a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$

In other words, we would need two NOT gates (which are basically NAND gates), and another NAND gate.

However, I want to practise Boolean algebra simplification. Using a truth table I have formed the Sum of Products:

$f(a,b)=ab' + a'b + ab$

I have worked down a number of paths unsuccessfully. I would appreciate if someone could either show the steps of simplification, or give me some guidance on the laws to use to achieve this simplification. If there are any notation mistakes I have made, please let me know :)

Unfortunately, you've gotten as far as you can get on this problem.

(Note: I'm going to write AND, OR, NOT, and NAND as $\wedge \vee \neg \uparrow$ respectively, since the standard sum/product/overbar notation tends to end up with lots of stacked bars, and I don't like those.)

You currently have:

$$(a \wedge \neg b) \vee (\neg a \wedge b) \vee (a \wedge b)$$

At this point, you could use NANDs to build all those NOTs and ANDs and ORs…but building an OR was your goal in the beginning! Normally, going into sum-of-products form is exactly the right next step to take, but here you're stuck, because you started with a simple sum in the first place.

It turns out the simplest way to build an OR gate out of NANDs is exactly what you were doing at first.

$$\neg a = a \uparrow a$$

$$a \vee b = \neg a \uparrow \neg b$$

$$a \vee b = (a \uparrow a) \uparrow (b \uparrow b)$$

To my knowledge, nobody's ever found a way to build OR with less than three NANDs, and I very much doubt it's possible (though I wouldn't know how to prove that).


Decision vs Optimisation Problem in P If a decision problem is in P, is the associated optimization problem then also efficiently solvable?
I always thought that this is the case but according to Wikipedia page on Decision Problems the complexity of a decision and function problem might differ and to me a function problem was always a special case of an optimization problem, hence I was under the impression that if the decision problem is efficiently decidable the same applies to the corresponding optimization problem.

Let us consider a generic optimization problem:

Maximize $f(x)$ subject to the constraint $x \in \mathcal{D}$.

The corresponding decision version is

Given $\mathcal{D}$ and $T$, is there $x \in \mathcal{D}$ such that $f(x) \geq T$?

In most cases, the range of $f(x)$ is at most exponential in the description length of $\mathcal{D}$, and so the optimization problem reduces to the decision version via binary search. For example, if $0 \leq f(x) \leq n$, then we first ask whether there is a solution with $f(x) \geq n/2$; depending on the answer, we ask whether there is a solution with $f(x) \geq n/4$ (if the answer was negative) or with $f(x) \geq 3n/4$ (if the answer was positive); and so on.
Conversely, if we can solve the optimization problem then we can easily answer the decision problem, and so the two are essentially equivalent.


Minimizing inversions in an array with a single swap This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased:

  Given a permutation $a$ of integers from $1$ to $N$, how can I
  minimize the number of inversions by a single swap of any two
  integers?

  An inversion is a pair of indices $(i, j)$ such that $i < j$ but
  $a[i] > a[j]$.

I think that this can be achieved by swapping the numbers which have been shifted the most from their position. That is:

If $n_{inv}(a)$ is the number of inversions in a permutation $a$, and $swap_a(i, j)$ is the permutation obtained by swapping the integers at $i$, $j$, then:

$$
\underset{i, j}{argmin} \{n_{inv}(swap_a(i, j))\} =
\underset{i}{argmax} (a[i] -i), \underset{j}{argmin} (a[j] -  j)
$$

In pseudo-code:

leftmost = [-1, -1]        # The first value is the displacement
rightmost = [1, -1]        # The second the index where it occurred
for i in 1..n
    d = N[i] - i           # N being the array of numbers
    if d > leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d < rightmost[0]
        rightmost[0] = d
        rightmost[1] = i
return leftmost[1], rightmost[1]

The thing is, I have no idea why this is correct, or even if it is. How can I prove that this works?
Or determine the conditions for which it will work?

I have been struggling to understand how I reached this idea and feel that proving it would help me.

To be clear, I am not looking for a solution to the minimizing inversions problem, but only a way to prove that the solution I came up with is correct or incorrect.

Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i < j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i < k < j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i < a_j$ and $a_i > a_j$.

If $a_i < a_j$ then the pair $(i,j)$ becomes an inversion, and for every $i < k < j$, there are three possible cases:

$a_k < a_i < a_j$: number of inversions stays the same.
$a_i < a_j < a_k$: number of inversions stays the same.
$a_i < a_k < a_j$: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a_i,a_{i+1}$.

In contrast, if $a_j < a_i$ then the number of inversions decreases by one plus twice the number of indices $i < k < j$ such that $a_j < a_k < a_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a_j < a_i$ and the number of indices $i < k < j$ satisfying $a_j < a_k < a_i$ is maximal. You take it from here.


Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set? I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set.

I was told that the potential function:

$$ \Phi(x_1, ... , x_n ) = \sum_i log(w[x_i])$$

would work (where $w[x_i]$ is the weight of the subtree rooted at $x_i$, i.e. the number of elements in the subtree rooted at $x_i$).

I was given the following argument but it doesn't quite make sense to me:

I can sort of see why a -1 would come in since $\frac{1}{2} = 2^{-1} \implies log(\frac{1}{2}) = -1$, but re-arranging the equation (and taking logs) gives:

$$ log(w[c]) - log(w[p]) \leq 1$$

which reverses the sign the wrong way. Plus, if you write down the details of the potential function change, things change inside the logs, which makes it tricky to analyze...

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of $\sqrt{n}$ finds on the bottom nodes in each list will take time $\Theta(n)$, which means that the bound of $O(m \log n)$ (here, $O(\sqrt{n} \log n)$) is incorrect. A more correct bound would be to claim that the runtime will be $O(m \log n + n)$, which accounts for the "startup cost" of doing some initially-expensive compresses.

Here's one way that you can see the runtime is $O(m \log n + n)$ without using the potential argument you mentioned in your question. Let's begin with an initial disjoint-set forest. We're going to color all the edges in the forest one of three colors: gold, blue, or red. The colors are given as follows:

Any edge from a node u to a node v, where the number of nodes in u's subtree is less than half the number of nodes in v's subtree, is colored blue.
Every other edge is red.

To understand blue and red edges, imagine that you're not going from some node up to the root, but from the root down to some node. Every time you follow a blue path, the number of nodes in the current subtree decreases by at least a factor of two. This means that if there are $n$ total nodes in the graph, any path from a node up to its root can have at most $O(\log n)$ blue edges on it, since the number of nodes in the subtree keeps dropping geometrically. That leaves red edges as everything else.

So now imagine that you start doing a find operation beginning at some node. Look at the path that you'll take up to the root. You're going to go through some number of red edges, some number of blue edges, and some number of gold edges. We don't know a priori how many red edges you'll walk through, but we can guarantee that you'll go through at most one gold edge (remember, they have to be directly pointing to the root) and at most $O(\log n)$ blue edges. This means that the cost of performing a find operation is $O(r + \log n)$, where $r$ is the total number of red edges that you pass through.

The reason that this coloring scheme is interesting is that something magic happens when you do a find. Remember, every node on the path is going to have its parent pointer changed to be the ultimate representative in the partition. Imagine that you use the potential function that you described in the question. Every time you follow a red edge (other than one that already points to the root directly), you change the node so that it points directly to the root. This means that its old parent must lose at least half the weight in its tree, which means that $\log[w_i]$ decreases by at least one. No node's weight increases, since we only move edges from descendants up to the root. This means that the drop in potential is at least $r - 1$, where $r$ is the number of red edges followed. Therefore, even though the runtime of any individual find is $O(r + \log n)$, the amortized cost of a single find is $O(\log n)$.

Now, this analysis completely ignores the costs of doing a union operation, and that's important. The good news is that it's not a problem. A union does two finds - each of which cost amortized $O(\log n)$ - and then links one tree to another. This increases the size of the root of that tree by the number of nodes in the linked tree, which is at most $n$. This means that the potential increases by at most $\log n$, so the amortized cost is $O(\log n)$.


Complexity of linear programming I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial?

Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?

There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia.


Finding largest sum of $k$ elements below threshold I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of indices is maximal under the constraint of being less than a given element $x$. My approach for this is the naive $O(n^k)$ algorithm, but this would take a lot of time for large $n$.

This is isn't a homework problem.

You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.

For simplicity, let me assume that $k$ is even.

The idea is as follows:

Partition $A$ into two parts.
For each part, compute a sorted list of sums of $k/2$ elements from the part.
For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in the second part which conforms to the constraints.

As stated, there are several problems with the idea:

It assumes that the optimal solution contains exactly $k/2$ summands out of each part.
It runs in time $O(n^{k/2} \log n)$.
It uses $O(n^{k/2})$ memory.

To handle the first difficulty, there are several options. We could just repeat the entire algorithm $\sqrt{k}$ times. Alternatively, there might be deterministic ways to achieve the same goal. Here is a hybrid solution:

Randomly partition $A$ into $k^3$ parts $P_1,\ldots,P_{k^3}$ (anything substantially larger than $k^2$ would work). With high probability, each element of the optimal solution is in its own part.
Consider all possible partitions of $A$ into two parts of the form $P_1,\ldots,P_i$ and $P_{i+1},\ldots,P_{k^3}$. One of these will contain exactly $k/2$ elements of the optimal solution.

To handle the second difficulty, we need to be slightly more careful in implementation. Using merging (the familiar subroutine from mergesort), it should be possible to compute the $k/2$-sums of each part in $O(n^{k/2})$. The final step can be implemented in $O(n^{k/2})$ using a classic two-pointer technique (the first pointer goes up on the first half, the second one goes down on the second half).

There are tricks to reduce the memory required from $O(n^{k/2})$ to $O(n^{k/4})$: further divide each part into two sub-parts. You can easily go over all $k/2$-sums in the first part by considering all pairs of $k/4$-sums in its subparts. Binary search on the second part can then be implemented using the two-pointer technique.


Research in Graph Theory versus Graph Algorithms I have a very generic question to ask.  It is related to
research.  I'm interested in Graph theory.  I have done a course in
it.  I have done some topics related to both graph theory as a point
of view of doing it as a mathematics student and also studied some
graph algorithms.  I'm going for research internship in graph theory.
But there is some glitch in my mind that I'm unable to fix about my
real interest in graphs because of lack of proper distinctive ideas
about the real difference in doing research in graph algorithm or
doing graph theory as a mathematics student.  I would like to know the following things:

What is the real difference in doing graph theory as a mathematics student or doing graph algorithms? Do both of them have some real difference?
Can someone tell me some good source for getting research papers on graph theory and graph algorithms.
Is it good to start doing graphs as a mathematics student?

I don't know if it is a right place to put forward such kind of problems.
Please let me know if it doesn't fit here.

Question 1

I would say that the two areas are definitely not identical, however there is a huge overlap. Partly it depends on where you draw some very fuzzy lines. Let's start with:

Graph Theory is about the properties of graphs as mathematical objects
Graph Algorithms as an area of research is about solving computational problems that are represented using graphs.

Of course graph theory is unsurprisingly very useful in developing graph algorithms, and graph algorithms can answer questions in graph theory. Indeed, as you have obviously noticed, many problems in Graph Theory can be cast as computational problems, and answered by giving an algorithm (in a sense this is an aspect of the Curry-Howard Correspondence), so especially at the introductory level, there is little more than the style of presentation that separates them.

Just to make things even more confusing, most researchers in one field have at least some interest and experience in the other, but there are a couple of points where we can draw certain lines of distinction:

Graph theory (as a field) will happily deal with infinite graphs, which are not so interesting from an algorithmic perspective.
Graph theorists will tend to be more interested in existential statements ("the chromatic number of a class of graphs is at most blah"), whereas graph algorithms people will be looking for the best algorithm to solve a problem ("how do we compute the actual value of the chromatic number as quickly as possible?").
Graph algorithms includes/overlaps with the application and tailoring of graph algorithms to solve problems that aren't really about graphs (e.g. developing a good algorithm to cluster protein interaction networks), which a graph theorist would be uninterested in (at least as a graph theorist).

Question 2

If you have access to university subscriptions or similar (this is no way exhaustive):

Journal of Graph Theory
SIAM Journal on Discrete Mathematics
Journal of Combinatorial Theory: Series B
Discrete Applied Mathematics
Journal of Graph Algorithms and Applications

To muddy things further, many of these include examples of both pure graph theory and graph algorithms.

A couple of lists for further exploration:

A list of graph theory journals
For unrelated reasons, John Lamp has several lists that have interesting journals in there, but you'll have to do some keyword searching: Pure Mathematics, Applied Mathematics, Theoretical Computer Science

There is the arXiv preprint server, which has preprint versions of research papers, but again, you'll have to spend a small amount of time to explore and find something you want (it's more set up for finding a paper you already know is there).

Question 3

This question cannot really be answered objectively. It depends entirely on things that you have no way of knowing (i.e. the future), and I have no way of knowing (how good the people are at your university, what opportunities you will gain or lose by taking that internship).

If you want my subjective general opinion, I would say yes. Graph theory is an important part of mathematics and computer science (I personally contend they're not different things anyway), and versatility and breadth of knowledge are important characteristics of a good researcher, even if you later decide you have no intention of being a graph theorist - it's not going to stop you from being able to do complex analysis or topology.

Again, this is about whether an arbitrary student would benefit from doing work in graphs (algorithms or theory) - you personally may be in a particular situation where it would not be beneficial, and we can't answer that here. For example, if taking the internship means that you don't get to do the internship in Category Theory that is actually the thing you want to do, then this could set you back. Early in a research career it is difficult to escape a particular path, without going back to step one. Later on, it's easier to transition, but for better or worse there's period effectively like apprenticeship where you can't easily jump to any job you're interested in, but that's a question for Academia.SE.


Optimal solution algorithm for K-center problems I'm wondering if there is an algorithm that calculates the optimal solution of a typical k-center problem (more than one dimension). I've tried, but without success, to find this algorithm. Does such an algorithm exist?

An optimal solution for the k-center problem can be found by an exhaustive search over the solution space, and by picking the best solution. The problem is NP-Hard for more than 2 dimensions, and moreover any $\delta$-approximation for $\delta < 2$ is NP-hard.


Least common ancestor relative to an arbitrary vertex as root Consider following problem:

  Given an undirected tree answer following type of queries. (No. of
  queries and vertices can be as high as $10^5$)

  $\text{LCA}(r, u, v)$: Find the Lowest Common Ancestor of vertices $u$ and $v$ assuming vertex $r$ as the root.

Now, in solution it's given that answer will always be one this: $r, u, v, \text{LCA}(r, u), \text{LCA}(r, v), \text{LCA}(u, v).$

Where $\text{LCA}(u,v)$ denotes Lowest Common Ancestor of vertices $u$ and $v$ if we assume vertex number $1$ as the root.

So I'm looking for a proof for claim made in a solution.

Let us consider several possibilities:

The root is $r$. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
The root is $u$, and $r,v$ are contained in different branches. In this case, $\mathrm{LCA}(r,u,v) = u$.
The root is $u$, and $r,v$ are contained in the same branch. If $r$ is an ancestor of $v$, then $\mathrm{LCA}(r,u,v) = r$. If $v$ is an ancestor of $r$, then $\mathrm{LCA}(r,u,v) = v$. Otherwise, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
The root is none of $r,u,v$, and all of $r,u,v$ belong to different branches. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v) = 1$.
The root is none of $r,u,v$, the vertex $r$ belongs to one branch, the vertices $u,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(u,v)$.
The root is none of $r,u,v$, the vertex $u$ belongs to one branch, the vertices $r,v$ to another. In this case, $\mathrm{LCA}(r,u,v) = \mathrm{LCA}(r,v)$.
The root is none of $r,u,v$, and all of $r,u,v$ belong to a single branch, say rooted by a child $s$ of $r$. We apply induction to the subtree rooted at $s$.

To convince yourself of the various claims, I suggest drawing some diagrams, and using the characterization of $\mathrm{LCA}(r,u,v)$ as the vertex on the unique path from $u$ to $v$ which is closest to $r$.


Permute the subintervals of an interval partition to most closely align with a model partition You are given two things: A fixed initial 'model' partition of an interval, e.g.

I------I---I-----I-------I----...

where each - or I represents an element in a discrete time series and the Is are the partition boundaries.  This can also be represented as a sequence of subinterval lengths, i.e. 7, 4, 6, 8, ...

Then, you're given a new set of subinterval lengths; and the task is to arrange these in such a way as to get as many coincident Is as possible.  Or equivalently, you are given a new partition on an interval of the same length (though, critically, the new partition may have greater or fewer elements) and the task is to shuffle the subintervals around to maximize alignment.  So if the model was

I------I---I-----I-------I----I

and you are given 2, 11, 5, 12, i.e.

I-I----------I----I-----------I

then the solution would be 11, 2, 12, 5,

I----------I-I-----------I----I
           *             *

achieving alignment at 2 locations (marked with an asterisk, compare to model).

There is an additional constraint: The locations of the aligned subintervals must be distributed approximately randomly throughout the length of the solution.  The simplest means of getting a partition with at least some alignment to the model would be to build the new partition segment by segment, drawing without replacement from the collection of test segments, aligning where possible.  But this would strongly bias the occurrences of alignment towards the beginning of the time series, and is therefore not allowed.  There is of course also the brute force O(n!) enumeration but my series are little too long for that.

Naturally a solution that finds the optimal permutation would be great, but one that is efficient and gets a permutation with a substantial fraction of the possible alignment would also be good.  My current version is a variation on the 'simple' algorithm derived above, except only drawing from a small subcollection of subintervals so as to avoid bias.  I know it can be improved upon!

You can use integer linear programming (ILP) to solve this.  In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find $k+1$ alignment points (including the two endpoints).  Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment.

Call a "block" the (non-empty) sequence of consecutive intervals between two alignment points.  The left and right endpoint of the interval are automatically alignment points.  If there are $k+1$ distinct alignment points (including these two endpoints), there will be $k$ blocks.

Let $\ell_1,\ell_2,\dots,\ell_n$ be the set of lengths of the first set of subintervals, and $\ell^*_1,\ell^*_2,\dots,\ell^*_{n^*}$ be the lengths of the second set of subintervals.  These are constants provided as input.

Introduce zero-or-one unknowns $x_{i,j}$ (for $1\le i\le n$ and $1 \le j \le k$), with the intent that $x_{i,j}=1$ means that the $i$th subinterval (of length $\ell_i$) from the first partition will end up in the $j$th block.  Similarly, introduce zero-or-one unknowns $x^*_{i,j}$, with the intent that $x^*_{i,j}$ means that the $i$th subinterval (of length $\ell^*_i$) from the second partition will end up in the $j$th block.

Now we get a set of linear inequalities, as follows:

$\sum_i \ell_i x_{i,j} = \sum_i \ell^*_i x^*_{i,j}$, for all $j$.  (This is two ways of representing the length of the $j$th block.)
$\sum_j x_{i,j} = 1$ (each subinterval from the first partition ends up in exactly one block) and $\sum_j x^*_{i,j} = 1$.
$x_{i,j} = 1 \land x_{i+1,j}=0 \implies x_{i+1,j+1} = 1$ (i.e., each block starts where the previous one ended).   This can be expressed as the ILP constraint $x_{i,j} - x_{i+1,j} \le x_{i+1,j+1}$.  Similarly for the $x^*$'s.
$x_{i,j} = 1 \land x_{i'',j} = 1 \land i < i' < i'' \implies x_{i',j}=1$ (i.e., the subintervals in a block are consecutive).  This can be expressed as the ILP constraint $x_{i,j} + x_{i'',j} - 1 \le x_{i',j}$ for all $i,i',i''$ with $i < i' < i''$.  Similarly for the $x^*$'s.
$x_{1,1} = 1$, $x^*_{1,1} = 1$, $x_{n,k}=1$, $x^*_{n^*,k}=1$.

Of course, in the worst case ILP can take exponential time, but ILP solvers are pretty good and often perform well on many real-world problems, so it is probably worth a try.

(You could also try coding this up using a SAT solver, but you'd need to implement arithmetic, so a front-end like STP would probably be a better bet than a plain SAT solver.)


Is it possible to shorten this Finite Automata Transition Graph? I designed this transition graph, seen below. The alphabet contains {a, b, c}, and the goal of this machine is to accept any strings (no limitations on length of string) that ends with a letter that is already in that string.

Example: abba, aaa, bb, ababababacc, cabc are accepted.
Example: abc, bccba, a, b, c, cccab, are a rejected.

Is there a shorter/simpler way to design this finite automata than this transition graph?

Each string that is input to an automaton takes you to some state. So you can see each state an encoding some kind of information about the inputs the machine has seen if it's in that state. For example, an automaton might have a state that corresponds to "all words with an even number of $b$s."

Why am I telling you this? Because, when you're designing an automaton, it's often helpful to think about what information you need to store about the input to accept the language you want. In this case, you want to accept all words whose last letter has already appeared in the string. So, the information you need to decide the language is "What letters have I seen so far?"  If you encode that information in some states of the automaton, it should be easy to add the right transitions to accept the language you want.


What are the (efficient) algorithms to cluster squares into groups using a threshold such that the closest squares form groups? I have a set of rectangles that needed to be grouped based on their locations.
(All the rectangles follow the same orientation.) Two rectangles would be in the same group if the distance between them is less than a certain (constant) threshold.

The obvious algorithm will find all groups in ${O(n^2)}$ time. What I am looking for is an efficient algorithm that can perform better.

Store the centers of the rectangles in a data structure that supports efficient nearest-neighbor queries, such as a quadtree.  Now for each rectangle $R$, you can determine whether there exist any other rectangles within the prescribed distance, and if so, list them all.  Then you can merge all such rectangles into the same group by using a union-find data structure to keep track of which rectangles are in which group.  Each rectangle starts out in its own group, and when you find two rectangles that are close to each other (within the prescribed distance), you use the Union operation to merge their two groups.

A number of optimizations are possible.  Here is one simple optimization.  For each internal node in the quadtree, keep track of a single bit that indicates whether all points (rectangles) in the subtree under that node are known to be in the same group.  When enumerating neighbors to $R$, if that bit is set, then you don't need to enumerate all points under  that node; it's enough to find any one point (rectangle) under that node, and merge it into the same group as $R$.


Are there any programming languages which support user defined control structures? For instance, the user would define a for each loop in their code as having a structure something like:

foreach([variable1] : [variable2]){
    [statements]
}

(when [ ] are placeholders) and then the pieces would be used like this:

for(i = 0; i < variable2.length; i++){
    variable1 = variable2[i];
    statements
}

and then in the rest of the program, the user could use a for each loop with that format:

total = 0;
foreach(num : numbers){
   total += num;
}

I hope that example makes sense. To be clear, I am saying that in this hypothetical language a for each loop does not exist, but the user can define one which will, for then on, work exactly the same as any other structure. Are there any languages which allow this?

There are two aspects to your question:

Can we arrange a convenient syntax to express one control structure in terms of another?
Can we actually define new control flow mechanisms.

For example, suppose we have a language which only has the if statements without else:

if A then B

Can we express if A then B else C somehow? Yes, like this:

a = A ;
if a then B ;
if not a then C

It would be even better if we could package up the above piece of code into convenient syntax so that we could write just if A then B else C.

Sometimes we can define new control structures using existing ones. For instance, a while loop

while A do B

can be replaced with a call to a recursive function (under some technical assumptions):

function whileLoop():
   if A then (B ; whileLoop ())

whileLoop();

This sort of transformation is a bit more involved because it requires that for each while loop we define a new recursive function. If we were to automate the process, we would have to worry about many details (how to invent unique names of generated functions, do the functions have access to the local variables, etc.) than when we're performing just a straightforward syntactic translation of one variant of loop to another.

On the other hand, there are control mechanism which simply are not expressible in a language, unless already supported. One such example would be continuations. You can't get these in C, for example, but they exist in Scheme.

Your question is about syntax: can we make a syntactic transformation that replaces one piece of syntax with another piece of syntax. Languages usually deal with this sort of thing through a macro mechanism or syntax extensions. Here are some examples:

C has macros which will get you some of the way
Scheme has a more elaborate macro system which gets you a lot further
Racket, a descendant of Scheme, has an elaborate multi-stage computation system which allows essentially arbitrary syntax extensions
OCaml has the camplp5 syntax extension tool which allows pretty much arbitrary syntax extensions
Template Haskell is an extension of Haskell which allows meta-level transformations of syntax.

I am sure there are many other languages with similar facilities that I am not familiar with.


Time complexity of the immanant Let $A$ be an $n \times n$ matrix over some field $\mathbb{F}$. The determinant
$$ \det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}$$
can be evaluated in $O(n^3)$ field operations (via Gaussian elimination, say).
Note that this is much better than naive evaluation of the polynomial above, which has $n!$ terms.
On the other hand, the similar-looking permanent
$$ \operatorname{perm}(A) = \sum_{\sigma \in S_n} A_{1 \sigma(1)} \cdots A_{n \sigma(n)} $$
has no known polynomial-time evaluation algorithm: it is $\#P$-complete even for matrices containing only zeros and ones over $\mathbb{F} = \mathbb{Q}$. The other significant difference is that the determinant is invariant under an arbitrary change of basis ($A \mapsto P A P^{-1}$ for any invertible $P$), whereas the immanant is only invariant under a permutation of basis elements ($A \mapsto P A P^{-1}$ for $P$ a permutation matrix).
There are a finite number of functions which interpolate between the determinant and the permanent. For any irreducible character $\chi \colon S_n \to \mathbb{Z}$, we can define the immanant of the matrix $A$ to be
$$ \operatorname{Imm}_\chi(A) = \sum_{\sigma \in S_n} \chi(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}. $$
Then the permanent corresponds to the trivial character $\chi(\sigma) = 1$, and the determinant corresponds to the sign character $\chi(\sigma) = (-1)^k$ where $k$ is the number of inversions in $\sigma$.

Question: What is known about the complexity of computing immanants? At what point do they switch over from being polynomial time to being NP-hard?

In order for this question to make sense, we need to know about what kinds of immanants arise for a given $n$, or in other words what the irreducible characters of $S_n$ are. It turns out that the irreducible characters of $S_n$ are in bijection with integer partitions of $n$, or in other words decreasing lists of positive integers adding to $n$. These are often also represented by their Young diagrams, for example the integer partitions of $n = 5$ are shown below:

In the standard way of associating partitions to characters, the one-row partition $(n)$ corresponds to the trivial representation (and to the permanent), while the one-column partition $(1, \ldots, 1)$ corresponds to the sign representation (and to the determinant).
There are some natural partial orders that can be put on the set of partitions of $n$, which place the one-row partition at one end of the order and the one-column partition at the other, such as the dominance order. We could perhaps fantasise that as you move up this order from the "easy" determinant to the "hard" permanent, you come across some kind of barrier where computation starts getting harder and harder.

The state of affairs as of 2013 is described in Mertens and Moore, The Complexity of the Ferminonants and Immanants of Constant Width. Let $\lambda$ be the partition corresponding to $\chi$.

Immanants are easy if the leftmost column of $\lambda$ contains $n - O(1)$ boxes (Barvinok; Bürgisser).
Immanants are hard if $\lambda_i - \lambda_{i+1} = \Omega(n^\delta)$ (Brylinsky and Brylinsky, improving on results of Hartmann and Bürgisser which applied only to hooks and rectangles).
The problem of computing the $\lambda$-immanant given $\lambda$ is hard even if $\lambda$ is restricted to have width 2, and promised to have at least $n^\delta$ boxes in the second column (Mertens and Moore; de Rugy-Altherre).

The paper of de Rugy-Altherre is subsequent to Mertens–Moore.


Scientifically acceptable method for comparing performance of algorithms I am comparing several different algorithms for navigation applications. Since I may possibly be publishing a paper comparing the performance of these algorithms with each other, I was wondering the best way to go about measuring performance.

As far as I know, there are two ways to compare performance: writing the code in a compiled language like C and measuring the time of execution, or counting the number of FLOPS. However, I am aware that different processors have different capabilities which results in different execution times on different platforms.

These algorithms will be implemented on low-cost embedded systems (the main application is satellites, where low power is key).

So in summary: what is the scientifically accepted way of comparing the performance of different algorithms?

There is no single answer.  The answer depends upon the specific situation you are in.  It's not that there is a single scientifically accepted way of evaluating performance.  Instead, a paper should be driven by the claims you want to make.  First, figure out what claims you want to make about your scheme.  Then, figure out what evidence is needed to support those claims.

For instance, perhaps you would like to claim that your scheme is fast enough to deploy on low-cost embedded systems.  Well, then your next step is to make that claim more precise: what counts as fast enough? how do you know? what specific systems do you mean?  Then, you can evaluate performance on those systems, by that metric, and assess whether it is fast enough.

Or maybe you would like to claim that your scheme is faster than previously published approaches.  Your next step would be to make that more precise: which previous approaches are you going to compare to?  on what platform?  with what workload?  And then you'd evaluate on those platforms.

The right metric to use for performance will depend on your specific situation.  For some, maybe it is wall-clock time.  For others, maybe it is energy consumption (power).  For still others, maybe it is guaranteed low-latency, or memory usage, or something else entirely.

In short: there is no single scientifically accepted method.  Instead, think of science as (a) being precise about what claims you are making, and then (b) providing appropriate evidence to support those claims.  What constitutes "appropriate evidence" will depend upon your specific situation.  You can often look to other publications in your field to see what evaluation method they used, as initially guidance, but ultimately this is a matter of critical thinking: evaluating evidence in a logical, careful, thoughtful manner.


Difficulty in updating the balance factor of nodes in AVL tree In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees.
I have understood how the rotation is working and have no trouble with that. The problem I am having is determining the final balance factor of nodes in the tree.
In the first case before rotation, the balance of factor of x will be +2 or -2(that's why we are performing the rotation). But what about the balance factor of y? Why is it always taken as +1 or -1 before rotation? Why it can't be 0(the height of T3 can be equal to the height of z)? What will we the balance factor of z before rotation? It can be anything right? In short, what will be the balance factor of nodes with the question mark before and after the rotation?

This is the code I am trying to write:

Node insert(Node node, int key)
{
    if(node == NULL)
        node = new Node(key);

    else if (key <= node->key)
    {
        node->balance++;
        node->left = insert(node->left, key);
    }

    else if (key > node->key)
    {
        node->balance--;
        node->right = insert(node->right, key);
    }

    // Right Tree Heavy
    if (node->balance == -2)
    {
        /*Do the required rotation and update the balance factor*/
    }

    // Left Tree Heavy
    if (node->balance == 2)
    {
         /*Do the required rotation and update the balance factor*/
    }

    return node;
}

Edit: Initially the tree was satisfying all the properties of avl tree. Then a new node was added to either T1 or T2 which made the tree unbalanced at node x. Can anyone explain all the cases of balance factor of nodes before and after the rotation.

The reason that the number of possible values for the balance factors at $y$ and $z$ is limited is not only the fact that the tree has been AVL before insertion, but also the precise location where the rotation is performed in an ex-AVL tree.

Rebalancing is only needed at the lowest position where the balance becomes $\pm 2$ where below had balance factors $0$. All those $0$ balance factors have been changed into $\pm 1$ depending on the side where the key has been entered. The short reason for this is that when a node has originally balance factor $0$ and one of its subtrees becomes taller after insertion, not only the balance factor becomes $\pm 1$ but also the total length of the tree at that node becomes one taller, so we have to consider its father.

If that father has balance $0$ it will become $\pm 1$, the tree is taller, and we proceed    up again [diagram b)].
If the father has balance $\pm 1$ we may happen to improve the
balance to $0$, and we stop, no rotation needed  [diagram a)].
If the balance becomes $\pm 2$ we rebalance at that point using the
proper rotation. After rotation the tree at that point has the same
height as originally, so we do not have to consider balance factors higher up
in the tree.  [diagram c)]

So the issue here is to determine the context where the rotation takes place. This is determined by following the insertion process bottom-up, from the leaf where the key was added.

The precise type of rotation (single/double, left/right) is determined by the insertion path that was followed below the node where we rotate.

In the single rotation case we have left-left insertion from $x$ so $y=-1$ (longer to the left, my balance factors are opposite to yours). The value at $z$ is not important, its complete subtree is copied during the single rotation at $x$.
In the double rotation case we have left-right insertion from $x$ so again $y=-1$. At $z$ we might have any value: $\pm 1$ depending on whether the key went left/right at $z$, but even $0$ in the special case $z$ itself was inserted!


Is there such a problem as b-Matching with different b values? Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a weight function $w(e), e \in E$ is maximized.
What if we have different $b$? e.g., $b(v)=5, \forall v \in R$ and $b(v)=2, \forall v \in L$. How do you call the problem? Is is constrained matching, or k-cardinality assignment, or what? I need to find some literature for it.
Thanks!

I'm not sure if it's a standard problem, but it seems this problem is described in Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.
(the other closest things I found are https://en.wikipedia.org/wiki/Generalized_assignment_problem and https://link.springer.com/content/pdf/10.1007/BF02190106.pdf, but they are talking about one-to-many assignments).
Anyway, you can solve it using maximum flow. For $b=1$ (usual matching) you can check these slides, namely this picture:

I.e. we create auxiliary vertices $s$ and $t$, create edges $(s, u)$ for all $u$ in the left part and $(v, t)$ for all $v$ in the right part. All edges have capacity one. By solving maximum flow on this graph, you'll find maximum matching (Note: you have to find an integral solution, i.e. where flow through each edge is either 1 or 0, but standard maximum flow algorithms will do that).
For $b>1$ the graph is the same. The difference is that all edges $(s,u)$ have capacity $b_L$ and $(v,t)$ have capacity $b_R$.
If your edges have weights, then you can negate edge weights and solve min-cost max-flow on this graph.


What are system clock and CPU clock; and what are their functions? While reading a book, I came across a paragraph given below:

  In order to synchronize all of a computer’s operations, a system clock—a small quartz
  crystal located on the motherboard—is used. The system clock sends out a signal on a regular basis to all other computer components.

And another paragraph:

  Many personal computers today have system clocks that run at 200 MHz, and all devices (such as CPUs) that are synchronized with these system clocks run at either the system clock speed or at a multiple of or a fraction of the system clock speed.

Can anyone kindly tell:

What is the function of the system clock? And what is meant by “synchronize” in the first paragraph?
Is there any difference between “system clock” and “CPU clock”? If yes, then what is the function of the CPU clock?

The system clock is needed to synchronize all components on the motherboard, which means they all do their work only if the clock is high; never when it's low. And because the clock speed is set above the longest time any signal needs to propagate through any circuit on the board, this system is preventing signals from arriving before other signals are ready and thus keeps everything safe and synchronized. The CPU clock has the same purpose, but is only used on the chip itself. Because the CPU needs to perform more operations per time than the motherboard, the CPU clock is much higher. And because we don't want to have another oscillator (e.g. because they also would need to be synchronized), the CPU just takes the system clock and multiplies it by a number, which is either fixed or unlocked (in that case the user can change the multiplier in order to over- or underclock the CPU).


Solving the recurrence $T(n)=T(n−1)/T(n−2)$ How can I solve this?
I saw Solving the recurrence $T(n)=T(n-1)*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?


A special case for the subset sum problem If we wanted to see if any disjointed subset of a set $X = [w_1, ..., w_n]$ exists such as the sum of its elements equal exactly a given value $M$ (0-1 Knapsack problem) we could employ a DP solution or a simple greedy algorithm.

A simple implementation of which could be the following. Sort the set $X$ in non-decreasing order and try taking taking the values of $X_{sorted}$ one by one only if said number is smaller than the difference of $M$ with the sum of the currently selected numbers. By the end of it we should be able to see if it is possible to form the number $M$ using a combination of that set. This will of course not work all the time.

My question is, how things would change if we knew that the numbers $w_1, w_2$ and so on are in fact guaranteed to be multiples of 2. Would then be another way to check if any given integer $M$ can be formed or not with a combination of those numbers?

Obviously, even numbers cannot add up to an odd $M$. Other than that, we could just set $v_i = w_i /2$ and $N = M/2$. Then finding a subset of $w_1, \dots w_n$ which adds up to $M$ would be the same as finding a subset of $v_1, \dots, v_n$ which adds up to $N$, where the latter is the unconstrained knapsack problem.


Does coNP-completeness imply NP-hardness? Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology is standard.

I am comfortable with the claim that if an NP-complete problem belonged to coNP, then NP=coNP. However, these lecture notes state that if an NP-hard problem belongs to coNP, then NP=coNP. This would then suggest that I cannot claim that my problem is NP-hard (or that I have proven coNP=NP, which I highly doubt).

Perhaps, there is something wrong with my thinking. My thought is that a coNP-complete problem is NP-hard because:

every problem in NP can be reduced to its complement, which will belong to coNP.
the complement problem in coNP reduces to my coNP-complete problem.
thus we have a reduction from every problem in NP to my coNP-complete, so my problem is NP-hard.

You claim that every problem in NP can be reduced to its complement, and this is true for Turing reductions, but (probably) not for many-one reductions. A many-one reduction from $L_1$ to $L_2$ is a polytime function $f$ such that for all $x$, $x \in L_1$ iff $f(x) \in L_2$.

If some problem $L$ in coNP were NP-hard, then for any language $M \in NP$ there would be a polytime function $f$ such that for all $x$, $x \in M$ iff $f(x) \in L$. Since $L$ is in coNP, this gives a coNP algorithm for $M$, showing that NP$\subseteq$coNP, and so NP$=$coNP. Most researchers don't expect this to be the case, and so problems in coNP are probably not NP-hard.

The reason we use Karp reductions rather than Turing reductions is so that we can distinguish between NP-hard and coNP-hard problems. See this answer for more details (Turing reductions are called Cook reductions in that answer).

Finally, coNP-hard and coNP-complete are both standard terminology, and you are free to use them.


Given an array $A$, find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$? I have an array $A$ of $n$ integers. I need to find all quadruples $(i,j,k,\ell)$ such that $i<j<k<\ell$ and $A[i]=A[k]$ and $A[j]=A[\ell]$. What is the best way to do this?

My attempt is an exhaustive search algorithm that works as follows:

Generate all quadruples $Q=\{(i,j,k,\ell): i<j<k<\ell\}$.
For each quadruple $(i,j,k,\ell)\in Q$, verify $A[i]=A[k]$ and $A[j]=A[\ell]$.

This algorithm requires $$O\left(\binom{n}{4}\right)=O(n^4),$$ steps in the worst case. Can we do better? (Is this problem known somewhere?)

EDIT: I was using greedy instead of exhaustive search as Yuval mentioned.

Consider the absolute worst case, where every element is equal to every other element. This means that the algorithm has to output $n(n-1)(n-2)(n-3) \in O(n^4)$ quadruples. So in the worst case we can't do better. But often for problems like this it's useful to also consider cases where we don't have to output as much.

So let's do better. If you sort the data in $O(n \log n)$ (making sure to store the original indices) you can then in an $O(n)$ step find all equivalence classes. Then you can output all quadruples by first iterating over all possible pairs of equivalence classes and then iterate over all possible combinations of elements from those two equivalence classes.

Those last two steps are in theory $O(n^4)$, but are a lot smaller when the equivalence classes get smaller.


Length Preserving One way function In the proof of existence of length preserving one way functions assuming the existence of one way functions, see

Length-preserving one-way functions

We need $p(n)$ to be a function which can not only be computed in polynomial time, but also, its inverse should be polynomial time computable. How do we ensure that ? $p(n)$ can be chosen to be monotonically increasing. But is that sufficient ?

$p(n)$ is just a polynomial that indicates the length of the output of the function $g$, as a function of the length of the input.  Imagine that it's something like $27n$ or $2n^2$, and then read through the proof and you'll see how it works.

I didn't see any requirement to compute an inverse of $p(\cdot)$ in that proof.  I'm not sure where you got that from.  But anyway, if you wanted to invert it, any such polynomial is monotonic and can be easily inverted, e.g., by using binary search or using Newton's method.


Union-Find link-by-rank preserve a root Suppose I have two union-find trees with roots $x$ and $y$ respectively. I want to join them in constant time (this is normally possible since I already "hold" the roots) but I need $x$ to be the root of the merged tree. I don't know what rank $x$ or $y$ have (or more precisely formulated I need this to work always - for any $x$ and $y$ I want the final tree to have $x$ as its root). Is that possible? I couldn't find a solution to this, but it's really not my day today :)

Unfortunately, that's not possible with the standard data structure for union-find (namely, with the union by rank method).

The data structure has invariants that in some cases require making $y$ be the root (namely, when $x$'s rank is smaller than $y$'s rank, you are required to make $y$ the root).  If you force $x$ to be the root in such a situation, then you destroy the invariants, which might make subsequent Find/Union operations slow.

It sounds like you are thinking that perhaps we can reorganize the inner structure of the tree under $x$ or the tree under $y$.  Unfortunately, it's not possible to do that in the standard Union-Find data structure.  The data structure doesn't have child pointers (doesn't have any way to get from $x$ to its children, or from $y$ to its children), so there is no way for a data structure to change the inner structure of the tree under $x$ or the tree under $y$.

So if you want to achieve this, you will probably need an entirely new data structure.  If so, you should probably ask a new question and specify your requirements in terms of the externally observable behavior of the API's, rather than in terms of the internal state of the data structure.


Automaton equivalent of the π calculus? If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing Machine, but with support for communication channels or signals of some type, but I'm not sure, and would appreciate some direction.

The question doesnt make too much sense because the $\pi$-calculus was proven Turing complete, or in other words equivalent to a Turing machine ever since its inception by Milner in 1992. There is a reference on Wikipedia.


How to calculate average waiting time for round robin cpu scheduling? I have tried to calculate average waiting time for the below details there are two answers I'm getting using two methods I'm not understanding which one is correct?

The time quantum is 2
This is the first method:

Process Id         Arrival Time        Burst Time
P0                      0                   5
P1                      1                   3
P2                      2                   1
P3                      3                   2
P4                      4                   3

This is the first gantt chart:

P0      P1      P2      P0      P2      P4      P1          P0          P4
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     8
P1                     8
P2                     2
P3                     4
P4                     7

  Average waiting time1: 29/5=5.8

And this is the second method:

This is the second gantt chart:

P0      P1      P2      P3      P4      P0      P1          P4          P0
0-2     2-4     4-5     5-7     7-9     9-11    11-12       12-13       13-14

Process Id         Waiting Time
P0                     9
P1                     8
P2                     2
P3                     2
P4                     6

  Average waiting time2: 27/5=5.4

The average waiting time would depend on the order in which the processes are scheduled. Your round-robin scheduler does not mention of an optimization scheme to minimize the waiting time. Both schedules listed out are correct and produce the respective waiting times.


Is this scheduling problem with arrival times, deadlines, and costs NP-hard? There are $n$ jobs where each job $i$ has an arrival time $r_i$, a deadline $d_i$ and a cost $c_i$. The problem is to find a scheduling time $t_i$ (where $r_i\leq t_i\leq d_i$) for each job $i$ in order to minimize $$\sum_i\max_{j\in S_i}(c_j),$$ where $S_i$ is the set of jobs scheduled at time $t_i$.

Can we solve this problem in polynomial-time or is it NP-hard?

For example, if all jobs can be scheduled at the same time $t$, then the objective will be $\max(c_1,c_2,\ldots,c_n)$. The issue is that all jobs cannot always be scheduled at the same time $t$ because of their arrival times and deadlines. If I schedule the jobs as they arrive, I may end up with the objective of $\sum_{i=1}^nc_i$, which is the largest possible. So, the problem is somehow how to partition the jobs into sets $S_i$ (where jobs in $S_i$ are scheduled at the same time) for which we obtain the minimum objective. As such, I am trying to reduce Partition to this scheduling problem but still did not find the right reduction. Do you have any hints?

The following observation enables a polynomial-time algorithm:

Whenever the time slot $t_i$ for a job $i$ has been chosen, it's optimal to assign the same time slot for all lower-cost jobs that overlap $t_i$, as doing so will incur zero additional cost.  Therefore, choosing the time slot for the most costly job "magnetises" all the jobs that can be assigned the same time slot, and partitions the remaining jobs into two sets: those whose intervals are completely to the left of this time slot, and those whose intervals are completely to the right.  The subproblems for these two sets of jobs can then be solved independently.

A general subproblem can be described by an interval $(a, b)$ and a maximum cost $c$: the jobs in this subproblem consist of all those jobs whose intervals fall within $(a, b)$ and which have cost at most $c$.  The optimal solution for a subproblem can be found by trying every possible time slot for the most costly job in the subproblem, and solving the corresponding 2 subproblems for each attempt.  A plain recursive strategy would take exponenential time, but there are only $O(n^3)$ distinct subproblems to solve: There are only $O(n)$ "basic intervals" (maximal intervals that do not cross the beginning or end of any job interval) to consider, so there are at most $O(n^2)$ possible intervals (blocks) of these, and $O(n)$ possible different job costs.  Thus dynamic programming can be applied.  It should be possible to test each of the $O(n)$ possible time slots available for the most costly job in $O(1)$ time each, excluding the time needed to solve subproblems, for $O(n^4)$ time and $O(n^3)$ space overall -- not fast, but certainly polynomial.


Locality-sensitive hashing random projection I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that will be used for the random projection. So, in LSH for Cosine Similarity, the define the hash function $h_i(\vec{v}) = 1$ only if $\vec{r_i} \cdot \vec{v} \geq 0$ and $h_i(\vec{v}) = 0$ only if $\vec{r_i} \cdot \vec{v} < 0$. There are a lot of places that mention that this dot product of $\vec{v}$ and $\vec{r_i}$ means which side of the line (assuming a 2D dimension for instance) the point in question $\vec{v}$ is (negative for one side and positive for the other side), just like in the image below:

However, to my understanding, what will give which side of the line where the point $\vec{v}$ is, is the dot product of the norm of the $\vec{r_i}$ (let's say that the norm is $\vec{n}$) and the vector $\vec{v}$, so the correct wouldn't be the equation $\vec{n_i} \cdot \vec{v}$ instead of $\vec{r_i} \cdot \vec{v}$ ?

No.  The statement you're reading is correct.  Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens.  The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).


How to generate the LR(0) finite state machine for a grammar Here is a context-free grammar with a single nonterminal symbol S and three terminal symbols +, *, and s:

S -> + S S | * S S| s

My purpose is to build the LR state machine for this grammar.  My attempt:

[State 0]      ->     [State 1]       ->       [State 2]
S -> . + S S   (+)    S -> + . S S    (*)      S -> * . S S
S -> . * S S          S -> . * S S             S -> . + S S //leads to loop
S -> .s               S -> .s

When I get to state 2, I see that an infinite loop begins to form. I think I am missing/misunderstanding part of the algorithm to form the machine. Can you ignore a production if it already exists somewhere else?

There is no loop, an item like $S\to \bullet{+}SS$ in your example might occur in several item sets of the LR automaton.  Let us continue the construction of state 2:

[State 2]
S -> * . S S
S -> . + S S
S -> . * S S
S -> . s

It has transitions to itself on "$*$", to state 1 on "$+$", to some state 3 with item set $\{S\to s\bullet\}$ on "$s$", and to yet another state on "$S$":

[State 4]                 [State 5]
S -> * S . S   --(S)-->   S -> * S S .
S -> . + S S
S -> . * S S
S -> . s

State 4 has again a transition to state 1 on "$+$", state 2 on "$*$", and state 3 on "$s$".  The construction is not complete yet, since you are missing some outgoing transitions from states 1 and 0, but hopefully you can finish it yourself.


Does SAT always have short analytic proofs? By analytic proof, I mean mainly resolution and also other valid syntactical manipulations of the set of clauses, old and new. So this is a search over problem space rather than solution space. The question is:

Is there a family of instances of SAT that doesn't have polynomial-size analytic proofs of their satisfiabilities?

If all families have short analytic proofs, then if we can find them in short time, that means P = NP. But even if there aren't always, there still may be other means to solve SAT in polynomial-time. So this is only one way to attack P vs. NP. But it's curious to know on its own.

It is known that proofs of the unsatisfiability of pigeonhole problems must be at least length $2^{n^\epsilon}$ when the resolution proof system is used.  $\epsilon$ depends on the difference between the number of pigeons and the number of holes, but $\epsilon > 0$ always.


Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$ Given a grid graph $G=(V,E)$ which has only two different integer costs/weights of 1 and 2. Find Minimum Spanning Tree in $O(|V|+|E|)$.
I tried the following:

Changing Kruskal using a counting Sort in $O(|E|)$. But can I say that this results in O(|E|+|V|)? Since Kruskal would normally be ${\displaystyle O(T_{sort}(|E|)+|E|\cdot \alpha (|V|))} =O(|E|)$ when $\alpha (|V|) \in O(1)$ Can this be stated for this case? I lack detailed understanding of inverse ackerman behaviour.
Other possibility changing Prim so that I use a priority queue which support del_min, decreaseKey and insert in $O(1)$. I thought about using two simple stacks or queues and only del_min from the one, which holds the 1 integers, but descreaseKey seems not efficient since I have to loop through the lists to find the elements. So maybe combine this with some kind so hash mapping to directly access each element in $O(1)$ for decreaseKey?

Both seem really close to the actual result, though I am struggling to see the right solution for this case.

Let $n=|V|$ and $m=|E|$.
Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning forest $F'$ of the graph obtained by identifying the edges of each tree in $F$ into a single vertex (where each edge in $F'$ actually represents an edge of $G$).
Some care is required to attain a running time of $O(n)$. The details are as follows.

Let $G_1$ be subgraph of $G$ induced by the edges of weight $1$.
Let $C_1, \dots, C_k$ be the connected components of $G_1$.
For each $C_i$, compute any a spanning tree $T_i = (V_i, E_i)$ of $C_i$.
This requires $O(m)=O(n)$ time in total.
For each edge $e=(u,v)$ of weight $2$ in $G$ let $i$ and $j$ be such that $u \in C_i$ and $v \in C_j$. Let $k(e) = (\min\{i,j\}, \max\{i,j\})$.
Sort the edges of $G$ in nondecresing order of $k(\cdot)$, keep at most one edge for each value of $k(\cdot)$. Let $S$ the resulting ordered set of edges.
Notice that $S$ can be found in time $O(m)=O(n)$ using radix-sort.
Create a graph $G_2$ with vertex set $\{1, \dots, k\}$ and edge set $\{ k(e) : e \in S \}$. For an edge $(i,j)$ in $G_2$ let $\ell(i,j)$ be and edge $e$ in $G$ such that $k(e) = (i,j)$.
This label $\ell(i,j)$ can be stored along with the edge $(i,j)$ itself, so that given $(i,j)$ we can find $\ell(i,j)$ in $O(1)$ time.
This step also requires $O(n)$ time.
Finally, compute any spanning tree $T' = (V', E')$ of $G_2$.
An MST of $G$ is the tree induced by the edges in $\left( \bigcup_{i=1}^k E_i \right) \cup \{ \ell(i,j) \mid (i,j) \in E'\}$.
Overall, the whole algorithm takes $O(n)$ time.
The same algorithm extends naturally to any constant number of distinct edge weights.
Here is a visualization of the algorithm on the graph you proposed in the comments. Blue edges has weight $1$, red edges have weight $2$. The connected components of $G_1$ are highlighted in gray (and each connected component will be represented by a vertex in $G_2$). In this particular example $S$ contains all red edges of $G$ since each red edge connects a different (unordered) pair of connected components in $G_1$.


Computing optimal assignments using little memory I have two lists where each item in the first list has a rating for each item in the second.  I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item can only be matched once.

For example, there are 150 movies available, 100 people, and each person has rated each movie between 0 and 100.  Once a movie is given to a person, it is no longer available for another person.

In this example, I'd like to find the scenario where the person/movie with the lowest rating is the best rating possible.  Then, the average of all ratings is the best possible. Ideally, no one person would be unhappy with their movie (data permitting).  There might be multiple optimal solutions, so I'd like to determine and rank the top 5 scenarios.

I plan to implement this in node.js and Javascript, so the memory footprint of data structure(s) is a factor.

What would be the optimal data structure and approach to solve something like this?

Your problem is closely related to the assignment problem, and can be solved efficiently using techniques derived from that literature.  I'll show how to solve it, by building up a solution step by step.

Maximizing the lowest rating

Here is how you could efficiently find the assignment that maximizes the lowest rating.  First, focus on the associated decision problem:

Input: movie ratings; an integer $t$
Goal: find an assignment where each person is assigned to a movie they rate at least $t$ or higher

This decision problem is an instance of bipartite matching, and can be solved using standard algorithms for it.  Namely, look for any assignment that assigns each person a movie that they related at least $t$.

Now, to find the assignment that maximizes the lowest rating, use binary search over $t$.

This doesn't solve your problem yet, because it doesn't take into account that you want to resolve ties by maximizing the average rating.

Resolving ties by maximizing the average rating

First, find the largest value $t$ such that there exists an assignment where everyone is assigned a movie they rate $\ge t$.  (See above for how to do it.)  Now if there are multiple such assignments, we want to find one of them where the average rating is maximized.

How do we do that?  Answer: use a standard algorithm for the Hungarian algorithm.

In more detail, we do several steps:

Delete any (person,movie) rating where the person has rated the movie something less than $t$.  It's not OK to assign that person that movie.
Now, you have an instance of the assignment problem, where each person has rated some of the movies with scores that are $t$ or larger.  You want to find a matching assignment) that maximizes the average of the scores of assigned movies.  Since every solution must assign 1 movie to each of the 100 people, the size of every assignment is the same, so maximizing the average is equivalent to maximizing the sum.  Maximizing the sum of the ratings is exactly the assignment problem.  Therefore, you can use any standard algorithm for solving the assignment problem (e.g., the Hungarian algorithm).

This will find an optimal solution: i.e., an assignment that maximizes the lowest rating, and that resolves ties by maximizing the average rating.

If you want to find the top-5 solutions, you can use an algorithm for enumerating solutions to the assignment problem in a streaming/output-sensitive fashion.  See, e.g., Algorithm for a list of best solutions to the Assignment problem and Does Ford-Fulkerson always produce the left-most min-cut.


Computing an Expression I am writing code to evaluate the following expression:
    $$ \frac{(a+b+c)!}{a! b! c!} $$
where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going
to be a floating point number. I could use a big number package, but the code
will run slowly. I am using 64-bit floating point numbers.

I claim by doing as much of the computation in integer (maybe 64 bit) I will minimize the floating point round off error. Therefore, I claim that if put the integers to be multiplied together in an array, cancel common denominators, and then do the final computation in floating point I will minimize round off error.

Do I have this right?

You don't need to use integers for any data. Just find the largest of three numbers x=max(a,b,c) and reduce both parts by x!. Then compute in doubles. For numbers as small as 500 both 32-bit ints and 32/64 bit doubles will be precise.

EDIT: Since 64-bit FP isn't enough to deal with 1500!, you can perform computations on (decimal) logarithms of multipliers.


How to Generate Control flow graph from a Petri net model? My research is mainly focused on generating test sequences automatically using Colored Petri net.CFG provides techniques for generating test sequences. But some papers says that, test sequence generation methods based on a control flow graph sometimes suffers from a feasibility problem (i.e. some paths in a CFG may not be feasible).So I need a technique to draw a Control flow graph from the Colored Petri net model, in a way that, when I will select paths from the control-flow graph it will contain only the feasible paths.Then I will generate test sequences from the CFG. Can anyone help me finding any technique please or give me any suggession??

Since you are interested in generating test sequences automatically using colored Petri nets, note that it's not clear that you need reduction to control flow graphs (and dealing with all the related issues). Some techniques were presented, that use various different methods to generate test sequences from Petri nets. Some examples include:

H. Watanabe and T. Kudoh, "Test suite generation methods for concurrent systems based on coloured Petri nets," Software Engineering Conference, 1995. Proceedings., 1995 Asia Pacific, Brisbane, Qld., 1995, pp. 242-251.

J. Desel, A. Oberweis, T. Zimmer and G. Zimmermann, "Validation of information system models: Petri nets and test case generation," Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., Orlando, FL, 1997, pp. 3401-3406 vol.4.

Xu, Dianxiang. "A tool for automated test code generation from high-level Petri nets." Applications and Theory of Petri Nets. Springer Berlin Heidelberg, 2011. 308-317.

On the other hand, since Petri nets and control flow graphs are not semantically equivalent in general (and capture different type of information), the translation between the two is usually done in some specific domain (and restrictions). (Although usually, control flow graphs can be transformed into equivalent Petri nets.). Some examples and discussions are given in:

De Jong, Gjalt G. "Data flow graphs: system specification with the most unrestricted semantics." Proceedings of the conference on European design automation. IEEE Computer Society Press, 1991.

The Design Of A General Method For Constructing Coupled Scientific Simulations, Matthew J. Sottile

Note that your question seems a bit too general. (Moreover, it also seems as an instance of XY, as noted by D.W.) Without more details, it seems hard to give a concrete and concise answer. Hopefully, given pointers can get you closer to your desired goal.


MST: Are all safe edges, light edges? Following are some definitions from CLRS:

  DEFINITIONS :
  1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
  2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
  3. A cut Respects a set A of edges if no edge in A crosses the cut.
  4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph.  For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$.  If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can be removed from $T$ and replaced with a lighter edge $f$, giving a tree $T-e+f$ with a smaller weight than $T$, contradicting the fact that $T$ is an MST.

As a concrete example, suppose $G$ is the path graph on vertex set $\{a,b,c\}$ and edge set $\{ab, bc\}$, with the edges $ab$ and $bc$ having weights  $1$ and $2$, respectively.  Then, edge $bc$ is not the lightest edge available, but it is a safe edge to add first and it is the lightest edge between $S$ and $V-S$ if we take $S = \{a,b\}$.


Why is $P \subseteq NP$? The Clay paper gives a short proof on this in page 2:
http://www.claymath.org/sites/default/files/pvsnp.pdf

However,

Where does it come from that these are inclusive sets and not separate? Or that $|P| ≤ |NP|$?

One definition of NP is "the set of languages accepted by non-deterministic Turing Machines in polynomial time."

There's a trivial transformation that lets us convert any deterministic Turing Machine into a non-deterministic one, which will have the exact same running time. Basically, you just take the same deterministic TM, rename it as non-deterministic, and don't use any non-determinism.

In short, any deterministic TM is also a non-deterministic TM (but the converse is not true).

So, suppose there's a language $L$. If we can accept $L$ in polynomial time with a deterministic TM, then we just make the trivial non-deterministic TM which runs identically, and we can now accept $L$ in polynomial time with a non-deterministic Turing Machine.

We know that $|P| = |NP|$ because both sets are infinite and countable. There are countably many Turing Machines, since each Turing Machine can be represented as an integer. There is at least one Turing Machine for each language in $NP$, and likewise, at least one Turing Machine for each language in $P$. Since both of these sets are infinite, they must be infinite countable.


what is the significance of the word "Sub-problems" in Greedy Method? With respect to Dynamic Programming we make a statement that :

  Greedy algorithm have a local choice of the sub-problems whereas
  Dynamic programming would solve the all sub-problems and then select
  one that would lead to an optimal solution.

Now in Dynamic Programming we have some problem with recursive nature which we solve by solving the sub-problems and then obtain the global optimum but in case of Greedy approach we do not solve the problem in any recursive nature rather we find a feasible solution at every stage with the hope of finding optimal solution.

So I am unable to get the notion of sub-problems in case of Greedy Approach .

Here is a concrete example, the problem of Set Cover:

  Set Cover

  Input: Sets $S_1,\ldots,S_m$ whose union is $U$

  Output: Minimal-size subset of $\{S_1,\ldots,S_m\}$ whose union is $U$

The well-known greedy algorithm for this problem (which gives a $\ln n$ approximation) proceeds as follows:

While $U \neq \emptyset$:

Add to the solution the largest set $S_i$.
Remove all elements of $S_i$ from all sets and from $U$.

Having chosen a set $S_i$, we are effectively moving to another Set Cover instance, in which the sets are $T_j := S_j \setminus S_i$, and the universe is $V := U \setminus S_i$.

This new instance is the sub-problem mentioned in your statement. The greedy choice — largest set — is the local choice mentioned in your statement.

To check your understanding, show that this view is appropriate for other well-known greedy algorithms such as Huffman encoding and the greedy algorithm for interval scheduling.