New answers tagged

0

You may also go this way: for any vertex $v\in V$, store a bitmask $b_v$ that encodes the positions of its neighbours with a bit $1$. Then run over all the couples $(v_i,v_j)$ with $i\neq j$ and let $N_{i,j}$ be the number of bits $1$ that $b_i$ and $b_j$ share. The number of cycles of length $4$ is given by: $$ \frac{1}{4}\sum_{i,j}\binom{N_{i,j}}{2}.$$ ...


2

I don't know whether this is the fastest possible, but this is how I'd do it if I had to do it fast: Use a hash map that maps pairs of vertices to the number of paths of length $2$ between them. Iterate over the vertices, adding $1$ to the entry for each pair of neighbours of the vertex. Then iterate over the entries, summing $\binom n2$ of the counts $n$. ...


2

The portion highlighted in red looks correct. The correction you suggest gives a different definition of the $\Omega$ notation. In fact, just see the line below the portion you highlighted. This second version is a stronger requirement since $f(n)$ must be larger than $kg(n)$ for all sufficiently large $n$ (i.e. for all $n$ starting from some value $n_0$) ...


3

If you know that the inverse of $a$ is $b$, then $ab\equiv 1\pmod{n}$. It turns out that the inverse of $a^2$ is just $b^2$, i.e $$a^2b^2=a(ab)b\equiv a(1)b=ab\equiv 1\pmod{n}$$ Similarly, the inverse of $a^K$ is just $b^K$. Now if you want to calculate a large exponential of a a number, modulo $n$, there are fast ways to do this. The number of steps is ...


4

No. As $x \to \infty$, the numerator $\sim 33 x^9$, but the denominator $\sim x^{3/2}$ (not $x^{1/2}$), so this is $\Theta\left( x^{9-3/2}\right) = \Theta\left(x^{15/2}\right)$


1

Hint: Assume that we have $k$ positive integers $a_0,\ldots,a_{k-1}$ and $k\leq 2^m$. For any $j$ such that $1\leq j \leq m$, we define $f_j(m)$ as the value of the $(j-1)$-th bit from the right in the binary representation of $m$, then take: $$ N_1^{(j)} = \prod_{k : f_j(k)=1}a_k,\qquad N_0^{(j)} = \prod_{k: f_j(k)=0}a_k $$ and compute ...


0

The answer is no. (Even if $F$ is already a Gröbner basis, the algorithm does not terminate.) Consider the lexicographic order ($x > y$) and the polynomials $$f= x^2 - y^2, \quad g_1= xy - y^2$$ The set $F=\{f,g_0\}$ is a Gröbner basis. Applying the algorithm inductively to $g_i= xy^{i+1}-y^{i+2}$ and $f$ gives: $$T(g_0,f) = \gcd(x^2,xy) = x \neq 1 ...


1

I belive that the following text is a solution of this problem. If someone find a mistake, it will be good (and bad, simultaneously). So, let the square be $ABCD$ (clockwise), the midpoints of $AB$, $BC$, $CD$, $DA$ are $K$, $L$, $M$, $N$, respectevly, $O=KM\cap LN$. Let's ask the policeman use the following strategy: $$ \ldots ONAKOKBLOLCMOMDNONA \ldots, ...


0

What I do on my calculator: (pseudocode) For prime variable A until sqrt(X) If A divides X Then Divide X by A Print A Repeat loop resuming from A Print X This works faster than yours because as X is updated, the list of possible prime factors becomes smaller without eliminating any factors of X. If the test variable A is greater than sqrt(X), then print X ...


1

