Practical Algorithms & Data Structures
Someone recently asked me for a rundown of practical topics in algorithms and data structures. It’s possible to spend an entire life trying to understand algorithms but, thankfully, it IS possible to learn the basics and go from there.
I won’t go over explaining each topic, since all of that is available online, but I’ll talk about what to learn and, more importantly, why it’s important.
If you really want to learn algorithms, at some point you will have to learn C. Most languages (ruby, python, php, java, etc.) abstract so much of how a computer works from you, that you dont really get an opportunity to understand algorithms first hand. That said, just understanding, conceptually, each of these algorithms.. is probably useful enough.
Here’s my list:
Analyzing Algorithms with Big-O notation
Start here. Learning Big-O notation is the most important part of understanding algorithms. Big-O notation is basically a way to analyze the worst case time it takes for an algorithm to complete.
Learn and find examples that have the following running times.
- O(1), also known as constant running time
2. O(n), also known as linear running time.
3. O(n^2), also known as quadratic running time.
Start with understanding the simple running times above, and then there are a few more, listed below, that are a little more advanced and you can learn later.
4. O(log(n)) — generally this is for algorithms where in each step, the number of items is cut in half at each step. For instance, searching a binary search tree filled with n items means cutting the search space in half at each step, leading to log(n) levels.
5. O(nlogn) — most sorting algorithms are O(nlogn).
Running times can get really complicated fast, so don’t worry about any other crazy ones.
The reason running time is important is two-fold:
- because it helps you communicate and analyze how fast your code is, without getting bogged down in the details of the language or the computer that it’s running on.
- O(n) can also be considered a way to define the growth in running time as n increases. So, when engineers ask “does it scale?”, they are fundamentally asking this question: as you increase n, what is the growth of running time of the algorithm? If it’s constant time, increasing n doesn’t change the running time. If its linear O(n) time, increasing n changes the running time by roughly n. If its quadratic O(n^2) time, increasing n causes the running time to roughly increase n times. Being able to analyze how an algorithm will scale as n increases helps you to write faster code.
Sorting
Now that you know Big-O notation, you can start analyzing the worst case running time of sorting algorithms.
Every algorithms course goes through sorting algorithms first as a way of understanding how to apply the concepts of Big-O notation.
Learn about the different types of sorting, practice coding them, and analyze them for Big-O running time.
What is a data structure?
A data structure is something that holds data.
What does it mean to hold data?
Fundamentally, holding data means three things
- being able to insert a piece of data.
- being able to find a piece of data — note that being able to print out all of the elements (in order or not in order) is also part of “finding” data.
- being able to remove a piece of data
Arrays, Linked Lists, Binary Trees, and Hash Tables
These are the four most common data structures you will encounter. Each of these data structures has their strengths and weaknesses, and as a software engineer it is your job to determine which data structure to use. It’s important to know these data structures.
Arrays
An array is a contiguous region of computer memory, where each address holds a value.
Arrays are pretty simple.
Think about how inserting, finding and removing in arrays would work, and quantify the Big-O of each of these operations on an array.
Linked Lists
Linked lists are similar to arrays, but use memory addresses as well, called pointers. Linked Lists are good because they are great for adding and deleting values from the sequence, which arrays are not very good for.
Figure out the Big-O running time of inserting, removing and finding elements in a linked lists. Quantify the Big-O of each of these operations..
Understand why one would use a doubly linked list or a singly linked list.
Binary Trees
Binary Trees hold data in a format that involves pointers similar to linked lists, but hold them such that each value also has (usually) two pointers to children, one that is smaller and one that is larger. This helps to cut the search space in half. Binary Trees are good for lookup, printing out in order, deleting, and inserting.
Figure out the Big-O running time of inserting, removing and finding elements in a binary tree. Quantify the Big-O of each of these operations..
NOTE: there’s a LOT of details that go into binary trees. there are really crazy ones. Don’t bother learning exactly how a balanced binary tree, red-black tree or AVL tree works. Just learn how a binary search tree works, and don’t worry about how trees can be self-balancing. You won’t be writing your own binary search trees, 99% of the time you will be using someone else’s implementation.
Hash Tables
Hash tables are amazing. Understand that they can give you incredibly fast lookup, incredibly fast insertion, incredibly fast removal, at the expense of not being able to easily print out the elements in order.
Understanding Hash Tables is important because from afar they are almost magical: they give you insertions, removals, and finding really quickly.
Figure out the Big-O running time of inserting, removing and finding elements in a hash table. Quantify the Big-O of each of these operations..
So yeah, that’s my really simple list of practical things to learn in algorithms & data structures.
Good luck!
