Algorithm: Steps to go from input to output

Algorithm

The term Algorithm does not have a generally accepted formal definition. However, for the course we will begin with: "An algorithm is process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer."

Algorithms have their root in mathematics. Since antiquity, step-by-step procedures for solving mathematical problems have been attested dating as far back as Babylonian mathematics (circa. 2500 BC). Consequently, computer science and programming has also been described as applied mathematics.

Deriving an algorithm.

Once the problem has been analyzed, an algorithm can be developed. The process of analysis will provide details on what input will be needed to obtain the desired output. Analysis will also reveal the steps needed to obtain the anticipated output.

Step 1: Obtain a description of the problem.

Step 2: Analyze the problem.

Step 3: Develop a high-level algorithm (very general).

Step 4: Refine the algorithm by adding more detail as needed.

Step 5: Review the algorithm.

How detailed should an algorithm be?

It's up to the developer. Some times algorithms are very general. Other times they are quite specific in their details. It depends on the level of detail needed to develop pseudocode.

A good algorithm.

If sufficiently detailed, a good algorithm can be used elsewhere. Thus, an algorithm can be defined as "a set of rules that precisely defines a sequence of operations." However, it does not provide a step for each and every line of code in a program. Even pseudocode (the step following algorithm development) doesn't do that.

• Good algorithms have a beginning.
• Good algorithms have an ending.
• Good algorithms complete a task.
• Good algorithms are efficient.
• Good algorithms have specific, outlined steps. The steps should be exact enough to precisely specify what to do at each step during pseudocoding.
• Good algorithms contain an exact order of operations that are concretely defined.
• Good algorithms contain steps that are possible. That is, each step in the algorithm is feasible.
• Good algorithms accept a well-defined set of inputs.
• Good algorithms produce some result as an output, so that its correctness can be reasoned about.
• Good algorithms should terminate after a finite number of instructions.

If the algorithm is good, then it will likely be used elsewhere in programming.

Algorithms in the computing community.

Since algorithms provide the steps to a solution, they are often shared with other individuals. If sufficiently elegant, they will make it into various literary works so that others can use them. For example, Euclid's Algorithm provides the steps to efficiently obtain the greatest common divisor of two positive integers. It is one of the oldest algorithms in common use.

Problem: Given two numbers not prime to one another, to find their greatest common measure.

1. Start with two positive integers, a and b, where a is greater than or equal to b.
2. Divide a by b and find the remainder. Let's denote this remainder as r.
3. If r is equal to 0, then b is the GCD of a and b. In this case, you can stop the algorithm.
4. If r is not equal to 0, set a = b and b = r, and go back to step 2.
5. Repeat steps 2 - 4 until r becomes 0.

Common Algorithms

Searching:

• Binary Search  
• Linear Search 
• Depth First Search  
• Breadth First Search  
• Rabin-Karp Algorithm 
• Z Algorithm 

Sorting

• Insertion Sort 
• Heap Sort 
• Selection Sort 
• Merge Sort 
• Quick Sort 
• Counting Sort 
• Bucket Sort  
• Bubble Sort  
• Radix Sort  
• Shell Sort  
• Comb Sort  
• Pigeonhole Sort  
• Cycle Sort 

Graphs

• Kruskal's Algorithm 
• Dijkstra's Algorithm 
• Bellman Ford Algorithm 
• Floyd Warshall Algorithm 
• Topological Sort Algorithm 
• Flood Fill Algorithm 
• Lee Algorithm 
• Prim's Algorithm 
• Boruvka's Algorithm 
• Johnson's Algorithm 
• Kosaraju's Algorithm 
• Tarjan's Algorithm 

Arrays

• Kadane's Algorithm 
• Floyd's Cycle Detection Algorithm 
• Knuth-Morris-Pratt Algorithm (KMP) 
• Quick Select Algorithm 
• Boyer - More Majority Vote Algorithm 

Tree

• AA Tree 
• Binary Indexed Tree or Fenwick Tree  
• Quadtree 
• Cartesian Tree 
• Fibonacci heap 
• Interval Tree  
• Finger Tree 
• Crit-bit Trees 
• Scapegoat Tree 
• Splay Tree 
• Suffix Tree 
• Counted B-Trees 
• Binary Space Partitioning 
• Van Emde Boas Tree 

Others

• Huffman Coding Compression Algorithm 
• Euclid's Algorithm 
• Union Find Algorithm 
• Manacher's Algorithm  
• Eukerian Path (Hierholzer's Algorithm)  
• Convex Hull | Set 1 (Jarvis's Algorithm or Wrapping) 
• Convex Hull | Set 2 (Graham Scan) 
• Convex Hull using Divide and Conquer Algorithm 
• Quickhull Algorithm for Convex Hull 
• Distinct elements in subarray using Mo's Algorithm 
• Line Sweep Algorithm 
• MO's Algorithm (Query square root decomposition) 
• Disjoint-set Data Structure 
• Ackermann Function 
• Zobrist Hashing 
• FM-index 
• Circular buffer 
• Hungarian Algorithm / Kuhn–Munkres Algorithm / Munkres Assignment Algorithm 
• Dekker's Algorithm 
• Winged Edge 
• Burrows–Wheeler Transform 
• Zipper 
• Five Balltree Construction Algorithms 
• Cuckoo Hashing 
• Rope (Data Structure) 
• Binary Decision Diagram 
• Disjoint-set Data Structure 
• Bloom Filter