New answers tagged

1

If you want to make use of pre-sorted lists, the the idea is to use the fact that the median will be located at $i = floor(\frac{N}{2})$, where $N$ is the length of the list you're looking for. The nice thing about splitting the list is that when we recurse, we can simply use the sub-lists from $[0, i)$ and $[i, N)$ to find the median again. However, as ...


1

I think you're confusing a couple of things here: When you split along an axis, you take a plane perpendicular to that axis and choose points that are "in front of" and "behind" this plane. While you're correct in saying that when you divide along the X axis you can simply look at the $x_0$ from the point $P(x_0, y_0)$, in general, you would like to ...


3

Every Directed Acyclic Graph (DAG) on $n$ vertices with the most edges possible is isomorphic to a graph like this: Let $f(n)$ denote the most edges that a DAG $G=(V,E)$ on $n$ vertices can have. Claim: We have that $$f(n)=\frac{n(n-1)}{2}.$$ Moreover, any DAG on $n$ vertices with $f(n)$ edges is isomorphic to the following graph: $$V^*(n) = ...


4

We assume the classical requirements for success of a conjugate gradient method, i.e. $A$ is symmetric positive definite. Use of a pre-conditioner with the modifications discussed below is not precluded. A modified conjugate gradient method which deals with multiple right hand sides is found in the literature, called block conjugate gradient, going back to ...


2

Conjugate gradient (and similar iterative methods) don't even know that there is a matrix involved, so it's hard to see how they could give us any information about its structure. Here's an idea (which I have never tried myself) ... After you have solved a few different versions of the problem with different values of $b$, you have a few known values of ...


-1

You're going to have different techniques for different numbers of digits. 1 digit numbers $n$ must be even, then there is only one sum: $\frac n2 + \frac n2$ 2 digit numbers For $n<20$ and $n$ even, there is the simple sum: $\frac n2 + \frac n2$ For other $n$, consider the sum of a number $10a+b$ and its reverse $10b+a$. The sum is $11a+11b = ...


0

