# Algorithm Definition and 34 Discussions

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. ### Comp Sci Number of trees in a Fibonacci Heap without CASCADING-CUT

I know that the maximum number of trees in a heap will be when all the trees are of smallest order as possible. Then, after performing CONSOLIDATE operation on the heap, all the newly created trees in the heap will be of different orders. Since in a different exercise I showed that the minimal...
2. ### Algorithms for Traveling Purchaser Problem (TPP)

Hey guys, how you doing? Im here to ask for you help. I am writing my bachelor paper as an implementation/review of the TPP algorithms out there. Almost every paper that I read references the Ramesh algorithm, that returns an exact solution for TPP problems, but I just can't find the algorithm...
3. ### I Notation of the approximation in quantum phase estimation algorithm

I'am interested in the notation of the approximation in quantum phase estimation algorithm. In the literature there are different definitions, which I divide into two cases here. Both different in their definition of the ##\delta##. In both cases I start with a quote of the source and show an...
4. ### I Measurement of a qubit in the computational basis - Phase estimation

Hello, I have a question about the measurement of a qubit in the computational basis. I would like to first state what I know so far and then ask my actual question at the end. What I know: Let's say we have a qubit in the general state of ##|\psi\rangle = \alpha|0\rangle + \beta|1\rangle##...
5. ### Evaluate the complexity of this graph coloring algorithm

Hello everybody, I should evaluate the complexity of this graph coloring algorithm. To do this, I use the adjacency matrix in which the graph nodes are the elements on the diagonal, while the elements outside the diagonal indicate if a node is adjacent to another ##(A_{i,j} = 1)## or not...
6. ### I Algorithmic model for primary decay chains

I have seen "radioactivedecay.py" python library which employs measured experimental data for its calculations. I have seen models that solve the system of differential equation with numerical algorithms to predict the proportion of nuclides at any given time. But I have yet to see a...
7. ### Det of Triangular-like Matrix & getting stuck in Algorithmic Proof

Find determinant of following matrix: ## A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n-1} & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & 0 & \cdots & 0 & 0 \end{pmatrix} ## Note: I tried to solve this question...
8. ### MATLAB More Efficient Way of Computing Neighbors in Range

Hi. I have a collection of points in 3D space. I'm using MATLAB to find all pairs of points within a certain range from one another. Right now I'm using rangesearch(X,X,r), where X is the collection of points and r is the range. These points are the locations of atoms and I am attempting to...
9. ### MATLAB Computing Sections of a Graph Which Can Be Removed By Removing Two Edges

Hi. I have graph which I am analyzing in MATLAB. I would like to determine sections of the graph which could be removed from the rest of the graph by removing only 2 edges. (The graph represents the network of atomic bonds from a simulation of silica, and I am attempting to locate strands of...
10. ### Comp Sci Algorithm Optimization [Python]

Homework Statement Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum. sum_pairs([11, 3, 7, 5], 10) # ^--^ 3 + 7 = 10 == [3, 7] sum_pairs([4, 3, 2, 3, 4]...
11. ### Counterexamples to my claim?

I'm trying to solve a problem that amounts to: Given b0, ..., bn-1 where1 <= bi, find the max of |a0 - a1| + |a1 - a2| + ... + |an-2 - an-1| where 1 <= ai <= bi. I'm 100% confident that each ai is either 1 or bi. I'm 90% confident that the elements a0, ..., an-1 are either 1, b0, 1, b1...
12. ### Is there an easy way to find ints i,j,k satisfying i*j=k^2?

Long-story short, as part of a larger problem I'm trying to solve, I need all i,j>=0 such that i*j=k2 for all k in [1, ..., n]. What I'm doing currently is iterating through [12, 22, ..., n2] and for each value m I'm using public static IEnumerable<Tuple<int, int>> Multipliers(ulong...
13. ### Why does not this Erdos-Renyi C code work?

Homework Statement I need to write an Erdos-Renyi random graph, by using the adjacency matrix (or alternatively list) and calculate the fitness of the graph. Definition: G(n, p) is a random graph with n vertices where each possible edge has probability p of existing. Homework Equations The...
14. ### Is my code suffering from an arithmetic error?

What it does is described well in my comments. I'm using decimal, which is more precise than double but has a smaller range of values. https://msdn.microsoft.com/en-us/library/ms228360(v=vs.90).aspx const decimal pi =...
15. ### Rounding error making my graphics barely off?

I'm trying to draw a circle and a (possibly rotated) square on a grid. I have the circle part down and it's the square that is giving me trouble. I am originally given 2 points which represent the coordinates containing opposite ends of the square. For example, those 2 points would be (8,14) and...
16. ### How to do a running median in n*log2(n)?

So I came up with the following solution which is n*log2(n) since the input is n elements and I use a binary insertion and calculating the median is constant time. This is passes all the test cases in the tests that don't time out. I need to figure out how to make it faster so I beat the...
17. ### Hashing problem

Homework Statement In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is made by machine 1,...). Installation order of some parts is not important, but some parts have to be installed before others...
18. ### How to analyze this code?

