Algorithm Definition and 724 Threads

In mathematics and computer science, an algorithm ( (listen)) is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of specific problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. In contrast, a heuristic is a technique used in problem solving that uses practical methods and/or various estimates in order to produce solutions that may not be optimal but are sufficient given the circumstances. As an effective method, an algorithm can be expressed within a finite amount of space and time, and in a well-defined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.The concept of algorithm has existed since antiquity. Arithmetic algorithms, such as a division algorithm, were used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC. Greek mathematicians later used algorithms in 240 BC in the sieve of Eratosthenes for finding prime numbers, and the Euclidean algorithm for finding the greatest common divisor of two numbers. Arabic mathematicians such as al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.The word algorithm itself is derived from the name of the 9th-century mathematician Muḥammad ibn Mūsā al-Khwārizmī, whose nisba (identifying him as from Khwarazm) was Latinized as Algoritmi. A partial formalization of the modern concept of algorithm began with attempts to solve the Entscheidungsproblem (decision problem) posed by David Hilbert in 1928. Later formalizations were framed as attempts to define "effective calculability" or "effective method". Those formalizations included the Gödel–Herbrand–Kleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's Formulation 1 of 1936, and Alan Turing's Turing machines of 1936–37 and 1939.

View More On Wikipedia.org
  1. P

    How Many Swaps Can Bubble Sort Take for Six Items?

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

    Metropolis Algorithm and integration volume

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

    C/C++ Visualizing the 2D Ising Model with Monte Carlo Algorithm

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

    Knuth Algorithm X: Selecting B,D & F over A

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

    Example of encryption key pair algorithm?

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

    I need an algorithm to best-fit a curve

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

    Limiting the placement of covering rectangle with smaller rectangles algorithm?

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

    Finding Vertex with 1 Edge in Large Graph - Algorithm

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

    Find Best Combinations of Non-Overlapping Matrix Elements

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

    Numerical solution for 1d fdtd maxwell equation using yee algorithm

    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) +...
  11. X

    Starnge Recursion algorithm definition

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

    Book to prove that an algorithm is correct?

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

    Constructing an Algorithm for a 2-D Array Pattern Match

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

    Thanks again.Identification Algorithm for Parameter-Varying System?

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

    MATLAB A convergence problem when i change a parameter in an algorithm wrote in MatLab

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

    Straight sequential search algorithm

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

    What Root-Finding Algorithm Converges Faster Than Newton-Raphson?

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

    MHB Exploring Cosets of a Ring with Division Algorithm

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

    Feynmans of geometry: computable trans. amps. by K+Le+P 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...
  20. K

    How Do You Correctly Express q(y,x) in the Metropolis-Hastings Algorithm?

    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(...
  21. Z

    What is the loop invariant for this algorithm?

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

    Help with my big oh algorithm analaysis

    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(); } } }
  23. Z

    Algorithm Complexity how do I tell

    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?
  24. C

    Weirdness of polynomial long division algorithm

    "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...
  25. S

    FindKth Algorithm: Solve Homework Problem

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

    What is the Algorithm Behind Candy Machines?

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

    Unstable velocity verlet algorithm

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

    Algorithm Complexity: Sorted Arrays into Sorted Array

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

    Sorting Algorithm Performance - Interview-Based Problem

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

    What is the running time of this algorithm?

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

    Euclidean Algorithm and Fibonacci proof

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

    The fastest algorithm for linear equations

    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,
  33. D

    Huffman file Decompression algorithm

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

    Algorithm for dividing a set of numbers into groups

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

    Is the Runge-Kutta Algorithm Equivalent to the Second-Order Taylor Expansion?

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

    Robust Algorithm to Order Parallel Polylines

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

    Efficient Prime Number Algorithm: Seeking Feedback and Offering Unique Insights

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

    How to do the extended euclidean algorithm

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

    Proof of Altered Division Algorithm

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

    MHB Complexity of Algorithm to calculate number of nodes in a binary tree

    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) +...
  41. Z

    Algorithm for cutting a polygon into specific shapes

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

    A fast image recognition algorithm for box?

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

    What Does Converting a Matrix to Tridiagonal Form Indicate in Practical Terms?

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

    How to write appropriate ide opl code (using cplex) for this algorithm

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

    Algorithm for acceleration of projectile undergoing squared velocity drag?

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

    Help Me Debug My Merge Sort Algorithm

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

    Doubt about quicksort algorithm

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

    Solving Finite Difference BVP with Thomas Algorithm

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

    Develop an algorithm or write pseudocode

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

    I need a clustering algorithm for complex #'s

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