Section 2 - Why We're Here

1A.2.1 The Purpose of This Course

CS 2C is a gigantic machine that converts computer programmers into computer scientists.

You are about to enter that machine. I'll be your guide.

In CS 2A (or CS 15A) you learned about basic C++ control statements, arrays and fundamental class and object-oriented solutions to many problems. In CS 2B (or CS 27B) you conquered OOP concepts with special emphasis on class inheritance and acquired the ability to construct solutions by building programs with multiple classes, some derived, some containing member objects or object-arrays.

So what's this quarter all about?

In CS 2C you will learn to discriminate between a solution and the solution. That's not to say there is only one right way to code a spec. But, while there are virtually an infinite number options, only a handful really make sense for the problem at hand. Quickly detecting these few options, and then picking the one that is appropriate, is what I mean by finding the solution.

A computer programmer looks at a problem and, with all good intentions, finds the first clean and well-structured program that comes to mind. In the best of circumstances he or she might think about a few ideas and choose one based, usually, on how easy it is to code and read. A computer scientist, on the other hand, considers the ultimate use of the class and program and weighs choices based on running time, hardware and operating system resources and available existing language tools. Is the data going to be built once, up-front, and accessed billions of times with infrequent updates? Or is it going to be constantly changing, requiring updates and additions? Will we be doing a lot of analysis requiring computation, or is this just about storing and retrieving raw information? And perhaps most importantly, based on what we will learn about the built-in STL overhead, which, if any, built-in class templates should we use and which should we write ourselves?

In this course, you will train yourself to:

1. look at a problem and zero-in on the best abstract data type (ADT) for the job based on the intended use of the class and program;
2. critically discuss the merits and pitfalls of contending ADTs if more than one is being considered;
3. decide whether or not to use STL template classes or "roll your own";
4. implement the plan and debug the code;

The vocabulary of this course is, at times, abstract. We will discuss directed graphs, sparse matrices, AVL trees, "Big Oh log N" search times, threaded binary trees, top-down splaying, merge sorts, priority queues and many other exotic sounding constructs. But that should not deter you. Remember that there was a time when terms like mutators, static member data and constructor-chaining were foreign-sounding, but now they're old friends.

And just as there were rough spots when you were trying to comprehend those ideas, so too, will there be times in the next 12 weeks when you get stuck on an algorithm or data structure implementation. It will be the way in which you handle that challenge -- not the stuff that comes easily to you -- that will determine if you will enjoy the role of computer scientist. Because, in the end, it's not about knowing how to apply what you know that counts in any discipline, but how you react to and overcome what you don't know.

1A.2.2 The Material

This will be a very different experience from any language course you have had. In a sense, what you learned in those other courses was "man-made", syntax and usage that came about by committee or decree. Here, we are going to discover ideas that transcend human invention. We'll bump up against speed-of-light limitations that arise from the natural laws of mathematics. And it will be interesting to see how one gets that beautiful math to fit into the artificial man-made languages such as Java and C++. What I'm trying to say is that the game has changed. This isn't computer programming 3. It's computer science 1. You may have mastered the vocabulary and grammar, but now you will learn how to use the language to conceive of and write the story.

1A.2.3 The Pacing

As in all of my courses, the first three weeks are a kind of warm-up. That's not to say they are easy. They will be fun, challenging and interesting, but the deep new material does not start until week four. At that time, strap yourself in: You'll feel a jolt forward.. You will be meeting entirely new species of flora and fauna, and each one demands your undivided attention if you don't want to end up as its lunch.

I will provide you with theory and code at every step of the way. You should paste and run all the programs or program fragments as they are presented.

I cannot emphasize enough how important the modules are. These are not references to look-back on as you do your assignments. I have assembled and crafted a combination of ideas and techniques that will ease the challenge of the complex material. Enjoy being in the module with your C++ IDE open, trying things out. Also, see if you can find a better coding or algorithm than the one I present. Don't underestimate what you can do if you immerse yourself in the material.

1A.2.4 The Textbook

The book is excellent. Somewhere along the line, write Mark Allen Weiss and thank him for writing it. I have seen dozens of data structures texts. Most vary from fair to horrible. This one is great. You'll use it for years to come. The only warning is that it is more of an upper-division text than a community college text, so some of you might find the occasional math intimidating. He also uses short-hand descriptions of concepts that might be new to you. However, I have tried to fill in the gaps by providing details at every step, so if you read these modules first, it will make the textbook more accessible.

You can skip over a lot of the mathematical passages in the textbook if you are getting bogged down. I'll present a specially crafted derivation for you in the modules when I think it is important that you see one.

Even though the modules are self-contained, they parallel the text very closely, which makes the text an essential "second opinion" of everything I say. I advise reading the week's module first to see what material I am covering, because that's the only material in the corresponding chapter that you'll have to read. I discuss AVL trees, so you'll want to read all the sections on AVL trees. I don't cover b-trees, so you can skip the section on b-trees. Like that. I am not going to provide page-by-page reading assignments.

Enough talk. Let's do.