Start looking in the top right corner of the matrix. Then repeat the following: if you have found $x$, return true; if the number you found is larger than $x$, move one entry to the left; if it is smaller, move one entry down. If this would take you out of the bounds of the matrix, return false. Formally, in order to give this a running time of $\Theta(n + ...


0

Not really a solution, but an observation. For simplicity assume each side of the square is 2 units long, call vertices of the square corner vertices and center of the square plus middle of each side "middle" vertices. All are crossroads. Side roads are sides of the square and other are mid-roads. Let's say gangster at some point is at the side street, and ...


1

A computer algorithm is an algorithm intended to be performed by a computer. A mathematical algorithm is an algorithm intended to solve a mathematical problem. There are many things computers do that are not in themselves mathematical (e.g. download a video), although it often happens that a lot of mathematics goes into designing the algorithm, and ...


0

An algorithm is a prescribed list of actions to be performed to obtain a result. A mathematical algorithm is an algorithm intended to be performed to solve a mathematical problem and described in mathematical language. A computer algorithm is an algorithm described in actions that are readily adaptable to programming languages. Mathematical and computer ...


1

This is studied in the theory of computability, especially in computable analysis, because the choice of the representation of real numbers determines which functions on real numbers are computable. What follows is based on Computable analysis: An introduction by Klaus Weihrauch. See also The Representational Foundations of Computation (draft) by Michael ...


0

There are 3 cases to the Master theorem for solving the recurrence $T(n)=aT(n/b)+f(n)=3T(n/2)+n^2 / (\log n)$. If you draw out the recursion tree, the cost of the root is $f(n)$ and the cost of all the leaves is $n^{\log_b a}$. We compare these two costs and we get the three different cases for the Master theorem. Since the cost of the root $f(n) = n^2 / ...


3

The minimum number of edges that need to be removed to disconnect the graph is $3$, and there are just $4$ ways to do this: remove all of the edges incident at one vertex of degree $3$. There are $9$ ways to remove a set $E$ of edges so that (a) the resulting graph is disconnected, and (b) removing any proper subset of $E$ leaves a connected graph. However, ...


0

The diagrams are describing the steps in some sorting algorithm (couldn't tell you which) and giving the resulting partial order at each step in the form of a Hasse diagram. It appears that each case starts with an antichain and ends in a chain.


1

Maybe try this paper? Fast Matrix Multiplication: Limitations of the Laser Method It goes into enough detail for me to think I understand what's going on. I think the laser method is figuring out answers for N values with less rounding errors than what occurs using Strassen's method using some differential equation or numerical method. In recent years ...


2

UPDATE: After adding condition 3 below (only 3 out of every 4 locations in a 2x2 square can be a block, savile row + lingeling (a SAT solver) prove there is no solution with 34 or more blocks in about 10 minutes. This does not of course provide any kind of nice proof I have tried modelling this problem in the Savile Row system, which can generate input for ...


2

Using @Emisor's construction, we can reduce the upper bound to 39. First a bit of set-up: I'll use Cartesian coordinates to refer to positions on the board, with (1,1) at the top left and (9,9) bottom right. I will identify solution blocks by the coordinates of their top left cell. I'll say the block is "anchored" at these coordinates. The obligatory ...


11

Proof that $N=49$ is impossible: +-------+--- 1) +-------+ 2) +-------+ 3) +-------+ | 1 2 3 | X |(1)2 3 |*1 | 1 2 3 |(7) | 1 2 3 |(4) | 4 5 6 | Y |(4)5 6 |*4 | 4 5 6 | 1 |(4)5 6 | 7 | 7 8 9 | Z |(7)8 9 |*7 |(7)8 9 | 4 | 7 8 9 | 1 +-------+--- +-------+ +-------+ +-------+ ...


0

Wait a minute, there is a problem with your third definition of recursively enumerable sets. $\def\nn{\mathbb{N}}$The domain of a partial recursive function $h : \nn \to \nn$ is simply $\nn$ itself! Anyway the most useful characterization is that a set $S \subseteq \nn$ is RE (recursively enumerable) if and only if it is the set accepted by some program $P$ ...


-1

What a lovely question! I'll concentrate on Variant 1. You are in fact trying to guess two numbers. In the course of $Q$ questions (which I'll number from 1 to $Q$), you are trying to determine: The number, between $0$ and $2^n$. That is $n$ bits of information. Whichth answer was a lie. This is a number between $1$ and $Q$, plus $Q+1$ to denote "no lie", ...


0

Here is an analysis for m=3 numbers - so instead of n-bit numbers where $m$ has to be a power of two. I will minimize the average number of questions. A chooses the number, and answers questions, to maximize the average number of questions. B chooses the questions to minimize the average number of questions. A should choose the number 1,2 or 3 randomly. ...


0

