New answers tagged

0

Nevermind. I managed to prove it. Since I had some difficulty finding the proof, I'll just post the answer here. The Frank-Wolfe algorithm solves min $f(x)$ subject to $x \in D$ using the iteration $x^+ = (1-\gamma) x + \gamma s^*$ for some $\gamma \in (0,1)$, and $s^* = \text{argmin}_s < s, \nabla f(x)>$. From convexity we have $f(x^+) \...


1

There are some corner cases for which your algorithm doesn't work. For example: What if some vertex is a part of a negative cycle unreachable from $s$ (your problem statement doesn't say anything about it, so we have to assume the worst case)? Your inequality might be satisfied even for vertices that are reachable from negative cycles, but doesn't belong ...


0

One way to solve these problems is visually. if we graph both solutions we see the $2^n$ (in orange) solution eventually outgrows $n^{nlog_2(n)}$ in blue.


1

I assume you meant $\log_2(n)$ and not $\log_2^n$. If I'm right, then take logarithms, say in base 2 (just for convenience). On the left you have $n$. On the right you have $\log_2(n)^2$. Now use L'Hospital's rule to compute $\lim_{n \to \infty} \frac{n}{\log_2(n)^2}$. From the result of this and the fact that $2^x$ is an increasing function, you conclude ...


1

Vertices A, B, C, D; all distances 2 except AC is 1 and BD is 100. Both algorithms will at some point use AC, which will force them to use BD, which is severely nonoptimal. EDIT: The example above can't be realized in the Euclidean plane, but just make all distances 13, except AC is 10 and BD is 24. Again, each algorithm chooses AC, forcing it to choose BD,...


3

The following two questions are equivalent: "Can the cards be folded to put them in increasing order, when they are labeled in a specified arbitrary order?" "Can the cards be folded to produce a specified arbitrary order, when they are labeled in increasing order?" The relevant result was proved by Koehler in 1968 ("Folding a Strip of Stamps"): An ...


0

I think this problem may be similar to figuring out whether a maze is a simple alternating transit maze: http://www.math.stonybrook.edu/~tony/mazes/satmaze.html In that case the solution would be whether when you write the numbers out like this: $n_1 n_2\cdots n_N$, you can draw a line that visits the numbers $1\cdots N$ in order, passing alternatingly ...


0

An iterative method for finding the best "maximum norm" approximation by polynomial of degree at most $d$ to a given smooth function $f(x)$ on a bounded interval $I = [a,b]$ was proposed by Evgeny Yakovlevich Remez in 1934, and has come to be known as the Remez exchange algorithm. The underlying idea is a characterization of the "mini-max" polynomial ...


0

Division requires 2 numbers. Therefore when we do that operation over and over again we obtain a square table. The area of that square is the cost of operation, I believe.


0

Is it the conditions of the euler circuit that doesn't make sense? Because if it does then the algorithm should make sense. In general the degree should be even on each vertex because you need a way to go from one to another while traversing each edge. Having even makes it such that you can enter from one way and exit another. Same goes for having a ...


0

You can use transformation of a closed curve described in my other question Averaging transformation of a closed plane curve (discrete variant). It is very good in cutting off fragments with vertices from a closed polyline (and opened also). It doesn't matter whether it is for convex or not - only it is important to have basically ordered points along ...


0

This is not a programming algorithm, just an easy to check process. $x,y,z\lt 10$ At least 1 of them is even. Say $x$. So $x^2\in\{4,16,36,64\}$ $y^2,z^2\in\{1,9,25,49,81\}$ OR $y^2,z^2\in\{4,16,36,64\}$ Last digit of $y^2+z^2$ must be $4$ or $6$ so $25$ must be there and neither of $y$ or $z$ can be even. SO you have only 4 combinations : $4+25=29;...


1

Neither of $x, y, z$ can be larger than $10$, so you have only $1000$ combinations to check by brute force, which is eminently feasible (and much quicker than trying to be clever). For the edited title: An algorithm that is not by brute force is not a good algorithm for this problem, because the additional time it will take to write it is much longer than ...


1

