Some motivation/perspective from the real-world

I enjoy http://www.quora.com/ and I saw a question/response which I wanted to share with you: (people defending data structures and algorithms)

Question: If advanced algorithms and data structures are never used in industry, then why learn them?

Response (quoted from Jerason-Banes) (WARNING: not as positive and uplifting as I like to be):

Congratulations. I have just tossed your resume in the "no" pile and am muttering to myself about how kids like you are what's wrong with this industry and why I have to retrain every engineer I do hire. You probably think that databases are magic, too. Just throw another index in there and all your problems are solved, right?

Why am I doing this? Am I just a grumpy old man who likes putting arbitrary obstacles in front of potential hires?

The answer is quite the opposite, in fact. If you have studied and are a trained engineer (note how I keep using that word), you will find the interview process shockingly easy. I'm asking some amazingly simple questions like "write FizzBuzz" or "is JavaScript a functional language?" There are a few super-difficult questions in the phone screen that I don't actually expect you to get. They're there to entice you about the things you will learn working for me.

So if I'm not throwing arbitrary barriers in the way, what am I doing?

The answer is that I'm designing systems to provide analytic answers from petabyte scale data. Now that Google has everyone convinced that they can search the entire internet as they type, I have to provide similar performance in my web application.

Accomplishing this is incredibly difficult. A simple lookup of the specs on even EMC SAN disks tells me that I don't have enough throughput. I can ask for some more expensive Infiniband hardware, but I don't work for Google. We're on a budget here. I need to find a way to take a bunch of cheap boxes and get them to perform together at interactive speeds. One super-powerful box can't do it, but maybe a bunch of IO in parallel can do it.

Now all I need to do is ask my engineers to write some query code against these structu... Damn. One of them just tried to load the entire set into memory and blew the stack on the entire infrastructure. We're rolling back his code. He's saying that the code worked in his testing and he doesn't understand why it failed. I shake my head, take him to the whiteboard and explain the concept behind memory being like a data reservoir that can only hold so much. A straight pipe through (i.e. Streaming) is limited only by time (rate of data movement) rather than capacity.

He says he understands and will avoid that mistake next time. Maybe he will, may he won't. The mental capacity to handle complex computational problems is rare. Many people exhibit the potential, few realize it. Especially in this world of silly ideas like "why do I need to learn data structures and algorithms?"

I may ultimately have to fire him. Which is too bad because I otherwise like him. He just can't do the job.

What you need to understand is that your attitude is self-selecting you for jobs that match your ideas of what programming is. However, these are not the fun jobs nor are they the ones that pay really well. Nor are you as likely to do something truly important.

If you're ok with just being a low-paid programmer and eventually exiting your profession to do something else, then don't learn algorithms and data structures. If computer science really well and truly excites you, then you know what to do.

Class 5: Classes, Objects, and Structs oh my

Part of the difficulty in some recent reading is that there are some basics of classes and objects in C++ that haven't yet been explained. Let's fix that up now.

In case you don't remember your object-oriented programming class here is the high level version. Classes are blueprints for objects which are code stand-ins for actual real-life things. An object encapsulates both data and actions and provides an interface.

The first example that clicked for me, years ago, was a microwave oven.

A microwave does some amazingly complex things. As someone that uses microwaves I don't even know how it does what it does. If a complex machine has a simple "interface" which hides the inner workings of the machine then anyone can use it.

Class Task 1: Add a line to the constructor which declares the birth of your new dog.

Class Task 2: Design, define, and call a new public method pet which should print some pleasant consequence of petting a dog to your screen. (Bonus if you use the dog's name.)

When it comes to object oriented C++ there are some extra features that allow you to work with addresses rather than the proper contents. The reason for this is because most code allocates space with the new operator. The new operator returns a pointer to the memory on the heap where your object lives. Let's look at the -> operator.

Class Task 3: Create an array of 10 Dog pointers, create 10 new dogs, taunt (or pet) all 10, then delete all 10.

Explore Task 4: Try creating an array of 10 Dogs. Look at the error message and decide what happened. How could you fix this issue?

There is another interesting function, called the destructor which is responsible for cleaning-up when your object pops out of existence. You call the destructor with ~Type(). For instance:

Many ways task 5: Note how this code instantiated the puppy differently than other snippets. Refactor this to use new/delete.

Warning: only try this at home!

We've been exploring how memory management works, both with malloc/free and new/delete. You will pretty much never hear someone recommend using malloc with classes, but I think it makes a nice feeling of mastery to do so. Also you can spot exactly how new and malloc are different (new calls the constructor automatically and delete calls the destructor automatically).

Many ways task 6: Come up with three other ways to call the destructor in the above snippet.

I'm not trying to overwhelm you with the inane details of C++ syntax, promise. But I figure that the more ways you see to get the job done the less you'll worry if you are doing things the "right" way and the better choices you can make in the future.

Structs: the C version of a "class"

I have fond memories of hacking together some related data into a struct (using C), malloc-ing enough space for several of my structs, and moving it all around if needed more space. You kids have it nice with your fancy classes.

The truth is that C++ expanded the capabilities of struct so that now it is effectively a class with different default permissions. Here we go:

Comparison Task 7: How many lines did I change between this struct example and the previous class example? Pick a class example from earlier and convert to a struct example.

So why use them? I find myself using struct when I have a plain old data (POD) collection, or if every method and attribute is public.

Size Task 8: use the sizeof operator to decide if there is a change in the number of bytes used by a struct and class.

A slew of new

Now I want to use a different method to get space for an array of things. new[] and delete[] will save some keystrokes here and there, so let's try them out.

Play Task 9: Go ahead and add a function to the Dog class, then use it on all ten dogs, before they fade from existence.

Misc: enumerations

So an enumeration is a way to have named constants from a specified set. They evaluate to 0, 1, …:

You might consider using them with classes to help classify an object:

Enum Task 10: Think of some set of things from your real life that could be classified into categories. Build a class which uses an enum to store this classification. (e.g. ex-lovers: remembered fondly vs. remembered with bile).

Misc: Templates!

So throughout today we've been making User-defined Types. This lets us take all of the core features of C++ and make our own stuff! One of the coolest tools for making generic user-defined code is the template<> operator. If you have a function that could work on many types, or on your classes, or whatever you can add this template line to work with a generic types throughout it. Example:

Overload Task 11: Create a class for a person, e.g. a Baker. Try to use my display function to show your object, e.g. display<Baker>(yourObject). What goes wrong?

Research Overload Task 12: Use this guide to allow my template function to work on your class.