CompSci degrees cost a lot of money, take a lot of time, and aren't a viable option for a lot of folks. Luckily, much of what you'll learn in a proper Computer Science program can be self-taught online for free. This gist is a roundup of some of the most helpful resources I've found.
I'm not pursuing a deep, academic comprehension of CS concepts — my goal is to become respectably conversant about the most prevalent and relevant subjects in the field.
Here are some meta-resources to give you an overview of the subject matter:
- https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ (Digestible explanation of Big-O notation)
- http://bigocheatsheet.com/ (Good index of data structures and sorting algorithms and their performance metrics)
- https://www.youtube.com/user/mikeysambol/videos (Quick, clear videos explaining said data structures and sorting algorithms)
My workflow for understanding this has been to internalize #1, and then go through #2 and #3 in tandem to dive into and grok each concept. I find it helpful to go over a bunch of stuff one day, partially understand it, and then revisit it a day or so later to cement the concepts in my head.
- A Hash Table is usually the data structure you want (here's a good JavaScript implementation [accompanying blog post])
- Quicksort is a commonly-chosen sorting algorithm
- Understand the tradeoffs between iteration and recursion:
- It's invaluable to know what patterns to look for in order to analyze the time complexity of an algorithm. Here's a good breakdown of how to do this: https://stackoverflow.com/a/14396503
- It's important understand the difference stable and unstable sorting:
- Stable: The relative order of equal sort items is preserved
- Unstable: The relative order of equal sort items is not preserved
- Heaps and Binary Search Trees (BST) are super important data structures, even though they look visually similar they have different applications
-
Complexity theory is concerned with the growth curve of number of operations to process a data set relative to the input size. The "Asymptotic behavior" section of this page explains it very well with a visual aid.
-
It is weirdly difficult to find a decent explanation of space complexity on the internet, but here are the best resources I've found:
-
Memorize the order of these complexities from cheapest to most expensive:
1. O(1) (constant time)
2. O(log n) (logarithmic time)
3. O(n) (linear time)
4. O(n log n) (linearithmic time)
5. O(n^2) (quadratic time)
6. O(2^n) (exponential time)
7. O(n!) (factorial time)
Also see this helpful list on Wikipedia.
All examples assume doSomethingWith() has a complexity of O(1). (Here is a really good article that focuses on this in the context of JavaScript.)
A simple loop is O(n):
const arr = [...];
for (let i = 0; i < arr.length; i++) {
doSomethingWith(arr[i]);
}A nested loop is O(n^2) (or replace 2 with however many levels of nested loops):
const arr = [[...], [...], [...], ...];
for (let i = 0; i < arr.length; i++) {
let nestedArray = arr[i];
for (let j = 0; j < nestedArray.length; j++) {
doSomethingWith(nestedArray[j]);
}
}A function that halves the amount of work remaining after each iteration is O(log (n)):
// Copied from https://gist.github.com/AlexKondov/60b9efaca1045aae9c8b412fe6f4bb29#file-binary-search-js
function binarySearch (list, value) {
let start = 0;
let stop = list.length - 1;
let middle = Math.floor((start + stop) / 2);
while (list[middle] !== value && start < stop) {
if (value < list[middle]) {
stop = middle - 1;
} else {
start = middle + 1;
}
middle = Math.floor((start + stop) / 2);
}
return (list[middle] !== value) ? -1 : middle;
}A function that loops over an entire data set and calls an O(log (n)) function for every iteration (AKA, a typical decent sorting algorithm) is O(n log (n)):
// Copied from https://codepen.io/jeremyckahn/pen/bKwVXB
const merge = (a, b) => {
const acc = [];
while (a.length && b.length) {
acc.push(a[0] > b[0] ? b.shift() : a.shift());
}
acc.push(...a);
acc.push(...b);
return acc;
};
const mergeSort = arr => {
const { length } = arr;
if (length === 1) {
return arr;
}
const divider = Math.floor(length / 2);
return merge(
mergeSort(arr.slice(0, divider)),
mergeSort(arr.slice(divider, length))
);
};- A good alternative to Hash Tables for word lookup problems is a trie
- Splay Trees are really neat
- Useful for cached data lookups
- Also they are cool because they require no extra bookkeeping data
- B-Trees are also really neat and are helpful for accessing ranges of data (think data that is stored on a slow medium like a hard disk)
- Merge Sort is weird but really fast (and deceptively simple once you wrap your head around it)
- Heap Sort is equally weird but fast and cool
- Red-Black Trees (RB Trees) are super fast but super confusing and I really hope I never have to implement one
- Radix Sort is magic: https://www.youtube.com/watch?v=xhr26ia4k38
- https://www.quora.com/What-are-the-most-important-sort-algorithms
- Data structures implemented in JavaScript: http://blog.benoitvallon.com/data-structures-in-javascript/data-structures-in-javascript/
- Sorting algorithms implemented in JavaScript https://github.com/benoitvallon/computer-science-in-javascript
- Complimentary blog series: http://blog.benoitvallon.com/category/sorting-algorithms-in-javascript/
- Visual aids for data structures and algorithms: https://visualgo.net/
- Thorough but approachable breakdown of complexity analysis: https://discrete.gr/complexity/