In order to find the intersection point of a set of lines, we calculate the point with minimum distance to them. Each line is defined by an origin ${a}_{i}$ and a unit direction vector, ${n}_{i}$. The square of the distance from a point $p$ to one of the lines is given from Pythagoras: $$ d_{i}^{2}={{\left[ \left| \left| p-{{a}_{i}} \right| \right| ...


0

Let's call your formula CNF. Let's call the clauses $C_1, C_2, C_3, C_4$ Let $v_i$ be a literal in $C_i$ By your conversion, every $(v_i, v_j)$ for $i \neq j$ and $v_i \neq \bar v_j$ is an edge in G. Now we have to prove: CNF is satisfiable $\iff$ G(V, E) has a clique of size 4 Suppose CNF is satisfiable $\quad$This means every clause has at least one ...


1

Edit: see bottom for a better answer. You can write this problem as an integer linear program. The only aspect of this that may not be obvious is how to handle the absolute value, since it is not quite linear. Let the sum of the entries of desired vector be $c$ as in your example. Rather than minimizing $|(\sum_{i=1}^m \sum_{j = 1}^n x_{ij} y_j) - c|$, ...


0

Hint: How many maximum matchings there might be? I hope this helps $\ddot\smile$


0

OK, I'm an idiot. All I needed to do was to look for a number $2^k-1$ that would consist of two distinct prime factors, which were not in the form $2^k-1$. For example $p=23, q=89, n = p \cdot q = 2047$. Then I get: $$ \gcd(2^{11!} - 1, n) = n $$ and I have to pick a different $a$, goes all the way to $$\gcd(12^{4!} - 1,n)=89$$


0

It depends. I hate to use that statement here, but the "best" solutions typically change with the size of the input, or depending on what we're optimizing (speed, space, programmer time, complexity, portability, etc.). You also have multiple different tasks being discussed: primality, generating primes, and factoring. For generating primes in sequence ...


2

While I do not know what you mean by "mathematical equation/skeleton," to understand how MD5 is implemented, all you need to know is high school algebra, bit vector algebra (e.g., if A and B are two size $n$ bit vectors, what A XOR B, A AND B, etc. mean), plus the ability to read a simple computer program. Look at the sample code in the English-language ...


2

The following algorithm will produce $H=\langle S\rangle$, provided $S$ is a subset of a finite group $G$. Push $1$ to a queue and let $H=\emptyset$. If the queue is empty, terminate Pop $x$ from the queue. If $x\in H$, go back to step 2 Set $H=H\cup \{x\}$ For each $s\in S$, push $x\cdot s$ to the queue Go back to step 2


0

Let's unpack the problem in the context of presenting an algorithm for iterating over maximum bipartite matchings proposed by T. Uno (1997). A matching of a (simple, undirected) graph $M$ is a set of edges such that no vertex is incident with more than one edge in $M$. Alternatively we could say that no two edges of $M$ meet at (share) any vertex in $G$. ...


0

The criterion for a bad symmetric $>0$ matrix $A$, concerning the Choleski method, is the same as for the LU decomposition. Just calculate the condition number of $A$; let $cond(A)=\dfrac{\lambda_1}{\lambda_n}\approx 10^k$ where $\lambda_1\geq\cdots\geq \lambda_n$ are the $>0$ eigenvalues of $A$. It suffices to calculate approximations of ...


1

The result of createSchedule is a list of rounds. Each round is described by nodes receiving message from their parent that round. Each parent can only send one message per round. public class Scheduler { @Override public List<Collection<Node>> createSchedule(Node root) { List<Collection<Node>> result = new ArrayList<>(); ...


2

My recommendation would be to use Cholesky decomposition of the matrix $AA^T$. For an upper-triangular matrix $A$ the Cholesky decomposition of $AA^T$ is obviously trivial. And then there exist several algorithms for finding the singular values given the Cholesky decomposition. I was trying to think of one myself, but apparently someone has already written ...


1

Note that the increments 0.01 * n and 0.1 * n will actually evaluate to $\lfloor \frac n{100}\rfloor$ and $\lfloor \frac n{10}\rfloor$ - except that we may have rounding errors from float to int conversion; but then again we must allow unbounded values for the int type (or we can say the complexity is vacuously $O(1)$), so why not assume infinite precision ...


1

Suppose the starting vertex is $r$. BFS visits vertices in the order of non-decreasing distance to $r$. In other words, for two vertices $u$ and $v$, if the distance between $u$ and $r$ is smaller than that between $v$ and $r$, $u$ will be visited before $v$. Here, we assume the graph is unweighted (i.e., the edge weight is 1) and distance between two ...


1

Both DFS and BFS are essentially the same algorithm that expand and visit vertices in some order, but differ in the way they store these vertices, which impacts this order. Hence, differ in their internal data-structure. DFS uses a stack where as BFS uses a queue, which means DFS explores newly discovered vertices first (LIFO) and BFS explores adjacent ...


1

Yes, if there is no known plaintext, and just a single cipher text $m^\ast$, you do need $k$ even if $p$ is known to everyone. In this case the plaintexts are numbers of a special form (because they're built up from smaller alphabet numbers in your case), so there might be a weakness there, and there are some other issues, but essentially yes. But as said, ...


0

Matrix multiplications is indeed of complexity $\mathcal{O}(n^3)$ (well, for school book implementations). It is cubic when we multiply two matrices together. However, in my personal opinion, it is quite rare to perform this operation in machine learning algorithms, hence perhaps that is why we rarely hear people blaming the complexity of algorihms on matrix ...


1

here is a simplified version of Hardy-Muskat-Williams. Find all solutions with $0 \leq b < 4n$ to $$ b^2 \equiv -4d \pmod {4n}. $$ Let's see, this just makes $b$ even. If there is any odd prime factor $q$ of $n$ with odd exponent and $(-d|q) = -1,$ there will be no such solutions $b$ and the thing is impossible. For each, we have $$ b^2 = -4d + 4nt, $$ ...


0

Here is J.M. s algorithm implemented as a c++ template class // Template for GCD template<typename AType> AType VARGCD(int nargs, ...) { va_list arglist; va_start(arglist, nargs); AType *terms = new AType[nargs]; AType result = 0; // put values into an array for (int i = 0; i < nargs; i++) { terms[i] = ...


1

$2.2^n$ is the same as $\frac{22^n}{100^n}$, this should tell you how it is calculated. We have the following inequality: $2^n<2.2^n<3^n$. So it is exponential time, if your algorithm takes approximately $2.2^n$ operations then for an input of $25$ you need approximately $3\times 10^8$ operations, which is going to take a somewhere between half a ...


0

Your algirithm fails for a number like $19\cdot 31$, because it doesnt include the possibility that the last digit $9$ is obtained from $1\cdot 9$. Even though the last digit is obtained from $m\cdot 1$, that doesn't mean that either of the factors will be equal to $1$. It just means one of the factors will end in a $1$.


3

You are right in that $N$ is a counter for how many times the program has left to go through the body loop. However, I think your answer sheet is trying to tell you that it is more than a counter: It is also a stopping condition. When $N=0$, the program stops. Otherwise, the program keeps going. This is a common technique for numbers to actually be used as ...


1

Generalizing individ's answer, in $xyz=w^2(x+y+z) $, if $x+y = z$, then $xy(x+y)=2w^2(x+y) $ or $xy = 2w^2$. If $r(x+y) = z$ where $r$ is rational, then $xyr(x+y)=(1+r)w^2(x+y) $ or $rxy = (1+r)w^2$ or $xy = (1+\frac1{r})w^2 $. Therefore, for each $w^2$, for any $r$ such that $w^2/r$ is an integer, look at all the factorizations of $w^2(1+1/r)=xy$. In ...


0

$$xyz=w^2(x+y+z)$$ Decompose into factors of the number. $$tp=2w^2$$ Then the decision on the record. $$x=t$$ $$y=p$$ $$z=t+p$$


1

You have a typo: you should mod by $277$, not $7$. Indeed: $$ 83627264^4 \pmod{277} = 238^2 \pmod{277} = 136 $$


0

Although this doesn't seem to be what you're asking from the examples, if you only require them to be subsets (i.e. disregarding order and not necessarily continuous with respect to the original array), you can do $O(n)$. int freq[n] for num in arr: freq[num]++ result = 1 # empty set suffices for num in freq: result *= freq[num] / 2 + 1 return ...


1

If I understand what you are asking, you have a sequence of $n$ positive integers inclusively bound by $n$, and you want to find the number of subsets of indexes which produce sequences with only even multiplicities. This can actually be done quite efficiently. I will be using binomial coefficients, which you can read up on if need be on the wiki page: ...


1

Replace $a+b$ with the letter $c$. If $c$ is a factor of $s$, you have two solutions: $$a=0,b=c,n=s/c-1 \text{ or }\\a=c,b=0,n=s/c$$ Otherwise it is ordinary division with remainder. $b$ is the remainder, $a=c-b$, $n=\lfloor s/c\rfloor$


0

Do a level order Traversal of the binary tree using a Queue Data structure. And after completing each Level, insert a dummy node to denote that the level has been completed. Partial C code + Psuedocode: int num_of_levels(Node *root) { if(root == NULL) return Initialise a Queue Add root to Q Add a Dummy Node(NULL pointer) to Queue ...


2

One way to think about this is by the infamous max flow - min cut theorem which states; The maximum value of the flow from a source node s to a sink node t in a capacitated network equals the minimum capacity among all s-t cuts. [S,Sbar] Since, after multiplying all capacities by a constant C, the minimum s-t cut doesn't change, moreover the ...


0

All that is needed is that $\dfrac{n^j}{n^k} \to 0 $ for $j < k$. Of course you have to understand what $O$ and $\Theta$ mean.


2

Most likely, $$e=\gcd(n_1e,\dots,n_ke)$$ where $\gcd$ is the greatest common divisor function. Actually, the right hand side is $$\gcd(n_1e,\dots,n_ke)=e\cdot\gcd(n_1,\dots,n_k),$$ where $\gcd(n_1,\dots,n_k)$ is likely equal to one. This function can be calculated recursively for $k>2$. If $$g_i=\gcd(n_1,\dots,n_i)$$ for $1\le i\le k$, then ...


-1

this pseodocode should work: Input: a number $n$ Output: $1\cdot2\cdot3\cdot...\cdot n$ factorial(int number) if (number <= 1) return 1; else return number * factorial(number - 1); Full code: import java.util.Scanner; public class factorial { public static void main(String[] args) { Scanner input= ...


2

The Leibniz series is OK for calculating $\pi$ to reasonable precision, if Euler acceleration is applied to it. The idea is to replace $$a_{2n+1}-a_{2n+2}+a_{2n+3}-a_{2n+4}+\cdots$$ with $$\frac12a_{2n+1}+\frac12(a_{2n+1}-a_{2n+2})-\frac12(a_{2n+2}-a_{2n+3})+\frac12(a_{2n+3}-a_{2n+4})-\cdots$$ For a convergent series, this leaves the sum the same, but the ...


0

Sadly, this problem is NP-hard, hence there is no known polynomial time algorithm for this problem (and probably there is no way to find one such algorithm). Worse yet, as stated in that link, unless P=NP, no polynomial-time approximation algorithm for this problem can guarantee to find an independent dominating set with size within a factor of $K$ of the ...


2

It's true if and only if $n > \log(n)$, which you can prove by exponentiating and using Taylor series.


2

To clear up the definition first: to say that $S^*$ is "optimal for men" means that in $S^*$, every man is paired with the best possible woman he can possibly be with among all stable pairings. There is nothing vague about it. Now to address your point. "Two lines above", we were talking about the pairing $S^*$, the pairing produced by the Gale-Shapley ...


2

"I would like to know if a similar algorithm already exists." The answer is: yes. :) Rankade, our ranking system for sports, games, and more, does exactly what you need, and it leads to optimal (i.e.: most balanced) team composition. It's free to use, and here's a comparison with Elo and TrueSkill.


1

Let $P$ be the set of prime factors of $N$ and call the function $g(M).$ Then we have by inclusion-exclusion that $$g(M) = M! \prod_{S\subseteq P, S\neq \{\}} h\left(\prod_{p\in S} p, \bigg\lfloor\frac{M}{\prod_{p\in S} p}\bigg\rfloor\right).$$ where $$h(m, f) = \left(f! \times m^f \right)^{\mu(m)}.$$ If you read Maple consult the algorithm below. ...


1

I take your question to be about representing a selection of elements from $\{1, 2, \dots, n\}$ without regard to order. A common way is to use an $n$-digit binary string whose $i$th digit (reading right to left) is $1$ if and only if the element $i$ belongs to the selection. Each such string corresponds to a unique integer. For example, suppose I make the ...


0

It would appear that although $k$ is used in the definition preceding the discussion, the properties of $k$ do not follow through. The loops on each node in $G'$ simply represent the presence of an incoming link, and hence summing the loops for each node represents its indegree.


0

Yes, it is a fundamental assumption for the algorithm that there is an equal number of men and women. Otherwise it would be futile to hope for any way of matching everyone, stable or not.


1

What about a generating function like \begin{align} \sum_{n=0}^\infty \Biggl(\frac{4}{x-1} + \sum_{k>0} \frac{x^{k-1}(x^2\!+1)}{1-x^k}\Biggr) &= - 3 - 2x - x^2\! + x^3\! + 3x^5\! + 4x^7\! + x^8\! + 4x^{9}\! + x^{10}\! \\ &\hspace{3em} + 6x^{11}\! + 6x^{13}\! + 2x^{14}\! + 5x^{15}\! + 2x^{16}\! + 7x^{17}\! + 8x^{19}\! + \cdots, \end{align} ...


0

It does work just the way you think! Look at the proof at wikipedia. The fact that all the edges are assumed positive is used when they say that dist[w]>dist[v] is a contradiction because as there can not be a negative weighted path from w to v, v must come first. Here it continues to be a contradiction because otherwise, there would be a negative ...



Top 50 recent answers are included