Tag Info

New answers tagged

0

If the points are nearly coplanar (co-hyperplanar?), then the problem is ill-conditioned. No algorithm you use will give you a "robust" answer in floating-point arithmetic. You can try this for yourself with nearly colinear points in the plane. That said, there are approaches that are better than others. For example, QR factorization using Householder ...


0

AFAIR the algorithm works with the divide-and-conquer paradigm. It splits the plane (and the set of points!) by 'half', solves the problem recursively and then merges the results. The merging is done in such way, that the points get ordered along the splitting line. Then you just scan the left part and the right part in parallel to find a pair crossing the ...


0

I don't think there is much difference. It depends on where you're looking for a closer pair around the separating line $l$ and what optimizations you do. You could compare each point from each plane to all the points that have the potential of being in distance $\delta$ both from plane $P_L$ and both from plane $P_R$ knowing you could only find one in the ...


0

To solve your problem I suggest you to use properties of intersections of sets: Given $X_i$ set with $i \in \mathbb{N}$: $$ \bigcap_{i=0}^n X_i = (...((X_0 \cap X_1) \cap X_2) \cap \dots X_n) $$ In other words you can implement the intersection of set (in your case interval) as, taking specifically your example $X_{result} = ([1,5] \cap [3,6]) \ \cap [2,7] ...


0

When I studied the various known matrices of combinatorical numbers I also looked at the following idea: what if we discuss functions with a set of results, not only one number? So for instance the concept of sine and cosine gets some special charme if we look not only at f(x) = sin(x), g(x)=cos(x) but at 2x2-matrices containing cos() and sin() and the input ...


1

Consider $n$ a representative size in your program. Let's say $n$ is the length of the list you're working with. The runnig time, or complexity, of an algorithm is the number of operations you need to do so that your algorithm terminates with an entry data of size $n$. You also have to choose which operations you count, only multiplications, every ...


0

Let $P_1, \dotsc, P_m$ be the points on the surface you known. Let $d_1,\dotsc, d_m$ be the measured distances. Let $X^*$ denote your "true" position. Assume that the measure error is additiv and i.i.d normal distributed with zero mean (it is not that realistic): $$ \| X^* - P_i \| - d_i \sim \mathcal N(0, \sigma). $$ Then, you could try to fit $X$ in ...


0

Variant 0 Clearly there are $n!$ possible configurations, which gives a trivial lower bound on the number of tries needed to distinguish all of them, since each try only gives $2$ cases. But like with comparison sorting, it is unlikely that we will ever be able to determine the optimal number of tries except for very small $n$. We can get to within a linear ...


0

For a given knot vector knots[], the valid range for the defined B-spline curve is from knots[degree] to knots[num_poles] (note: the array starts with index 0). So, for a knot vector like [0, 0.1, 0.2, 0.3, ....1], 0 is never in the valid range at all. So, you probably should not insert knot at 0.0.


3

Any $O(1)$ algorithm would have to use only $N$ digits of the input $n$, for some $N$, and that would mean the output would repeat. So there is no algorithm that is $O(1)$ to compute then $n$th digit of any irrational number. There is no known good algorithm for finding the $n$th base $10$ digit of $\pi$ without effectively computing the prior digits. There ...


0

Taking a few wild guesses as to what you mean. Suppose the board squares are numbered 0 to 63 in a rastering kind of way. And that the distance you're referring to is the smallest number of horizontal and vertical steps you would need to take to get from one square to the other. Then the vertical distance between $a$ and $b$ is simply: ...


0

Hint: Yes, there is such function. If $$\frac{x(x-1)}{2}\leq y<\frac{x(x+1)}{2}$$ then the number is on the $x+1$th row and is the right child $x+2$ bigger. Now find the inverse of the above. Hint: Use a floor function.


0

Yes, there is. We have worked on such an algorithm; see for example here, and our paper Abelian ideals of maximal dimension for Lie algebras. For semisimple Lie algebras, the maximal dimension of abelian subalgebras is well known and easy to compute. The difficult case is this invariant for solvable Lie algebras, including the construction of such abelian ...


