Algorithm Definition and 651 Threads

I'm trying to find a reasonably fast method for testing whether or not a point (x,y euclidean coordinate system) lies inside a (preferably convex, concave or complex - though different methods for each would be OK) compound polygon with edges consisting of line segments, arcs and/or elliptical...

Homework Statement Here is a pastebin link to my question, it contains an algorithm, my trace of the algorithm, and my question.Homework Equations I am interested in the theta notation for the runtime of an algorithm The Attempt at a Solution Here is the link http://mathb.in/1202 My thoughts...

I am trying to understand the quantum algorithm for order finding, but I can't find the proof anywhere. Can anyone help? Thanks in advance \frac{1}{√r} Ʃ^{r-1}_{s=0} e^{2πisk/r} |μ_{s}> = |x^{k} mod N>

I can't generally map Loop Invariant method for proving the correctness of an Algorithm. Take the case of an Insertion Sort http://csnx.groups.allonline.in/pool/Introduction%20to%20Algorithms-Cormen%20Solution.pdf in the above link, at the page 2-3, they have proved the correctness of...

I am recently trying to identify system parameters with projection algorithm, but faced a problem, and the dynamic model is the following: \ddot{y}(t)+a\cdot\dot{y}(t)=b\cdot e(t) The true value of a is 2.8, b is 0.1. While inputing volt e(t)=12sin(2\pi t)+5sin(2t), I can get a good...

I have to write a program validating credit card numbers using Luhn's algorithm. I am having trouble getting my last function to work. For a credit card number I'm supposed to double every second digit from right to left, and sum them (note double digits, like 10=1+0), and then add the rest of...

Homework Statement Suppose that u, v ∈ Z and (u,v) = 1. If u | n and v | n, show that uv | n. Show that this is false if (u,v) ≠ 1. Homework Equations a | b if b=ac [b]3. The Attempt at a Solution I understand this putting in numbers for u,v, and n but I don't know how to...

How to write the algorithm? I figured out a method to find the inverse. The assignment is making use of the property of triangular matrices to find the inverse of a matrix \displaystyle A. The inverse of a triangular matrix(Upper/ Lower) is also triangular(Upper/ Lower) and is easy to find...

Twice I have had to calculate the speed of algorithms depending on input size. The first time I was working in MATLAB(which is based on C) and was timing the difference in time to perform matrix operations on the identity matrix in standard storage and in sparse storage, as I grew the matrix...

Homework Statement reduce the fraction \frac{943578}{1978935} to its lowest terms using Euclid's algorithm The Attempt at a Solution I start with finding the gcd of these two numbers using E.algorithm 1978935=943578*2+91779 942578=91779*10+25788 91779=25788*3+14415 25788=14415*1+11373...

Does anyone happen to know a good algorithm for a numerical Karhunen-Loeve transformation for tensors? Specifically, I'm trying to solve for the eigentensors of a correlation bitensor, along the lines of \int_{-\infty}^{\infty} d^4x' \, C_{abc'd'}(x,x') \phi^{c'd'}(x') = \lambda \phi_{ab}(x)...

[FONT=Arial]I am trying to prove the following scenario of Quicksort has a running time of Theta(n^2). Initially, we only have arrays of size n, where n = ij. The idea is that at every partition step of Quicksort, you end up with two sub-arrays where one is of size i and the other is of size...

Homework Statement In Florida, the fourth and fifth digits from the end of a driver's license number give the year of birth. The last three digits for a male with birth month m and date b are represented by 40(m-1)+b. Determine the dates of birth of people who have last five digits 42218 and...

Hi everyone, Duval' algorithm computes all the k-ary Lyndon words up to any length, say n. See here for a brief introduction to Lyndon words and note the section Generation. http://en.wikipedia.org/wiki/Lyndon_word The article claims that "the sequence of all Lyndon words of length at most...

1. My difficulty is to show that if a is an integer such that 2 does not divide a and 3 does not divide a then 24 does not divide a squared minus 1 2.Is there any equation which helps? 3. My idea is that it has to be an integer such that 6 does not divide a...therefore i have to show...

Hey guys, this is my first time working on a genetic algorithm. It seems to me that the algorithm is primarily defined by how you choose to define your crossover operator and fitness function. Let's say the crossover takes two parents and produces one child. Is it necessary/good/bad/etc that the...

