Algorithms are the heart of programs--they are the instructions for performing particular tasks. In computer programs, algorithms are constructed using the specifics of the programming language (and any libraries related to that language).
Generally speaking, algorithms are measured by:
 | How fast they are. This is often based on processor and bus speed of the computer as well as the speed of the underlying programming architecture (e.g., compiled v. interpreted environments). |
| How much memory or disk space they consume |
| How many resources (e.g., floating-point processor, I/O, etc.) they consume. |
Algorithms must balance each of these factors to be useful.
Recursion
Computer algorithms are often recursive (the routine calls itself). Recursion can be multiply recursive (the routine calls itself multiple times) or indirectly recursive (the routine calls another routine which calls the first. Recursion is useful in breaking complex problems into smaller, simpler sets of instructions that can be called repeatedly to solve an apparently complex problem. Common recursion problems include factorial solutions (e.g., 3! = 3 * 2 * 1), Fibonacci Numbers (0, 1, 1, 2, 3, 5, 8, 13, ... add the last two to get the next), curves, and so forth.
Data Structures for Algorithms
Lists: list structures are commonly used to organize data in a program. List processing considerations include:
| Element type (string, number) and size |
| Complexity of elements (single or lists within lists) |
| Fixed or resizable lists |
| List ordering based on content (sequential, alphanumeric, or other) |
| Links between elements (e.g., first to second to third etc., circular references, back and forth, or between elements in a more complex fashion) (linked lists) |
| Ability to find single or multiple elements within a list |
| To insert into a list, add to it, or delete from it |
| The ability to create or destroy a list |
| Pointers: the ability to point to various parts of the list from an indexing list |
Special types of lists include stacks and queues:
| Stack - a list in which something is added or removed from the same end of the list (last-in, first-out - LIFO). |
| Queues - list in which items are added to one end and removed from the other. |
Arrays: arrays are very structured lists (table-like) organized around specific data types (and even different data types). Arrays range from single (more like a list) to multi-dimensional (lists of lists (of even more lists)).
Trees: a special type of list which is based on "tree-like" (root, branch, leaves) nodes which connect to sub-trees. Tree terminology includes roots (a starting point), branches (connectors to sub-trees), and depth (how far down the tree goes). Trees are used extensively for decision list branching (the basis of many expert systems), network modeling (computers hooked to servers hooked to more servers).
Dealing with Data using Algorithms...
Sorting: putting lists, trees, and arrays into order (sequential, etc.) is common problem for algorithms. Some of the common methods for sorting include:
| Index tables: key fields are collected and "pre-sorted" to improve search efficiency (common used in database management systems). |
| Insertionsort: builds a sorted list as each item is considered in sequence. |
| Quicksort: split the list into smaller lists, sort each list, and merge the lists. |
| Mergesort: similar to quicksort, divide the list in half, sort each list, and put together a new sorted list. |
| Bubblesort: sorts lists by finding "out of order" items and ordering them adjacently. |
| Selectionsort: organize the list by some feature of the data (size, etc.). |
| Unsorting: randomly select items as you search through them. |
| Heapsort: create a tree structure called a heap that is made up of the list, sort the tree structure. |
| Countingsort: the sorting is based on integers, obviously very fast. |
| Bucketsort: similar to selection sort in which list elements are placed in "buckets", in which they are sorted, and put back to together via linked lists. |
Searching: is the process of finding things in the lists after they are sorted (see last section). There are various types of searches:
| Exhaustive: examine everything till you find it. |
| Binary: start in the middle of a sorted list, if the target item is bigger go down, otherwise go up. |
| Interpolation: if you know the range of values in the sorted list, jump to the section of the list which contains the range of the target item. |
Searching strings: apply the above techniques. String searches tend to be the most intensive due to the large variations in string constitution (number of letters/digits) and size and the need to find sub-strings (e.g., find "frog" in words like "froggy")
Hashing: a kind of "guessing game" in which you estimate "where in the list" you will find what you want, place that range of values in a table (called a hash table) and search it. Chaining via linked lists is often used to manage the hash.
Network algorithms: used to search, traverse, and analyze network structures to find out size, aggregate behavior (performance), distances of paths in a network, scheduling (time dependent problems), etc.. Key is understanding how the network is structures (uni- or bi-directional paths between nodes).
Creating Algorithms
From a programming point of view, there are two things to consider:
- What kind of problem do you have (the data, how is it structured, what do you need to accomplish)?
- What is the best algorithm (e.g., a common model such as those described above or something unique).
Testing is essential to:
| Verify the validity of the algorithm (does it work). |
| See how well it holds up (min/max data sizes, computer memory limitations). |
| Measure performance, specifically speed and efficiency to get the job done. |