Algorithm Definition and 724 Threads

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?

Homework Statement So basically I got this problem and I am still constructing an algorithm for it. I am not entirely sure the algorithm is going in the right direction, though. The problem is as follows: The 2-D array and the pattern are read from two input files named Array and Pattern...

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...

Hello! I use the Crank-Nicolson numerical method to calculate temperatures on a metalic plate(aluminium) 10cmx30cm. I assume that the left vertical side is always in 0 degrees Celsious and the right vertical side in 100 degrees.Both horizontal sides are insulated. So we have a heat...

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 \pi(x) and \pi(y) and q(y,x) is the jump distribution in the relation: \alpha(x,y)= \min \left(...

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...

I implemented a velocity verlet algorithm, and use it to simulate movement of particles. Depending on the parameters, sometimes the simulation of the movment of the particles is stable, while other times, the simulation may go haywire and the position of the particles becomes exponential. Is...

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...

Stuck on this CW question. have been learing about Eulcidean Algorithm and Bezouts Identity but I'm at a complete loss. Q: Prove by induction that if r_{n+1} is the first remainder equal to 0 in the Euclidean Algorithm then r_{n+1-k} \geq f_{k} I know that proof by induction starts with a...

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...

Homework Statement Show that, for positive integers a and b, there exists unique integers q and r such that a = bq + r and -b/2 < r \leq b/2. Homework Equations We can assume the standard division algorithm holds. That is, for integers a and b, there exists unique integers q and r such...

I guess this is the first question on partly CS topic in this forum. But I think you guys will be able to help me. I have an algorithm which goes as follows: int CN(struct node *node) { if(node==null) return 0; return 1 + CN(node->left) +...

Hello everybody, I have a shape (polygon) made up from pixels (squares) similar to the image below. I need an algorithm to cut it into "lines" i.e. shapes of 1x[1..20] pixels. The lines should not be necessarily straight, but they should fill the entire area. Any ideas on where to start...

If you have an image (just black and white) with a box SOMEWHERE in the image, but there's also some noise in the image, is there a good way to find four corners? I'm sure someone has herd of an algorithm for this, it would just be good if I had a direction to go in.

Hi, I need to write a code to convert a symmetic matrix into tridiagonal form and am planning to use the Householder algorithm. I understand the mathematical steps. Can anyone explain that when we are converting a matrix "A" into a tridiagonal form what does it physically indiacte? I...

im a new user of cplex and now I am having difficulty to transform this algorithm into cplex code. im using ilog cplex optimization studio12.2. my problem is i have several customers, several periods, one depot and i want to distribute some amount of goods to the customer using several...

I am trying to write a java program to simulate the motion of a projectile undergoing a drag proportional to the velocity squared, but i am having some issues writing the acceleration part. This is my attempt, not sure if its right though; a=g-kv^2 da/dt=-k dv^2/dt since dv^2/dt=2vdv/dt...

Hi I'm trying to program a merge sort algorithm on python but it just doesn't work! I first implemented a fusion algorithm which takes as arguments a list A divided into 2 sorted sub lists A[p..q] and A[q+1..r]. Fusion then returns the list A completely sorted. This program seems to work...

Good evening, I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm. Every source about this subject seems to agree that the worst case scenario is when the list to be sorted is already sorted and the pivot is...

hye all... we know that in solving of finite difference methode of boundary value problem, the thomas algorithm is needed to solve it.. anyone here know how to use the thomas algorithm? thanks.

Homework Statement Develop an algorithm or write pseudocode to determine the winning candidate for a constituency in the national elections. The algorithm must accept as input the names of the four candidates and the number of votes each candidate receives. The successful candidate is the...

I'm going to be clustering sleep spindles (see pic below) based on both phase shift and amplitude at a yet-to-be-determined time during the event. The baseline will be the Cz channel, one of the 23 EEG channels. There are about 100-200 sleep spindles on each patient's recording, so I'll have...