Book Club: Grokking Algorithms. 3: Introduction to algorithms, Selection sort, and Recursion

Grokking Algorithms An illustrated guide for programmers and other curious people, by Aditya Y. Bhargava

 Chapters 1 to 3: Introduction to algorithms, Selection sort, and Recursion

If you read any of these chapters, please go ahead and discuss what you thought in the comments! I really liked the explanation of Big O notation, I think it's perceived as something very complex which it doesn't have to be - perhaps because it's not used practically very often as a developer?

📝 you can read my notes below.

📆 The next post will be on chapters 4 - 6. I'll aim for June or July 2023.
If you're on Storygraph and want to join me, say hi and I'll start a Buddy Read.

Introduction to algorithms

This chapter nicely introduces Big O notation, which is lauded as a thing everyone needs to know for tech interviews... but it's simply a way of indicating how fast an algorithm is.

We cover Binary Search first which is a fundamental algorithm that chops your sorted set into two parts (the bi in binary) and discards the half that doesn't meet your criteria.

Algorithm speed is measured in growth:

• how quickly the runtime increases with the size of input

Runtime is expressed in Big O notation:

• a measure of how fast an algorithm is
• establishes the worst-case scenario (e.g. if the name you're looking for in the phone book was 'Z' not 'A')

Here's the Khan Academy video about logarithms, mentioned on page 7.

Selection sort

This chapter compares computer memory to a set up draws, and introduces arrays and lists as ways to sore multiple elements in memory. Arrays being a collection of draws next to each other, and linked lists being a treasure hunt for each next item.

Arrays are great for fast reading, whereas linked lists are great for fast inserts and deletes.

Array insert is proportional to the size needed in memory to move the entire array.
List read is proportional to the length of the list to iterate through, to find all addresses in memory

Linked lists can only allow sequential access, arrays can do both sequential and random access.

Recursion

The recursion chapter has a lot of practical examples!

When a function calls itself, thats recursion.
Here's an example I did in Java, there's always a base case and a recursive case!

    /**
     * counts down to 1
     * @param i number to start counting down from
     */
    public static void countdown(int i) {
        System.out.println(i);
        if (i <= 1) { // base case
            return;
        } else { // recursive case
            countdown(i-1);
        }
    }

With recursion the call stack can get huge which takes up a lot of memory (too much and you get a stack overflow). Stacks have two operations, push, and my favourite, pop. All function calls go on the stack.