If you really wanted to you could get worst-case $O(n\log n)$ using a fast fourier transform, at least when $n$ is a power of $2$. I know nothing about such things, but I doubt that this could be worth the trouble, because it seems to me that the brute-force approach is going to be $O(n)$ on average. Because you can compare two random strings of arbitrary ...


2

We have that: $$A^n+A^{n-1}+...+1=\frac{A^{n+1}-1}{A-1} \equiv (A^{n+1}-1)(A-1)^{-1} \pmod{10^9+7}$$ We know that we can use the Extended Euclidean algorithm to find $(A-1)^{-1}$ because $10^9+7$ is prime, so the only way this wouldn't work is if $A-1$ is a multiple of $10^9+7$, which almost never happens. If we have $1 < A \leq 10^9$, then it definitely ...


0

Well you shouldn't care actually. As $n$ gets bigger, all terms $n^i$ with $i<4$ are negligible when compared to $n^4$ (This is because $\lim_{n \rightarrow \infty} \frac{n^i}{n^4} = 0$ when $i<4$). Hence, you know that starting from a certain $n_0$ (you don't have to know its value yet), $n⁴ + 100n² + 50 < c n^4$ (for any $c>1$ you want). And ...


1

The biggest term in this polynomial is $n^4$, so you have to choose a term bigger than $n^4$. Since $2n^4 > n^4$, you can choose $2n^4$ to find some constant $n_0$ where $n > n_0 \implies f(n) \leq 2n^4$. In this case, $n_0=11$. However, you didn't have to pick $2n^4$. For example, you could've picked $3n^4$ since $3n^4 > n^4$. In this case, we ...


0

Well, you can basically take a guess for $c$. Notice if you were to take a larger $n$, you could make $c$ smaller. But $2$ seems right, so let's try that. You could then graph $2n^4$ and $n^4 + 100n^2 +50$ and see that our desired inequality holds for all $n\geq 11$.


0

One approach: take the minimum of all your numbers, here $102$ as the first trial. Divide it into all your other numbers, choosing the quotient that gives the remainder of smallest absolute value. For your example, this would give $-9,2,3,-27,-6,0,-11$ The fact that your remainders are generally negative says your divisor is too large, so try a number a ...


0

If you have a coordinate system with origin at the center of the circle, x-axis horizontal, and y-axis vertical, then $x= r cos(\theta)$ and $y= r sin(\theta)$ where r is the straight line distance from the center of the circle to the point (x, y) and $\theta$ is the angle the line from the center of the circle to the point makes with the horizontal.


3

1) I can't entirely speak for the authors, but yes the block size $B$ looks to be chosen primarily by memory considerations. Modern computer systems have three or more levels of working memory which trade off capacity for latency: persistent storage (hard drive/SSD), RAM, and on-board cache (some of these levels are themselves split into more sublevels: ...


3

If you used first powers, it would have no selectivity as the total number of spaces at the ends of lines is just the length of a line times the number of lines minus the length of the text. As you increase the power, you penalize large gaps at the end of the line more. It is really a question of taste. Would you rather have gaps of $10,1,1,1,1,1,1$ or $0,...


1

Clarifying the statement below in a simple and easy manner:- "The children's sub-trees each have size at most 2n/3 - the worst case occurs when the last row of the tree is exactly half full". Let us suppose we have a max-heap as given below :- 1 / \ ...


1

Complicated proofs aside, there's a simple way to prove this on a coordinate plane: Draw a vertical line going through (0,0). Think about the definition of a slope, $\Delta$Y/$\Delta$X. The change in Y ($\Delta$Y) can be anything, depending upon how far up the line you go - so let's call $\Delta$Y n. Now, the change in X ($\Delta$X) is zero. No matter how ...


1

Stardard algorithms for computing SVD factorization of an $m \times n$ matrix A process in two steps: bidiagonalization of A SVD factorization of bidiagonal matrix using QR method or divide-and-conquer. The bidiagonalization procedure cannot utilize the triangular structure of A, and therefore standard SVD solvers cannot be optimized for triangular ...


1

