4

First of all, if you can determine whether a graph $G$ contains an independent set of size $k$, then you can also find such a set efficiently. This is known as "search-to-decision reduction". Here is the basic idea. Choose an arbitrary vertex $v$, and remove it. If the graph still has an independent set of size $k$, then keep going. Otherwise, all ...


4

I am assuming that $W = \sum_{i=1}^{2n-1} w_i$ and $B = \sum_{i=1}^{2n-1} b_i$. Let $B^*, B_1, B_2, \dots, B_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^*$. Consider the two groups $G_E = \{ B^* \} \cup \{B_i \mid i \text{ is even} \}$ and $G_O = \{ B^*...


3

Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need. Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$. Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)


3

Here the problem status is "open". The page was revised in 2006 and it seems updated to September 2017, so we can safely suppose that the problem is still open. Anyway, an algorithm that solves the problem using $O(n^2)$ comparison (and total complexity $O(n^2\cdot \log(n))$) is known from 1992: J.-L. Lambert, Sorting the sums $x_i+y_j$ in $O(n^2)$ ...


2

You store the numbers n-k+1 to n in an array. Then for each prime number p ≤ k: Find which power of p is a factor of k! (Thats k/p + k/p^2 + k/p^3 ... ) Then remove that power from the array: Find the first number divisible by p (that would be the number at index 0 if n-k+1 is divisible by p, otherwise at index p - ((n-k+1) modulo p)). That number is ...


2

If i understand you correctly, then the following holds: $\sum_{k=1}^nk= \frac{n(n+1)}{2} \ge \frac{n^2}{2} = \Theta (n^2)$ Thus there is no asymptotic gain.


2

I like John L's suggestion. Have the app compute the view for the current position of all sliders. Also, for each of the 6 other sliders, for each other 9 positions of that slider, precompute the view obtained from that. In other words, you precompute all views that can be obtained by changing the position of a single slider. That involves precomputing 6*...


2

Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function. You need to strengthen your second condition.


2

Your problem can be solved in linear time. This paper describes a method to solve a system of $n$ linear inequalities with at most two variables per inequality and $m$ distinct variables in total in $O(n m^3 \log m)$ time. (I am swapping the meaning of $n$ and $m$ with respect to the paper in order to keep the name $n$ consistent with your question). In ...


1

The probability $1/i$ is correct, since it refers to the relative order of $a_1,\ldots,a_i$ before sorting the first $i-1$ elements. However, the argument seems wrong. The relevant probability is not $p_i(k)$, but rather $q_i(k)$, which is the probability that $a_i$ is the $k$'th smallest element out of $a_1,\ldots,a_i$ (before sorting). This probability is ...


1

It is possible that the literature on image vectorization might be useful. That basically tries to reconstruct the strokes that produced the image. However, I think this is going to be challenging when the width of the strokes is narrower than two pixels or so, and it is possible that standard techniques might work poorly in that domain. I would recommend ...


1

This can be solved by reduction to the unbalanced assignment problem. Build a bipartite graph where the vertices are the two sets of numbers, and there is an edge from a vertex in one set to a vertex in the other set if and only if the distance between the numbers is less than or equal to 0.18. Set the weight of each edge to the distance between the two ...


1

The formula $\varphi(a)=a \prod_{p|a}(1-\frac{1}{p})$ tells us to approach the problem by the prime factors. Here is another useful formula. Legendre's formula. For any prime number $p$ and any positive integer $n$, let $\nu _{p}(n)$ be the exponent of the largest power of $p$ that divides $n$, i.e, $p^{\nu_{p}(n)}$ divides $n!$ but $p^{\nu _{p}(n)}$ does ...


1

Yes, you are correct! You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition. p. 226 Printed: in the worst case, it needs 2 N + 1 array accesses Fixed: in the worst case, it needs 2 N - 1 array accesses ...


1

Theorem B on page no. 272 of the book states that, if $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, then q ∈ [ q̂ - 2 , q̂ ]. Therefore, the algorithm is valid only when $v_{n-1}$ $\geqslant$ $\lfloor b/2 \rfloor$, which makes $v_{n-1} \neq 0$ obvious. To ensure this we need to multiply both u and v by a factor ${(= (base-1) / v_{n-1})}$.


1

The key is to understand that they are different problems: The spanning tree looks to visit all nodes in one "tour", while shortest paths focuses on the the shortest path to one node at a time. As an example, imagine you know the shortest route from your home to two different places A and B. Since the graph is directed, you can get to B from A but not vice ...


1

You can add a small value positive $\delta$ to each edge and use Dijkstra's algorithm to find the shortest path. Any $\delta < \frac{1}{V}$ will suffice.


Only top voted, non community-wiki answers of a minimum length are eligible