What?
Algorithms are the recipes of programs. They define the step by step instructions for how the program operates.
The choice of algorithms can have a profound effect on both the time it takes to run an program and the amount of memory that program uses. There are many trade offs when it comes to algorithm selection.
Trade offs?
Yes! When programming, everything is about trade offs. Sometimes an algorithm is fast, however it is harder to understand. Other times an algorithm may be slow but it simple to understand. Further, an algorithm may be fast but it may hog memory. Occasionally, an algorithm is faster, uses less memory, and is easy to understand, however, those are often unicorns.
Why does this matter?
In day to day programming, it is rare to invent a new algorithm. Often, your job is all about organizing data. The algorithms you use will be more centered around correct data structure usage and less around inventing a new Quick sort or Hash Table. Unless you are planning on staying strictly academic, you will focus on being able to correctly use algorithms and data structures and less on making new and inventive ones.
In fact, new and inventive algorithms in day to day programming is somewhat discouraged. It adds an extra burden on future maintainers of the code to understand all of the thinking are reasoning behind the algorithm. A daunting task for someone who only want to display dancing pigs on the screen.
My advice is to try to keep new algorithm logic as contained and locked away as possible from day to day business logic.
Big Oh?
Algorithm performance is commonly measured in an academic setting using Big O Notation. While it is useful to know, the Big Oh is often an incomplete measurement when it comes to real world performance. It is important understand the system where the program is running. For example, often the cost of getting one byte from memory is the same cost as getting 20 bytes from the same location.
Consider the Binary Tree vs B-Tree. Both algorithms have similar Big Oh performance. You would think that the B-Tree algorithm would be almost unused. It is more complex, harder to implement, and harder to maintain. However, Databases everywhere are commonly backed by btrees instead of binary trees. This is because the cost of getting more data than needed from either RAM or Disk is cheaper than requesting new memory locations.
Design?
There are several different design techniques for making an algorithm. I could talk about them, however I think it is better that I just reference them. Remember, designing new algorithms is not generally part of the job. However, it is useful to know some approaches should the opportunity arise.
Greedy Algorithms - This is a heuristic approach to finding optimal solutions to a problem. Greedy algorithms work by trying to grab the large chunk of data/values/etc. The hope of the greedy algorithm is that by grabbing the biggest (or smallest) chunks, a solution can come roughly close to the optimal solution (which is often too hard to absolutely compute).
For example, Making change using a greedy approach would work by grabbing the largest denominations available and working down. So if I gave you $5 for a $.25 item. The Greedy algorithm would specify that you get back 4 $1 bills, 1 $.50 coin and 1 $.25 coin.
Divide and conquer - This approach is all about breaking a problem into smaller solutions (usually by dividing it in half). A good example of this is the Merge sort.
Iterative Method - Think of this as the "guess and check" methodology of programming. Computing the actual solution might be too computationally intense. However, an approximation could be made and verified against the right solution or compared to previous guesses. After the approximation is made, further refinement is done until it is "good enough".
An example of this is newton's method for finding roots.
Dynamic programming - This is a method of programming where memory is traded off for performance. With this, previously computed values are saved off instead of being thrown away. They can sometimes be reused in computing new values.
This is often most useful for computations that can be described in a recursive fashion. For example, Fibonacci numbers.
Let me know if you guys find this useful or if you see any problems with it. I'll try to get to Z if everyone is ok with that .
Algorithms are the recipes of programs. They define the step by step instructions for how the program operates.
The choice of algorithms can have a profound effect on both the time it takes to run an program and the amount of memory that program uses. There are many trade offs when it comes to algorithm selection.
Trade offs?
Yes! When programming, everything is about trade offs. Sometimes an algorithm is fast, however it is harder to understand. Other times an algorithm may be slow but it simple to understand. Further, an algorithm may be fast but it may hog memory. Occasionally, an algorithm is faster, uses less memory, and is easy to understand, however, those are often unicorns.
Why does this matter?
In day to day programming, it is rare to invent a new algorithm. Often, your job is all about organizing data. The algorithms you use will be more centered around correct data structure usage and less around inventing a new Quick sort or Hash Table. Unless you are planning on staying strictly academic, you will focus on being able to correctly use algorithms and data structures and less on making new and inventive ones.
In fact, new and inventive algorithms in day to day programming is somewhat discouraged. It adds an extra burden on future maintainers of the code to understand all of the thinking are reasoning behind the algorithm. A daunting task for someone who only want to display dancing pigs on the screen.
My advice is to try to keep new algorithm logic as contained and locked away as possible from day to day business logic.
Big Oh?
Algorithm performance is commonly measured in an academic setting using Big O Notation. While it is useful to know, the Big Oh is often an incomplete measurement when it comes to real world performance. It is important understand the system where the program is running. For example, often the cost of getting one byte from memory is the same cost as getting 20 bytes from the same location.
Consider the Binary Tree vs B-Tree. Both algorithms have similar Big Oh performance. You would think that the B-Tree algorithm would be almost unused. It is more complex, harder to implement, and harder to maintain. However, Databases everywhere are commonly backed by btrees instead of binary trees. This is because the cost of getting more data than needed from either RAM or Disk is cheaper than requesting new memory locations.
Design?
There are several different design techniques for making an algorithm. I could talk about them, however I think it is better that I just reference them. Remember, designing new algorithms is not generally part of the job. However, it is useful to know some approaches should the opportunity arise.
Greedy Algorithms - This is a heuristic approach to finding optimal solutions to a problem. Greedy algorithms work by trying to grab the large chunk of data/values/etc. The hope of the greedy algorithm is that by grabbing the biggest (or smallest) chunks, a solution can come roughly close to the optimal solution (which is often too hard to absolutely compute).
For example, Making change using a greedy approach would work by grabbing the largest denominations available and working down. So if I gave you $5 for a $.25 item. The Greedy algorithm would specify that you get back 4 $1 bills, 1 $.50 coin and 1 $.25 coin.
Divide and conquer - This approach is all about breaking a problem into smaller solutions (usually by dividing it in half). A good example of this is the Merge sort.
Iterative Method - Think of this as the "guess and check" methodology of programming. Computing the actual solution might be too computationally intense. However, an approximation could be made and verified against the right solution or compared to previous guesses. After the approximation is made, further refinement is done until it is "good enough".
An example of this is newton's method for finding roots.
Dynamic programming - This is a method of programming where memory is traded off for performance. With this, previously computed values are saved off instead of being thrown away. They can sometimes be reused in computing new values.
This is often most useful for computations that can be described in a recursive fashion. For example, Fibonacci numbers.
Let me know if you guys find this useful or if you see any problems with it. I'll try to get to Z if everyone is ok with that .