Homework Statement This is a problem of the 10-minute test we had today in school. Its written in Pascal and it is asked of us to analyze it and figure out what is the output when it runs without writing it down. Homework Equations 3. The Attempt at a Solution [/B] I wrote it in the editor...
19. ### A Problem with a convolution algorithm

Hi. I've been reading "Statistical Mechanics Algorithms and Computations". And I came to a problem while processing Algorithm 1.26 (I attach a link at the end). I don't get why the weights are the way they are, specially I can't understand the sequence {1/2l,1/l,...,1/l,1/2l}. Does anyone...
20. ### Djikstra's algorithm with distance 1 between every node

Does anyone know whether there exists a specialized Djikstra's algorithm for when every node has the same distance between it? Or to think of it another way, an algorithm for simply finding the minimum number of moves to get from 1 node to another? e.g. in the following A - B - C...
21. ### Python Programming MIDI with Python

Python is the only programming language I know, and I know there is a huge library of MIDI music out there. I want to play around with machine learning and algorithmic composition to see what I can produce. So, what books should I read to be able to do this? What I am looking for is: Books to...
22. ### Largest permutation of elements in the range 1,....,N

with at most k swaps. (In other words, like the largest number formed by swapping k digits.) Example. A=[4,2,3,5,1], k = 1 ---> [5,2,3,4,1] I'm wondering why my algorithm is failing the test cases which I'm unable to see. using System; using System.Collections.Generic; using System.IO...
23. ### Algorithm to find the smallest substring containing a set of....

characters in a specified amount. I've been working on this for 10+ hours and can't seem to get it right. It passes all the unit tests I've written, but when I use it in the context of the program I'm writing it fails. The idea is like ACTAGACC { A : 2, C : 1} ------> 4, because smallest...
24. ### Largest number formed by replacing k digits

I'm wondering if you guys can help me figure out where I'm going wrong here. The prompt is Given k and an n-digit number, help Sandy determine the largest possible number she can make by changing k digits. Full prompt here: https://www.hackerrank.com/challenges/richie-rich My solution is...
25. ### I Evolution style algorithm to determine EOM

I had seen a documentary about an algorithm that uses notions of evolution to deduce the equation of motion of a system by sampling a variable connected with the system. For example, they used the double pendulum case where they sampled the position of the free end of the pendulum and arrived...
26. ### Finding cycles in a graph

Homework Statement Homework Equations Recursion, graphs, DFS The Attempt at a Solution To try to solve this algorithm, I first need to find all the basic cycles in the Graph G. When I have these cycles, I can simply pick the smallest edge in each of them and add them to the set F, while...
27. ### Why is the complexity class expression this?

I'm trying to understand complexity class algorithms off of my professor's lecture notes, but I still can't get a hang of it. void sort(int a[], int N) { //N is the length of the array for (int base=0; base<N; ++base) for (int check=base+1; check<N; ++check)...
28. ### Algorithm for creating unique groups of elements

Homework Statement so for a side task I'm supposed to assign people to groups for an icebreaker in python, can anyone give me links to theories that I could read up on or give me suggestion X number of people at my company signed up for a dinner roulette as a way to meet new people. Everyone...
29. ### Help to write a psudoecode (formal) of this procedure.

This is the core idea- https://www.physicsforums.com/threads/complexity-analysis-problem-of-an-algorithm.812931/ I would like to write a formal psudoecode (latex), but as new writer I am having hard time to write, whatever I wrote is not easy to understand, so i would appreciate forum...
30. ### Algorithm for Numerical approximation to add data points

Hi, I am working on TDR (Time Domain Reflectometry). I send a 7GHz bandwidth fast rising edge (14ns) square wave into a coax. I get a return Signal. I have an ADC with 10Msamples/sec. I am using MPLAB IDE for coding the microcontroller. Now I would like to increase the Points on the...
31. ### High Frequency signal with fast risetime, its bandwidth

Hi, I am new to world of electronics and to high frequency Domain. But I am working on a design where I have a coax of 30cm length. I have used an external oscillator to generate 7GHz fast falling pulse. I am using a Controller to control the oscillator. Now I have a pulse of about 350ns...
32. ### How to find min and max of 100 numbers ?

Homework Statement The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ... Homework Equations ##T(n)=T(\lceil \frac{n}{2} \rceil) + T(\lfloor \frac{n}{2} \rfloor) + 2## The Attempt at a Solution Recurrence for the above problem is ##T(n)=T(\lceil...
33. ### Check for Isomorphism in Hypergraphs

Hi, I was trying to check whether two hypergraphs are isomorphic to each other using MATLAB. I did the brute force method by permuting the vertices and check all the permutations one by one. This method is pretty slow. An idea suggested by my friend was to represent the hypergraphs as...
34. ### Runtime of Seemingly Unpredictable Division Algorithm

Last week on my computer science assignment I had to write a division algorithm using only addition and subtraction to tackle a problem. My first attempt was the simple and naive repeated subtraction, although I quickly discovered it was not nearly efficient enough for how I needed to use it, So...