This week we covered chapters 2 and 3 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link).
The topics discussed:
- ordered arrays
- linear search
- binary search
- Big O notation
- classes of algorithms (constant, linear, logarithmic)
- Jameson, Dennis, and I had one problem or another getting the MOBI format of the book to work with our Kindle apps.
- Houston and I tried out Visual Studio Code. We were both impressed at how easy it was to use. I personally like the integration — one tool for source control, file management, editing, debugging, and console access. Jameson is going to use VS Code as well, as he’s had more experience with this tool. PyCharm (a Python IDE), which he’s also used, is like IntelliJ (a Java IDE).
- The question at the end of chapter 2 about the number of iterations needed to find a number in a list of 100,000 elements is one where Houston “cheated” by doing this manually (i.e., by coding it up) instead of using math (i.e., log base-2).
- For Houston, Dennis, and I, this was a refresher. Dennis said he didn’t do well in these courses in school, so he’s looking forward to knowing this material better. He wished he would have had this book, as it seems more approachable. Two chapters covered two week’s worth of classes. It’s starting to make him think about where he’s written something inefficient that could have been better; he’s asking questions like, “How do I analyze it and think about what it means for the application as a whole?” Houston thinks this book would have been helpful to have in college as well. Jamie has learned to understand concepts that he’s known of/about.
- Jamie and Houston had high praise for the book’s explanation of logarithms, especially the relationship between exponents and logarithms. It’s always been, “Just plug it into the calculator” instead of truly understanding the math.
- Dennis gave an example of something he worked on a Lirio that worked okay for small sets, but then slowed to a crawl for larger sets. Recognizing potential performance issues ahead of time is helpful.
- Binary vs. linear search — you need an ordered list to do a binary search, so you need to ask whether it’s worth the overhead of keeping the list sorted.
- Jamie mentioned the bisect library for Python that allows you to work with sorted arrays using some under-the-hood performance tricks with C.
- Big O is about families of math functions. For example, if Algorithm A is 100N and Algorithm B is 0.5N, they are both O(N) even though Algorithm A is 200 times slower.
- We talked about whether Big O is something every developer should know; in other words, having the language to understand why something can be improved/changed.