If you have constraints where you turn on/off things by multiplying continuous variables with binary variables, you are typically not going to end up with convex (as in convex relaxations etc) models. Instead, you should model this using big-M strategies. For instance, if you want to model $xy\geq 1$ where $x$ is continuous and $y$ is binary, you introduce ...


1

Rabin has given a randomized algorithm for expressing prime $p = 4k+1$ as a sum of two squares in expected time $O(\log p)$. This previously published method is described in the first section of Rabin and Shallit's 1986 paper, "Randomized Algorithms in Number Theory" (Comm. in Pure and Applied Math v.39(supplement):S239-S256). See also the previous ...


0

All one-letter variables are integers. (i). If $1<u\in N$ then u is divisible by a prime. Proof: Let $v$ be the least $w$ such that $1<w\leq u$ and $w|u.$ Then $v$ is prime, for if $ v=w_1 w_2$ with $w_1>1<w_2 ,$ then $w_1$ is a divisor of $u$ with $1<w_1<w,$ contrary to the def'n of $w.$ (ii). If $p$ is prime and $p|n^2$ then $p|n$. ...


2

Good start. Now note that $$1=(am^2+bn)^2=(a^2m^3+2ambn)m+(b^2)n^2.$$


2

If $p$ a prime divides both $m$ and $n^2$, then $p$ divides $n$ by primality, hence $p$ divides $m^2$ and $n$, contradicting the fact that $\gcd(m^2, n) = 1$. Thus, $m$ and $n^2$ are relatively prime.


2

Start with $$am^2 + bn = 1$$ and multiply by $bn$ to get $$abm^2n + b^2n^2 = bn.$$ Since $bn = 1 - am^2$ this can be written as $$abm^2 n + b^2n^2 = 1 - am^2$$ which may in turn be written as $$abm^2n + am^2 + b^2n^2 = 1.$$ Thus $$(abmn + am)m + (b^2)n^2 = 1$$ so you can take $c = abmn + am$ and $d = b^2$.


0

the Euclidean gives $8\cdot53 - 9\cdot47 =1$, and thus considering the equality in $\mod 53$, and assuming the fact that $-9$ in $\mathbb{Z}_{53}$ equals to $44$. We're done.


0

The identity element is $1$ because $(1\times a)\mod b=a$ A multiplication inverse is such that $(a\times a^{-1})\mod b=1$ For $47^{-1} $ in $ \mathbb{Z}_{53}$ i.e. We have to find the element a such that $47a=53b+1\implies a=\frac{53b+1}{47}$. Now the integer value of $b \mod{53}$ for which a is an integer is the answer. That is what the euclidean algorithm ...


2

If you apply the Euclidean correctly, you'll have two integers $a$ and $b$ so that $$a\cdot 47 + b\cdot 53 =1.$$ What does this equation tell you if you interpret it mod $53$?


1

I'm assuming that the circles have to be placed as illustrated tangent to the common edge in the order they are specified - that is, we're not shuffling the circles around to solve an arbitrary packing. There will still be some tricky cases when adjacent circles are of significantly different diameters. However in the case where the circle sizes are ...


2

You have posed two distinct questions: Given $f$ and an explicit definition of $f^{(i)}$, how do we verify that $f^{(i)}$ is correct? Given $f$, how do we find $f^{(i)}$? The first question is easier because we already know what $f^{(i)}$ is. For example, given $f(n) = 2n$ and $f^{(i)}(n) = (2^i)n$, we can verify that $f^{(i)}$ is correct using a proof ...


1

As Andre Nicolas mentioned in the comments, your proposed formula is incorrect. Let $D_n$ denote the number of derangements of a sequence with length $n$. Since you gave a formula for positive $n$, let's compare your formula with $D_n$ for small positive $n$. $D_1 = 0$ since every element in the sequence $\{1\}$ is a fixed point, that is, it is in its ...


1

There are $n^2$ (not $2^n$) ordered pairs. Of these, $n$ are pairs of two identical elements. The remaining $n^2-n$ pairs each come in two different orders, of which you want only one, so you have $\frac{n^2-n}2$ different comparisons. This is $\binom n2$, the binomial coefficient that counts the number of ways of choosing $2$ elements out of $n$.