Q: Find the maximum number of interchanges needed to sort a list of six pieces of data using the bubble-sort algorithm working: for the first past, maximum needed is n-1 swaps where n is the amount of the pieces of data 2nd - n-2 3rd - n-3 4th - n-4 5th - n-5 so generally it takes...

Hello, the Metropolis algorithm can be used to evaluate canonical expectation value integrals by sampling from the Boltzmann density. In the canonical ensemble, one has a finite and constant volume V, over which the configurational part of the expectation-value integral is integrated over...

Hi, So I'm trying to solve the 2D Ising Model using a simple Monte Carlo algorithm, for small square lattices, imposing periodic boundary conditions. Before I compute any thermodynamic quantities though, I want to study the energetics of the system with only nearest-neighbour interactions...

Hi all, at http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X in the example I don't understand that why not "A" is in the final solution & only B, D & F are in the final solution whereas "A" was selected at Level 1

Greetings, I know that when encrypting something with the public key of a key pair, the encrypted data can only be decrypted with the private key of the pair. And it can not be decrypted with the public key that was just used. I do not understand how it is possible to perform a mathematical...

I'm making an applet for distance runners that predicts their finish time for any distance, using recent race times for any distance. For example, a user might enter 3 recent race times which are 16:37 for a 5k (5:21 min/mile pace), 27:42 for an 8k (5:34 min/mile pace), and 35:18 for a 10k (5:41...

I'm looking for a 'covering rectangle with smaller rectangles' algorithm with the unique feature of being able to exclude some possible center points of rectangles. Basically, limiting the possible areas the smaller rectangles can be placed, while still having the algorithm try to solve for...

If I have a very large graph (set of edges and vertices, NOT the "picture/sketch" of the graph), what is a very efficient way to find all the vertices with only one edge attached to them. Most of the vertices will have many edges attached to them. Also any vertex may be connected to itself...

Algorithm for finding best (or combinations of) "non-overlapping" matrix elements. I'm looking for the best general way to find the "best" combination for a list of non-overlapping matrix elements. For example, given the matrix AE BE CE DE AF BF CF DF AG BG CG DG AH BH CH DH...

