Algorithms Definition and 25 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
  1. AmericaPacific42

    Algorithms for quadcopters to use back-EMF to detect obstacles close?

    Would it help to study Verilog (VHDL) or Field-Programmable-Gate-Arrays (FPGA) if self-crafted x64/aarch64-assembly would take too much power/be too slow?
  2. Monsterboy

    Comp Sci Using Single Source Shortest Path Algorithm to find the longest path

    This is the weighted, directed acyclic graph I created in JavaScript class WeightedDirectedGraph { constructor() { this.adjacencyList = {}; } addNode(node) { if(!this.adjacencyList[node]) { this.adjacencyList[node] = []; } } addEdge(node1, node2, direction, weight) {...
  3. SadPaul

    Comp Sci Prove Dijkstra's O(E + VlogV) complexity

    My effort: I think that the sorting problem in question is Heap Sort which has an O(logV) complexity, but how can I operate with that information so I can solve this? Can you help me by giving me the outline of an idea?
  4. SadPaul

    Comp Sci Shortest path problem in bipartite graph

    Hey guys, I need a little help with this exercise so I know I'm on the right path. My explanation: The Bellman-Ford-Moore algorithm computes shortest paths in O(nm) time, so in this situation we say that in a directed bipartite graph the number of iterations that the algorithm will do is...
  5. E

    Comp Sci Time Complexity Algorithm Proof

    Use the formal definition of Big-Oh to prove that if f (n) and g(n) are nonnegative functions such that f (n) = O(g(n)), f (n) + g(n) = Ω(g(n)). By the definition of Big-Oh: If f(n) and g(n) are non-negative functions such that f(n) = O(g(n)) there must be positive constants c and n0 such...
  6. M

    Dynamic Programming - Restoring white space between words in a file

    All the white space among words in a text file was lost. Write a C++ program which using dynamic programming to get all of the possible original text files (i.e. with white spaces between words) and rank them in order of likelihood with the best possible runtime. You have a text file of...
  7. E

    Proof by Induction of String exponentiation? (Algorithms)

    Homework Statement Wherein α is a string, λ = ∅ = the empty string, and T* is the set of all strings in the Alphabet T. Homework Equations (exp-Recursive-Clause 1) : α0 = λ (exp-Recursive-Clause 2) : αn+1 = (αn) ⋅ α The Attempt at a Solution [/B] This one is proving difficult for me. I...
  8. K

    Contributing to research

    I am someone who likes to come up with new algorithms. Is there a platform to exchange such ideas. Any mailing lists to advance computer science? Perhaps there are programs that accept new algorithms. Sorry if this is a vague post but this is a broad topic.
  9. QuantumQuest

    Insights Intro to Algorithms for Programming - Comments

    Greg Bernhardt submitted a new PF Insights post Intro to Algorithms for Programming Continue reading the Original PF Insights Post.
  10. R

    Programs Prospects of Pursuing Graduate Studies in Quantum Computing

    Hello, I am close to finishing my undergraduate degree in Computer Engineering, and I am very interested in pursuing graduate studies. For a long time, I have been passionate about computer science and I've been looking into the research done in various labs in the schools that I'm considering...
  11. V

    Big Oh for a Fraction of 'n'

    Let me start by saying that this is from a 30 question assessment on Big Oh, Big Theta, and Big Omega. I understood every other question, however, even after being given the correct answer, I do not understand why my answer was wrong for this one. If you could point me in the direction of any...
  12. N

    Multiplying Big Numbers Using FFT

    Multiplying big numbers is a very common application of the FFT, and as such, there are many papers on the subject available online. However, these papers all use sophisticated algorithms where a simple one seems to work. My question is, what's wrong with the simple algorithm: Multiplication...
  13. N

    Approximation Algorithms: Greedy Load Balancing/Vertex Cover

    Homework Statement You are asked to consult for a business where clients bring in jobs each day for processing. Each job has a processing time ti that is known when the job arrives. The company has a set of ten machines, and each job can be processed on any of these ten machines. At...
  14. N

    Network Flow - Bipartite Matching

    Homework Statement You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n days, the hospital has determined the number of doctors they want on hand; thus, on...
  15. mooncrater

    Different Node Deletion/Insertion in a Binary Search Tree

    What happens, if instead of having any pointer pointing to a node's parent, we had pointer pointing to the node's successor? We know, that Searching would remain the same. But in my opinion Insertion and Deletion would change. This would happen, because in insertion, we would be needed to find...
  16. mooncrater

    I Asymptotics for finding the successors in a Binary Tree

    Consider the algorithms : TREE-SUCCESSOR(x) 1. if x.right_child !=NIL 2. return TREE-MINIMUM(x.right_child) 3. y=x.parent 4. while y != NIL and x == y.right_child 5. x = y 6. y = y.parent 7. return y TREE-MINIMUM(x) 1. while x.left_child != NIL 2. x = x.left_child...
  17. benarceneaux

    Basic Algorithm Analysis

    First off I'm studying for an exam tomorrow, this isn't homework. Also, I've already written the proof and verified I've gotten the correct answer. I'm here to ask some questions about the solution that I am not completely confident I understand. Here's the problem: Prove that n2 + 3n2 is Θ(n3)...
  18. S

    Finding all the "move combinations" to partition an array

    of size N into an K subgroups. I've been trying for hours to do this and still haven't found a solution. Example: The array {A,B,C} of size N=3 and I want all the move combinations that make it into K=1 subgroups. The only such subgroup is the one with all the elements, and I can get that with...
  19. U

    C data structures and algorithms - graph problem

    Homework Statement Given connected, directed and weighted (positive weights) graph. Find the shortest cyclic path for each vertex. Cycles have back edges and can also be self loops. 2. The attempt at a solution I need some clarifications for this problem related to implementation in C. After...
  20. Kartik Yadav

    Big-Oh proof

    To prove that n log n is big oh of log(n!), I did: n log n <= C log(n!) n log n/ log(n!) <= C Let k = 1 n > k, so for n = 2 2 log 2 / log 2 <= C 2 <= C C is an element of [2, infinity) Taking C = 2 and k = 1 can we say, n log n <= 2 log(n!) and hence n log n is big oh of log(n!) ?
  21. Domenico94

    A What is quantum computing research mostly focused on?

    What is quantum computing research mostly focused on? I mean, is it mostly about a physical point of view ( Like building better quantum transistor, or better quantum diodes, or, for example, using entalgment effect, to achieve better purposes), or is it mostly focused with quantum architectures...
  22. B

    Discrete Book on the Algorithms?

    Could you recommend me a book or two treating the algorithms and their mathematical foundation, designs, and analysis? My main programming languages are C++ and Python.
  23. maistral

    Nonlinear constrained optimization - how?

    Perhaps the title says it all, but I should expand it more, I guess. So I am trying to explore more about constrained optimization. I noticed that there are very little to no formal (with examples) discussions on algorithms on nonlinear constrained optimization in the internet. They would...
  24. X

    Power learning - 16 hours a day

    I have big plans for summer (note: I still plan on exercising, eating healthy, and showering regularly. Of course, my goal is 12-16 hours per day, 5-6 days a week), 10 math books to finish in 4 months of moderate to very hard difficulty (for me, not in general. I plan on learning all the...
  25. W

    Help with self-learning

    Hello, I still haven't introduced my self, I'm new here. Since I don't like typing about things on the wrong place I will jump directly into my problem. I have learned to program at home, I'm familiar with the syntax of C/C++/C#/Java/Python/PHP/HTML & CSS/JavaScript/bash/batch and a little bit...