Programming with
Data Structures and Algorithms

This course is an accelerated introduction to college-level computer science. We assume you already have significant programming and some computing background, at the level of an AP computer science student. The concrete pre-requisite is a score of 5 (the highest) on the AB (advanced) AP Computer Science exam, or equivalent preparation. This means you know

  1. programming in Java,
  2. object-oriented software design (not the same as the previous item!),
  3. basic algorithms and data structures, and
  4. techniques for their analysis.

If you aren't comfortable with this list, this class is not for you. Brown CS already offers two outstanding introductory sequences, headed by cs015 and cs017, which are designed to accommodate such students. Therefore, cs019 will not offer any “remedial” help; if you don't have the background for this class, please take one of those two classes! Note also that the rest of the Brown CS curriculum assumes you know Java, but this class won't teach you any, so any valor now may prove to be foolhardy later.

Instead of Java, we'll be using a programming language called Racket, in which we will practice functional programming. (We don't assume you know anything about either, and will teach you both from scratch.) We will actually use only a tiny sliver of Racket, not exposing you—much as we'd love to!—to its many powerful features, because this isn't a course about Racket. Rather, it's a course about software construction, which means: being able to design programs, and being able to translate designs into implementations. Designing software means making wise choices about data structures, algorithms, and program organization. Implementing means more than just writing code: it means making wise decisions about systems and interfaces.

We use Racket for many reasons. First, linguistically, Racket—a descendant of Scheme and Lisp—is a strong counter-point to Java in terms of both syntax and semantics, so it exposes you to a diversity of ideas. Second, its idiomatic style is spartan where Java's is baroque, so you learn to approach programing differently. Third, lots of smart people think it's valuable for you to know more than just Java:

Fourth, if all we did was repeat what you learned in high school, what would have been the point of attending college? Finally, getting accustomed to programming functionally will help you cope with the upcoming “multicore revolution”.

Spartan doesn't mean we won't have fun! We will write programs with images and animation; we'll write games; we'll even program cell phones. Indeed, it is precisely by engaging with these real-world computing platforms and phenomena that you can best study the important ideas of computer science. Nevertheless, you should keep in mind:

Every reader should ask himself periodically “Toward what end, toward what end?”—but do not ask it too often lest you pass up the fun of programming for the constipation of bittersweet philosophy.
—Alan Perlis, Foreword to SICP

A Missive From the Course Staff

Dear Student,

Since you are in cs019, you're probably already quite knowledgeable and accomplished. That's terrific, and we're glad we have a course we can offer you.

College is, however, very different from high school. Previously, the problems you were given had neat, distilled solutions—often ones you could find on the Internet—and your job was to pin down this “correct answer”. In contrast, a college course like cs019 deals with reality, which is often messy, sometimes uncharted, and only poorly documented. This will frustrate you sometimes, but overcoming that frustration will make your experience that much more satisfying.

One more thing.

Careful thought and hard work will get you through everything in this class, not always as quickly as cleverness, but often more thoroughly and lastingly. That said, while cleverness is a useful trait and we encourage it, being clever can also be a bane if you feel constantly compelled to demonstrate just how smart you are.

Most of all, every class is a work-in-progress, and this one even more so is a work-in-creation. You will undoubtedly find typos and perhaps even more grievous bugs in the material. Please bring them to our attention; we'll fix them, thank you for it, and think well of you. But don't try to exploit it for the purpose of doing less work. Not only will we not be impressed, we'll assume you were smarter than that and subtract points for the things you didn't do, and you'll not only be short points but also feel frustrated and misunderstood. If you legitimately do not understand something, just ask!

Welcome to cs019. We look forward to having you in it!

—The Course Staff