New answers tagged

0

Need a lot of clarification on the question. Is 'x' a given? What is the domain of values for 'x'? Is the value 'A' one of the bounds of the range over which the summation is performed, or a variable used in the function which is to be summed? If 'A' and 'x' are integers, the expression f(A) = n^x may be satisfied by no integer values 'n'. That suggests ...


0

Just a few comments to get the discussion started. I don't think that this problem for sums is very meaningful. Every element in ${\mathbb Q}(\sqrt{a},\sqrt{b})$ is a sum of three elements in proper subfields, and an element in ${\mathbb Q}(\sqrt[4]{m})$ is a sum of elements in proper subfields if and only if it is already an element of ${\mathbb ...


0

I found the answer here. The algorithm has $O(n^2 logn)$ complexity https://www.quora.com/What-is-an-algorithm-for-enclosing-the-maximum-number-of-points-in-a-2-D-plane-with-a-fixed-radius-circle


0

You're looking for the algorithm that solves both The Texas Sharpshooter Problem and The Bomb Problem. See the link for code. Basically, find the triangle with smallest circumradius, then work up.


1

Take the log. $\log(\frac{e^{\sqrt{k}}}{k^c}) =\sqrt{k}-c\log(k) \to \infty $ since $\log(k) = O(k^{\epsilon}) $ for any $\epsilon > 0$. $\log(\frac{e^{\sqrt{\log(k)}}}{k^c}) =\sqrt{\log(k)}-c\log(k) \to -\infty $ since $\sqrt{x}-x \to -\infty $ for any $x \to \infty $.


1

Assuming that's C code and the variables are integers, the following will give a $\Delta \in [-180, 180)$: delta = (targetAngle - myAngle + 540) % 360 - 180; If the variables are floating-point, you need to replace % with fmod, but performance-wise it becomes wasteful vs. just checking the ranges as you had it. [EDIT] Short explanation: targetAngle - ...


0

Besides the 3 points to interpolate, you also want the value at the middle point to be the peak. Therefore, you actually have 4 equations to satisfy: $f(0) = y_0$ $f(m) = y_m$ $f(1) = y_1$ $f'(m)=0 $ where $y_0$, $y_1$ and $y_m$ are the $y$ values at $x=0$, $x=1$ and peak location $x=m$. Therefore, if you really want a non-piecewise solution that ...


0

Your calculation of log is off. $log_{24}12 \ne 0.5$ and $log_6 12 \ne 1.5$ 2) a = 12, b = 24, $p =log_{24} 12 < 1$, $f(n) = n = \Omega(n)$, and $ c= 1 > log_{24}12$, it is the case 3 of the master theorem. 3) a = 12, b = 6, $p = log_6 12 > 1$, $f(n) = n = O(n)$, where $c = 1 < log_6 12$, this is the case 1.


0

Suppose you have $n$ rows and $m$ columns. Create $n$ nodes name $R_i$ to represent each row. Each row can have at most 1 white square, so add 1 edge entering $R_i$ with a capacity of $1$. If Table entry $T_{i,j}$ is white, add it to the graph. Connect an edge from $R_i$ to $T_{i,j}$ with a capacity $1$. This represents "The row has chosen this cell". ...


1

The inverse limit $L$ of the inverse system $(A_i,f_{ij}:A_i \to A_j)$ is defined by the exact sequence $$0 \to L \to \prod_i A_i \xrightarrow{g} \prod_{jk} A_{jk}$$ where $A_{jk} = A_j$ and where $g$ is defined by $g((a_i))_{jk} = a_j - f_{kj}(a_k)$. It is possible, in principle, to implement this directly for example in Macaulay2, but if $(I, <)$ gets ...


2