1

Your problem reminds me of an error detection and correction problem: A $n^2$ bits message protected by $2n$ bits of redundancy. The problem is that you can not reconstruct arbitrary messages with that much redundancy, I believe.


5

Use reshape: B=reshape(A(:,2),3,3) For the second part, it depends on the structure of the first column, but for this specific case you can use the "unique()" function: x=unique(A(:,1))'


1

Managed to find an answer that fits and seems to work: if $x_i \neq y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1)+2)$ and if $x_i=y_j$ then $d(i,j)=min(d(i-1,j)+1,d(i,j-1)+1,d(i-1,j-1))$


0

For each row, the greedy choice is to select the "breakpoint" of the row as late as possible. So the last word in the first row will have length $W_k$, where: $$ k = \max\{i \in \{1, \ldots, n\} \mid W_1 + \cdots + W_i \leq L\} \tag 1 $$ To prove optimality, it suffices to show two properties. Greedy Choice Property: Consider an optimal solution $A$ that ...


0

This does not answer your query, but instead shows that questions within the same intellectual neighborhood can be intricate. Theorem. Every point set of 12 points can be covered by disjoint unit disks. Aloupis, Greg, Robert A. Hearn, Hirokazu Iwasawa, and Ryuhei Uehara. "Covering Points with Disjoint Unit Disks." In CCCG, pp. 41-46. 2012. (PDF ...


0

The solution for any quadratic equation is the following (I'm assuming your in junior high school given that you used the algorithm": The two roots of a quadratic of the form $ax^2+bx+c=0$ can be expressed as, $x_1=\frac{-b+\sqrt {b^2-4ac}}{2a}$ $x_2=\frac{-b-\sqrt {b^2-4ac}}{2a}$


0

Algorithm: Divide everything by the coefficient of $x^2$, which is non-zero. Take the coefficient of $x$, divide it by $2$, square it, then add and subtract it from the expression. Complete the square. But then, this is just the method used to derive the standard formula for solving quadratic equations. So why not just memorize it?


0

To solve the quadratic equation the algorithm is to apply the quadratic equation and the roots are $x_1,x_2=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$


0

Plugging the expression of $y$ into that of $x$, you have a single equation in a single unknown $x=f(x)$, which you could solve by classical methods such as the secant, regula falsi, Newton, Brent... alternatively to fixed-point. Some of these methods give you guarantees on convergence. A first step is to observe the shape of $f(x)$ for typical values of ...


0

Assume the algorithm is not correct. Let $g_1,...,g_n$ be the gas stations we get when using the algorithm. Since the algorithm is not correct we can find $g_1^*,..,g_k^*$ solving the problem with $k<n$, $k$ minimal. Now choose a solution $g_1^*,..,g_k^*$, such that $g_1=g_1^*,..., g_{l-1}=g_{l-1}^*$ and $g_l \neq g_l^* $ with l being maximal. I.e. ...


2

If $A$ has $n$ elements, $B$ has $m$ elements, $p$ are just in $B$, then $m-p$ are in both; and $n-(m-p)$ are just in $A$.


1

Since the index $p \in [1, mn]$ and we have $x=[x_{11},x_{12},\dots \dots, x_{1n}, x_{21},x_{22},\dots \dots, x_{2n}, \dots \dots, x_{m1},x_{m2},\dots \dots, x_{mn}]$ Or $x=[x_{11},x_{12},\dots \dots, x_{1n}, x_{2(n+1)},x_{2(n+2)},\dots \dots, x_{2(2n)}, \dots \dots, x_{m((m-1)n+1)},x_{m((m-1)n+2)},\dots \dots, x_{m((m-1)n+n)}]$ Thus for a given $p$ we ...


1

Notice that in the first sum the summand, $2^{n^2}$, does not depend on the summation index, so $\sum_{i=1}^{\log (n!)} 2^{n^2} = 2^{n^2}\sum_{i=1}^{\log (n!)} 1 = 2^{n^2}\log(n!)$. For the second sum, notice that by the Binomial theorem we have $2^n = (1+1)^n = \sum_{i=0}^n 1^i1^{n-i}\binom{n}{i} = \sum_{i=0}^n\binom{n}{i}$.


1

There is no such thing as the sequent calculus (even for a particular logic, like -- to keep things simple -- classical propositional logic). There is a number of varieties. There is no such thing as the natural deduction calculus (for the same logic) either. But on any story, sequent calculi and natural deduction systems are different sorts of beasts ...


1

I think you've omitted one sentence from the Wikipedia description of Graham's algorithm: This process is continued for as long as the set of the last three points is a "right turn" So after correctly discarding point (2, 4) you continue to check if last 3 points make a left or right turn. In your example (3, 1), (3, 7), (2, 5), (1, 6) last 3 points ...


0

Suppose we have a triple of cities $(a,b,c)$ that form a triangle. If $d$ is a city with greater population than $b$ and $c$, then the triples $(a,b,d)$ and $(a,c,d)$ both have a bigger population than the original. One of those triples must be a triangle, since otherwise $b$ and $c$ would lie on the line connecting $a$ and $d$, meaning $a,b,c$ would be ...


0

I managed to come up with an acceptable proof (at least in my eyes). Would highly appreciate feedback. Let $A,B$ be cities and $S$ will denote the set of all cities. Suppose for a second that our solution must include $A$ and $B$, and our only free choice is in the third city. In this case, the best solution will be $A+B+C$ where $C$ is the city with ...


1

Let $(a, b,c)$ be the cities your algorithm finds. Let $(u,v,w)$ be an optimal solution (also ordered by decreasing population). Claim. $z_a=z_u$. Proof. Assume otherwise. Then $z_a>z_u\ge z_v\ge z_w$ and $(a,v,w)$ would be strictly better, which is absurd; hence $a,v,w$ are collinear. But then $(u,a,w)$ would be strictly better than $(u,v,w)$, qea. ...


2

Yes your computations and your answer looks correct.


0

What sort of numbers are you selecting? If you agree to use $n$ bit unsigned integers you are just trying to avoid the few that the computer will use for the search. For example, if $n=10$ the range is $0-1023$ Presumably the computer's first guess will be $511$ or $512$ so those are poor choices. If you say lower, the next choice will be $255$ or $256$, ...


0

You have to formulate your problem more rigorously since it's not clear how a binary search could land on an irrational number like $e$ or $\pi$. But here's a hint for the idea you're working with: For example, my guess will be 0.25, so the computer will find it in 2 guesses, but then I'll change my guess to 0.25+0.502, but that will be found in 3 ...


0

There are some issues with this setup. I'll give two extreme examples of what could not be done and a comment on what I think is the general problem. First say we generate a very large number of lists $B$. Then I interpret the probability $P_j$ as being the approximate portion of lists we would find $A_j$ in. If our algorithm is successful, the ...


1

Note that if we know $i$ and $j$ (assume $1 \leq j \leq m$), then $$ p = m \cdot (i - 1) + j $$ which I will leave you to verify. We can see then that $$ \left\lceil \frac pm \right \rceil = \left\lceil (i-1) + \frac jm \right \rceil $$ Since $i$ is an integer and $1 \leq j \leq m$, this indeed will always give us $i$. Once we have $i$, we may simply ...


0

There is a lot of literature on this subject, giving complex criteria for when the greedy solution works. One easy criterion, assuming that your denominations are integers (e.g. in terms of pennies) and 1 is one of your denominations, and when you sort your denominations in increasing order each denomination is at least twice the previous denomination, then ...


1

$g, n \ge 0, \quad \eta > 0$ $\eta+2=2g+1n$ $2g = 2 + \eta - n$ $ g = 1 + \dfrac{\eta - n}{2}$ We need to have \begin{align} g &\ge 0\\ 1 + \dfrac{\eta - n}{2} &\ge 0\\ \eta - n &\ge -2\\ n &\le \eta + 2 \end{align} $ \text{Then the acceptable values of n are $\mathbf S = $} \begin{cases} \{0, 2, 4, \dots, \eta + 2\} ...


1

We can prove the formula through the theory of elliptic integrals and modular forms. That boils down to proving that: $$ \sum_{n\geq 1}\binom{2n-1}{n}^3 x^n = -\frac{1}{8}+\frac{1}{2\pi^2}\left(K\left(\frac{1-\sqrt{1-64x}}{2}\right)\right)^2 $$ where $K$ is the complete elliptic integral of the first kind. The remaining parts follow from the fact that ...


1

You don't need to factorise anything. Every positive integer can be expressed as one of the following: $2n+1$ $4n+2$ $4n$ The first and third are differences of two squares: $2n+1=(n+1)^2-n^2$ $4n = (n+1)^2-(n-1)^2$ Numbers of the second form can't be expressed as the difference of two squares (because every square is equal to $0$ or $1$ mod $4$, so ...


0

As the other people answered it is merely a test to divide by all numbers of the form $6n+1$ and $6n+5$. The $+=6$ in the for loop makes the coefficient of $n$ be $6$. Starting at $5$, one can show that all prime numbers can be written in the form of $6n+1$ or $6n+5$. There are a lot of numbers that are in the form of 6n+1$ or $6n+5$, but all prime numbers ...


2

this will not be a direct answer at what does not really seem a direct question, which in its apparently big scope/ ambition pushes outside the bounds of se questions but is nevertheless aimed to be a scientific and guiding response. you seem to be studying graph isomorphism in general, and as you are apparently aware the precise complexity of this is a ...


3

If $k=2n+1$ is an odd number, then $k=(n+1)^2-n^2$. Finding other ways is esentially the same as factoring the number.


4

Googling comes up with the paper Erik D. Demaine and Martin L. Demaine. Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity. Graph. Comb. 23, 1 (February 2007), 195-208. where corollary 3 states that It is NP-complete to decide whether $n$ given polyomino pieces, each fitting within an $\Theta(\log n) \times \Theta(\log ...


3

Among $6n,6n+1,6n+2,6n+3,6n+4,6n+5$, the numbers $6n,6n+2,6n+3,6n+4$ are composite and there is no need to try them (as their own factors have already been tried before). Only $5+6n$ and $5+6n+2=6n'+1$ remain ($2$ out of $6$). You can generalize, for instance with $30n+k$: only $30n+1,30n+7,30n+11,30+13,30+17,30n+19,30n+23,30n+29$ need to be tried ($8$ ...


5

This checks to see if $n$ is a multiple of 2 or 3 (at the start) and then (main loop) whether $n$ is a multiple of 5,7,11,13,17,19,23,25,29,31 etc. $i$ is going up by 6 starting at 5, and it checks $i$ and $i+2$. So the only question is why every single prime is in that list? It's because every prime bigger than 3 must leave remainder 1 or 5 when you divide ...


0

Here is the algorithm for problem (a) Step 1 If the student decided to stay in the urban centre then let him stay in the urban centre (Because the urban centre can accommodate all students anyways) else if he decided not to stay then go to Step 2 Step 2 Match the student to his top rural location if available else if occupied then go to Step 3 Step 3 ...


0

You can read https://en.wikipedia.org/wiki/Matching_(graph_theory)#In_weighted_bipartite_graphs where you might consider your original problem as finding a maximum weight matching between students and programs where a student's third choice is connected to them by an edge with minimum positive weight $w_3 > 0$, and their second choice is connected to them ...


1

Hint: First place to start is reading about the Nobel Prize-winning Gale-Shapley algorithm which is used to match med students to first residencies, for example.


1

You did not specify whether the lines are given before all the queries, which would be much easier than if you can intersperse insertions and deletions of the lines among the queries. In both cases, what you would need is the convex region bounded below by all the lines. If all the lines are given in advance, it should not be hard to figure out how to obtain ...



Top 50 recent answers are included