Today was a double day. I did Grokking Chapters 2 AND 3, and Petzold Chapters 2 AND 3. Also I wrote a Morse code translator.
Memory is like a giant set of drawers. When you want to store something, you ask the computer for a drawer, and it gives you one.
There are two main ways to store a list:
arr[73] is instant). But if you want to insert something in the middle, every item after it has to shift over by one drawer. Fast READ, slow INSERT.If you have a list of numbers and you want to sort them from smallest to biggest:
That is selection sort. Finding the smallest takes O(n). You repeat n times. So total time is O(n²). Learn-to-swim pool slow.
I wrote it in Python today. I had a typo bug where I spelled a variable smalest_index on one line and smallest_index on another. Python treated them as two different variables and the output was the unsorted list [5, 3, 6, 2, 10]. I found the bug by reading my own code, fixed the typo, and got [2, 3, 5, 6, 10].
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selectionSort([5, 3, 6, 2, 10])) # [2, 3, 5, 6, 10]
Recursion is a function that calls itself. Every recursive function needs two parts:
If you forget the base case, the function calls itself forever and the computer runs out of memory. That is called a stack overflow.
My own example: imagine your goggles are inside a bag, which is inside a bigger bag, which is inside a bigger bag. The algorithm is:
I wrote a countdown function and ran countdown(50). It called itself 51 times before stopping at 0.
def countdown(i):
print(i)
if i <= 0:
return
else:
countdown(i - 1)
The call stack is where the computer keeps track of all the function calls. Every call gets added (pushed) to the top of the stack, and when the function returns, it gets removed (popped). Deep recursion = tall stack = lots of memory.
Petzold shows you the Morse code table reorganised not by alphabet but by the number of dots and dashes. If a code has 1 symbol, there are 2 letters (E, T). 2 symbols → 4 letters. 3 symbols → 8 letters. 4 symbols → 16 letters.
The pattern is: every time you add one symbol, you double the number of possible codes.
The formula is codes = 2^symbols.
With 10 dots and dashes you could make 2^10 = 1024 different codes. This is the first time binary (2 choices → doubling) shows up in the book. It is going to keep showing up.
I drew the full Morse branching tree in my notebook — all 30 letters, each split by dot vs dash at every junction. Then I used my own tree to encode my name: K-A-S-H-I-S-H.
Louis Braille went blind at age 3. At age 15 he invented the Braille system. He based it on a system the French Army already had called “night writing” — soldiers used raised dots to read messages in the dark without lighting a candle. Barbier’s night writing used 12 dots per character. Braille simplified it to 6 dots so one fingertip could feel one letter.
6 dots, each either raised or flat → 2^6 = 64 combinations. More than enough for 26 letters, with room for punctuation, numbers, and shortcuts (Grade 2 Braille).
Morse, Braille, and binary are the same idea: anything you can represent with ON/OFF, you can build a code out of.
I wrote a Python Morse translator with a dictionary that maps every letter to its code. Then I extended the dictionary myself to include digits 0-9, periods, and slashes, so I could translate my GitHub URL into Morse.
morse_code = {'A': '.-', 'B': '-...', 'C': '-.-.'}
word = input("Type a word: ")
for letter in word.upper():
if letter in morse_code:
print(letter, "=", morse_code[letter])
Tomorrow: Grokking Chapter 4 (Quicksort) and Petzold Chapter 4 (Anatomy of a Flashlight).