[I invited OP to write up an answer, and to post it, but OP has not taken up this suggestion, so I'm posting my comment as an answer.] In terms of your diagram, the algorithm has already found the shortest path from $s$ to $x$ and to $u$, and decides to add the edge joining $u$ to $v$ instead of the edge joining $x$ to $y$ --- that is, it chose $v$ instead ...


1

The proof you linked to isn't very good. The whole issue could be avoided by noting that $\sqrt{2\pi n}(1 + \Theta(\frac1n)) = \Theta(\sqrt n)$ at the beginning. The author's approach is still ok in principle, but they make a mistake when they replace $\log(\Theta(1)+\Theta(\frac1n))$ with $\Theta(\frac1n)$. The expression $\log(\Theta(1)+\Theta(\frac1n))$ ...


1

The explanation is not well written. There’s really no need to introduce $a\bmod b$, though it does no real harm to do so. The real point is that there are unique integers $k$ and $r$ such that $a=kb+r$ and $0\le r<b$. Of course it’s true that $r=a\bmod b$, and if this explanation is being given in a computer science context it may be that pointing this ...


3

I approve @Heimdall. Let me explain why such a simple formula is valuable. You may know that one of the best local approximation of a surface built on a square grid like yours is through bilinear interpolation : let us consider the simple case of points with coord. $(0,0,h_{00}),(1,0,h_{10}),(1,1,h_{11}),(0,1,h_{01})$. Then the quadric surface passing ...


0

Have you tried just packing them on the boundary? (I'll explain what I mean below). Let $C$ be the circle of radius $R$ and order your $N$ circles as $C_1,\cdots,C_N$ such that $r_1 \ge r_2 \ge \cdots \ge r_N$. Place $C_1$ inside $C$ tangent to $C$. Then place $C_2$ tangent to $C_1$ and $C$, $C_3$ tangent to $C_2$ and $C$, $C_4$ tangent to $C_3$ and $C$, ...


1

This relation can not be used with the Master Theorem because $f(n)=n\log \log n$ does not meet any of the cases. Is $f(n)=O(n^{1-\epsilon})$? No, because $n\log \log n$ grows faster than $n$. Is $f(n)=\Theta(n\cdot\log^k n)$? No, because $n\cdot\log\log n$ grows slower than $n\log n$. Is $f(n)=\Omega(n\cdot\log^k n)$? No, because $f(n)=o(n\log n)$ and ...


0

The trick to manipulating indices is to use general sigma notation rather than the delimited form. This makes the process completely mechanical and reduces the chance of making an error. We get \begin{align*} \sum_{i=j}^{n} (n-i) &= \sum_{j \leqslant i \leqslant n} (n-i)\\ &= \sum_{n-j \geqslant n-i \geqslant n-n} (n-i) \\ &= \sum_{0 \leqslant ...


0

I translate your problem as: \begin{align} X_0 &= 100 \\ X_{i+1} &= X_i + X_i Z_i \quad \left( i \in \{0,\dotsc,N-1 \} \right) \end{align} There is little you can do if the $N$ percentages $Z_i$ have arbitrary values. $$ X_{i+1} = X_i + X_i Z_i = X_i (1 + Z_i) $$ which leads to $$ X_N = X_0 \prod_{i=0}^{N-1}(1+Z_i) $$


2

So to solve my problem, I need a general, easily computable algorithm for packing n circles into 1 circle. Some remarks: Assuming the $N$ small circles $c_i$ have radius $r_i$ each and position $u_i = (x_i, y_i)$ and the big circle $C$ is centered around the origin and has radius $R$. Then a feasible configuration $u = (u_1, \dotsc, u_N)$ is one ...


2

This is the stars and bars problem. Imagine a line of $64$ stars and $63$ candidate bars between them. Pick $15$ of those bars to be real and read off the groupings. There are ${64 \choose 15}=122131734269895$ To make the list, there are many algorithms on the web to generate the combinations of $15$ choices out of $63$. For example, you can use the fact ...


0

For $A_k$ and $A_{k'}$ to not be orthogonal, we must have $$(A_k[i,j],A_{k'}[i,j])=(A_k[i',j'],A_{k'}[i',j'])$$ by definition. Equivalently, by definition of $A_k$, $A_{k'}$, \begin{align*} ki+j &\equiv ki'+j' \pmod n, \text{ and} \\ k'i+j &\equiv k'i'+j' \pmod n \end{align*} which is equivalent to \begin{align*} k(i-i') &\equiv j'-j \pmod ...


0

You can use a recursive algorithm to iterate through the solutions, but there is an easy way to count them. The amount of non negative solutions to \begin{equation} x_1 + x_2 + \cdots + x_n = a \end{equation} is $a + n - 1 \choose n - 1$ or equivalently $a + n - 1 \choose a$. Since we want integer solutions, let $y_k = x_k + 1$. Each $y_k$ is now an ...


0

function partitionCombination(N,m,p) { if (N == 0) print(p); else { L = p.length; for (i = m; i >= 1; i--) { p[L] = i; partitionCombination(N-i,i,p); } p.length = L; } } function partitionOrderCounts(N,p) { if (N == 0) print(p); else { L = p.length; for (i = N; i >= 1; i--) { ...


2

This is the subset-sum problem -- it is NP-Complete, hence although there are certainly algorithms for it, none are necessarily "fast" in general (possibly for special cases of the problem though). The most common approach is dynamic programming. EDIT: while Wikipedia is unnecessarily general, as usual, the subset sum problem usually refers to OP's problem ...


0

We have of course $\beta^3 = m$, so we can rewrite the original expression as $\beta^2 |I^*| \leq 2(\beta^3|I| + \beta^3) + \beta |I|$. Then dividing by $\beta^2$, $|I^*| \leq 2 \beta |I| + 2 \beta + \frac{|I|}{\beta} = 2m^{1/3} |I| + 2m^{1/3} + \frac{|I|}{m^{1/3}}$. The two short steps that are glossed over in the proof are to notice that since $|I| ...


1

What can we say about it? Is it always better to choose $n \log n$ if the size $n$ is not given? Or can we say on an average $n \log n$ outperforms $n^2$. Strictly speaking, no to both questions. The only thing we can say for sure is that $n \log n$ algorithm outperforms $n^2$ algorithm for sufficiently large $n$. In practice, all $n \log n$ algorithms ...


5

No. Suppose sorting algorithm $A$ takes $1000n \log(n)$ steps and algorithm $B$ takes $n^2$ steps and we need to sort 1000 elements. Then $A$ takes $1000 \cdot 1000 \cdot \log(1000)=3000000$ steps, but $B$ takes $n^2=1000^2=1000000$ steps. However, it is eventually better. For example, for $n=10000$, $A$ is better than $B$.


3

If you want to write down an algorithm, you shouldn't aim to express it as "mathematical formulae" -- by which I assume you mean the kind of symbolic expressions used to write things in algebra or calculus. That notation is not good for communicating algorithms, and you will do nobody any favor by trying to cram your algorithm into it. It will be harder to ...


1

It takes at least $n$ comparisons to check whether a given number $x$ is contained in an unsorted list $L = (x_1, x_2, \ldots, x_n)$ with $n$ elements. Create a matrix $A$ by writing the elements from $L$ on the diagonal $(A_{n1}, A_{(n-1)2}, \ldots, A_{2(n-1)},A_{1n})$. Fill the upper left triangle of the matrix with a small number $a$ which is smaller than ...


0

That Inequality is certainly true and your methodology seems correct, however I am curious as to why the question asks you to find "the constants $C$ and $k$," as opposed to just "constants $C$ and $k$." For example, a similar methodology could yield $C$ = 5 and $k$ = 2. $$ \begin{align} & |f(x)| \le C|x^2| \ \ \ \ \ \ \forall x > k\\[8pt] ...


1

\begin{align*} \sum_{i=j}^{n} (n-i) &= \sum_{i=j-j}^{n-j} (n-(i+j))\\ &= \sum_{i=0}^{n-j} (n-(i+j))\\ &= \sum_{i=0}^{n-j} k(i), \quad \left( \text{k(i):= n-(i+j)}\right) \\ &=\sum_{i=0}^{n-j} i \quad \left(\text{$ k(i)=\widehat{n-j,0}, \,when \,\,\, i=\widehat{0,n-j} $ }\right)\\ &=\sum_{i=1}^{n-j} i ...


0

XOR of even and odd number is odd. Hence in a given array [A1,A2...AN], find total number of even elements and total number of odd elements. As we've to find number of all pairs having odd XOR, then answer is multiplication of total odd elements and total even elements. Below is my solution in PHP. <?php /** * Created by PhpStorm. * User: abhijeet ...


1

The general case can be modeled as a flow problem in a bipartite graph $G=(V_1\cup V_2,E)$, with $|V_1|=n$ and $|V_2|=m$. To take into account your constraints, add a source $s$ and link to all vertices of $V_1$, and a sink $t$, linked to all vertices of $V_2$. Impose that the entering flow in each node of $V_1$ is at least $R_{min}$ and at most $R_{max}$, ...


1

Another way yet, using $\sum_{i=a}^b i=\frac{b+a}{2}(b+1-a)$: \begin{align*} \sum_{i=j}^n(n-i)&=(\sum_{i=j}^nn)-(\sum_{i=j}^ni)=n(n+1-j)-\frac{(n+j)}{2}(n+1-j)\\ &=\frac{n-j}{2}(n+1-j) \end{align*} On the other hand, \begin{align*} \sum_{i=1}^{n-j}i=\frac{1+n-j}{2}(n-j+1-1)=\frac{n-j}{2}(n+1-j) \end{align*}


1

$$ \sum_{i=j}^n (n-i) = \sum_{i=1}^{n-j} i $$ $$ n=10, \ j=6: \ \left\{ \quad \begin{align} & \overbrace{(10-6)}^{i\,=\,6} + \overbrace{(10-7)}^{i\,=\,7} + \overbrace{(10 - 8)}^{i\,=\,8} + \overbrace{(10-9)}^{i\,=\,9} + \overbrace{(10-10)}^{i\,=\,10} \\[10pt] = {} & \underset{\begin{array}{c} \uparrow \\ i\,=\,1 \end{array}} 1 \!\!\! + 2 + 3 + ...


2

Set $n-i=k,i=n\iff k=0,i=j\iff k=?$ $$\sum_{i=j}^n(n-i)=\sum_{k=0}^{n-j}k=\sum_{k=1}^{n-j}k$$



Top 50 recent answers are included