Homework Statement to compute 1d fdtd maxwell equation using yee algorithm with fortran 90Homework Equations 1D discretization for maxwell equation (TEM mode) : electric field vector: Ez(i-1/2,n+1/2) = Ca*(Ez(i-1/2,n-1/2) + Cb(Hy(i,n)-Hy(i-1,n) magnetic field Hy(i,n+1) = Da*(Hy(i,n) +...

I'm reading the book "Algorithms Design" and a recursion algorithm is defined as: T(n)\leqqT(n/q)+cn But in the Karatsuba’s Algorithm, the recurrence for this algorithm is T (n) = 3T (n/2) + O(n) = O(nlog2 3). The last equation is strange, since 3T(n/2) is bigger than the set. Why they define...

Does anyone knows a good book that teaches techniques to prove that an algorithm is correct?

Hello everybody I started recently working on an engineering problem that requires as a first step, the identification of the system. I already have a model which is a set of differential and algerbraic equations. Unfortunatelly, the system is a parameter varying one, and the aime is to...

Homework Statement A company has a number of employees whose records, for simplicity, contain: Employee number Employee name Write separate programs, each of which searches for a key whose value is to be input, using the sequential search variations given below. Let...

Some time ago I saw a thread in which was mentioned a root-finding algorithm that converges twice as fast as the Newton-Raphson method. Newton-Raphson converges to a zero at a quadratic rate, and a poster pointed out that another algorithm converges to a zero at a quartic rate. I have tried...

I'm trying to list the cosets of the following ring and describe the relations that hold between these cosets. R=Z_4[x]/((x^2+1)*Z_4[x]) I'm using the division algorithm since x^2+1 is monic in the ring Z_4[x].Now for every f that belongs to Z_4[x] by the division algorithm...

Kisielowski Lewandowski Puchta have made a significant advance in calculating the transition amplitudes between quantum states of geometry. They have found a systematic algorithm that enumerates the (generalized) spinfoam-like histories by which one state evolves into another. And in this case...

I digged out this old tread, but it is closed. I'll repost, but with my question. https://www.physicsforums.com/showthread.php?t=74004&highlight=metropolis [SIZE="4"]\pi(x) and [SIZE="4"]\pi(y) and [SIZE="4"]q(y,x) is the jump distribution in the relation...

Hi, I'm having trouble getting a loop invariant expression for this algorithm: Majority(A): c = 1 m = A[0] for i = 1 to len(A) - 1: if c == 0: m = A[i] c = 1 else if A[i] == m: c = c + 1 else: c = c - 1 return...

for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if (i == j){ for(int k = 0; k < n*n; k++){ System.out.println(); } } else{ for(int h = 1; h <= n; h = h*2){ [INDENT]System.out.println(); } } }

Hi, If the algorithm recurrence can be shown to belong to something complicated say like T(n) = log_{3/2} n lg(n) + (log_{3/2}(n) (log_{3/2}(n) - 1 ) /2) lg(2/3) What order of complexity can I expect it to be in?

"Weirdness" of polynomial long division algorithm Hello. So, i just started to learn about the polynomial long division. As an introductory example, the book presents the long division of natural numbers, claiming that its basically the same thing. The example: 8096:23 Solution...

Homework Statement Consider the following problem: Given an unsorted array A[0...n-1] of distinct integers, find the k-th smallest element (with k=0 giving the smallest element). For example, findKth( [ 9 10 6 7 4 12 ] , 0) = 4 and findKth([ 1 7 6 4 15 10 ] , 4 ) = 10. Complete the...

Hi all, You have probably seen these candy machines before. Tubes that contain candies of different colors and drop candies into a receiver once you inserted the coin. I was watching these more than a quarter of an hour at lunch time (waiting for someone to buy candy) and thought that...

Homework Statement We have k >= 1 sorted arrays, each one containing n >= 1 elements (all equal length). We want to combine all of them into a single sorted array with kn elements. We have a "naive" algorithm: merge the first two arrays, then merge the third array into the result, then merge...

Hi guys, My professor recently asked a challenging question - he says it's been asked on an interview and he wanted to pose it as a homework. Attached is the graph of sorting algorithm performance. The interviewer asks: "Tell me everything you can about this algorithm just by looking at...

Homework Statement Suppose that you have k >= 1 sorted arrays, each one containing n >= 1 elements, and you wish to combine them into a single sorted array with kn elements. Homework Equations The Attempt at a Solution Can I assume that each array has a size of n elements for...

hi all, Which is the fastest algorithm for linear equations in the form of A*X = B. Where A can be a symmetric or sparse matrix and also bear in mind that A matrix is huge in size something like 5000x5000. Regards,

I am going to be compleley honest, I don't know anything about Huffman coding. Except that I think I understand the Huffman tree algorithm. Can anyone assist me in getting started the problems states: The preceding exercise compresses a file to generate two files filename.huf and...

I'm looking for an algorithm for dividing a set of numbers into groups, and then doing it again in such a way that no numbers are in a group together more than once. For instance if you have 18 numbers and divide them into groups of three you should be able to do this 8 times without any...

Homework Statement We're supposed to prove that y_{n+1} = y_n + \frac{k_1 + 2k_2 + 2k_3 + k_4}{6} k_1 = hf(t_n, y_n) k_2 = hf(t_n + \frac{h}{2}, y_n + \frac{k_1}{2}) k_3 = hf(t_n + \frac{h}{2}, y_n + \frac{k_2}{2}) k_4 = hf(t_n + h, y_n + k_3) f(t, y) = \frac{dy}{dt} is equivalent to...

I'm trying to come up with a way to order 'random' (poly) lines, knowing only the coordinates of the vertices (and, obviously, which vertices belong to any given line). I'm not a mathematician or geometrician, but I have a feeling there must be an 'easy' way to do this! Would probably have...

I would really like to get some constructive feed back on this prime-seeking algorithm. Computationally it's no better than the rest. However, it does offer some unique insight. I have partitioned the set of naturals between prime and composites using a rigorous structural schema that I prove...

Here's the definition I have: Extended Euclidean algorithm Takes a and b Computes r, s, t such that r=gcd(a, b) and, sa + tb = r (only the last two terms in each of these sequences at any point in the algorithm) Corollary. Suppose gcd(r0, r1)=1. Then r_1-1 mod r_0=t_m mod r_0. The...