First, the article is reducing 3SAT to Max2SAT (not Max2SAT to 3SAT). In 3SAT, each clause has 3 variables and has the form $c_i=(l_1 \cup l_2 \cup l_3)$. For each clause $c_i$, create the following 10 clauses: $(l_1), (l_2), (l_3), (c_i), (\lnot l_1 \cup \lnot l_2), (\lnot l_2 \cup \lnot l_3), (\lnot l_1 \cup \lnot l_3), (l_1 \cup \lnot c_i), (l_2 \cup ...


0

You ca use two parabolas: one on the interval $[0,\text{midloc}]$ and another on $[\text{midloc},1]$. That is $$ y(x)=\begin{cases}a\,x^2+b\,x+\text{start} & 0\le x\le\text{midloc}\\ c\,(x-1)^2+d\,(x-1)+\text{end} & \text{midloc}\le x\le1\end{cases} $$ The coefficients $a,b,c,d$ are found imposing that the value at $x=\text{midloc}$ is $y=\text{mid}$ ...


1

Your approach to Gaussian elimination is fundamentally at odds with the currect state of hardware. You are up against the memory wall, i.e. the fact that floating point operations can be completed at a rate which is far higher than the speed at which data can be retrieved from may memory. By processing your matrix one column at a time, your are constantly ...


2

Here, $\lg^2 n$ stands for $(\log_2 n)^2$. Your question is then to study the asymptotic behavior of $\sum_{k=0}^{\log_2 n} \log_2 \frac{n}{2^k}$.${}^{(\dagger)}$ Below are two different methods, one using knowledge of $\sum_{\ell=1}^m \ell = \frac{m(m+1)}{2}$ and yielding a sharp estimate; the second requiring no prior knowledge, but only giving a ...


3

First simplify it to $27x+8y=1200$. Then $27x = 1200 - 8y = 8(150-y)$. Since $27$ and $8$ are coprime, this implies that $x=8z$ and so $27z=150-y$. Therefore, the general solution is $x=8z$, $y=150-27z$.


0

Additonnally, good properties of Sobol (uniformity) comes from the choice of Polynonme and initial integers for each dimension. Property A and A' should be satistified for better convergence.


1

$$\sum_{i = 0}^{n-2} (n - 1 -i) = (n -1) + (n-2) + ... + 2 + 1 = \frac{(n -1)n}{2}$$ It is the sum of the simplest arithmetic series.


1

Plug in the possible values of $i$ into the summation! You get: $$ (n-1) + (n-2) + \cdots + 2 + 1 $$ which is the sum of consecutive integers from 1 to $(n-1)$. This sum has a well-known formula: $$ {(\mbox {last term})\cdot(\mbox{last term} + 1)\over 2}={(n-1)n\over 2} $$


1

Start by thinking how you would identify such a pair. The most obvious way is to pick the first number and try adding it to every other number. If this fails, move on to the second number and try adding it to every other number (except the first). This method will test every possible pairing and is therefore $O(n^2)$. So you now have to find a way to ...


1

I believe it's unknown if there is an algorithm that can compute a prime larger than $N$ in polynomial time (that is, $O((\log{N})^k)$ for some k). Cramér's conjecture implies that exhausitive search (counting up from $N+1$ and testing with AKS) runs in polynomial time.


0

prove it by contradiction. if we assume there exists a constant C such that $$ 6n^2 + 20 n \ge C n^3 $$ for all n large let $ n > \max\{20, 7/C\} + 1$ and so $$ 6n^2 + 20 n \lt 6 n^2 + n^2 = 7 n^2 = C* \frac{7}{C} n^2 \lt Cn^3$$ it ends to the contradiction.


0

We use $n_0$ in the same condition: $T(N)\le c\cdot f(N)\ $ when $N\ge n_0$. Since the definition only require existence, we can estimate roughly by choosing $c$ and $n_0$ as needed for the estimation to work. So, for $6n^2+20n\in O(n^3)\ $ we need to have $6n^2+20n \le c\cdot n^3 $ for almost all $n$. Well, in this particular case we are free to choose ...


2

There is no choice of $c$ and $n_0$ that is "the correct" choice. If there is any correct choice, then there are many correct choices. A big-O or big-omega proof does not depend on making "the correct" choice, only on making a correct choice. By the way, be more careful with the equations. The variable names $N$ and $n$ are not interchangeable, and the ...


0

The point of big-$O$ (and big-$\Theta$ and big-$\Omega$) notation is to make precise the notion of the rate of growth of a function. When we say $f = O(g)$ we mean that $f$ grows more slowly than $g$. In order to be useful this notion shouldn't really depend on constant multiples of the function, nor should it really depend on the behavior of the function at ...


0

This will not give you explicit constants, but is most likely one of the fastest ways to deal with such problems. Note that the definition of $O(\cdot)$ you give is: $$ f(n) \in O(g(n) \text{ iff } \exists C> 0, n_0 \text{ s.t. } \forall n\geq n_0, \ f(n) \leq Cg(n). $$ Another way to see it is to rewrite (assuming $g(n)>0$ for $n$ big enough, which ...


0

The answer is no. Your $k_i$ parameters are not enough to reconstruct the graph, and not enough to count triangles in the complementary graph (which is what $K_n$ represents). For example, consider $P=\{\{1,2\},\{2,5\}\}$ and $Q=\{\{1,3\},\{1,4\},\{2,5\}\}$. They have the same $k_i$ parameters, namely $2,1,0,0,0$. However the first one has five triangles ...


1

There is. Suppose the number of boxes of each size is respectively $x_1, x_2, x_3, \cdots, x_k$. Then the number of boxes visible is the largest of these numbers. Proof: We cannot nest any box in a smaller box. In a larger box, exactly one such box fits. In short, in each visible box is at most one box of a given size So the number of boxes visible is at ...


1

It only guarantees convergence to a local minimum or maximum. But if the function is convex, then local minimum is the global minimum.


0

You can show correctness of this algorithm via induction on the number of intervals in the optimal solution. Assume that your greedy strategy works for $n$ intervals in the optimal solution. Let $R_\mathrm{OPT}$ denote an optimal set of $n + 1$ intervals and $R_\mathrm{DGS}$ the set of intervals produced by your greedy strategy. Let $i_\mathrm{OPT}$ be the ...


1

You need to add a lot more detail and clean up some inaccuracies. First, the negation of the conclusion isn’t that $G$ is not connected by a unique simple path: it’s that there are two vertices, $u$ and $v$, of $G$ that are not connected by a unique simple path. We’re assuming that $G$ is connected, so $u$ and $v$ are connected by at least one simple path; ...


2

First, note that the answer cannot depend on $i$: $i$ is a dummy variable used as loop index (and so is $j$), so the answer can only depend on $n$. The inner loop performs two atomic operations, namely A[j] = A[j] + 1 and j = j + i so each inner iteration has constant cost $2$ (or similar, depending on the model of computation): anyway, ...


0

Consider the following 2 cases: 1.There was an even number of people numbered $1,2,3,..,2n$.Now you go around ina circle eliminating people. You are left with $1,3,5,...,2n-1$ which is almost the same as that of n people numbered $1,2,3,...,n$ except that the elements of the former numbering is 2 times that of the later minus 1. $$f(2n)=2f(n)-1$$ 2.If ...


1

Since the question is tagged [algorithms], and this is not e.g. stackoverflow but rather the theoretical world of mathematics, there is an algorithm that doesn't use division at all, only multiplications as requested... $j \gets 10^k$ $i \gets 0$ repeat $\quad$if $i \times b = a$, $\quad\quad$ take $(i \bmod j)$ as solution $\quad$fi $\quad i ...


1

This looks like a min cost flow problem with additional constraints. I would suggest linear programming. Let $x_{ij}^k$ a boolean variable that equals $1$ if and only if student $i$ ($=1...300$) of type $k$ (A or B) is assigned to project $j$ ($=1…170$), and let $c_{ij}$ be the rank of project $j$ by student $i$. You want to maximize $$ ...


1

I guess you mean k decimal digits. If $\gcd(b,10^k)=1$ you can use your product algorithm together with modular arithmetic to compute $a\times c \bmod 10^k$ with $c=b^{-1} \bmod 10^m$ with $m>k$. Example $$b=1234567, k=10, m=14, d=170141183460469231731687303715884105733$$ $$a=b \times d=210050690441241118011293999486607892762472611$$ With these values ...


1

What's happening is a ray is being cast to the right (in the positive $x$ direction) and we're counting edge crossings. The first condition is a bit of a cryptic way to say "if the $y$-coordinate of starting and ending points are both above or below the test $y$-coordinate then we definitely don't cross an edge". The next condition is calculating the ...


1

I think what you're looking for is the same as hex valued colors. These are of the form: $$ X_6X_5X_4X_3X_2X_1 $$ where $X_2X_1$ is a hex valued number representing the blue value, $X_4X_3$ is a hex valued number representing the green value, and $X_6X_5$ is a hex valued number representing the red value. All you have to do is represent your integer as: C ...


4

The existence of a solution is guaranteed by Baranyai's theorem. A proof of the theorem can be found, for instance, in Dieter Jungnickel - Graphs, Networks and Algorithms. The proof is constructive, so an algorithm can be derived from it. The book I mention contains references for explicit constructions in certain special cases. Furthermore, a Python ...


1

Setup a variable (a bank account, so to speak) $s_X$for each person $X$. For each instance of "$X$ lends amount $Y$ to $Z$" increase variable $s_X$ by $Y$ and decrease variable $s_Z$ by $Y$. In the end each variable tells how much money in total they should obtain back (or should give back in case of negative amounts). Observe that the sum of all accounts is ...


0

The problem is that there are so many ways that you have not specified what you want well enough. You can just split the rectangle into $N$ horizontal or vertical stripes. You can cut those stripes as you do. You can even make four rectangles that leave a little bit of space in the middle.


0

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=1$ and for $n\ge 3$ $$T(n) = 5 T(\lfloor n/3 \rfloor) + n \lfloor \log_3 n \rfloor^2.$$ It seems reasonable to use integer values here as the running time of an algorithm is a function of discrete quantities. Furthermore let the ...


1

$$\sum_{i=1}^{n-1}\sum_{j=i+1}^n\sum_{k=1}^j1=\sum_{i=1}^{n-1}\sum_{j=i+1}^nj=\sum_{i=1}^{n-1}(n+i+1)(n-i)/2=\frac{1}{2}\left(n^2\sum_{i=1}^{n-1}1-n\sum_{i=1}^{n-1}i+n\sum_{i=1}^{n-1}i-\sum_{i=1}^{n-1}i^2+n\sum_{i=1}^{n-1}1-\sum_{i=1}^{n-1}i\right)=\frac{1}{2}\left(n^2(n-1)-\frac{1}{6}(n-1)n(2n-1)+n(n-1)-\frac{1}{2}n(n-1)\right)= ...


0

Let's look at the first one: $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=1}^{j}1$ $ \displaystyle \sum_{k=1}^{j}1$ means $1+1+\ldots + 1$ added to itself exactly $j$-many times. Therefore $ \displaystyle \sum_{k=1}^{j}1 = j$ Then the triple-sum becomes $\displaystyle \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}j$ Let's look at the inner-sum again: ...


1

Suppose the preference orderings are such that all $100$ women prefer this fellow second most. There are $99$ other men. Pick randomly $99$ other women. Now, make it so that each of the $99$ men has a different favorite woman and that favorite woman also likes that man the best (they are "soulmates"- how sweet). In any stable match, these soulmates will ...


0

Hint: Suppose for a moment that the ideal number generator generates any integer between $ A $ and $ B $ instead of real number. Then the probability of $ X_1 + X_2 \le C $ can be found as $ \sum_{M} P(X_1 = M) P(X_2 \le C - M) $ For a concrete example, let say A = B = 6, then the probability that $ X_1 + X_2 \le 8 $ is $ P(X_1 = 1)P(X_2 \le 7) + P(X_1 ...


0

If we draw a directed multigraph with two nodes, 0 and 1, and draw $p$ edges from 1 to 1, $q$ edges from 1 to 0, etc. q ___ ------> ___ --\ / \ / / \/-- p | | 1 | | 0 | | r --> \___/ <------/ \___/<-- s then the number of such strings is the number of ...


2

Newton's method only guarantee the convergence to a stationary point $\bar x$ with $\nabla f(\bar x) = 0$ if you start closely enough to $\bar x$ (and if the Hessian $\nabla^2 f(\bar x)$ is non-singular.


1

(b) We have \begin{equation} \cos(x) = 1 - \frac{x^2}{2} + \frac{x^4}{24} + O(x^6) \end{equation} from which it follows that \begin{equation} \frac{1-\cos(x)}{x^2} = \frac{1}{2} - \frac{x^2}{24} + O(x^4). \end{equation} Therefore \begin{equation} f(x) - \frac{1}{2} = O(x^2). \end{equation} (c) When $x \rightarrow 0$, $x \not = 0$ the expression $1 - ...


1

Assume the problem intends that all the $x_i$ are integers. This can be done in order $O(N)$ as follows: Create a (zero-based) vector $C$ of size $K$, initially all zeros. $C_m$ at stage $m$ of the algorithm represents the number of ways to form a sum of $m \mod K$ using a consecutive sub-sequence of $\{ x_1, \ldots x_m\}$. Thus after stage $N$, $C_0$ ...


1

"Search" means looking for a point $a$ in the solution space $S$ that solves the problem (in some sense - perhaps maximizing some function on $S$). A "local search" algorithm starts at some (nonoptimal) point $s$ and tries to find a nearby point $s'$ that's better. To do that, the algorithm needs to know which points in $S$ it should think of as near $s$. ...



Top 50 recent answers are included