A compendium for self-education about "data structures and algorithms," created by and for "people without computer science degrees."
Core computer science concepts, such as "data structures and algorithms," are taught using a classist, fucked-up pedagogical approach that makes me viscerally, incoherently angry. Nevertheless, I would like to know what the fuck people mean when they say things like "data structure" or "algorithm" and refer to specific structures or specific algorithms. Despite 20 years of practical programming experience, working in a variety of Information Technology sectors, I still feel completely lost when attempting to navigate this area of specialized knowledge.
THIS IS NOT A PERSONAL FAILURE. Moreover, there are explicit and intentional reasons that benefit mostly white men that explain the consistency and reliability for which education around computer science fails so many people like myself.
This repository exists, therefore, as a place for me to compile my own notes about this esoteric but critically important branch of the knowledge tree. It is my hope that it becomes useful, over time, to others who are feeling similarly despondent about the over-the-top doucheyness with which "CS courses" and "techies" talk about this area of their craft.
We understand that this doucheyness is a form of power-hoarding, i.e., gatekeeping. In the spirit of the original hacker ethos, "information should be free," we recognize this social gatekeeping behavior as a form of censorship and are determined to use the Internet to route around it.
TL;DR: Fuck your CS courses and your classist academia. We're going to learn this thing without your goddamn "help."
This is not a book. You don't have to read it "in order." In fact, I'm not even sure there's any particular order to read it in. I've also avoided any kind of "easier to harder" gradation, because these have not been useful to me when I've encountered them.
Instead, I encourage you to jump directly to the subsections that interest you. If you get frustrated, try a different section. Although you will certainly find yourself becoming more proficient the more you practice, each section is written to be accessible by novice coders with no prior exposure to the algorithm or data structure in question and assumes no prior knowledge of other algorithms or data structures.
I strongly encourage you to actually run and play around with the code itself. Do not merely read the source code, although do also read the source code. The source code files are thoroughly commented and are written with the intent of being educational. However, do absolutely download the files, or type them verbatim into your text editor, and execute them yourself.
Better yet, debug them yourself. This doesn't mean that there are bugs in the code. There aren't. (At least, I hope there aren't!) Instead, it means use your language's built-in debugging tools to inspect the code at each stage of its operation. This section will explain how to do that in more detail.
The JavaScript code samples are all compatible with NodeJS and all modern Web browser consoles because they conform to ECMAScript 5. You can run them in a shell at a command line, you can copy-and-paste them into the JavaScript console in your browser's developer tools.
To run them in a shell, execute them with node like this:
# to run the recursive implementation example of the trie data structure
node trie/trie_recursive.jsNodeJS supports the Chrome DevTools Protocol with which you can attach any supported debugger, including the command-line debugging interface built into NodeJS itself. To debug the JavaScript code samples with the built-in NodeJS debugger, execute them like so:
node inspect trie/trie_recursive.jsYou can use the debugger to run one line of the code at a time, and it will allow you to inspect the values of all the variables during program execution. Once in the debugger, type help to get help. (The NodeJS debugger's help isn't very extensive, so feel free to hop into the Better Angels's public chat room if you need help from a human.)
Alternatively, open the .html file in your web browser (probably just by double-clicking it). The code will run automatically, though you may need to ensure your developer tools are open to see it. To learn more about your browser's developer tools, refer to your browser's documentation:
- Google Chrome DevTools Overview provides everything you need to know about using the DevTools in Google Chrome, but for our purposes, focus on the following articles:
- Mozilla Firefox Developer Tools portal provides everything you need to know about using the Developer Tools in Mozilla Firefox, but for our purposes, focus on the following articles:
The Java code samples are all compatible with Java SE 8. They must first be compiled before they can be run. To compile them, invoke the Java compiler like this at a command shell:
# to compile the recursive implementation of the binary search example
javac binary_search/BinarySearchRecursive.javaOnce compiled, the code samples can be run by informing the Java application launcher where to find them, and which class's code to execute. Do so like this:
java -classpath binary_search BinarySearchRecursive
# ^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^
# Tell Java to look for Name of the class whose `main()`
# compiled code (`.class`) method should be executed.
# files in the
# following directory.Java's standard debugger is called jdb (on both macOS/*nix and Windows). To debug the Java code samples, first compile them with the -g option to include debugging information:
javac -g binary_search/BinarySearchRecursive.java
# ^^
# Make sure you include this `-g` switch!Once compiled with debugging information included, you can use the Java debugger to inspect the values of all variables during program execution, run the code one line at a time, step by step, and more:
jdb -classpath binary_search BinarySearchRecursive.javaOnce in the debugger, type help to get help. (The jdb help is pretty thorough but can be terse, so feel free to hop into the Better Angels's public chat room if you need help from a human.)
The PHP code samples are all compatible with PHP 5.6 and newer. To run them, execute them like this at a command shell:
# to run the object-oriented implementation of the singly linked list data structure example
php singly_linked_list/singly_linked_list_object_oriented.phpPHP's standard debugger is called phpdbg. To debug the PHP code samples, execute them like so:
phpdbg singly_linked_list/singly_linked_list_object_oriented.phpYou can use the debugger to run one line of code at a time, and it will allow you to inspect the values of all the variables during program execution. Once in the debugger, type help to get help. (The phpdbg help is verbose but not very intuitive, so feel free to hop into the Better Angels's public chat room if you need help from a human.)
The Perl code samples are all compatible with Perl 5.16 and newer. To run them, execute them like this at a command shell:
# to run the functional-style implementation of the stack data structure example
perl stack/stack_functional.plPerl has a built-in debugger. To debug the code samples, execute them like so:
perl -d stack/stack_functional.pl # debug the functional stack exampleYou can use the debugger to run one line of the code at a time, and it will allow you to inspect the values of all the variables during program execution. Once in the debugger, type h to get help. (The Perl debugger's help is pretty thorough, but can be terse, so feel free to hop into the Better Angels's public chat room if you need help from a human.)
The Python code samples are all compatible with both Python 2.7 and Python 3 versions. To run them, execute them like this at a command shell:
# to run the iterative implementation of the binary search algorithm example
python binary_search/binary_search_iterative.pyPython's standard debugging module is called pdb. To debug the code samples, execute them like so:
python -m pdb binary_search/binary_search_iterative.py # debug the binary_search_iterative.py exampleYou can use the debugger to run one line of the code at a time, and it will allow you to inspect the values of all the variables during program execution. Once in the debugger, type help to get help. (The pdb help is pretty good, but feel free to hop into the Better Angels's public chat room if you need help from a human.)
The Ruby code samples are all compatible with Ruby 2.0 and newer. To run them, execute them like this at a command shell:
# to run the imperative-style implementation of the selection sort algorithm example
ruby selection_sort/selection_sort_imperative.rbRuby's standard debugging library is called Debug. To debug the Ruby code samples, execute them like so:
ruby -r debug selection_sort/selection_sort_imperative.rbYou can use the debugger to run one line of code at a time, and it will allow you to inspect the values of all the variables during program execution. Once in the debugger, type help to get help. (Ruby's debugger help is somewhat limited, so feel free to hop into the Better Angels's public chat room if you need help from a human.)
In addition to containing detailed inline code comments, each example is also formally documented using the best practices of the language in which the example code is written. Formal documentation means that the files, classes, class members, methods, functions, arguments of each function, and other relevant implementation details are accessible by tools that automatically generate a programmer's manual for how to use the class, method, or function implemented by the example. Each language has its own de-facto standard tool for this:
- JSDoc is used for documenting the JavaScript code samples.
- Javadoc is used for documenting the Java code samples.
- PHPDoc is used for documenting the PHP code samples.
- Plain Old Documentation (POD) format is used for documenting the Perl code samples.
- Google-style Python docstrings are used for documenting the Python code samples. Additionally, the Python code samples embed
doctests to show example usage and output. - RDoc is used for documenting the Ruby code samples.
I've done this in order to habitualize novice programmers to reading (and hopefully writing) such auto-generatable documentation. Since each code sample is self-contained and relatively small, this also provides a good opportunity to practice installing, using, and tweaking the formatting or output of such automatic code documentation tools, if you want to do that. (I recommend it.)
In addition to running the code samples, I suggest you try one or more of the following exercises with each sample. It's more fun if you can find a friend to do them with. This is called "pair programming" (or just "pairing" for short), and it works a little bit like the way a pilot and co-pilot collaborate when flying a plane: one person has their hands on the keyboard (the "driver") and the other person suggests things to try (the "navigator"). Switch up who's driving and who's navigating as often as you feel comfortable, but try to make sure one of you isn't monopolizing one role or the other. (You might be surprised how much you can learn from navigating rather than driving, or vice versa, if you're not used to it.)
- Re-implement one of the algorithms or construct one of the data structures using a different programming language than the ones in the repository. For instance, if you know Ruby but only see a Python code sample, rewrite the code so it does the same thing in Ruby.
- Re-implement the same algorithm using a different programming style. For instance, if you see a code sample implementing an algorithm recursively, implement an iterative variant, or vice versa.