An algorithm is a procedure that takes in input, follows a certain set of steps, and then produces an output. Oftentimes, the algorithm defines a desired relationship between the input and output. For example, if the problem that we are trying to solve is sorting a hand of cards, the problem might be defined as follows:
Definition:
Problem: Sort the input.
Input: A set of 5 cards.
Output: The set of 5 input cards, sorted.
Procedure: Up to the designer of the algorithm!!
This last part is very important, it's the meat and substance of the algorithm. And, as an algorithm designer, you can do whatever you want to produce the desired output! Think about some ways you could sort 5 cards in your hand, and then click below to see some more ideas. The study of algorithms involves finding the best ways to achieve the desired output given an input and a goal. Learning about algorithms is essential to being a successful computer programmer, and understanding them can help give you an idea of how computers work. So, if you'd like to learn to code, it's absolutely essential to learn about algorithms.
Even though algorithms existed before the modern computer, they lie at the heart of computing and technology. Everything you've ever done on any piece of technology relies on algorithms because they tell technology what to do. Algorithms are responsible for your ability to surf the web at tolerable speeds. Imagine that you're visiting a website, and that website has a lot of unsorted content to show you. If it randomly picked a content order every time you visited it, and threw that order away and tried again if it wasn't correct, you'd be waiting for minutes, hours, or even days before your web page loaded!
Studying computer science and computer programming always involves algorithms because the study of algorithms teaches you to think like a machine so that you can program them in the best way possible. If you'd like to learn how to write applications, make websites, or do data analysis, you need to know about algorithms so that your code will run fast and run correctly.
On the theoretical side, many of the simpler algorithms have long since been discovered and heavily studied, but there are many areas left to research. For example, in theoretical computer science, a lingering question is whether P = NP, or in other words, "Are problems that can be quickly verified by a computer able to be quickly solved by a computer?" Currently, we don't think so. But if it turned out to be true, then computing and technology would experience an enormous speed increase that we would all benefit from. However, this would also mean that modern cryptography is not safe and any hacker could easily crack codes to any system in the world!
As computing grew, applications of computing grew along with it. In order to perform the algorithms that would enable those applications, computer scientists needed a way to represent and store that data. If we wanted to input a set of cards into a computer program, how would we store that data? How would we feed it into the algorithm? Early on, it was good enough to simply represent data as computer bits (zeroes and ones). However, that method could never last, it was too difficult and time-consuming.
Data structures were the answer. Their invention and research is paralleled by, and is often taught alongside, algorithms. The card sorting algorithm, for example, could take in an array of numbers to represent cards. More data structures were invented over time, and they allowed algorithm design to progress with them. With these in place, it became much easier to reason about, develop, and research algorithms.
Algorithms have 3 main properties that are important to remember during their design and analysis.
Time complexity. This is the time an algorithm takes to complete, and it is often given using big O notation with its input as the independent variable. For example, if we want to search a card in the sorted n cards, we can do in logarithmic time, and the time complexity would be O(log(n))
Space complexity. This is the space (in computer memory) the algorithm uses during its execution. Again, if we're sorting n cards, and we need to make an extra array of size n for each card to do so, the space complexity would be O(log(n^2))
Correctness. An algorithm is correct if and only if, for every input, it halts and outputs the correct output. Contrary to what you might think, algorithms that are not correct are sometimes useful. For example, partially correct algorithms only guarantee that if the algorithm halts, the answer will be correct.
An algorithm can be expressed in a variety of ways, many of which you'll find in different wikis here on Brilliant. A few examples of how an algorithm can be described are as follows:
A high-level description: This might be in the form of text or prose that describes the algorithm: it's input, output, and goal. Generally, this does not involve implementation details of the algorithm.
Formal definition: A formal definition will often give the input and output of the algorithm in formal mathematical terms. The procedure by which the output is achieved is also formally notated. This is a more mathematical way of representing an algorithm.
Pseudo-code: This is a way of loosely formalizing an algorithm, and it is often used when learning algorithms. There are general implementation details; however language-specific details are left out so as not to complicate things.
Implementation: An implementation in a given language will be a piece of code that is understandable and runnable by a computer. It will fulfill the goals and procedure of the algorithm; however, it is harder to include high-level detail in an implementation because a computer will reject plain text.
Labels that describe function:
| Algorithm Label | Description |
|---|---|
| Sorting algorithms | Sort a list of comparable inputs. |
| Graph algorithms | Perform elementary graph algorithms such as search. |
| Shortest path algorithms | Find the shortest path(s) between points in a graph. |
| String matching algorithms | Search larger pieces of text for input strings. |
| Max-flow algorithms | Calculate the maximum flow in a flow network. |
| Computational geometry algorithms | A branch of algorithms that can be stated in terms of geometry |
| Number-theoretic algorithms | Algorithms that deal with number theory such as GCD |
| Fast fourier transform algorithms | Efficient algorithms that perform fourier transform |
| Matrix algorithms | Algorithms that perform operations on matrices |
Some apporach of thinking and solving a problems:
Divide and conquer algorithms: Divide problem into smaller subproblems that can be recombined for an answer.
Greedy algorithms: Simple, naive approaches to problems that typically return sub-optimal answers
Dynamic programming algorithms: Create smaller subproblems whose answers help solve larger and larger subproblems.
Recursive algorithms: Algorithms that continuously call upon themselves to solve smaller and smaller problems until a basis is formed for the final solution
Brute force algorithms: An approach to solving problems that attemps to solve the problem with more computing power, rather than elegance
Backtracking algorithms: Algorithms that build collections of partial candidates for solutions, forgetting them only when they become impossible
Probabilistic and randomized algorithms: Algorithms that use any form of randomization (also called non-deterministic algorithms)
Approximation algorithms: Methods that attempt to cut down on computation time by making approximations, getting within some factor of the optimal answer
Multi-threaded algorithms: Algorithms that run on multiple threads to parallelize work
Linear programming algorithms: Solutions that achieve optimal answers by using linear relationships of the inputs
When designing an algorithm, it is important to remember that computers are not infinitely fast and that computer memory is not infinitely large. That's why we make algorithms, after all. So, maybe you're designing an algorithm for a computer that is super fast but doesn't have much memory. Maybe you'll make some concessions on the computational requirements so that you can save memory.
But even if you never had to worry about speed or space, you still need to design a good algorithm. Why? You need to design a good algorithm because you need to know that the algorithm will do what you want it to do and that it will stop once it's done. You need to know that it will be correct.
Efficacy
The efficacy of the algorithm you're designing comes down to time complexity and space complexity.
In an ideal world, the algorithm is efficient in both ways, but there is sometimes a tradeoff
between them. It is up to the designer to weigh their needs appropriately in order to strike a
balance.
It is also up to the designer to make a good algorithm. Doing so requires an understanding of algorithms as well as an understanding of existing algorithms to guide your design process. Otherwise, they might find themselves with a bad algorithm.
The analysis and evaluation of an algorithm is a two-step process. In the analysis portion, the algorithm is studied to learn about its properties: time/space complexity and correctness. Any method of describing the algorithm, as enumerated above, can be studied. However, that description must contain enough information about the inner workings of the algorithm to provide a clear picture of its procedure.
In general, there are a few ways to describe time complexity. There's the best-case, the average-case, and the worst-case for the algorithm. As a programmer, it's important to know each case so that you fully understand how your algorithm will operate. Which case you focus on is up to you, but the worst-case performance is often used as a benchmark for algorithms.
The evaluation portion is more qualitative and requires the observer to make decisions about the efficacy of the algorithm on its own, and as it relates to other similar algorithms. You might see the algorithm and notice that it is making some critical errors that increase its runtime. You might also discover that its runtime is drastically different than other algorithms that accomplish the same thing. In either case, the evaluation result is poor.
Let's take a look at the pseudo-code for an algorithm and try to analyze its time complexity. The following pseudo-code is that of insertion sort, a basic sorting algorithm. It takes as its input an array A, of the number and returns that same array, sorted. Note that this pseudo-code assumes 1-indexing (the first index in the array is 1, not 0).