Leo Gau home
[Logarithmic][1]
via flickr/quapan

Chapters 2-3 of the The Algorithm Design Manual

This week, I finished the Algorithm Analysis chapter and started Data Structures. Here are some ideas that grabbed me.

***

Going through the book and the course, I’ve found that Skiena is really good at describing technical subjects. He makes very good analogies that give you an intuitive feel for whatever he’s describing. Last week it was his description of algorithms. This week he tackles logarithms and pointers.

Logarithms

A major part thinking like a computer scientist is mapping problems into a class of algorithm. We care about the class of an algorithm because it governs the size of the input. How large of a problem can this algorithm solve? Can it handle 100 objects? 100,000,000?

Logarithms play a large part algorithm classes, so it’s important to get a deep – in your bones – kind of understanding of what logarithms are and how to use them. Logarithms are an inverse exponential functions but, what does that really mean?[1]

Here’s how Skiena puts it:

“Logarithms reflect how many times we can double something until we get to n, or halve something until we get to 1.”

This is unbelievably useful to think about binary search, tree, and basically everything else.

For example, if you are doing a binary search on a NYC phone book, how many times do you have to halve the book until you get to a specific name? Log n.

I know this is baby stuff but, I think it’s a great way of looking at logarithms.

Pointers

Basic data structures are the building blocks we use to build more complex algorithms. When we can begin to think in terms of stacks and dictionaries, it allows us to solve more complex problems without worrying about the details.

Data structures fall into two categories – contiguous (arrays) and linked (pointers). They both have their own pros and cons.

Skiena talks a lot about the technical differences  and in doing so, he reveals a great analogy for thinking about pointers.

A pointer represents the address of a location in memory. His analogy is: a cell phone number. A cell phone number can be thought of as a pointer to its owner as they move about the world.

How great is that? Taking the analogy further, just like a pointer doesn’t need to know the contents of what it’s pointing to to be used, a cell phone number can be copied and shared. The caller doesn’t even need to know anything about the person, he just needs the cell phone number to reach the person.

Pointers will still be complex but it’s a little something to ease the confusion.

Bonus notable idea

When should you use stacks and queues and when should you use dictionaries?

Stacks and queues support data retrieval independent of its content – they retrieve data based on the time they came in.

Dictionaries support data based on content.

Explicitly stating this gives me a more intuitive feel for when to use these different data structures.

  1. Radiolab produced an amazing episode on the topic of Numbers and the first segment touches on logarithms. It’s a fun look at how we (humans) think logarithmically. You can listen to that segment here but, I highly recommend the whole thing. []