November 9, 2020

A Common-Sense Guide to Data Structures and Algorithms – Part 3

This week we covered chapters 4 through 6 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link). I’ve been coding along in Python on my Github.

The topics discussed:

  • Bubble Sort
  • Quadratic time complexity
  • Selection Sort
  • Insertion Sort
  • Considering time complexity for space complexity
  • When discussing Bubble Sort, I wondered whether the author would eventually cover a trick for identifying O(N^2) algorithms by looking for nested loops. Here you have N numbers to correctly place, and for each of those numbers you need to do a linear sweep (N) to accomplish that.
  • Houston and I learned the syntax of swapping items in Python (e.g., list[i], list[i+1] = list[i+1], list[i]).
  • The linear solution to finding duplicate numbers from the book uses a trick in JavaScript that allows you to define indices on the fly. This didn’t work in Python, so I used a dictionary instead.
  • The way the author described why constants don’t matter — for example O(10N^2) compared to O(2N^2) — was excellent: “Big O Notation doesn’t care merely about the number of steps an algorithm takes. It cares about the long-term trajectory of the algorithm’s steps as the data increases.” When you get to comparing the same class of algorithms, the constants may be worth investigating.
  • I liked the statement about the best and worst cases (e.g., completely sorted list, reverse-sorted lists) not happening all that frequently. One assumption: The distribution of types of lists is Gaussian.
  • Perhaps we get into it later, but some of these quadratic algorithms — e.g., finding the intersection of two lists — become linear in time if you trade off for storage for bookkeeping data structures.
  • Jamie understands the steps that need to happen, but he doesn’t necessarily think about how to do things in this way by default. He usually leans on frameworks or brute-forces some things; he wants to write these out by hand in several languages so that he can understand them.
  • We talked about some other performance and development topics