1

You don't quite pin down the problem here — if not all courses can be fitted into the semesters, what counts as the best schedule? The natural thing to do would be to give each course a score and aim to maximize the score of the courses scheduled. The decision version of this problem ("is there a schedule with score $≥ K$?") is in NP, since it's easy to ...


0

In the initial position there are three towers, that I will call A,B,C, and assume the problem we want to solve recursively is: Problem: Move all disks located in tower $X$ to tower $Y$ (for $X,Y\in \{A,B,C\}$ and $X\neq Y$). The recursive solution is as follows: For $n=1$ disks: move the disk from $X$ to $Y$. For $n=k+1$ disks: Use the solution ...


0

The classic fuzzy logic approach has "truth" on a sliding scale between $0$ (false) and $1$ (true). This defines the logical operation "and" by multiplication, so that, for example, two almost-true values will have a slightly lower but largely true result. The logical operation "not" is simply a reversal in range, i.e not $X := (1-X)$. Your logical "or" ...


0

Given $a)$ and $b)$ hold, the algorithm has to cycle through all $k$ up to $n$ because only two facts about $P(n)$ are known: a) It holds for $P(1)$. b) Given $P(k)$ holds, $P(k+1)$ also holds. If you were to build a machine from these atomic principles, all you can do is to start at the (only known) true statement $P(1)$ and, successively, make your way ...


1

We have cell centers $c_i$ (along one coordinate axis), with $c_i \lt c_{i+1}$. For $N$ cells, there are $N+1$ cell edges, so one cell edge (or the width of a specific cell) needs to be known in order for us to find the coordinates for the rest of the cell edges. Let's label the left edge of cell $i$ as $b_{i-1}$, and right edge $b_{i}$, $1 \le i \le N$. ...


0

For even $n$, the least number of $0$s in the final product is $|r-\frac{n}{2}|\cdot 2$. If $r$ isn't $\frac{n}{2}$, then no matter how you arrange your ones and zeros, there's going to be $2\cdot|r-\frac{n}{2}|$ zeros and ones facing another zero or one. So, for even $n$, your outcome space is the set of vectors with an even number in $[n, 2\cdot|r-\frac{n}{...


1

This is a special case of computing the distance between two convex sets (a point by itself is a convex set). This paper A fast procedure for computing the distance between complex objects in three-dimensional space was brought to my attention by Joseph O'Rourke and it references an $\mathcal{O}(\log M)$ algorithm for the two dimensional case. Here $M$ is ...


1

If the convex polygon is represented by the intersection of finitely many half-planes $$P := \{ x \in \mathbb R^2 \mid A x \leq b \}$$ then we can find the point $x^* \in P$ closest to a given $y \in \mathbb R^2$ by solving the quadratic program $$\begin{array}{ll} \text{minimize} & \|x - y\|_2^2\\ \text{subject to} & A x \leq b \end{array}$$ If ...


-1

Assume that $A,B$ are generic square matrices. Then $A$ has essentially at most $n$ REAL eigenvectors $\pm (v_i)$ that are subjects to $n$ linear independent inequalities. The probability that at least one of the previous vectors is convenient is $\leq p_n=\dfrac{n}{2^{n-1}}$ When $n\geq 90$, $p_n\leq 2^{-80}$, that is to say that the event above NEVER ...


1

You could do something that is somewhat like binary search indeed: To find the closest point on $P_1P_2P_3\ldots P_n$, find the closest point on $P_1P_3P_5\ldots P_{\lceil n/2\rceil}$. If it is between $P_k$ and $P_{k+2}$ then we need only test vertex $P_{k+1}$ and its adjacent edges for the original polygon. If it is exactly at $P_k$, we also need only ...


0

The title and body pose two different questions. I'll answer the question in the body, how one could do it easier, without providing an algorithm as requested in the title. $90342$, $39458$ and $51545$ all have two hits; that's a total of six hits in five digits, so at least one hit must be shared. The only coinciding digit is the $4$ in the penultimate ...



Top 50 recent answers are included