Introduction to Algorithms: Chapter Two, Part One

This is hopefully the first of many posts about my journey through Introduction to Algorithms by Cormen, et al., referred to on the internet as the “bible” of algorithms. As a bootcamp graduate, I’ve received zero “formal” education about computer science, so I’m diving in because a) learning is fun and b) I might actually need this stuff.

Either I’m really ok with being dorky or I just don’t yet understand how truly nerdy this photo is.

I found the textbook online for free, from a bunch of sources, so I’m going to assume it’s ok to walk through it on the internet and quote from and share problems and answers. If you are using this book to learn and you don’t want to see the answers to questions, I suggest you turn around!

Chapter One: Remember math?

Chapter One of the book is mostly introductory talk and a brief synopsis of what happens in each chapter. I don’t know my ass from my elbow when it comes to algorithms, so I skipped most of it. That said, a couple of things stuck out, including this fine summary of what, exactly, an algorithm is:

“Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.”

Stuff goes in, we do something to it, stuff comes out. Sounds like a function… maybe I do know something about algorithms after all.

The coolest thing in the first chapter is an example of what one can do with an algorithm: Google Maps! Nowhere in the book does it say “Google Maps” but we’re talking about “a road map on which the distance between each pair of adjacent intersections is marked, and we wish to determine the shortest route from one intersection to another.” Of course I know Google Maps must use a complex algorithm to determine where to guide you, but it’s still cool to see it referenced in a textbook that I’m about to study.

Overall impression: I can do this. The text is light enough and even cracks a joke at one point about how heavy the book is (it’s really heavy).

I also took some time to do some googling and come up with some topics that the internet seems to agree are the most important computer science concepts for junior engineers to understand:

• linked lists
• graphs
• tree structures
• sorting
• recursion

I don’t yet know how broad these topics are (I suspect some of them are quite broad, like “sorting”) or how difficult they are to pick up (“graphs” sounds particularly challenging) but I’m up for just about anything. There’s no way I’ll have the attention span for this whole book (it’s like 5 pounds!), but if I can focus on the most critical skills to pick up, it will make me a more viable candidate in the job market and also a more valuable teammate when I do start working.

Chapter Two: The Bubble Sort

First up, Chapter Two doesn’t call it a bubble sort but an “insertion sort.” That is, the method by which you arrange a set of numbers smallest-to-largest or vice-versa.

Pseudo Code

The chapter also introduces pseudo code, or writing that looks a lot like code but is language-neutral and can theoretically be translated into any programming language with similar structures. Here’s the pseudo code for the insertion sort:

for j = 2 to A.length
  key = A[j]
  i = j - 1
  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1
  A[i+1] = key

One thing to note about pseudo code: there are no begin / end or do / end structures — that is assumed by block indentation.

My Answers: Bubble Sort in Ruby and Javascript

First, I wanted to get these functions working in real code. I feel most comfortable with Ruby, but I am trying to strengthen my Javascript skills, so I will be writing both languages as I work through the book.

Ruby:

for j in 1...array.length do
    key = array[j]
    i = j - 1
    while i >= 0 && array[i] > key do
        array[i + 1] = array[i]
        i -= 1
    end
    array[i + 1] = key
end

Javascript:

for (var j = 1; j < array.length; j++) {
    var key = array[j];
    var i = j - 1;
    while ( i >= 0 && array[i] > key ) {
        array[i+1] = array[i];
        i--
    }
    array[i+1] = key;
}

One note: Extremely close readers would notice I made some minor changes from pseudocode to code to get these functions to work. Namely, I started j at 1 and used i >= 0 in the while loop. If I wrote the functions as written in the pseudocode, they skipped the first index of the array. I certainly don’t think I found a flaw in the text, but I also can’t reconcile that problem.

First problem down, 1300 pages more to go…

Oh, and these are ridiculously common functions, so there’s a sliiiiightly easier way to write this in both languages.

Ruby: array.sort

Javascript: array.sort()

Exercise 2.1–2

The first real exercise I did was to reverse-sort an array. In Ruby, we could just do array.sort.reverse and in Javascript array.sort().reverse() and in the code, we change just one line: while i >= 0 && array[i] < key do, simply changing the expectation for the value at array index i to be less than the key.

That’s ok, it’s only day one. Soon enough I’ll be doing things that aren’t built-in functions in the language.