Kashish Dugar

Before today, I had been doing Python for a while. I finished Python Crash Course by Eric Matthes and shipped three Python projects to GitHub — Race Day Manager (Tkinter swim meet app), Curio Log (Django web app on Render), and Pack-it-up (a visual packing simulator with 3-level OOP). I also went through most of Kalb’s Object-Oriented Python. That phase was about writing code that works. This blog is about the phase after that — understanding what is actually underneath the code.

So today is Day 1 of systems. Yesterday I shipped Pack-it-up and Alien Invasion to GitHub. Today I opened two new books: Grokking Algorithms by Aditya Bhargava and Code by Charles Petzold.

Grokking Chapter 1 — Binary Search and Big O

Chapter 1 teaches you two things.

First, binary search. If you have a sorted list and you want to find something, you can cut the list in half every time instead of checking every item one by one. If the list has 100 items, binary search finds the answer in about 7 steps (because 2 to the power of 7 is 128). Simple search would take up to 100 steps. The bigger the list, the bigger the difference.

I wrote binary search in Python today:

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # prints 1
print(binary_search(my_list, -1)) # prints None

The book was written in Python 2. I fixed the Python 2 stuff myself — print x became print(x), and / became // so I get integers back instead of floats.

Second, Big O notation. Big O tells you how slow an algorithm gets as the input gets bigger. There are five main classes. I made swimmer analogies for all of them because that is how my brain works:

O(log n) — Michael Phelps. Cutting the list in half every time. Binary search.
O(n) — a club swimmer. Checking every item one by one. Simple search.
O(n log n) — a beginner swimmer. Not covered yet, but faster than n².
O(n²) — a learn-to-swim pool kid. Checking every item against every other item.
O(n!) — a baby splashing in the shallow end. Trying every possible order. Very slow.

Petzold Chapter 1 — Best Friends

Petzold’s first chapter is about two kids who are best friends, who live across the street from each other, and who want to send secret messages at night using flashlights. They invent Morse code basically from scratch — dots and dashes, one for each letter.

The point is that any time you want to communicate across a distance using only one simple on/off signal, you need a code. Morse code is a code. English is a code. The alphabet is a code. Codes are everywhere, and that is what this book is going to be about.

What is next

Tomorrow: Grokking Chapter 2 (Selection Sort) and Petzold Chapter 2 (Codes and Combinations).