Tag Info

New answers tagged

0

Herbert Kociemba wrote a generating function (in Mathematica code) which gives how many "canonical sequences (where commutating moves and cancellations like U U' etc. are taken into account) in OBTM" for a given maneuver length. (OBTM is outer block turn metric. This the same move metric for cube20.org.) See his post here. By following his post (that is, ...


0

The algoritm you are looking for is called Squarified Treemap Algorithm. Its description and discussion of related issues can be found in this paper by Mark Bruls, Kees Huizing, and Jarke J. van Wijk. The proposed algorithm is recursive in nature. Key portion of the paper goes like this: ... Following the example, we present our algorithm for the ...


2

By induction, we prove that $k = 2^{2^j}$ after $j$ iterations of the loop. Importantly, $2^{2^j}$ is strictly increasing as a function of $j$. Now, define $m = \log_2(\log_2(n))$. Then, if $j < m$, the loop will not terminate at the conclusion of the $j$th iteration, since $2^{2^j} < 2^{2^m} = n$. Therefore the loop will run at least $m$ times. But ...


1

You aren't doing the induction correctly it should be T(n+1)=n+1 +2kn/2=(k+1)n+1 which is not less than kn Correct proof T(2) = 1 T(n) = n + 2T(n/2) T(n) <= k n lg(n) T(n+1) = n+ 2 (kn/2 lg(n/2)) = n + kn lg(n/2) < kn lg(n)


1

There has been quite a bit of work on this practical shape-packing problem, but I am not certain I know the latest advances. And I do not know if there is any but commercial software available. Here is a bit of information. First, nearly every version of the problem of packing shapes (polygons) into a region (usually a rectangle or an infinite strip) is ...


0

Asking the number of ways to solve a Rubik's Cube is like asking the number of ways to drive from New York to Washington DC. There's one shortest way, but you could also drive literally anywhere, detouring through Los Angeles, Salt Lake City, Minneapolis, back to Los Angles, then to Washington, DC. There's no limit on how many moves a solution can have.


1

If $r$ is the distance from the Earth's centre, $\phi$ is the longitude in radians (increasing from zero at Greenwich as one goes eastwards) and $\theta$ is the latitude in radians (increasing from zero at the Equator as one goes northwards), then the $(x,y,z)$ coordinates are given by: $$p(r,\phi, \theta) = r(\cos \phi \cos \theta, \cos \phi \sin \theta, ...


1

The steps for such demostration are indicated in the book of Berg "Computational Geometry. Algorithms and aplications". Exercise 1.1. The convex hull of a set S is defined to be the intersection of all convex sets that contain S. For the convex hull of a set of points it was indicated that the convex hull is the convex set with smallest perimeter. We want to ...


1

The vector $Ce_k$ is the $k$th column of the matrix $C$ for $k = 1,\ldots,K$. So this inequality says that $Ce_j$, that is, the $j$th column of $C$, is closer to $y_i$ in the $l_2$-norm then all other columns of $C$. Another way of writing this is that $j$ is the index such that $$ \|y_i - c_j\|_2^2 = \min_k \|y_i - c_k\|_2^2, $$ where $c_k$ is the $k$th ...


5

Just draw it out. The two high-degree vertices form one class together; the five low-degree vertices form the other.


0

What you're asking for is known as the order of $a$ modulo $n$. The strongest result I know of is that $\text{ord}_n a\mid \phi(n)$.


5

The big $O$ [O] notation is there to express the growth rate of a function (the running time of an algorithm) in a simple way, abstracting away unnecessary details. This growth rate is an essential factor in judging the useability of the algorithm. In particular, if you look at the behavior of a polynomial like $T(n)=3n^2-100n+6$ [T(n)=3n²-100n+6], it has ...


2

One almost equivalent way to understand big-O is if $f(x)/g(x)$ becomes closer and closer to a non-negative constant (even zero) as $x$ grows then $f(x) = O(g(x))$. Thus it means they either have the same fundamental growth rate, or $g(x)$ has a fundamentally faster growth rate (in the case that $f(x)/g(x)$ becomes closer and closer to zero). But in terms of ...


1

$$\sum_{k=1}^{n}\frac{1}{2k-1}=\sum_{k=1}^{n}\frac{1}{2k}+\sum_{k=1}^{n}\frac{1}{2k(2k-1)}=\frac{H_n}{2}+\log(2)-\sum_{k>n}\frac{1}{2k(2k-1)}$$ hence it follows that your sum behaves like $\frac{1}{2}\log(n)+O(1)$. Through the above line and the asymptotics for harmonic numbers, we can say even more: ...


0

One could use the Euler Summation formular: $$\sum_{a < x \le b} f(x) = \int_{a}^b f(x) dx + \int_{a}^{b}f'(x)\{x\}dx+f(a)\{a\}-f(b)\{b\} $$ with $$ f(x) = {1\over 2x-1} $$


4

We can write $\displaystyle \sum^{n}_{r=1}\frac{1}{2r-1} = 1+\frac{1}{3}+\frac{1}{5}+....+\frac{1}{2n-1}+\left[\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+....+\frac{1}{2n}\right]-\left[\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+....+\frac{1}{2n}\right]$ So $\displaystyle \sum^{n}_{r=1}\frac{1}{2r-1} = \sum^{2n}_{r=1}\frac{1}{r}-\frac{1}{2}\sum^{n}_{r=1}\frac{1}{r}$ Now ...


0

The text is saying that for this algorithnm to work, the coefficients of the objective function must all be positive. It then goes on to state that this is an easy thing to achieve. Let's consider your example: Minimize $Z = -3x_1+5x_2+6x_3-9x_4+10x_5-10x_6$ coefficients: $-3,5,6,-9,10,-10$ Subject to: (1) $–2x_1+ ...


1

Ignore the $k$, that's basically irrelevant. The point is really that if $a,b$ are small positive numbers, then $|\sqrt{a}-\sqrt{b}|$ is much larger than $|a-b|$. You can see this with a linear approximation: $\sqrt{b} \approx \sqrt{a} + \frac{b-a}{2\sqrt{a}}.$ So $|\sqrt{a}-\sqrt{b}| \approx \frac{|a-b|}{2 \sqrt{a}}$. Thus the error in the input basically ...


2

You might consider the Borodin-Moenck-scheme for computing such a product (see page 372 in "Fast Modular Transforms"). The key idea is to replace $n-1$ successive polynomial multiplications of a degree-1 and a degree-$i$-polynomial by $n-1$ "balanced" multiplications of polynomials of equal degree (or almost equal, if $n$ is not a power of two). That is, in ...


2

I finally ended up using weighted reservoir sampling with uniformly increasing weights. Here is a detailed paper: http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf Implementation in Java: http://utopia.duth.gr/~pefraimi/projects/WRS/


2

As I pointed out in a comment, you can choose a single number with linearly increasing probability by choosing two distinct numbers and using the larger one. (This gives probability $0$ for the least element, so you need to add a dummy least element to get exactly the probabilities you describe.) To use this for efficiently selecting $k$ distinct elements ...


0

The constant term is easy to compute, it's just the product of the $a_i$. The coefficient of $x^{n-1}$ is $\sum_i a_i$, so that is also easy. Assume for a moment that $n = 2k$ is even, then the coefficient of $x^k$ is the sum of all possible products consisting of $k$ different $a_i$. There are $\binom{n}{k} \approx 2^n/\sqrt{n} $ such products and there ...


1

The most concise way to expand this is with the use of elementary symmetric polynomials. For each integer $k\in\{0,\ldots,n\}$ the $k$-th elementary symmetric polynomial in $a_1,\ldots,a_n$ is defined as $$e_{n,k}:=\sum_{1\leq j_1<\ldots<j_k\leq n}a_{j_1}\ldots a_{j_k}.$$ In words $e_k$ is the sum of all products of $k$-tuples from $a_1,\ldots,a_n$. ...


1

The number of steps needed to compute $\gcd(m,n)$ is given by the length of the continued fraction of $\frac{m}{n}$, hence the worst case is to compute the $\gcd$ of two consecutive Fibonacci numbers (since $\frac{F_{n+1}}{F_n}=[1;1,\ldots,1]$) and an upper bound for the number of steps involved is: $$ 1+\frac{\log(\max(m,n))}{\log\varphi} $$ where $\varphi$ ...


0

The commenters are right that exp(ln(x) * y) is the most efficient way to do this. On the other hand I have an over-complicated way to do it below, which may be slightly faster because it uses a look-up table. I'm not sure I exactly understand what you mean by quadratic function, at first I thought you meant the complexity had to be quadratic, but it sounds ...


1

If there is an inbuilt exponential function, then you can use the following equation to approximate it in the given intervals: $$x^y \approx \exp \left(y\frac{x-1}{6}\left(1+\frac{8}{1+x}+\frac{1}{x}\right)\right)$$ The inner term is an approximation to ln(x) using Simpson's Rule, which is quite accurate. You can use a lookup table or a taylor series or ...


0

Divide your plane into say 1 million squares (1000 by 1000 grid). Each of your fixed circles will fit inside some square of squares (a simplification, but makes calculations easier). Create for each square a list of the circles that may pass through it. This is a little tedious, but you only have to do it once. Now, as your circle moves, you only need to ...


0

It's well after this post has been published and I know only a little about the topic, but if the question is only where to start the program that should be pretty simple: First note the formula to solve the problem in two variables: Find the minimal N such that $$ ax + by \neq N $$ Theorem: N = ab - a - b = (a - 1)*(b - 1) - 1 WLOG assume a < b. ...


0

First we rule out the $k$. Since we know it belongs to $W$ we can remove it from the graph. We also modify the cost of the neighbour of $k$ in order to take into account the prize received from the edge with $k$. Thus the new cost of $i$ is $v_i-x_{(k,i)}$. (Notice that if a cost is now negative we know that this vertex belongs to $W$ hence we can repeat ...


1

A linear recurrence of first order, which can always be "solved" (as long as finding closed forms of some ugly sums is possible). The general form is: $$ a_{n + 1} = f(n) a_n + g(n) $$ where $a_0$ is given. Divide by the summing factor: $$ S_n = \prod_{0 \le k \le n} f(k) $$ Note this is valid as long as $f(k) \ne 0$ over the relevant range. Thus: ...


1

The answers to the question you linked are not all correct. In particular, the answer relating to maximum flow computation is wrong. Let me first give you an example showing that this answer is wrong and then further readings stating correct algorithms for finding edge-disjoint trees in a graph. Consider the following graph: This graph obviously admits ...


0

There certainly is a better way than what you did. For example, for $n=100$, your algorithm cannot be run on any computer smaller than our universe, since you cannot store all $n!$ chains anywhere in memory. I advise you to improve your algorithm to only create legal chains, which will greatly decrease the work you have to do.


3

Here is a possible sketch for a proof. Step 1. Rewrite the diophantine equation $f(x) = 0$ as $f_+(x) = f_-(x)$, where the coefficients of $f_+$ and $f_-$ are all in $\mathbb{N}$. Step 2. Rewrite each monomial $c_{r_1, \dotsm, r_k}x_1^{r_1} \dotsm x_k^{r_k}$ of $f_+$ and $f_-$ as a sum of monomial with coefficients $1$ (for instance $3x_1^2x_3 = x_1^2x_3 + ...


0

Here is a more symmetric construction, with proof: Inductively, we will construct the ternary words $W_{13^k}$ according to the following rules: first, we colour $W_1$ with $0$. Given $W_{13^k}$, we substitute every letter $i\in\{0,1,2\}$ by the word $A_i$, where $$\begin{array}{cc} A_0&=0121021201210\\ A_1&=1202102012021\\ A_2&=2010210120102 ...


0

The optimum average length of the compressed binary stream $f(s^{[n]})$, (let's call it $L^{[n]}$) is given by the first Shannon theorem, in the range: $$ H(s^{[n]})\le L^{[n]}<H(s^{[n]})+1$$ so the compression rate $r=L^{[n]}/n$ ($n=[s]$ in your notation) is $$ \frac{H(s^{[n]})}{n}\le r<\frac{H(s^{[n]})}{n}+\frac{1}{n}$$ Here $H(s^{[n]})$ is the ...


0

The question is answered by Shannon's source coding theorem. For i.i.d. input, the theorem establishes that the minimum compressed bit rate is given by the entropy of the source. For statistically dependent input bits the same result applies, but entropy has to be defined in a more general manner to take dependence into account. See for example John G. ...


1

Calculating the primes up to $n$ in $O(n)$ time isn't particularly fast, and nor is it particularly slow. A naive Sieve of Eratosthenes works in time $O(n \log n \log \log n)$ and is very easy to implement. It can be sped up to run faster than $O(n)$ using some wheel techniques. I believe one can reduce the time to $O(n/\log n)$. See Paul Pritchard, A ...


2

Actually, matrix multiplication can be seen as a bilinear map $$K^{n\times k}\times K^{k\times m}\rightarrow K^{n\times m},$$ where $K$ is the ground field. Such a bilinear map can be expressed as a tensor of order 3 of format $(nk)\times (km)\times (nm)$ (any bilinear map $K^{\ell_1}\times K^{\ell_2}\rightarrow K^{\ell_3}$ can be represented by a tensor of ...


1

Yes. Start with the permutation which lists the numbers $1$ through $N$ in increasing order. Then repeatedly do the following: In the permutation you have, find the last pair of consecutive numbers in which the latter is greater than the former (if there is no such pair, stop, you're done). Call this pair $mn$. Increase $m$ by $1$ until you get a number $m'$ ...


1

You can easily implement a recursive algorithm. Let the function $perm(n)$ return the set of all permutations of $\{1,2,\cdots,n\}$. Then if you have generated $perm(n-1)$, you can get $perm(n)$ by inserting $n$ into any permutation from $perm(n-1)$ into any position. For example if $n=4$, then a possible permutation for $n=3$ is $213$, so this will ...


2

Say you have a column $C_i$ with negative sum, and you change the sign of all elements in that column. This must increase the total sum of all the elements in the grid (hereby just called the "total sum"), since all the other columns are unaffected, and the sum of all the column sums is the same as the total sum. The same thing goes for rows, of course. ...


1

Your problem is very closely related to the set packing problem (see https://en.wikipedia.org/wiki/Set_packing ) which is known to be NP-complete (i.e. very hard, e.g. most likely exponential time to solve). Probably even in your formulation where you insist that the subsets you choose must cover the entire set, the problem is still hard, even if the total ...


1

A proof system is a Formal system with logical axiom (possibly none) and rules of inference (at least one). Some examples : Hilbert-style proof system : usually more than one (logical) axioms and few rules : modus ponens and generalization. See Herbert Enderton, A Mathematical Introduction to Logic (2nd ed - 2001), page 109, for a system with few axioms ...


1

Well at iteration $i$ we select (c.f. the first paragraph) : $T$ if $s\ge t$ (upper choice : the smallest/nearest $t$ is chosen) and $S$ if $s< t$ (lower choice : the smallest/nearest $s$ is preferred) Since $d_i=\Delta x(s-t)$ has the same sign as $s-t$ ($\Delta x>0$)... Bresenham algorithm I'll suppose that $x'=[x], y'=[y]$ with $[x]$ the ...


3

No theory containing at least the peano axioms can prove its own consistency (proven by Gödel). But there can be a stronger theory proving the consistency of the weaker theory. The catch is, to prove the consistency of the stronger theory, you need an even stronger one. ZFC is believed to be consistence and can be used to prove the consistency of PA. To be ...


1

If you want to learn about algorithms, it is a very good idea to learn programming. It always helped me to understand the algorithms, if I also programmed them. And if you are good with understanding algorithms, programming will not be very hard. As programming languages i recommend python and C/C++


0

This is a partial answer (I don't really know how to answer question 2) Question 1) Yes. Every boolean function can be expressed by a series of gates. Actually even few gates are needed for the completeness. For example the most common restriction is that the pair of gates $not$ and $and$ gives completeness. An other example is that any function can be ...


0

I think there are many explanations of what it is, but as far as intuition is concerned I think the following is by far the most satisfying. We see bilinear maps as generalizations of the properties of a product, for instance if $K$ is a field or even a ring then the map $\times: K \times K \to K$ is a bilinear map, and this is the starting point, in a ...


0

The proof is by induction. To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less. Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ...


0

You might be able to get better answers if you post in stats.stackexchange or datascience.stackexchange. Anyway, here's a very simple method to get you started: Assume you have $m$-questions and $n$ users which you want to cluster into $N$ groups. For user $i$, let $x_i = (x_{i1},\dotsc,x_{i2}) \in \{a,b,c,d\}^m$ be the vector corresponding to the ...



Top 50 recent answers are included